Query set of points in AREA within distance from line segment

Question

I have line segments and points stored in a db. How would I query the db in order to retrieve the all the points that are within a certain distance of multiple line segments. The purpose is that when the user clicks on a path (road), all the objects that are within a distance from the path should be highlighted.

Thank you.

Update: Example... I have a path that goes from (0,0) to (0, 10). The program should find and highlight all objects within x-distance of this path. Suppose that the x-distance is "2"... then, the program should highlight all objects within the rectangle (0,2)(10,-2). Basically, this is the same as finding all objects with a proximity to the line (not just a single point).

It is easy when the line is horizontal... But I don't know how to solve for all cases, including then the line may be a slope.

Update: The points are stored in a large database, so I cannot check each and every one of them for the proximity. I'm trying to find a way to retrieve only the ones that are close enough without overlapping requests too much... Once they are retrieved, I can refine the search by using the method described in "distance between a point and a line segment". (I think!) Thanks!

Answer 1

This will give you the distance from point p to line segment v,w. (based on this question: Shortest distance between a point and a line segment). You'll have to run through all your points and calculate the distance to all your line segments to find the ones close enough to the route.
If it's too slow, you'll have to make some kind of simplification that doesn't need square roots.

function distanceToLineSegment(p, v, w)
{
    var len2 = dist2(v, w);
    if (len2 == 0) return Math.sqrt(dist2(p, v));
    var s = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;
    if (s < 0) return Math.sqrt(dist2(p, v));
    if (s > 1) return Math.sqrt(dist2(p, w));
    var i = {x: v.x + s * (w.x - v.x), y: v.y + s * (w.y - v.y)};
    return Math.sqrt(dist2(p, i));

    function dist2(p, q) {
        return Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2);
    }
}

alert(distanceToLineSegment({x:2, y:3}, {x:-1, y:4}, {x:3, y:8}));

This is a somewhat optimized implementation that checks a list of points against a route.
The points to check are stored as an array far[] of points with x and y values and an id string. There is a second, initially empty array close[] into which the points are moved if they are found to be close to the route, so that points aren't checked twice. These two arrays are stored in an object points, so that they can be passed by reference between the functions, instead of constantly being copied. I've also removed the square root functions for efficiency.
Further optimization is probably possible by changing the distance calculation to a coarser approximation (maybe using rectangles) instead of a mathematically correct one.

function isCloseToRoute(points, route, distance) {
    var distance2 = Math.pow(distance, 2);
    for (var i = 0; i < route.length - 1; i++) {
        isCloseToLineSegment(points, route[i], route[i + 1], distance2);
    }

    function isCloseToLineSegment(points, v, w, distance2) {
        for (var i = points.far.length - 1; i >= 0; i--) {
            if (distanceToLineSegment2(points.far[i], v, w) <= distance2) {
                points.close.push(points.far.splice(i, 1)[0]);
            }
        }
    }

    function distanceToLineSegment2(p, v, w) {
        var len2 = dist2(v, w);
        if (len2 == 0) return dist2(p, v);
        var q = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;
        if (q < 0) return dist2(p, v);
        if (q > 1) return dist2(p, w);
        var i = {x: v.x + q * (w.x - v.x), y: v.y + q * (w.y - v.y)};
        return dist2(p, i);
    
        function dist2(p, q) {
            return Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2);
        }
    }
}

var points = {close: [], far: [{x: 1, y: 0, id: "A"}, 
                               {x: 2, y: 1, id: "B"}, 
                               {x:-1, y: 8, id: "C"}, 
                               {x:-3, y: 4, id: "D"}]};
var route = [{x: 0, y: 0}, {x: 1, y: 2}, {x:-1, y: 4}, {x: 2, y: 8}];

isCloseToRoute(points, route, 2);
alert(points.close.length + " points found near route");
for (i in points.close) console.log(points.close[i].id);

