如何搜索XY坐标指定半径内的物体（无宝石）？
How to search for objects within a specified radius of an XY coordinate (without gems)?
--背景--
首先，不幸的是，由于我正在使用的软件有一个内置的 Ruby 库，它不允许安装 gem。我认为 Geocoder 看起来很有前途，唉...
我在 2D space 中有 X 数量的 link 和节点，我希望找到最接近给定 XY 坐标的 link。本质上是想创建我自己的方法来执行此操作，例如：
def manual_search_from_point(x, y, distance_from_point_to_search, collection_of_objects)
...
end
其中“collection_of_objects”通常是我要检索的对象组的数组 (links)。
不确定是否有一种方法可以在不计算对象之间的距离的情况下连续径向搜索越来越远（增加“distance_from_point_to_search”）来查找对象。考虑到这一点，我认为收集所有 links XY 坐标（端点等）并找到从该点到初始 XY 点的距离可能是值得的，使用：
def self.distance(x1, y1, x2, y2)
Math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
end
...从那里开始。
-- 当前状态 --
我目前正在尝试将所有 link 的坐标作为值添加到散列中，并将 link 对象本身作为键，然后处理每个 link 的XY 值并计算出距离，并再次使用 link 对象创建一个新的散列作为键，到该对象的距离作为值。我已经制作了第一个散列，但不确定如何将这些值作为单个 XY 进行循环。 （一个 link 个对象可以有多个 XY 点）
points_hash = Hash[ array.map {|k| [k, k.bends]} ]
-- 期望的输出--
发件人：
{#<Link:0x803a2e8>=>[394514.80, 421898.01, 394512.92, 421895.82]...} #(X1, Y1, X2, Y2)
至
{#<Link:0x803a2e8>=>[157], #(distance in metres (value not real distance))
\#<Link:0x803a2e8>=>[196]...} #(distance in metres (value not real distance))
如果我想要得到的东西有点棘手，可以提供更多信息。也很高兴被告知我做错了！
非常感谢。
创建 AABB-Tree: AABB-Tree is an spatial index i.e., it accelerate spatial queries. You can use other index datastructure like kd-tree, uniform grid, quad-tree, R-tree, etc. But I found AABB-tree simpler and near optimal for range queries (what you want to do is a range query e.g., like nearest neighbors)
1.1) 首先将每个 link 放入一个 AABB 中。计算每个 AABB 的质心。
1.2) 将你所有的AABB 放入一个包含所有AABB 的大AABB 中。使那个大 AABB 成为树 root 节点。
1.3) 找出大AABB的最大边（可以是X或Y）
1.4) 根据最大边对应的质心坐标（X或Y）对所有AABB进行排序。
1.5) 找到排序列表的中间位置，将其分成两个列表。
1.6) 创建两个附加到根节点的child节点，并为每个节点分配一个列表。
1.7) 递归调用步骤 1.2) 将每个 child 节点构建为子树。
1.8) 当列表的大小<= N时停止递归。然后将所有AABB分配给该节点。
进行范围查询以找到最接近 link 的点（即递归遍历树）。
2.1) 以要查询的点为圆心，定义一个半径无限大的圆。将圆作为参数传递给遍历函数。
2.2) 如果根节点的AABB与圆相交，则递归调用左右遍历函数children。顺序很重要，所以你应该先选择离圆心较近的child。
2.3) 如果该节点是叶节点（即没有 children，它包含 links 的 AABB 列表）然后检查圆是否与 [=] 的 AABB 相交54=]s，如果确实如此，则计算点到每个 link 的距离并保持最短距离。在计算到每个 link 的距离时，将其与圆的半径进行比较。如果距离小于半径更新圆的半径为最短距离，并保留最短距离link的ID。
遍历函数完成后，您将获得对数时间的最短距离。
接近
考虑 link
[a, b]
其中 a 和 b 是 two-element 数组，对应于欧几里得 space 中的 x-y 坐标。我假设 a != b.
在矢量术语中，通过点a和b的直线上的每个点都可以表示为：
αa + (1-α)b
对于标量的某个值 α。对于落在a和b之间的线段上的点，α满足0 <= α <= 1。据说这些点包含 a 和 b 的 凸组合 。我将计算 α (alpha) 的值，该值对应于穿过 a 和 b 的线上的点以及垂直于该点的线线并通过给定点 p.
首先计算通过a和b之间直线的斜率。让
a = [ax,ay]
b = [bx,by]
通过a和b的直线上的点c = [cx,cy]表示：
cx = alpha*ax + (1-alpha)*bx
cy = alpha*ay + (1-alpha)*by
我们可以简化为：
cx = alpha*(ax-bx) + bx
cy = alpha*(ay-by) + by
请注意，当 alpha 为零且等于 ax 和 [=64= 时，cx 和 cy 等于 bx 和 by ] 当 alpha 等于 1.
假设现在给定一个点：
p = [px,py]
并希望找到通过a和b的直线（不一定是线段）上与p最近的点。我们可以这样做。
首先计算通过a和b的直线的斜率（假设bx != ax，则对应一条垂直线）：
slope = (by-ay)/(bx-ax)
垂直于这条线的直线的斜率等于：
pslope = -1/slope
让我们计算通过点p的直线的截距：
intercept + pslope*px = py
所以
intercept = py - pslope*px
现在让我们看看根据 alpha 的值，这条线与通过 a 和 b 的线相交的位置：
intercept + pslope(alpha*(ax-bx) + bx) = alpha*(ay-by) + by
求解 alpha：
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
让我们举个例子试试看。考虑一个图的两个 link，如下图 professionally-prepared 所示。 （糟糕！我看到我的图形服务忽略了将点 [2,3] 标记为“A”。）首先考虑 link 或线段 A-B 和点 P .
ax = 2
ay = 3
bx = 5
by = 7
px = 5
py = 2
slope = (by-ay).fdiv(bx-ax)
#=> (7-3).fdiv(5-2) => 1.333..
pslope = -1.0/slope
#=> -0.75
intercept = py - pslope*px
#=> 5.75
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
#=> 0.8
cx = alpha*(ax-bx) + bx
#=> 2.6
cy = alpha*(ay-by) + by
#=> 3.8
因为0 <= alpha (0.8) <= 1,(cx,cy)落在A-B线段上，所以那个点是线段上离P最近的点，而不仅仅是那个点在经过 A 和 B 最接近 P.
的线上
发现P到C的距离的平方等于
(cx-px)**2 + (cy-py)**2
#=> (2.6-5.0)**2 + (3.8-2.0)**2 => 9
如果我们希望包括距离 P 不超过 3.5 的所有 link，这相当于包括所有 link 的平方距离至 P 不超过：
max_dist_sqrd = 3.5**2
#=> 12.25
作为9.0 <= max_dist_sqrd (12.25)，这个link将被包括在内。
现在考虑 link D-E.
dx = 7
dy = 6
ex = 6
ey = 9
px = 5
py = 2
slope = (ey-dy).fdiv(ex-dx)
#=> (9-6).fdiv(6-7) => -3.0
pslope = -1.0/slope
#=> 1.0/3.0 => 0.333
intercept = py - pslope*px
#=> 2 - (0.333)*5 => 0.333..
alpha = (ey - pslope*ex - intercept)/(pslope*(dx-ex) - (dy-ey))
#=> (9 - 0.333*6 - 0.333)/(0.333*(7-6) - (6-9)) #=> 2.0
因为alpha > 1.0我们知道点F不在线段D-E上。让我们简单游览一下，看看重点在哪里：
fx = alpha*(dx-ex) + ex
#=> 2.0(7-6) + 6 => 8.0
fy = alpha*(dy-ey) + ey
#=> 2.0(6-9) + 9 => 3.0
因为alpha > 1.0我们知道线段D-E上离P最近的点是D。如果 alpha > 1.0，最近的点应该是 E。
因此我们发现从点P到线段D-E的最近距离的平方等于：
(dx-px)**2 + (dy-py)**2
#=> (7-5)**2 + (6-2)**2 => 20
因为 20.0 > max_dist_sqrd (12.25)，这个 link 不会被包括在内。
代码
def links_in_point_circle(links, point, max_dist)
max_dist_sqrd = max_dist**2
links.select { |link| sqrd_dist_to_link(link, point) <= max_dist_sqrd }
end
def sqrd_dist_to_link( ((xlow,ylow),(xhigh,yhigh)),(px,py) )
return vert_link_dist(xlow,ylow,yhigh,px,py) if xlow == xhigh
slope = -1.0/((yhigh-ylow).fdiv(xhigh-xlow))
intercept = py - slope*px
alpha = (yhigh - slope*xhigh - intercept)/(slope*(xlow-xhigh) - (ylow-yhigh))
closest_x, closest_y =
case alpha
when -Float::INFINITY...0
[xhigh, yhigh]
when 0..1.0
[alpha*(xlow-xhigh) + xhigh, alpha*(ylow-yhigh) + yhigh]
else
[xlow, ylow]
end
(closest_x-px)**2 + (closest_y-py)**2
end
def vert_link_dist(xlow, ylow, yhigh, px, py)
return Float::INFINITY if px != xlow
case
when py < ylow then (ylow-py)**2
when ylow..yhigh then 0
else (py-yhigh)**2
end
end
例子
links = [[[2,3],[5,7]], [[7,6], [6,9]]]
point = [5,2]
max_dist = 3.5
links_in_point_circle(links, point, max_dist)
#=> [[[2, 3], [5, 7]]]
使用上面Cary Swoveland提供的方法，答案就差不多有了。使用下面的示例：
class Link
attr_accessor :bends
def initialize(bends)
@bends = bends
end
end
link_1 = Link.new([1, 1, 2, 2, 3, 3, 4, 4])
link_2 = Link.new([5, 5, 6, 6, 7, 7, 8, 8])
link_3 = Link.new([11, 11, 14, 14, 17, 17, 22, 22, 25, 25])
valid_links = Array.new
links = [link_1, link_2, link_3]
links.each do |link|
# Conditional goes here, to populate valid_links
valid_links << link
end
point = [1.1, 1.1]
def link_coordinates(link)
# To get the link XYs in desired format:
# [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]] (1)
link = link.bends.each_slice(2).each_cons(2).to_a
#=> [[[1, 1], [2, 2]], [[2, 2], [3, 3]], [[3, 3], [4, 4]]] (for first link)
end
closest_segment = valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)}
以上在 sqrd_dist_to_link 内产生错误。之前“links”仅使用值且格式为：
links = [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]] (2)
@closest_segment = links.min_by { |link| sqrd_dist_to_link(link, point)}
成功返回线段最近的 XY 坐标，格式为：[[x1, y1], [x2, y2]]。
考虑到标记为“(1)”的“links”和标记为“(2)”的 links 输出相同的格式，我不确定如何调整内容以便valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)} 将根据需要检索最近的 XY 线段的 link 对象。
注：
我会在它正常工作时更新它，以便它能够正确地作为答案。
--背景--
首先，不幸的是，由于我正在使用的软件有一个内置的 Ruby 库，它不允许安装 gem。我认为 Geocoder 看起来很有前途，唉...
我在 2D space 中有 X 数量的 link 和节点，我希望找到最接近给定 XY 坐标的 link。本质上是想创建我自己的方法来执行此操作，例如：
def manual_search_from_point(x, y, distance_from_point_to_search, collection_of_objects)
...
end
其中“collection_of_objects”通常是我要检索的对象组的数组 (links)。
不确定是否有一种方法可以在不计算对象之间的距离的情况下连续径向搜索越来越远（增加“distance_from_point_to_search”）来查找对象。考虑到这一点，我认为收集所有 links XY 坐标（端点等）并找到从该点到初始 XY 点的距离可能是值得的，使用：
def self.distance(x1, y1, x2, y2)
Math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
end
...从那里开始。
-- 当前状态 --
我目前正在尝试将所有 link 的坐标作为值添加到散列中，并将 link 对象本身作为键，然后处理每个 link 的XY 值并计算出距离，并再次使用 link 对象创建一个新的散列作为键，到该对象的距离作为值。我已经制作了第一个散列，但不确定如何将这些值作为单个 XY 进行循环。 （一个 link 个对象可以有多个 XY 点）
points_hash = Hash[ array.map {|k| [k, k.bends]} ]
-- 期望的输出--
发件人：
{#<Link:0x803a2e8>=>[394514.80, 421898.01, 394512.92, 421895.82]...} #(X1, Y1, X2, Y2)
至
{#<Link:0x803a2e8>=>[157], #(distance in metres (value not real distance))
\#<Link:0x803a2e8>=>[196]...} #(distance in metres (value not real distance))
如果我想要得到的东西有点棘手，可以提供更多信息。也很高兴被告知我做错了！
非常感谢。
创建 AABB-Tree: AABB-Tree is an spatial index i.e., it accelerate spatial queries. You can use other index datastructure like kd-tree, uniform grid, quad-tree, R-tree, etc. But I found AABB-tree simpler and near optimal for range queries (what you want to do is a range query e.g., like nearest neighbors)
1.1) 首先将每个 link 放入一个 AABB 中。计算每个 AABB 的质心。
1.2) 将你所有的AABB 放入一个包含所有AABB 的大AABB 中。使那个大 AABB 成为树 root 节点。
1.3) 找出大AABB的最大边（可以是X或Y）
1.4) 根据最大边对应的质心坐标（X或Y）对所有AABB进行排序。
1.5) 找到排序列表的中间位置，将其分成两个列表。
1.6) 创建两个附加到根节点的child节点，并为每个节点分配一个列表。
1.7) 递归调用步骤 1.2) 将每个 child 节点构建为子树。
1.8) 当列表的大小<= N时停止递归。然后将所有AABB分配给该节点。
进行范围查询以找到最接近 link 的点（即递归遍历树）。
2.1) 以要查询的点为圆心，定义一个半径无限大的圆。将圆作为参数传递给遍历函数。
2.2) 如果根节点的AABB与圆相交，则递归调用左右遍历函数children。顺序很重要，所以你应该先选择离圆心较近的child。
2.3) 如果该节点是叶节点（即没有 children，它包含 links 的 AABB 列表）然后检查圆是否与 [=] 的 AABB 相交54=]s，如果确实如此，则计算点到每个 link 的距离并保持最短距离。在计算到每个 link 的距离时，将其与圆的半径进行比较。如果距离小于半径更新圆的半径为最短距离，并保留最短距离link的ID。
遍历函数完成后，您将获得对数时间的最短距离。
接近
考虑 link
[a, b]
其中 a 和 b 是 two-element 数组，对应于欧几里得 space 中的 x-y 坐标。我假设 a != b.
在矢量术语中，通过点a和b的直线上的每个点都可以表示为：
αa + (1-α)b
对于标量的某个值 α。对于落在a和b之间的线段上的点，α满足0 <= α <= 1。据说这些点包含 a 和 b 的 凸组合 。我将计算 α (alpha) 的值，该值对应于穿过 a 和 b 的线上的点以及垂直于该点的线线并通过给定点 p.
首先计算通过a和b之间直线的斜率。让
a = [ax,ay]
b = [bx,by]
通过a和b的直线上的点c = [cx,cy]表示：
cx = alpha*ax + (1-alpha)*bx
cy = alpha*ay + (1-alpha)*by
我们可以简化为：
cx = alpha*(ax-bx) + bx
cy = alpha*(ay-by) + by
请注意，当 alpha 为零且等于 ax 和 [=64= 时，cx 和 cy 等于 bx 和 by ] 当 alpha 等于 1.
假设现在给定一个点：
p = [px,py]
并希望找到通过a和b的直线（不一定是线段）上与p最近的点。我们可以这样做。
首先计算通过a和b的直线的斜率（假设bx != ax，则对应一条垂直线）：
slope = (by-ay)/(bx-ax)
垂直于这条线的直线的斜率等于：
pslope = -1/slope
让我们计算通过点p的直线的截距：
intercept + pslope*px = py
所以
intercept = py - pslope*px
现在让我们看看根据 alpha 的值，这条线与通过 a 和 b 的线相交的位置：
intercept + pslope(alpha*(ax-bx) + bx) = alpha*(ay-by) + by
求解 alpha：
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
让我们举个例子试试看。考虑一个图的两个 link，如下图 professionally-prepared 所示。 （糟糕！我看到我的图形服务忽略了将点 [2,3] 标记为“A”。）首先考虑 link 或线段 A-B 和点 P .
ax = 2
ay = 3
bx = 5
by = 7
px = 5
py = 2
slope = (by-ay).fdiv(bx-ax)
#=> (7-3).fdiv(5-2) => 1.333..
pslope = -1.0/slope
#=> -0.75
intercept = py - pslope*px
#=> 5.75
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
#=> 0.8
cx = alpha*(ax-bx) + bx
#=> 2.6
cy = alpha*(ay-by) + by
#=> 3.8
因为0 <= alpha (0.8) <= 1,(cx,cy)落在A-B线段上，所以那个点是线段上离P最近的点，而不仅仅是那个点在经过 A 和 B 最接近 P.
发现P到C的距离的平方等于
(cx-px)**2 + (cy-py)**2
#=> (2.6-5.0)**2 + (3.8-2.0)**2 => 9
如果我们希望包括距离 P 不超过 3.5 的所有 link，这相当于包括所有 link 的平方距离至 P 不超过：
max_dist_sqrd = 3.5**2
#=> 12.25
作为9.0 <= max_dist_sqrd (12.25)，这个link将被包括在内。
现在考虑 link D-E.
dx = 7
dy = 6
ex = 6
ey = 9
px = 5
py = 2
slope = (ey-dy).fdiv(ex-dx)
#=> (9-6).fdiv(6-7) => -3.0
pslope = -1.0/slope
#=> 1.0/3.0 => 0.333
intercept = py - pslope*px
#=> 2 - (0.333)*5 => 0.333..
alpha = (ey - pslope*ex - intercept)/(pslope*(dx-ex) - (dy-ey))
#=> (9 - 0.333*6 - 0.333)/(0.333*(7-6) - (6-9)) #=> 2.0
因为alpha > 1.0我们知道点F不在线段D-E上。让我们简单游览一下，看看重点在哪里：
fx = alpha*(dx-ex) + ex
#=> 2.0(7-6) + 6 => 8.0
fy = alpha*(dy-ey) + ey
#=> 2.0(6-9) + 9 => 3.0
因为alpha > 1.0我们知道线段D-E上离P最近的点是D。如果 alpha > 1.0，最近的点应该是 E。
因此我们发现从点P到线段D-E的最近距离的平方等于：
(dx-px)**2 + (dy-py)**2
#=> (7-5)**2 + (6-2)**2 => 20
因为 20.0 > max_dist_sqrd (12.25)，这个 link 不会被包括在内。
代码
def links_in_point_circle(links, point, max_dist)
max_dist_sqrd = max_dist**2
links.select { |link| sqrd_dist_to_link(link, point) <= max_dist_sqrd }
end
def sqrd_dist_to_link( ((xlow,ylow),(xhigh,yhigh)),(px,py) )
return vert_link_dist(xlow,ylow,yhigh,px,py) if xlow == xhigh
slope = -1.0/((yhigh-ylow).fdiv(xhigh-xlow))
intercept = py - slope*px
alpha = (yhigh - slope*xhigh - intercept)/(slope*(xlow-xhigh) - (ylow-yhigh))
closest_x, closest_y =
case alpha
when -Float::INFINITY...0
[xhigh, yhigh]
when 0..1.0
[alpha*(xlow-xhigh) + xhigh, alpha*(ylow-yhigh) + yhigh]
else
[xlow, ylow]
end
(closest_x-px)**2 + (closest_y-py)**2
end
def vert_link_dist(xlow, ylow, yhigh, px, py)
return Float::INFINITY if px != xlow
case
when py < ylow then (ylow-py)**2
when ylow..yhigh then 0
else (py-yhigh)**2
end
end
例子
links = [[[2,3],[5,7]], [[7,6], [6,9]]]
point = [5,2]
max_dist = 3.5
links_in_point_circle(links, point, max_dist)
#=> [[[2, 3], [5, 7]]]
使用上面Cary Swoveland提供的方法，答案就差不多有了。使用下面的示例：
class Link
attr_accessor :bends
def initialize(bends)
@bends = bends
end
end
link_1 = Link.new([1, 1, 2, 2, 3, 3, 4, 4])
link_2 = Link.new([5, 5, 6, 6, 7, 7, 8, 8])
link_3 = Link.new([11, 11, 14, 14, 17, 17, 22, 22, 25, 25])
valid_links = Array.new
links = [link_1, link_2, link_3]
links.each do |link|
# Conditional goes here, to populate valid_links
valid_links << link
end
point = [1.1, 1.1]
def link_coordinates(link)
# To get the link XYs in desired format:
# [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]] (1)
link = link.bends.each_slice(2).each_cons(2).to_a
#=> [[[1, 1], [2, 2]], [[2, 2], [3, 3]], [[3, 3], [4, 4]]] (for first link)
end
closest_segment = valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)}
以上在 sqrd_dist_to_link 内产生错误。之前“links”仅使用值且格式为：
links = [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]] (2)
@closest_segment = links.min_by { |link| sqrd_dist_to_link(link, point)}
成功返回线段最近的 XY 坐标，格式为：[[x1, y1], [x2, y2]]。
考虑到标记为“(1)”的“links”和标记为“(2)”的 links 输出相同的格式，我不确定如何调整内容以便valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)} 将根据需要检索最近的 XY 线段的 link 对象。
注：
我会在它正常工作时更新它，以便它能够正确地作为答案。