Numerical issue in ClipWithConvex

[luithefirst]

There is a numerical issue in Line2d.ClipWithConvex(Polygon2d). My algorithms sometimes generates cases where one or both vertices of the line are "exactly" on the polygon outline. It turns out if such lines are passed to ClipWithConvex, the result is a line with NaN values -> fully clipped, but this is actually not true. The test below illustrates one such case. It only runs into the issue when using the binary exact double values that are generated in my application. The values created from string can be used to see the differences when stepping through ClipWithConvex. In the error case poly.Contains(line.P1) returns false (is outside -> there must be an intersection with an edge), but P1 is actually on one of the edges and then edge.Intersects(line) does not find an intersection.

static void Test()
{
    var polyPointsCCW = new[]
    {
        new V2d(-0.0939698756460923, -0.232697623928329),
        new V2d(0.192737672108995, -0.232715604234477),
        new V2d(0.161068324080593, 0.267286382830312),
        new V2d(-0.0939385191187643, 0.267302375088439),
    };

    var line = new Line2d(new V2d(0.122649290942927, -0.232711208777991), new V2d(0.122680647470255, 0.267288790238778));

    TestClip(new Polygon2d(polyPointsCCW), line);

    var polyPointsCWBits = new[]
    {
        new V2l(-4631936373040510188, -4625820201104931391),
        new V2l(4596112126756858047, -4625819553296130844),
        new V2l(4594971118245019810, 4598486623334369124),
        new V2l(-4631938632516426832, 4598486911425280084),
    };

    var l0 = new V2l(4593502233478970048, -4625819711659140416);
    var l1 = new V2l(4593504492954886720, 4598486666702384608);

    var polyPointsCCW2 = polyPointsCWBits.Map(p => BitsToDouble(p));
    var line2 = new Line2d(BitsToDouble(l0), BitsToDouble(l1));

    TestClip(new Polygon2d(polyPointsCCW2), line2);
}

public static V2d BitsToDouble(V2l x)
{
    return new V2d(BitConverter.Int64BitsToDouble(x.X), BitConverter.Int64BitsToDouble(x.Y));
}

static void TestClip(Polygon2d poly, Line2d line)
{
    var clippedLine = line.ClipWithConvex(poly);
    if (clippedLine.P0.X.IsNaN())
        Report.Line("FULLY CLIPPED -> FAIL!!");
    else
        Report.Line("NOT OR PARTIALLY CLIPPED");
}

From my quick analysis, the issues appears to be in Line2d.IntersectsLine and that it's not tolerant enough to find the intersection of a line vertex that is directly on the edge.

[hyazinthh]

I think your quick analysis is correct. Line2d.IntersectsLine does not use any epsilon to check whether the resulting parameter t is within [0, 1] and misses the intersection in your case. There is an overload for Line2d.IntersectsLine that has an absoluteEpsilon parameter. Using this one with Constant<double>.PositiveTinyValue resolves the issue for this test case.

For other intersection test types there are also overloads with and without epsilon parameters. Some of them use a default epsilon parameter of 0.0 or use a separate implementation altogether (like Line2d - Line2d), while the others use Constant<double>.PositiveTinyValue. Maybe we want to use Constant<double>.PositiveTinyValue as a default for all intersection tests?