javascript - 查询AREA中距线段距离内的点集

Question

我将线段和点存储在数据库中。我将如何查询数据库以检索多条线段一定距离内的所有点。 目的是当用户点击路径(道路)时，距该路径一定距离内的所有对象都应突出显示。

谢谢。

更新: 例子... 我有一条从 (0,0) 到 (0, 10) 的路径。程序应该找到并突出显示该路径 x 距离内的所有对象。 假设 x 距离为“2”...那么，程序应突出显示矩形 (0,2)(10,-2​​) 内的所有对象。基本上，这与查找靠近该线的所有对象(而不仅仅是单个点)相同。

当线是水平的时，这很容易......但我不知道如何解决所有情况，包括线可能是倾斜的。

更新:这些点存储在一个大型数据库中，因此我无法检查每个点的邻近度。我正在尝试找到一种方法来仅检索那些足够接近且不会过多重叠请求的内容...一旦检索到它们，我可以使用“点和线段之间的距离”中描述的方法来优化搜索”。 (我认为!) 谢谢!

Answer 1

这将为您提供从点 p 到线段 v,w 的距离。 (基于这个问题:Shortest distance between a point and a line segment)。您必须遍历所有点并计算到所有线段的距离，才能找到距离路线足够近的点。
如果太慢，您将不得不进行某种不需要平方根的简化。

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}));

这是一个稍微优化的实现，用于根据路线检查点列表。
要检查的点存储为点数组 far[]，其中包含 x 和 y 值以及 id 字符串。还有第二个最初为空的数组close[]，如果发现这些点靠近路线，则将这些点移动到该数组中，这样就不会检查两次点。这两个数组存储在一个对象points中，这样它们就可以在函数之间通过引用传递，而不是不断地被复制。为了提高效率，我还删除了平方根函数。
通过将距离计算更改为更粗略的近似值(可能使用矩形)而不是数学上正确的近似值，可能可以进一步优化。

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);

如果将 map 划分为网格，则可以使用 isCloseToRoute() 来检查哪些网格单元位于路线附近。它将返回一个网格单元列表，其中的键类似于“6,4”；如果您为数据库中的每个点指定一个键来指示它位于哪些网格单元中，则可以查找它们，而无需对坐标进行任何数学运算。
您创建一个输入对象，就像检查点列表时一样，用网格单元的中心点填充 far[] 数组，并在其上运行 isCloseToRoute() ，距离为 (distance + gridSize*sqrt(2)/2).
在示例中， map 是一个 1000 x 1000 的正方形，分为 64 个网格单元，每个网格单元的大小为 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);

我对 isCloseToRoute() 进行了更多优化。该示例运行一个测试，针对 1000 段随机路线检查 1000 个随机点。

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);