8000 Fix bounding box bug for polygons crossing the antimeridian by nrabinowitz · Pull Request #130 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fix bounding box bug for polygons crossing the antimeridian #130

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.

Sign up for GitHub

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

Merged
merged 4 commits into from
Aug 23, 2018
Merged

Fix bounding box bug for polygons crossing the antimeridian #130

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
74fa161
Fix bounding box bug for polygons crossing the antimeridian
Aug 23, 2018
facd5d9
Add fix message to CHANGELOG
Aug 23, 2018
71ca03e
Code review updates
Aug 23, 2018
ff1f0af
One more test cleanup
Aug 23, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,6 +6,8 @@ The public API of this library consists of the functions declared in file
[h3api.h](./src/h3lib/include/h3api.h).

## [Unreleased]
### Fixed
- Fixed bounding box bug for polygons crossing the antimeridian (#130)
### Changed
- Longitude outputs are now guaranteed to be in the range [-Pi, Pi]. (#93)

Expand Down
11 changes: 9 additions & 2 deletions src/apps/testapps/testBBox.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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};
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 }

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

const GeoCoord outside = {1.0, M_PI - 0.5};
assertBBox(&geofence, &expected, &inside, &outside);
assertBBox(&geofence, &expected, &insideOnMeridian, &outside);

const GeoCoord westInside = {0.1, M_PI - 0.05};
t_assert(bboxContains(&expected, &westInside),
"Contains expected west inside point");
const GeoCoord eastInside = {0.1, -M_PI + 0.05};
t_assert(bboxContains(&expected, &eastInside),
"Contains expected east outside point");

const GeoCoord westOutside = {0.1, M_PI - 0.5};
t_assert(!bboxContains(&expected, &westOutside),
Expand Down
170 changes: 74 additions & 96 deletions src/apps/testapps/testPolyfill.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -26,76 +26,43 @@ GeoCoord sfVerts[] = {
{0.659966917655, -2.1364398519396}, {0.6595011102219, -2.1359434279405},
{0.6583348114025, -2.1354884206045}, {0.6581220034068, -2.1382437718946},
{0.6594479998527, -2.1384597563896}, {0.6599990002976, -2.1376771158464}};
Geofence sfGeofence;
Geofence sfGeofence = {.numVerts = 6, .verts = sfVerts};
GeoPolygon sfGeoPolygon;

GeoCoord holeVerts[] = {{0.6595072188743, -2.1371053983433},
{0.6591482046471, -2.1373141048153},
{0.6592295020837, -2.1365222838402}};
Geofence holeGeofence;
Geofence holeGeofence = {.numVerts = 3, .verts = holeVerts};
GeoPolygon holeGeoPolygon;

GeoCoord emptyVerts[] = {{0.659966917655, -2.1364398519394},
{0.659966917655, -2.1364398519395},
{0.659966917655, -2.1364398519396}};
Geofence emptyGeofence;
Geofence emptyGeofence = {.numVerts = 3, .verts = emptyVerts};
GeoPolygon emptyGeoPolygon;

GeoCoord primeMeridianVerts[] = {
{0.01, 0.01}, {0.01, -0.01}, {-0.01, -0.01}, {-0.01, 0.01}};
Geofence primeMeridianGeofence;
GeoPolygon primeMeridianGeoPolygon;

GeoCoord transMeridianVerts[] = {{0.01, -M_PI + 0.01},
{0.01, M_PI - 0.01},
{-0.01, M_PI - 0.01},
{-0.01, -M_PI + 0.01}};
Geofence transMeridianGeofence;
GeoPolygon transMeridianGeoPolygon;

GeoCoord transMeridianHoleVerts[] = {{0.005, -M_PI + 0.005},
{0.005, M_PI - 0.005},
{-0.005, M_PI - 0.005},
{-0.005, -M_PI + 0.005}};
Geofence transMeridianHoleGeofence;
GeoPolygon transMeridianHoleGeoPolygon;
GeoPolygon transMeridianFilledHoleGeoPolygon;
static int countActualHexagons(H3Index* hexagons, int numHexagons) {
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
actualNumHexagons++;
}
}
return actualNumHexagons;
}

