Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Numerical issue in ClipWithConvex #62

Open
luithefirst opened this issue May 5, 2021 · 1 comment
Open

Numerical issue in ClipWithConvex #62

luithefirst opened this issue May 5, 2021 · 1 comment

Comments

@luithefirst
Copy link
Member

luithefirst commented May 5, 2021

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
Copy link
Member

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants