2D中最近的邻居 [英] nearest neighbor in 2D
问题描述
我有一个包含x和y坐标的两个元组的列表
（x0，y0）
（x1 ，y1）
...
（xn，yn）
给定一个新点x，y，我想找到列表中的点
最接近x，y。我必须在内循环中做很多事情，然后我将
添加到列表中的每个新点x，y。我知道
提前x和y的范围。
想到的一个解决方案就是将空间分区为
象限并按象限存储元素。当一个新元素
进来时，识别它的象限并且只搜索最近邻居的相应
象限。这可以递归完成，2D / b $ b二进制搜索各种各样....
任何人都可以指向我提供的某些代码或模块/>
适当的数据结构和算法来处理这个任务
有效吗？列表的大小可能在
10-1000元素的范围内。
谢谢，
John Hunter
I have a list of two tuples containing x and y coord
(x0, y0)
(x1, y1)
...
(xn, yn)
Given a new point x,y, I would like to find the point in the list
closest to x,y. I have to do this a lot, in an inner loop, and then I
add each new point x,y to the list. I know the range of x and y in
advance.
One solution that comes to mind is to partition to space into
quadrants and store the elements by quadrant. When a new element
comes in, identify it''s quadrant and only search the appropriate
quadrant for nearest neighbor. This could be done recursively, a 2D
binary search of sorts....
Can anyone point me to some code or module that provides the
appropriate data structures and algorithms to handle this task
efficiently? The size of the list will likely be in the range of
10-1000 elements.
Thanks,
John Hunter
推荐答案
>>>>> "约翰" == John Hunter< jd ****** @ ace.bsd.uchicago.edu>写道：
John>给定一个新的点x，y，我想找到列表中的点
John>最接近x，y。我必须在内循环中做很多事情，并且
John>然后我将每个新点x，y添加到列表中。我知道范围x
John>和y提前。
John>我想到的一个解决方案是将空间分区为
John>象限并按象限存储元素。当一个新元素
John>进来，确定它的象限，只搜索适当的
John>最近邻居的象限。这可以递归地完成，
John> 2D分类搜索....
通过递归，您的解决方案可以在O（log n）时间内工作。施工
需要O（n log n）时间。不幸的是，它可以返回错误的点，因为
最近的象限内的最近点可能不是最近的
点。
问题是一个经过充分研究的基本计算几何问题，虽然我不知道任何实际执行它的Python代码。尝试查看
网页上的Voronoi图表 径向三角测量和径向三角测量。了解如何在上面提到的（也许是随机的）时间中解决它的问题
复杂性。
问候，
Isaac。
>>>>> "John" == John Hunter <jd******@ace.bsd.uchicago.edu> writes:
John> Given a new point x,y, I would like to find the point in the list
John> closest to x,y. I have to do this a lot, in an inner loop, and
John> then I add each new point x,y to the list. I know the range of x
John> and y in advance.
John> One solution that comes to mind is to partition to space into
John> quadrants and store the elements by quadrant. When a new element
John> comes in, identify it''s quadrant and only search the appropriate
John> quadrant for nearest neighbor. This could be done recursively, a
John> 2D binary search of sorts....
By recursion your solution would work in O(log n) time. The construction
would take O(n log n) time. Unluckily, it can return the wrong point, as
the nearest point within the nearest quadrant might not be the nearest
point.
The problem is a well-studied basic computational geometry problem, although
I don''t really know any Python code that actually do it. Try to look at the
web for "Voronoi diagrams" and "radial triangulation" to understand how to
solve it properly in the above mentioned (perhaps randomized) time
complexity.
Regards,
Isaac.
John Hunter写道：
John Hunter wrote:
我有一个包含x和y的两个元组的列表coord
（x0，y0）
（x1，y1）
...
（xn，yn）
给一个新的点x，y，我想找到列表中最接近x，y的点。我必须在内循环中做很多事情，然后我将每个新点x，y添加到列表中。我知道
中的x和y的范围。
想到的一个解决方案是将空间划分为象限并按象限存储元素。当一个新元素进入时，识别它的象限，只搜索最近邻居的相应
象限。这可以通过递归方式完成，可以进行各种二维搜索....
任何人都可以指向一些提供适当数据结构和算法的代码或模块有效地处理这个任务吗？列表的大小可能在10-1000个元素的范围内。
谢谢，
John Hunter
I have a list of two tuples containing x and y coord
(x0, y0)
(x1, y1)
...
(xn, yn)
Given a new point x,y, I would like to find the point in the list
closest to x,y. I have to do this a lot, in an inner loop, and then I
add each new point x,y to the list. I know the range of x and y in
advance.
One solution that comes to mind is to partition to space into
quadrants and store the elements by quadrant. When a new element
comes in, identify it''s quadrant and only search the appropriate
quadrant for nearest neighbor. This could be done recursively, a 2D
binary search of sorts....
Can anyone point me to some code or module that provides the
appropriate data structures and algorithms to handle this task
efficiently? The size of the list will likely be in the range of
10-1000 elements.
Thanks,
John Hunter
你可以进行for循环，在那个循环中你将有一个变量
lessest_distance。我不太了解几何数学，但我很漂亮
确定你可以使用pytagoras的东西来找到从（Xn，Yn）到
（X，Y）的长度使用窦cosseus等。
当功能完成后，你应该返回lessest_distance
You could to a for loop, and inside that loop you will have a variable
lessest_distance. I dont know much geometric mathematics, but Im pretty
sure you can use pytagoras stuff to find the lenght from (Xn,Yn) to
(X,Y) using sinus cosinus and such.
And when the function is finished, you should return lessest_distance
John Hunter写道：
John Hunter wrote:
想到的一个解决方案是将空间分区为
象限并按象限存储元素。当一个新元素进入时，识别它的象限，只搜索最近邻居的相应
象限。这可以递归地进行，2D→二元搜索....
One solution that comes to mind is to partition to space into
quadrants and store the elements by quadrant. When a new element
comes in, identify it''s quadrant and only search the appropriate
quadrant for nearest neighbor. This could be done recursively, a 2D
binary search of sorts....
当你将一个粒子放在接近/边界处时会发生什么一个象限
虽然？最近的邻居可能在最近的
邻居象限......虽然你也可以搜索这些。
然而，独立的数量使用
''象限'这个词隐含的区域表明这与迭代所有
空间相同....： - ）
-
Graham Lee
Wadham学院
牛津
What happens when you put a particle in near/at the boundary of a quadrant
though? It''s possible for the nearest neighbour to be in the nearest
neighbour quadrant...although you could search over these as well.
However, the number of independent areas implied by use of the word
''quadrant'' suggests that this would be the same as iterating over all
space.... :-)
--
Graham Lee
Wadham College
Oxford
这篇关于2D中最近的邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