If you divide your map into a grid, you can use isCloseToRoute() to check which grid cells are near the route. It will return a list of grid cells which have a key like "6,4"; if you give each point in your database a key that indicates in which grid cells it's located, you can look them up without having to do any math on the coordinates.
You make an input object just like when checking a list of points, fill the far[] array with the center points of the grid cells, and run isCloseToRoute() on it with a distance of (distance + gridSize*sqrt(2)/2).
In the example, the map is a 1000 x 1000 square, divided into 64 grid cells each sized 125 x 125.

function isCloseToRoute(points, route, distance) {
    var distance2 = Math.pow(distance, 2);
    for (var i = 0; i < route.length - 1; i++) {
        isCloseToLineSegment(points, route[i], route[i + 1], distance2);
    }

    function isCloseToLineSegment(points, v, w, distance2) {
        for (var i = points.far.length - 1; i >= 0; i--) {
            if (distanceToLineSegment2(points.far[i], v, w) <= distance2) {
                points.close.push(points.far.splice(i, 1)[0]);
            }
        }
    }

    function distanceToLineSegment2(p, v, w) {
        var len2 = dist2(v, w);
        if (len2 == 0) return dist2(p, v);
        var q = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;
        if (q < 0) return dist2(p, v);
        if (q > 1) return dist2(p, w);
        var i = {x: v.x + q * (w.x - v.x), y: v.y + q * (w.y - v.y)};
        return dist2(p, i);
    
        function dist2(p, q) {
            return Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2);
        }
    }
}

var route = [{x: 210, y: 190}, {x: 820, y: 480}, {x:530, y: 470}, {x: 440, y: 760}];
var distance = 100;
var mapSize = 1000;
var gridSize = 125;
var gridCells = Math.floor(mapSize / gridSize);
var grid = {close: [], far: []};

for (x = 0; x < gridCells; x++) {
    for (y = 0; y < gridCells; y++) {
        grid.far[y * (gridCells) + x] = {x: (x + 0.5) * gridSize, 
                                         y: (y + 0.5) * gridSize, 
                                       key: x + "," + y};
    }
}

isCloseToRoute(grid, route, distance + 0.707107 * gridSize);
alert(grid.close.length + " grid cells near route");
for (i in grid.close) console.log(grid.close[i].key);

I've optimized isCloseToRoute() a bit more. The example runs a test with 1000 random points checked against a 1000-segment random route.

function isCloseToRoute(points, route, distance) {
    var distance2 = Math.pow(distance, 2);
    for (var i = 0; i < route.length - 1; i++) {
        isCloseToLineSegment(route[i], route[i + 1]);
    }

    function isCloseToLineSegment(v, w) {
        var len2 = distanceToPoint2(v, w);
        var lenX = w.x - v.x, lenY = w.y - v.y;
        for (var i = points.far.length - 1; i >= 0; i--) {
            if (distanceToLineSegment2(points.far[i]) <= distance2) {
                points.near.push(points.far.splice(i, 1)[0]);
            }
        }

        function distanceToLineSegment2(p) {
          if (len2 == 0) return distanceToPoint2(p, v);   // enable if zero-length segments are possible
            var q = ((p.x - v.x) * lenX + (p.y - v.y) * lenY) / len2;
            if (q < 0) return distanceToPoint2(p, v);
            if (q > 1) return distanceToPoint2(p, w);
            var r = {x: v.x + q * lenX, y: v.y + q * lenY};
            return distanceToPoint2(p, r);
        }

        function distanceToPoint2(p, q) {
            return Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2);
        }
    }
}

// generate random test data
var points = {near: [], far: [{x: 500, y: 500}]};
var route = [{x: 200, y: 200}];
var distance = 100;
for (var i = 1; i < 1000; i++) {
    points.far[i] = {x: Math.random() * 1000, y: Math.random() * 1000};
    route[i] = {x: route[i - 1].x + 3 * Math.random() - 1, y: route[i - 1].y + 3 * Math.random() - 1};
}

var t = new Date().getTime();
isCloseToRoute(points, route, distance);
t = new Date().getTime() - t;
alert(points.near.length + " points found near route.\n(1000 points checked against 1000 segments in " + t + " ms)");
for (i in points.near) console.log(points.near[i].x + "," + points.near[i].y);