我有线段和点存储在一个数据库中。我如何查询数据库，以检索所有的点是在一定距离内的多个线段。目的是当用户点击一条路径(道路)时，距离该路径一定距离内的所有物体都应该高亮显示。
谢谢。
更新:例子……我有一条从(0,0)到(0,10)的路径。程序应该查找并突出显示该路径x距离内的所有对象。假设x距离为"2"…然后，程序应该突出显示矩形(0,2)(10，-2)内的所有对象。基本上，这与找到所有接近这条线的对象(而不仅仅是一个点)是一样的。
这很容易当线是水平的…但是我不知道如何解决所有的情况，包括这时的直线可能是斜率。
更新:这些点存储在一个大的数据库中，所以我不能检查每一个点的接近度。我试图找到一种方法来检索只有那些足够接近没有重叠的请求太多…一旦它们被检索到，我就可以使用"点与线段之间的距离"中描述的方法来优化搜索。(我认为)谢谢!
这将给出从点p到线段v,w的距离。(基于这个问题:点和线段之间的最短距离)。你必须遍历所有的点，并计算到所有线段的距离，以找到离路线足够近的点。如果它太慢，你就必须做一些不需要平方根的简化。
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}));这是一个比较优化的实现，根据路由检查点列表。
要检查的点存储为具有x和y值和id字符串的点的数组far[]。还有第二个，最初为空的数组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);如果你将地图划分为一个网格，你可以使用isCloseToRoute()来检查哪些网格单元靠近该路径。它将返回一个键为"6,4"的网格单元列表;如果你给数据库中的每个点一个键，表示它位于哪个网格单元格中，你可以查找它们，而不必对坐标做任何数学运算。
您创建一个输入对象，就像检查点列表一样，用网格单元格的中心点填充far[]数组，并以(distance + gridSize*sqrt(2)/2)的距离对其运行isCloseToRoute()。
在示例中，地图是一个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);