BEGIN_TESTS(polyfill);

sfGeofence.numVerts = 6;
sfGeofence.verts = sfVerts;
sfGeoPolygon.geofence = sfGeofence;
sfGeoPolygon.numHoles = 0;

holeGeofence.numVerts = 3;
holeGeofence.verts = holeVerts;
holeGeoPolygon.geofence = sfGeofence;
holeGeoPolygon.numHoles = 1;
holeGeoPolygon.holes = &holeGeofence;

emptyGeofence.numVerts = 3;
emptyGeofence.verts = emptyVerts;
emptyGeoPolygon.geofence = emptyGeofence;
emptyGeoPolygon.numHoles = 0;

primeMeridianGeofence.numVerts = 4;
primeMeridianGeofence.verts = primeMeridianVerts;
primeMeridianGeoPolygon.geofence = primeMeridianGeofence;
primeMeridianGeoPolygon.numHoles = 0;

transMeridianGeofence.numVerts = 4;
transMeridianGeofence.verts = transMeridianVerts;
transMeridianGeoPolygon.geofence = transMeridianGeofence;
transMeridianGeoPolygon.numHoles = 0;

transMeridianHoleGeofence.numVerts = 4;
transMeridianHoleGeofence.verts = transMeridianHoleVerts;
transMeridianHoleGeoPolygon.geofence = transMeridianGeofence;
transMeridianHoleGeoPolygon.numHoles = 1;
transMeridianHoleGeoPolygon.holes = &transMeridianHoleGeofence;

transMeridianFilledHoleGeoPolygon.geofence = transMeridianHoleGeofence;
transMeridianFilledHoleGeoPolygon.numHoles = 0;

TEST(maxPolyfillSize) {
int numHexagons = H3_EXPORT(maxPolyfillSize)(&sfGeoPolygon, 9);
t_assert(numHexagons == 3169, "got expected max polyfill size");
Expand All @@ -112,12 +79,7 @@ TEST(polyfill) {
H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&sfGeoPolygon, 9, hexagons);
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
actualNumHexagons++;
}
}
int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == 1253, "got expected polyfill size");
free(hexagons);
Expand All @@ -128,12 +90,7 @@ TEST(polyfillHole) {
H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&holeGeoPolygon, 9, hexagons);
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
actualNumHexagons++;
}
}
int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == 1214, "got expected polyfill size (hole)");
free(hexagons);
Expand All @@ -144,12 +101,7 @@ TEST(polyfillEmpty) {
H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&emptyGeoPolygon, 9, hexagons);
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
actualNumHexagons++;
}
}
int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == 0, "got expected polyfill size (empty)");
free(hexagons);
Expand Down Expand Up @@ -178,20 +130,43 @@ TEST(polyfillExact) {
H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&someHexagon, 9, hexagons);
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
t_assert(hexagons[i] == origin, "Got origin back");
actualNumHexagons++;
}
}
int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == 1, "got expected polyfill size (1)");
free(hexagons);
free(verts);
}

