Fix bounding box bug for polygons crossing the antimeridian #130

nrabinowitz · 2018-08-23T15:41:57Z

This fixes a previously unknown bug calculating the bounding box for most polygons crossing the antimeridian. Bounding boxes were using the max longitude as west and the min longitude as east, which only considers the vertices closest to the antimeridian, instead of using the min positive longitude as west and the max negative longitude as east (vertices furthest from the antimeridian).

My tests failed to catch this because my test polygons were all orthogonal rectangles 😞.

coveralls · 2018-08-23T15:44:54Z

Coverage remained the same at 100.0% when pulling ff1f0af on nrabinowitz:fix-transmeridian-bbox into 9edf3d1 on uber:master.

isaachier

Nice stuff. A few nits but nothing major.

isaachier · 2018-08-23T16:23:12Z

src/apps/testapps/testBBox.c

@@ -88,9 +88,16 @@ TEST(transmeridian) {
                        {-0.4, M_PI - 0.1}};
    const Geofence geofence = {.numVerts = 4, .verts = verts};
    const BBox expected = {0.4, -0.4, -M_PI + 0.1, M_PI - 0.1};
-    const GeoCoord inside = {-0.1, M_PI};
+    const GeoCoord insideOnMeridian = {-0.1, M_PI};


IDK how you all feel about this idea, but I find it would be easier to read this code if it used designated initializers:

const GeoCoord insideOnMeridian = { .lat = -0.1, .lon = M_PI }

Yeah, we've been really inconsistent on this in tests, but I think that's probably the best/most legible option for most structs. GeoCoord might be the exception, because a) we instantiate a lot of them, and b) it's really equivalent to a lat, lon tuple, so instantiating it with the same syntax as a double[] array makes sense.

I get that. Just a warning about designated initializers: it's not 100% portable, but should be okay on most platforms.

isaachier · 2018-08-23T16:26:54Z

src/apps/testapps/testPolyfill.c

+static int countActualHexagons(H3Index* hexagons, int numHexagons) {
+    int actualNumHexagons = 0;
+    for (int i = 0; i < numHexagons; i++) {
+        if (hexagons[i] != 0) {


I have been wondering where in the code we rely on zero-initialization. There are reasons to avoid zero-initialization if possible. Is this a case when the caller relies on the fact that hexagons contains only valid hexagons or zeros?

Yes. In algorithms where we return a list of hexagons and cannot say ahead of time how many we need, we require the caller to pass in a zero-filled array of the max possible size and then only fill H3 addresses for the real hexagons. We could theoretically fill in index order and then add a NULL as a stop signal afterward, but internally this isn't as efficient because we often need to use the array as a set, which we do via modulo arithmetic on the index, resulting in arbitrary index positions.

isaachier · 2018-08-23T16:27:59Z

src/apps/testapps/testPolyfill.c

+                        {0.05, M_PI - 0.2},      {-0.1, M_PI - 0.00001},
+                        {-0.1, -M_PI + 0.00001}, {-0.05, -M_PI + 0.2}};
+
+    Geofence geofence;


Why not Geofence geofence = { verts, 6 };?

Will update using designated initializers.

isaachier · 2018-08-23T16:28:11Z

src/apps/testapps/testPolyfill.c

+
+    GeoPolygon polygon;
+    polygon.geofence = geofence;
+    polygon.numHoles = 0;


Same question.

isaachier · 2018-08-23T16:30:12Z

src/apps/testapps/testPolyfill.c

+
+    int actualNumHexagons = countActualHexagons(hexagons, numHexagons);
+
+    t_assert(actualNumHexagons == 1204,


If we keep t_assert as immediately exiting program, this is fine. Changing that to another behavior might result in a memory leak if we don't hit line 260.

This would be true in a lot of places. I'm assuming the current behavior is fine in this test, otherwise we'd have the same problem all over. If t_assert doesn't exit the program, I'd assume it doesn't exit the function either, so we'd still hit L260.

Ya I have a feeling that's true. OK for now, assertions will remain fatal.

isaachier · 2018-08-23T16:30:22Z

src/apps/testapps/testPolygon.c

+                        {0.05, M_PI - 0.2},  {-0.1, M_PI - 0.1},
+                        {-0.1, -M_PI + 0.1}, {-0.05, -M_PI + 0.2}};
+
+    Geofence geofence;


Same question.

isaachier · 2018-08-23T16:32:55Z

src/h3lib/include/polygonAlgos.h


    bbox->south = DBL_MAX;
    bbox->west = DBL_MAX;
    bbox->north = -1.0 * DBL_MAX;
    bbox->east = -1.0 * DBL_MAX;
+    double minPosLon = DBL_MAX;
+    double maxNegLon = -1.0 * DBL_MAX;


For any case of -1.0 * DBL_MAX I would highly suggest changing to ~~-DBL_MIN~~ -DBL_MAX. I'm sure this is what happens in most compilers anyway, but unary minus avoids theoretical multiplication.

Do you mean -DBL_MAX? Will update.

Ya my mistake. Thanks.

isaachier · 2018-08-23T16:35:29Z

src/h3lib/include/polygonAlgos.h

+        // Save the min positive and max negative longitude for
+        // use in the transmeridian case
+        if (lon > 0 && lon < minPosLon) minPosLon = lon;
+        if (lon < 0 && lon > maxNegLon) maxNegLon = lon;


Fix bounding box bug for polygons crossing the antimeridian

nrabinowitz requested review from dfellis, isaachier and isaacbrodsky August 23, 2018 15:41

isaachier approved these changes Aug 23, 2018

View reviewed changes

Nicholas Rabinowitz added 3 commits August 23, 2018 11:24

Fix bounding box bug for polygons crossing the antimeridian

74fa161

Add fix message to CHANGELOG

facd5d9

Code review updates

71ca03e

nrabinowitz force-pushed the fix-transmeridian-bbox branch from 33f9a11 to 71ca03e Compare August 23, 2018 18:24

One more test cleanup

ff1f0af

nrabinowitz merged commit 469a50b into uber:master Aug 23, 2018

mrdvt92 pushed a commit to mrdvt92/h3 that referenced this pull request Jun 19, 2022

Merge pull request uber#130 from nrabinowitz/fix-transmeridian-bbox

a507142

Fix bounding box bug for polygons crossing the antimeridian

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix bounding box bug for polygons crossing the antimeridian #130

Fix bounding box bug for polygons crossing the antimeridian #130


		int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

		t_assert(actualNumHexagons == 1204,

Fix bounding box bug for polygons crossing the antimeridian #130

Fix bounding box bug for polygons crossing the antimeridian #130

Conversation

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment