4

I am trying to work out given two GeoJSON lines (WGS84), if they intersect (i.e. cross one another). Let me give some pseudocode to illustrate:

// Providing Line 1 = lon1, lat1 and Line 2 = lon2, lat2
function linesIntersect(lon1, lat1, lon2, lat2) {

    var intersectionCheck = mathsToDoGeodesicIntersectionChecking()
    // This could be an external library or another code sample

    return intersectionCheck; // Return a boolean with true or false

}

The code samples I have tried are to long winded to post in the question, but you can see in the following GitHub repo (open line-crosses.html in a browser and open the dev tools to see some tests run).

It appears that the popular library Turf.js does not have a line intersect function. I am keen to make sure that the lines be created geodesically and checked in the same fashion (i.e. accounting for the curvature of the Earth rather).

The operation seems comparatively simple in a projected coordinate system scenario. I have a script (based off of code for in the comments of this post) that converts the lines coordinates to Web Mercator and checks for intersection, however I am uncertain as to the issues this may cause.

The code provided by moveable-type appears to get very close but unfortunately seems to check entire line paths and not line segments you provide (i.e. will these two lines ever intersect at their current bearings). Similarly GeographicLib looks like it may be able to help but I am struggling to find the solution using the library.

I am not specifically interested in where they intersect but more if they do. It would also be highly beneficial if they could handle discontinuity, as in to say to be able to handle a line that starts at a latitude of -179 and ends in at latitude 179 (see here for more explanation of what I mean).

1

If the endpoints of your segments are within 5000 km of each other, then pick some suitable midpoint (e.g., the point halfway between the 2 midpoints), and use this as the center of projection for GeographicLib's gnomonic projection. Map the two line segments into this projection and solve the resulting 2d intersection problem. This will give you a good idea whether or not the segments intersect. To get more accuracy repeat with a new center of projection at the intersection point (extending the segments if necessary). Repeat this enough times and you get an exact answer. I have code posted to do this here. (There's no discontinuity at longitude = ±180° with this method.)

  • Hi cffk, thanks for your input. I actually came across your code and it looks like what I'm looking for. However I can not find the gnomonic projection class in the JavaScript library :( : geographiclib.sourceforge.net/html/js – James Milner Feb 3 '16 at 9:24
  • The gnomonic projection isn't part of the Javascript library (sorry). However the C++ code implementing the projection is very short. It should be straightforward implementing this in Javascript. – cffk Feb 3 '16 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.