S2Polyline with antipodal vertices

[Michael Brichko]

Hi,

I'm creating a S2Polyline with antipodal vertices and in most cases the polyline is valid although it should be invalid, this seems to be related to a floating point precision, could you please advice how to overcome this?

In all examples below, only points2 is invalid

        std::vector<S2LatLng> points1;
        points1.emplace_back(S2LatLng::FromDegrees(-90,0));
        points1.emplace_back(S2LatLng::FromDegrees(90,0));

        std::vector<S2LatLng> points2;
        points2.emplace_back(S2LatLng::FromDegrees(0, -50));
        points2.emplace_back(S2LatLng::FromDegrees(0, 130));

        std::vector<S2LatLng> points3;
        points3.emplace_back(S2LatLng::FromDegrees(0, -10.125));
        points3.emplace_back(S2LatLng::FromDegrees(0, 169.875));

        std::vector<S2LatLng> points4;
        points4.emplace_back(S2LatLng::FromDegrees(0, -180));
        points4.emplace_back(S2LatLng::FromDegrees(0, 0));

        std::vector<S2LatLng> points5;
        points5.emplace_back(S2LatLng::FromDegrees(0, 0));
        points5.emplace_back(S2LatLng::FromDegrees(0, 180));

        S2Polyline polyline(points3, S2Debug::DISABLE);
        if (polyline.IsValid())
        {
            cout << "valid" << endl;
        }
        else
        {
            cout << "invalid" << endl;
        }

For example, if I'm looking at  points3 (and all others), the invalidation of polyline must happen here:

bool S2Polyline::FindValidationError(S2Error* error) const {

  ......

    if (vertex(i - 1) == -vertex(i)) {

      error->Init(S2Error::ANTIPODAL_VERTICES,

                  "Vertices %d and %d are antipodal", i - 1, i);

      return true;

    }

  }

  return false;

}

Careful inspection shows slight difference in the values, while they should be identical:

-0.17579627993435451
 0.17579627993435473

Thanks a lot !

[Eric Engle]

The internal S2 format is a unit-length vector in 3-D, where the north pole is at [0,0,1], lng 0 lat 0 is at [0,0,0], and lng 90 lat 0 is [0, 1, 0].)

The conversion from lng,lat to S2Point is inexact because it has to be. Trig functions like sin() have no exact finite representation of their result.

But they're pretty good. The degree of error is around the nanometer scale, so in practice you only ever notice in tests like what you have here ;-]

--
You received this message because you are subscribed to the Google Groups "s2geometry-io" group.
To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/3a383500-dcc1-48a1-90f6-86c735cb5b45%40googlegroups.com.

[Michael Brichko]

Thank you for quick response Eric !

I understand what you are saying but this isn't a test code, don't you think that below condition (vertex(i - 1) == -vertex(i)) is incorrect ? It won't be true for most of cases. Isn't there is a reason for this check ? Because of this inequality I'm able to create edges of 180 degress, which I suspect could lead to a very incorrect results. Also, the API of S2Polyline says "Edges of length 0 and 180 degrees are not allowed" but in fact in most cases it's possible to create such edges. Maybe there is no point for this check at all and 180 degrees edges are totally fine ?

Thanks,

Michael

To unsubscribe from this group and stop receiving emails from it, send an email to s2geom...@googlegroups.com.

[Eric Engle]

The S2Polyline.isValid() check has the goal of returning true when operations on the line will always return correct results. But when two points are exactly antipodal, as being checked for by isValid, there are operations that may misbehave.

Now, the API statement you quoted is technically correct, but you aren't creating edges with exactly 180 degrees between them. It only appears that way, because the way you measure the angle between two points isn't infinitely precise:

1) You measure the angle in radians between two S2Points, which has a certain amount of error. The result is then rounded to the nearest double value.

2) You convert the radian angle to degrees to print it, which has a certain amount of error. The result is then again rounded to the nearest double value.

Those steps are making it appear as you though you have an exactly 180.0 degree edge, but instead all you can really say is that the true answer is within 2*eps of 180.0, where eps is the double rounding error. That's biting you here.

Best,

Eric

To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/7b46ab91-36e1-474f-8f3e-be4027ef5b98%40googlegroups.com.

[Michael Brichko]

Thanks a lot Eric, this totally makes sense !

To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/7b46ab91-36e1-474f-8f3e-be4027ef5b98%40googlegroups.com.