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

spherical polygons set build fails when two edges are aligned but in reverse direction #21

maisonobe opened this issue Apr 26, 2017 · 1 comment


Copy link

@maisonobe maisonobe commented Apr 26, 2017

SphericalPolygonsSet instances can be built from a list of vertices, which are points on the 2D unit sphere. When these vertices form a zigzag or star shaped boundary and two distant edges happen
to be on the same circle (according to the hyperplaneThickness parameter setting) and these edges
are in opposite orientation, then the polygon built is completely wrong.

This test case is an example of this behavior. If the hyperplane thickness (first constructor parameter) is set to 1.0e-10, then all edges are considered to belong to separate circles and the zone is properly built.
If the hyperplane thickness is set to 1.0e-6, then the edge built from vertices at indices 6 and 7 (counting from 0) and the edge built from vertices at indices 10 and 11 are considered to belong to the same circle and the polygons built is different.

public void testZigZagBoundary() {
    SphericalPolygonsSet zone = new SphericalPolygonsSet(1.0e-6,
                                                         new S2Point(-0.12630940610562444, 0.8998192093789258),
                                                         new S2Point(-0.12731320182988207, 0.8963735568774486),
                                                         new S2Point(-0.1351107624622557,  0.8978258663483273),
                                                         new S2Point(-0.13545331405131725, 0.8966781238246179),
                                                         new S2Point(-0.14324883017454967, 0.8981309629283796),
                                                         new S2Point(-0.14359875625524995, 0.896983965573036),
                                                         new S2Point(-0.14749650541159384, 0.8977109994666864),
                                                         new S2Point(-0.14785037758231825, 0.8965644005442432),
                                                         new S2Point(-0.15369807257448784, 0.8976550608135502),
                                                         new S2Point(-0.1526225554339386,  0.9010934265410458),
                                                         new S2Point(-0.14679028466684121, 0.9000043396997698),
                                                         new S2Point(-0.14643807494172612, 0.9011511073761742),
                                                         new S2Point(-0.1386609051963748,  0.8996991539048602),
                                                         new S2Point(-0.13831601655974668, 0.9008466623902937),
                                                         new S2Point(-0.1305365419828323,  0.8993961857946309),
                                                         new S2Point(-0.1301989630405964,  0.9005444294061787));
    Assert.assertEquals(Region.Location.INSIDE, zone.checkPoint(new S2Point(-0.145, 0.898)));
    Assert.assertEquals(6.463e-5, zone.getSize(),         1.0e-7);
    Assert.assertEquals(5.487e-2, zone.getBoundarySize(), 1.0e-4);
@maisonobe maisonobe self-assigned this Apr 26, 2017
Copy link
Contributor Author

@maisonobe maisonobe commented Apr 26, 2017

A similar problem occurs in Euclidean 2D. The following test triggers a NullPointerException.

public void testOppositeEdges() {
    PolygonsSet polygon = new PolygonsSet(1.0e-6,
                                          new Vector2D(+1, -2),
                                          new Vector2D(+1,  0),
                                          new Vector2D(+2,  0),
                                          new Vector2D(-1, +2),
                                          new Vector2D(-1,  0),
                                          new Vector2D(-2,  0));
    Assert.assertEquals(6.0, polygon.getSize(), 1.0e-10);
    Assert.assertEquals(2.0 * FastMath.sqrt(13.0) + 6.0, polygon.getBoundarySize(), 1.0e-10);
@maisonobe maisonobe closed this in 18ce441 Apr 26, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant