8

I have an application where the user draws a path (a series of connected straight lines) and this path may not intersect any feature in a particular GeoJSON layer.

I need to check that no point along these lines intersect the GeoJSON layer, not just the endpoints.

How can I perform this check?

5
  • It could be do-able with Turf.js – ghybs Nov 20 '15 at 4:54
  • Anything in particular I should look at in Turf.js? – LavaHot Nov 20 '15 at 4:56
  • I don't think turf.js does this. You may be able to adapt some other intersection detection code for your purposes. For instance, this, which is designed to operate on GeoJSON linestrings, could get you most of the way, but if you need it to work with polygon layers, you'd need to either adapt it to accept polygon input or extract the polygons as linestrings from your GeoJSON layer first. – nathansnider Nov 23 '15 at 12:08
  • 2
    Wow impressive work! :-) I would have thought turf.intersect would do the job? (building on your jsfiddle: fiddle.jshell.net/tyt4oeux/1) But maybe I overlooked the question. – ghybs Nov 24 '15 at 7:17
  • Ah-ha, but of course that works! I just took the API docs at their word that turf.intersect needed a polygon as input. It never hurts to try, I guess. Since turf.intersect has the advantage of being simpler as well as detecting when a line is entirely within a polygon, that's clearly the way to go here, I think. – nathansnider Nov 24 '15 at 9:36
5

You can try the Turf library and a method like intersect: http://turfjs.org/docs/#intersect

Here's the code example from that library:

var poly1 = {
    "type": "Feature",
    "geometry": {
        "type": "Polygon",
        "coordinates": [[
            [-122.801742, 45.48565],
            [-122.801742, 45.60491],
            [-122.584762, 45.60491],
            [-122.584762, 45.48565],
            [-122.801742, 45.48565]
        ]]
    }
}
var poly2 = {
    "type": "Feature",
    "geometry": {
        "type": "Polygon",
        "coordinates": [[
            [-122.520217, 45.535693],
            [-122.64038, 45.553967],
            [-122.720031, 45.526554],
            [-122.669906, 45.507309],
            [-122.723464, 45.446643],
            [-122.532577, 45.408574],
            [-122.487258, 45.477466],
            [-122.520217, 45.535693]
         ]]
     }
}

var intersection = turf.intersect(poly1, poly2);
4
  • You should add an example of how to do this: links rot over time. – alphabetasoup Apr 8 '16 at 21:25
  • If that link will rot over time, then my entire answer will become void. The entire example is based on the existence of Turf library, and if that one will not be there ... However I copied that example to my answer. – Adrian Ber Apr 11 '16 at 5:39
  • 4
    The link rotted, here's the new one turfjs.org/docs/#intersect – Calvein Jun 9 '16 at 4:08
  • Link rot again (or mistake); no slash, just: turfjs.org/docs#intersect – Hendy Nov 26 '17 at 18:20
1

EDIT: See ghybs's fiddle from the comment above for a simpler and better solution using turf.js. Original answer follows:


Here is a modified version of the intersection routine from the geojson-js-utils library that takes GeoJSON linestrings as input and produces GeoJSON points of their intersection as output:

function lineStringsIntersect(l1, l2) {
    var intersects = [];
    for (var i = 0; i <= l1.coordinates.length - 2; ++i) {
        for (var j = 0; j <= l2.coordinates.length - 2; ++j) {
            var a1Latlon = L.latLng(l1.coordinates[i][1], l1.coordinates[i][0]),
                a2Latlon = L.latLng(l1.coordinates[i + 1][1], l1.coordinates[i + 1][0]),
                b1Latlon = L.latLng(l2.coordinates[j][1], l2.coordinates[j][0]),
                b2Latlon = L.latLng(l2.coordinates[j + 1][1], l2.coordinates[j + 1][0]),
                a1 = L.Projection.SphericalMercator.project(a1Latlon),
                a2 = L.Projection.SphericalMercator.project(a2Latlon),
                b1 = L.Projection.SphericalMercator.project(b1Latlon),
                b2 = L.Projection.SphericalMercator.project(b2Latlon),
                ua_t = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x),
                ub_t = (a2.x - a1.x) * (a1.y - b1.y) - (a2.y - a1.y) * (a1.x - b1.x),
                u_b = (b2.y - b1.y) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.y - a1.y);
            if (u_b != 0) {
                var ua = ua_t / u_b,
                    ub = ub_t / u_b;
                if (0 <= ua && ua <= 1 && 0 <= ub && ub <= 1) {
                    var pt_x = a1.x + ua * (a2.x - a1.x),
                        pt_y = a1.y + ua * (a2.y - a1.y),
                        pt_xy = {"x": pt_x, "y": pt_y},
                        pt_latlon = L.Projection.SphericalMercator.unproject(pt_xy);
                    intersects.push({
                        'type': 'Point',
                            'coordinates': [pt_latlon.lng, pt_latlon.lat]
                    });
                }
            }
        }
    }
    if (intersects.length == 0) intersects = false;
    return intersects;
}

