问题标签 [closest-points]

我有 2 组节点 - 组 A 和组 B。每组的大小为 25,000。

我得到一个百分比（比如说 20%）。我需要找到最小距离，以使 Set A 中 20% 的节点在 Set B 中任何节点的距离内。

解决方案：

找到集合 A 中最接近集合 B 中任何节点的 20%。答案是那 20% 中离集合 B 中任何节点最远的节点。

蛮力解决方案：

这行得通，但它所花费的时间是疯狂的。（O（n^2 + 排序）我认为？）

我怎样才能加快速度？如果可能的话，我想打 O(n)。

以下代码在 bing 地图上绘制了一条简单的线。有没有办法让这条线的起点和终点在最近的道路上。我不想使用路由服务。如果加载时间与下面的代码一样快，那就太好了。

谢谢你。

有没有什么好的方法可以在靠近多个目标的排序数组 A中找到所有值索引？使用 numpy.searchsorted() 可以让我们高效地找到靠近多个目标 的索引：在 Python 中查找最接近的值并返回数组的索引 但是，如果数组 A 中有重复的值。此方法将仅返回索引的 1而不是所有可能的索引。例如这样的数组：

它将返回 idx = [2, 11] 但我希望它返回 [[2,3],11] 我可以做的只是循环遍历 idx 以获取布尔索引，如 [A==A[idx[0] ],A==A[idx[1]],...] 但是如果目标数组非常大，这可能会非常低效。

有一件事是我可以首先使用 numpy.unique() 找到数组的唯一集。找到所有相同的值。然后在该唯一数组上搜索排序（），这可能会节省一些时间。然后我可以使用这个索引来查找所有相同的值。

这是一个例子：

我认为，如果len(ua)<<len(A)它比尝试直接在 A 上找到最接近的要高效得多。但是，npy.where 步骤仍在循环通过 _uaIdxs，如果它很大，那么它的效率将非常低。如果可以构建一个替代 unique()，为 A 中的每个唯一值获取索引列表（[[indices has value ua[0]]，[indices has value ua[2]]...]）。它会更有效率：

但我不知道是否有什么可以做unique2()预期做的事情。除了 searchsorted 之外，可能还有其他完全不同的算法可以以更有效的方式获得相同的结果。

为简单起见，我们假设 A 已排序。对于未排序的数组 A，我们总是可以先对其进行 argsort 排序。

有没有人可以提供一种更有效的方法来做到这一点？

谢谢！

我正在寻找最接近的对代码，我发现它使用了 qsort() 库函数。我基本上不明白它的比较参数是如何工作的。与此特定代码相关的解释将不胜感激。谢谢。

分配是使用蛮力到最近的一对点。

我似乎拥有了我需要的大部分东西 - 框架出现，圆圈出现在我点击的地方，最接近的对似乎正确突出显示，我说“似乎”，因为这是我的问题所在。我只需要在任何给定时间突出显示两个圆圈（最近的一对），但之前最接近的对不会取消选择/取消突出显示。

我希望这是我忽略的简单事情。我已经有一段时间了，所以很可能我的头脑和眼睛太累了，无法解决这个问题。希望新的眼睛能给我带来一些好处。

任何帮助是极大的赞赏。

我有两个数组代表两个不同的 GPS 路径。每个数组包含偶数索引中的纬度（从 0 开始）和奇数索引中的经度，如下所示：

我想计算这两条路径的最近点之间的距离之和。我使用 Haversine 方法计算纬度和经度对之间的距离。

这就是我所做的：我在当前数组中搜索距离最小的纬度和经度对。然后我将最小距离添加到一个汇总所有最小距离的变量中。然后我从数组中删除处理的纬度和经度。

这是代码：

你认为这是一种笨拙的方法吗？我怎样才能快速做到这一点？

注意我已经看到最近的点对问题，但不知道如何使用纬度和经度来实现它，以便比较两个不同数组之间的点。

我想将一个数组中的点与另一个数组中的点进行比较，并找到最接近的对。到目前为止，我遇到的只是一个数组。我不想比较来自同一个数组的点。蛮力算法有效，但速度太慢。是否有使用分治法的算法或实现？

编辑 1：一个点被定义为地球表面上的一对（纬度，经度）。

我正在尝试执行最接近的配对算法- 但是有一个区域我完全卡住了。

可以使用递归分治法在 O(n log n) 时间内解决该问题，例如，如下所示：

1) 根据 x 坐标对点进行排序。

2) 通过垂直线 x=xmid 将点集分成两个大小相等的子集。

3) 在左右子集中递归求解问题。这分别产生左侧和右侧最小距离 dLmin 和 dRmin。

4) 找出一组点对中的最小距离dLRmin，其中一个点位于分界线的左侧，第二个点位于右侧。

5) 最终答案是 dLmin、dRmin 和 dLRmin 中的最小值。

我的问题在于第 3 步：假设您已将 8 个元素的数组分成两半，在左半部分有 4 个点 - 1、2、3 和 4。假设第 2 点和第 3 点是这 4 个点中最接近的一对。好吧，如果你继续递归地把这个子集分成两半，你最终会计算出 1-2 之间的最小值（左边），你会计算 3-4 之间的最小值（右边），然后你会返回这两对的最小距离对..

但是 - 你完全错过了 2-3 之间的距离，因为你从来没有计算过，因为他们在对立面......那么这个问题是如何解决的呢？请注意第 4 步是如何在这个递归过程之后出现的，它似乎是一个独立的步骤，并且仅适用于第 3 步之后的最终结果，而不适用于第 3 步中发生的子数组的每个后续划分。是吗？还是有另一种我想念的方法？

MyPoint我可以找到一个点和一个多边形之间MyPolygon的距离

MyPolygon显然，必须在某处计算实际最近点。有没有一种简单的方法来获得最近的点？我在 Boost 文档中找不到任何内容，我相信其他人也有这个问题。

我有一个带有散点的 3d 矩阵（Nx4 矩阵，xyz 数据）。我的目标是将最近的点链接在一起，并将每个链注册在一个 Kx4 数组（x，y，z，数据）中，K 是链的长度。链的总数取决于点......一个特殊性是这些线只向上（z +），我不想在同一个z上链接点，或者向下。

到目前为止，我一直在尝试不同的策略，一种是使用另一种数组形状（Mx4xNz - 基本上意味着这些值是按 z 堆叠的，而不是全部在 2d 矩阵上）：[在取得一些进展后进行编辑，使用 delaunay/nearestneighbor]

1. 在 Zn 水平上选择一个点
2. 转到 Zn+1 级，使用 delaunayTriangulation 和nearestNeighbor 查找坐标 x,y 范围内的最近点
3. 将点注册到向量中

（我怀疑使用nearestNeighbor 和Nx4 矩阵还有其他可能性，但我想不出如何向上“引导”搜索并将连续点链接起来......）

我发现自己有以下问题：向上找到最近点似乎效果很好，但仅限于 1 个方向！

链接不起作用：

联动作品：

在循环期间，我收到警告：警告：已检测到并删除了重复的数据点。三角测量索引是根据 delaunayTriangulation 属性 X 中的唯一点集定义的。

木质素=零（max_iter，4，s）；

对于 i = 1:s;

结尾

任何人都知道为什么会发生这种情况？