7

I'm working on a system that uses bounding boxes as a fast first check for a point-in-polygon filter. My current naive implementation (just taking the min/max lat and long for all points) fails on polygons that cross the antimeridian (180 longitude).

I've done enough research to determine that the Right Way is probably to use spherical polygons, but I'm hoping to avoid the complexity of this approach (code complexity and time complexity). I think I can ignore issues at the poles, at least for the present, so the problem is relatively simple if I can accurately identify polygons that cross the antimeridian, set the appropriate east/west values, and then change the bbox check if east < west. But I'm stuck on identification.

Constraints:

  • I don't control the format of the input polygons.
  • I assume all longitudes in the polygon are in the range -180 - 180
  • I assume that all input polygons follow the right-hand rule, i.e. have a counter-clockwise winding order.

Given these constraints, what's the easiest way to identify a polygon that crosses 180 longitude?

Taras
  • 32,823
  • 4
  • 66
  • 137
nrabinowitz
  • 336
  • 4
  • 10
  • 2
    You see if succeeding vertices are more than some apart and/or change sign in the longitude values. – mkennedy Sep 22 '17 at 18:33
  • @mkennedy - but that disallows polygons with arcs > 180 degrees; I'd like to avoid that. – nrabinowitz Sep 22 '17 at 20:43
  • Large value could be set to 270 or 350. Having a two-point line with a length larger than 180 degrees (or say 270) anywhere except near a pole is...chancy. – mkennedy Sep 22 '17 at 21:32
  • If all coordinates indeed are in the [-180,180] interval then there are no crossings of the antimeridian! – whuber Jan 04 '19 at 23:26
  • @whuber I don’t understand your comment - I’m assuming all longitudes are normalized to this range, but may well be part of an anti-meridian crossing polygon. – nrabinowitz Jan 06 '19 at 06:19
  • Please give an example of a specific sequence of coordinates that unequivocally indicates the antimeridian is crossed. – whuber Jan 07 '19 at 23:43
  • @whuber - if coordinates are assumed to follow the right-hand rule, then a box like [[179, 1], [179, -1], [-179, -1], [-179, 1]] would cross the antimeridian, right? Perhaps I need another constraint like "Polygons are assumed to cover less than half of the Earth's surface"? – nrabinowitz Jan 08 '19 at 00:57
  • The crossing of any line is not determined or affected by your use of the right-hand rule. In this example the right-hand rule establishes that the polygon in question is the complement of the square drawn on the map--but it still does not cross the antimeridian. A better constraint would be that no line segment (representing a spherical arc) may contain two diametrically opposite points. That's the same as limiting all segments to less than 180 degrees of arc. In effect, your reply to the comment by @mkennedy ruled out the best and simplest solution. – whuber Jan 08 '19 at 15:00

3 Answers3

0

The easiest way to identify a polygon that crosses 180 longitude is:

  1. Create polyline vector file with antimeridian line that crosses 180 (for test purposes I used GCS_WGS_1984 WKID: 4326 Authority: EPSG coordinate system).
  2. Use select by location tool to select polygon features that intersect antimeridian line.

This method is tested with ArcGIS Desktop:

Picture 1: WGS 84 test Picture 2: UTM test

Comrade Che
  • 7,091
  • 27
  • 58
  • 2
    Nothing in the question indicates access to ArcGIS Desktop; OP is looking for an algorithm, not a pre-existing (and incidentally closed-source) tool. – alphabetasoup Dec 04 '18 at 07:45
  • 2
    @RichardLaw This method is not programm dependant. You can implement your own select by location tool. How can you see in the answer this method is tested with ArcGIS Desktop. So you can test it in QGIS or where ever you want. This answer points OP to the need of creating his own select by location tool. – Comrade Che Dec 04 '18 at 09:47
0

I think that you have to make assumptions that constrain the polygon in some way. Consider that if you are at a defined point on the globe, and you want to get to another defined point, you assume that the edge to that point is a straight line. On a globe, that will be a great circle path. But you can go either direction on the great circle and still be on a straight line! This leads to all sorts of possibilities of edges that cross over one another and so forth. The topology of an "area" that is defined by four connected vertices on a globe is pretty complex. And there of course are the singularities at the poles.

D Reece
  • 1
-1

Detecting Antimeridian Crossings

  • Take your polygon's coordinates (in GeoJSON format), then check if the absolute value of the longitudinal difference between two consecutive vertices of the polygon is greater than a certain threshold. Practically, 180 degrees could be a sensible threshold default to start with (you can increase this of course).

For most practical purposes, after you've detected antimeridian crossings, you probably want to split your polygon in order to allow further geospatial operations. Here's the full tutorial + code snippets using Python and Shapely.

pawarit28
  • 41
  • 7
  • This is the Answer to a different question – Vince Jun 13 '21 at 03:45
  • I've stripped the answer down to answer this post's original question. However, for real-world applications, antimeridian detection alone is probably not useful without splitting/editing the polygon. I would appreciate if you removed your downvote (as the solution in the link can indeed detect antimeridian crossings) – pawarit28 Jun 14 '21 at 19:06