TEST(polyfillTransmeridian) {
GeoCoord primeMeridianVerts[] = {
{0.01, 0.01}, {0.01, -0.01}, {-0.01, -0.01}, {-0.01, 0.01}};
Geofence primeMeridianGeofence = {.numVerts = 4,
.verts = primeMeridianVerts};
GeoPolygon primeMeridianGeoPolygon = {.geofence = primeMeridianGeofence,
.numHoles = 0};

GeoCoord transMeridianVerts[] = {{0.01, -M_PI + 0.01},
{0.01, M_PI - 0.01},
{-0.01, M_PI - 0.01},
{-0.01, -M_PI + 0.01}};
Geofence transMeridianGeofence = {.numVerts = 4,
.verts = transMeridianVerts};
GeoPolygon transMeridianGeoPolygon = {.geofence = transMeridianGeofence,
.numHoles = 0};

GeoCoord transMeridianHoleVerts[] = {{0.005, -M_PI + 0.005},
{0.005, M_PI - 0.005},
{-0.005, M_PI - 0.005},
{-0.005, -M_PI + 0.005}};
Geofence transMeridianHoleGeofence = {.numVerts = 4,
.verts = transMeridianHoleVerts};
GeoPolygon transMeridianHoleGeoPolygon = {
.geofence = transMeridianGeofence,
.numHoles = 1,
.holes = &transMeridianHoleGeofence};
GeoPolygon transMeridianFilledHoleGeoPolygon = {
.geofence = transMeridianHoleGeofence, .numHoles = 0};

int expectedSize;

// Prime meridian case
Expand All @@ -200,12 +175,7 @@ TEST(polyfillTransmeridian) {
H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&primeMeridianGeoPolygon, 7, hexagons);
int actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagons[i] != 0) {
actualNumHexagons++;
}
}
int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == expectedSize,
"got expected polyfill size (prime meridian)");
Expand All @@ -218,12 +188,7 @@ TEST(polyfillTransmeridian) {
H3Index* hexagonsTM = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&transMeridianGeoPolygon, 7, hexagonsTM);
actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagonsTM[i] != 0) {
actualNumHexagons++;
}
}
actualNumHexagons = countActualHexagons(hexagonsTM, numHexagons);

t_assert(actualNumHexagons == expectedSize,
"got expected polyfill size (transmeridian)");
Expand All @@ -234,24 +199,14 @@ TEST(polyfillTransmeridian) {
H3Index* hexagonsTMFH = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&transMeridianFilledHoleGeoPolygon, 7, hexagonsTMFH);
int actualNumHoleHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagonsTMFH[i] != 0) {
actualNumHoleHexagons++;
}
}
int actualNumHoleHexagons = countActualHexagons(hexagonsTMFH, numHexagons);

// Transmeridian hole case
numHexagons = H3_EXPORT(maxPolyfillSize)(&transMeridianHoleGeoPolygon, 7);
H3Index* hexagonsTMH = calloc(numHexagons, sizeof(H3Index));

H3_EXPORT(polyfill)(&transMeridianHoleGeoPolygon, 7, hexagonsTMH);
actualNumHexagons = 0;
for (int i = 0; i < numHexagons; i++) {
if (hexagonsTMH[i] != 0) {
actualNumHexagons++;
}
}
actualNumHexagons = countActualHexagons(hexagonsTMH, numHexagons);

t_assert(actualNumHexagons == expectedSize - actualNumHoleHexagons,
"got expected polyfill size (transmeridian hole)");
Expand All @@ -262,6 +217,29 @@ TEST(polyfillTransmeridian) {
free(hexagonsTMH);
}

TEST(polyfillTransmeridianComplex) {
// This polygon is "complex" in that it has > 4 vertices - this
// tests for a bug that was taking the max and min longitude as
// the bounds for transmeridian polygons
GeoCoord verts[] = {{0.1, -M_PI + 0.00001}, {0.1, M_PI - 0.00001},
{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 = {.numVerts = 6, .verts = verts};
GeoPolygon polygon = {.geofence = geofence, .numHoles = 0};

int numHexagons = H3_EXPORT(maxPolyfillSize)(&polygon, 4);

H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));
H3_EXPORT(polyfill)(&polygon, 4, hexagons);

int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

t_assert(actualNumHexagons == 1204,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

"got expected polyfill size (complex transmeridian)");

free(hexagons);
}

