在距离线段的距离内的AREA中查询点集 [英] Query set of points in AREA within distance from line segment
问题描述
我有一个线段和点存储在一个数据库。我如何查询数据库以便检索在多个线段的一定距离内的所有点。
目的是当用户点击路径（道路）时，距离路径一定距离内的所有对象都应该突出显示。
谢谢
更新：示例...
我有一个路径从（0,0）到（0,10）。程序应该找到并突出显示该路径x距离内的所有对象。
假设x距离是2...然后，程序应该突出显示矩形（0,2）（10，-2）中的所有对象。基本上，这与查找具有接近线的所有对象（而不仅仅是单个点）相同。
这是很容易的，当行是水平的...但我不知道如何解决所有的情况，包括然后线可能是一个斜率。 p>
更新：点数存储在大型数据库中，因此我无法检查每个数据库的邻近程度。我试图找到一种方法，只检索足够接近，没有重叠的请求太多...一旦他们被检索，我可以通过使用描述的方法在一个点和线段之间的距离。 （我想！）
谢谢！
这将给你从点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））;函数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 = 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）;函数dist2（p，q）{return Math.pow（p.x - q.x，2）+ Math.pow（p.y - q.y，2）; {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} 1，y：2}，{x：-1，y：4}，{x：2，y：8}]; isCloseToRoute（points，route，2）; alert（points.close.length +路由）; for（i在points.close中）console.log（points.close [i] .id）;
p>
如果将地图分成网格，可以使用isCloseToRoute（）来检查路线附近的网格单元格。它将返回一个有6,4这样的键的网格单元的列表;如果你给数据库中的每个点一个键，指示它在哪个网格单元格，你可以查找它们，而不必在坐标上做任何数学。
你做一个输入对象就像检查点列表，用网格单元格的中心点填充far []数组，并以距离（distance + gridSize * sqrt（2）/ 2）运行isCloseToRoute（）。
在示例中，地图是一个1000 x 1000平方，分为64个网格单元格，每个单元格的大小为125 x 125.
function isCloseToRoute ，route，distance）{var distance2 = Math.pow（distance，2）; for（var i = 0; 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）;函数dist2（p，q）{return Math.pow（p.x - q.x，2）+ Math.pow（p.y - q.y，2）; {x：440，y：760}}; var distance（x： = 100; var mapSize = 1000; var gridSize = 125; var gridCells = Math.floor（mapSize / gridSize）; var grid = {close：[]，far：[]}; for（x = 0; x
我已经优化了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 .splice（i，1）[0]）; }} function distanceToLineSegment2（p）{if（len2 == 0）return distanceToPoint2（p，v）; //如果零长度段可用则启用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）; }}} //生成随机测试datavar points = {near：[]，far：[{x：500，y：500}]}; var route = [{x：200，y：200} 100; for（var i = 1; i <1000; i ++）{points.far [i] = {x：Math.random（）* 1000，y：Math.random route [i] = {x：route [i-1] .x + 3 * Math.random（） - 1，y：route [i-1] .y + 3 * Math.random var t = new Date（）。getTime（）; isCloseToRoute（points，route，distance）; t = new Date（）。getTime（） - t; alert（points.near.length + n（在点数在+ t +ms内检查1000个点））; for（i in points.near）console.log（points.near [i] .x +，+ points.near [i] .y）;
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!
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);
这篇关于在距离线段的距离内的AREA中查询点集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
