Point in polygon algorithm that handles polygons that straddle the antemeridian

Question

I have a database of polygon points as latitude, longitude pairs and I need to test if a given lat,lng point is inside any of the polygons.

There are several algorithms around including these but they don't work if the polygon straddles the antemeridian (off the coast of New Zealand, where longitude flips from +180 degrees East to -180 degrees West).

One solution I see is to detect if the polygon straddles the antemeridian and if so split it into two polygons, one on each side, then check each of them.

Answer 1

The other (simpler) option, IMO, is to just test for that special case, and if it exists, apply a transform to your query point and the polygon. For example, if it spans the anti-meridian, just translate everything by a specific longitude amount to make it not span the meridian, and do your standard test.

Answer 2

This is probably overkill, but you might considering using spherical polygons instead of treating the map as a plane. Here's a library in Java that handles them and can do point-in-spherical-polygon checks. Although, if you have polygons that contain more than half of the globe, or both poles, you might have issues since the definition of the enclosed area starts to break down.

Answer 3

Thanks for the suggestions. In the end the polygon I'm testing against is a rectangle so if it straddles the antemeridian (it has longitudes of different signs) chop it into two polygons, one on each side and query for objects that intersect either of them.