2D中最近的邻居

本文介绍了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