lineIntersect for large polygons near poles

[rob4acre]

Hi,

I came across a possible issue with the lineIntersect module. I'm using it to find possible cases of intersecting polygons that represent satellite beam coverage patterns. These can extend over large areas (the visible portion of the earth seen from Geo orbit) and can pass near the polar regions. In most cases lineIntersect is working, but some of the geojson polygons have long line arcs at the edges of the patterns, for example

https://gist.github.com/rob4acre/cada8b6c8b9286fc2a91e8a53609ac4b

This shows the beams and the intersects that turf/lineIntersect is finding with the pseudocode in the following simple script that loops over the features and looks for intersects, like

function detectIntersections(features) {

  // check all permutations for the features (polygons)
  for (var i = 0, len = features.length; i < len; i++) {
    for (var j = i + 1, len = features.length; j < len; j++) {

      // find any intersections between the polygon border lines
      var lineI = turf.polygonToLine(features[i]);
      var lineJ = turf.polygonToLine(features[j]);

      var intersections = turf.lineIntersect(lineI, lineJ);
      // if there is an intersection, then add to the count
      if (intersections.features.length > 0) {
        var iName = 'Feature ' + String(i) + ' ' + featureName(features[i]);
        var jName = 'Feature ' + String(j) + ' ' + featureName(features[j]);
        var msg = iName + ' intersects ' + jName;
        console.log(msg);
      }

    }
  }
}

The long line arc in the north should follow a great circle arc that goes nearly over Svarlbard.

lineIntersect is detecting intersections that do not really exist. I think that this is because the path between coordinates is not following the great circle (shortest distance on the Earth's surface) but a straight line in lat/long coordinates (see black line on image above).

Unless I am missing something (which is entirely possible) it looks like lineIntersect is only giving correct results in the case of lines with relatively short lengths, away from the poles.

Thanks in advance for taking a look at this. Rob

[rowanwins]

Hi @rob4acre

Yeah something similar was just reported in #1573 .

While I'm waiting on some action on some 3rd party modules this one would be worthy of a rewrite as it's used in a couple of places so it would be good to get right.

Cheers Rowan

[erikquinn]

+1 for this.

Here's some more test data to replicate the issue easily. I have a very long line that crosses hemispheres and detects intersections that do not exist with the provided polygon. At its closest, the line is about 900 nautical miles away from the closest part of the polygon.

Based on many instances like this one for me, it seems like this is happening mostly with long lines which cross +180/-180 longitudes, and they seem to be drawing the line the long way around the globe, which (with the little analysis I've done) I think is a likely cause of the incorrect intersections being detected.

---

For the below line and polygon, turf.lineIntersect produces the following 2 invalid "intersection" points, even though none should exist:

{"type":"FeatureCollection","features":[{"type":"Feature","properties":{},"geometry":{"type":"Point","coordinates":[-79.62285176753579,28.475139363120412]}},{"type":"Feature","properties":{},"geometry":{"type":"Point","coordinates":[-76.79237026020789,27.706128529003742]}}]}

LINE:

{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[151.24497,-34.24912],[-97.0080944444,33.19851944444]]}}

POLYGON:

{"type":"Feature","properties":{},"geometry":{"type":"Polygon","coordinates":[[[-77.00000024,27.46666639],[-76.376,28.18633333],[-76.9175,29.76666667],[-77,30],[-79.18472222,30.20277778],[-79.30714291,30.13751249],[-80.06527778,29.73333333],[-80.2,29],[-79.61669444,29.20833306],[-79.52941289,29.00368827],[-79.6299632,28.43491264],[-79.03333333,28],[-78.05833333,27.46666639],[-77,27.46666639],[-77.00000024,27.46666639]]]}}