The modifications were necessary because the original function was calculating intersections from latitude and longitude alone, as if they were just coordinates on a plane, producing inaccurate results (especially at high latitudes or over long distances). Using L.Projection to convert to a conformal (or, in this case, nearly conformal) projected coordinate system during the calculation fixes this.

One could modify it further to accept Leaflet geometry objects instead of just LineStrings, but instead I used this rather unwieldy function to create LineStrings to be passed to the intersection function:

function lineify(inputGeom) {
    var outputLines = {
        "type": "GeometryCollection",
            "geometries": []
    }
    switch (inputGeom.type) {
        case "GeometryCollection":
            for (var i in inputGeom.geometries) {
                var geomLines = lineify(inputGeom.geometries[i]);
                if (geomLines) {
                    for (var j in geomLines.geometries) {
                        outputLines.geometries.push(geomLines.geometries[j]);
                    }
                } else {
                    outputLines = false;
                }
            }
            break;
        case "Feature":
            var geomLines = lineify(inputGeom.geometry);
            if (geomLines) {
                for (var j in geomLines.geometries) {
                    outputLines.geometries.push(geomLines.geometries[j]);
                }
            } else {
                outputLines = false;
            }
            break;
        case "FeatureCollection":
            for (var i in inputGeom.features) {
                var geomLines = lineify(inputGeom.features[i].geometry);
                if (geomLines) {
                    for (var j in geomLines.geometries) {
                        outputLines.geometries.push(geomLines.geometries[j]);
                    }
                } else {
                    outputLines = false;
                }
            }
            break;
        case "LineString":
            outputLines.geometries.push(inputGeom);
            break;
        case "MultiLineString":
        case "Polygon":
            for (var i in inputGeom.coordinates) {
                outputLines.geometries.push({
                    "type": "LineString",
                        "coordinates": inputGeom.coordinates[i]
                });
            }
            break;
        case "MultiPolygon":
            for (var i in inputGeom.coordinates) {
                for (var j in inputGeom.coordinates[i]) {
                    outputLines.geometries.push({
                        "type": "LineString",
                            "coordinates": inputGeom.coordinates[i][j]
                    });
                }
            }
            break;
        default:
            outputLines = false;
    }
    return outputLines;
}

and this function to take Leaflet objects, convert them to LineStrings and check for intersections:

function crossCheck(baseLayer, drawLayer) {
    var baseJson = baseLayer.toGeoJSON(),
        drawJson = drawLayer.toGeoJSON(),
        baseLines = lineify(baseJson),
        drawLines = lineify(drawJson),
        crossPoints = {
            type: "GeometryCollection",
            geometries: []
        };
    if (baseLines && drawLines) {
        for (var i in drawLines.geometries) {
            for (var j in baseLines.geometries) {
                var crossTest = lineStringsIntersect(drawLines.geometries[i], baseLines.geometries[j]);
                if (crossTest) {
                    for (var k in crossTest) {
                        crossPoints.geometries.push(crossTest[k]);
                    }
                }
            }
        }
    }
    return crossPoints;
}

Here is an example fiddle using this with Leaflet.draw:

http://fiddle.jshell.net/nathansnider/egzxw86h/

When you finish drawing an object, it will place markers on the map at the points where the drawn object intersects with the base geometry. It can't check for intersections while a path is still being drawn, because Leaflet.draw doesn't give us any event handlers to use while the drawing is still in progress. It will check as soon as a draw event is completed though.

Also note that this will not detect intersections for paths that lie entirely within polygons they're being checked against. You could do those checks using turf.js (probably combining turf.explode with turf.within).

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.