TEST(polyfillPentagon) {
H3Index pentagon;
setH3Index(&pentagon, 9, 24, 0);
Expand Down
49 changes: 21 additions & 28 deletions src/apps/testapps/testPolygon.c
View file
Open in desktop
10000
Original file line number Diff line number Diff line change
Expand Up @@ -127,10 +127,7 @@ TEST(pointInsideLinkedGeoLoop) {

TEST(bboxFromGeofence) {
GeoCoord verts[] = {{0.8, 0.3}, {0.7, 0.6}, {1.1, 0.7}, {1.0, 0.2}};

Geofence geofence;
geofence.verts = verts;
geofence.numVerts = 4;
Geofence geofence = {.numVerts = 4, .verts = verts};

const BBox expected = {1.1, 0.7, 0.7, 0.2};

Expand All @@ -139,6 +136,19 @@ TEST(bboxFromGeofence) {
t_assert(bboxEquals(&result, &expected), "Got expected bbox");
}

TEST(bboxFromGeofenceTransmeridian) {
GeoCoord verts[] = {{0.1, -M_PI + 0.1}, {0.1, M_PI - 0.1},
{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 = {.numVerts = 6, .verts = verts};

const BBox expected = {0.1, -0.1, -M_PI + 0.2, M_PI - 0.2};

BBox result;
bboxFromGeofence(&geofence, &result);
t_assert(bboxEquals(&result, &expected), "Got expected transmeridian bbox");
}

TEST(bboxFromGeofenceNoVertices) {
Geofence geofence;
geofence.verts = NULL;
Expand All @@ -154,14 +164,8 @@ TEST(bboxFromGeofenceNoVertices) {

TEST(bboxesFromGeoPolygon) {
GeoCoord verts[] = {{0.8, 0.3}, {0.7, 0.6}, {1.1, 0.7}, {1.0, 0.2}};

Geofence geofence;
geofence.verts = verts;
geofence.numVerts = 4;

GeoPolygon polygon;
polygon.geofence = geofence;
polygon.numHoles = 0;
Geofence geofence = {.numVerts = 4, .verts = verts};
GeoPolygon polygon = {.geofence = geofence, .numHoles = 0};

const BBox expected = {1.1, 0.7, 0.7, 0.2};

Expand All @@ -174,22 +178,14 @@ TEST(bboxesFromGeoPolygon) {

TEST(bboxesFromGeoPolygonHole) {
GeoCoord verts[] = {{0.8, 0.3}, {0.7, 0.6}, {1.1, 0.7}, {1.0, 0.2}};

Geofence geofence;
geofence.verts = verts;
geofence.numVerts = 4;
Geofence geofence = {.numVerts = 4, .verts = verts};

// not a real hole, but doesn't matter for the test
GeoCoord holeVerts[] = {{0.9, 0.3}, {0.9, 0.5}, {1.0, 0.7}, {0.9, 0.3}};
Geofence holeGeofence = {.numVerts = 4, .verts = holeVerts};

Geofence holeGeofence;
holeGeofence.verts = holeVerts;
holeGeofence.numVerts = 4;

GeoPolygon polygon;
polygon.geofence = geofence;
polygon.numHoles = 1;
polygon.holes = &holeGeofence;
GeoPolygon polygon = {
.geofence = geofence, .numHoles = 1, .holes = &holeGeofence};

const BBox expected = {1.1, 0.7, 0.7, 0.2};
const BBox expectedHole = {1.0, 0.9, 0.7, 0.3};
Expand Down Expand Up @@ -237,10 +233,7 @@ TEST(bboxFromLinkedGeoLoopNoVertices) {

TEST(isClockwiseGeofence) {
GeoCoord verts[] = {{0, 0}, {0.1, 0.1}, {0, 0.1}};

Geofence geofence;
geofence.verts = verts;
geofence.numVerts = 3;
Geofence geofence = {.numVerts = 3, .verts = verts};

t_assert(isClockwiseGeofence(&geofence), "Got true for clockwise geofence");
}
Expand Down
Loading
0