问题标签 [closest-points]

我正在查看维基百科条目以了解如何解决此问题。它列出了五个步骤

1.沿x坐标排序点

2.用一条垂直线x = xmid将点集分成两个大小相等的子集

3.在左右子集中递归求解。这将分别给出左侧和右侧的最小距离 dLmin 和 dRmin。

4.求一对点之间的最小距离dLRmin，其中一个点位于分界线的左侧，第二个点位于右侧。

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

第四步我很难理解。如何选择线左侧的点与线右侧的点进行比较。我知道我不应该比较所有点，但我不清楚如何选择要比较的点。请不要给我发链接，我已经搜索了很多链接，但没有找到可以帮助我理解第 4 步的解释。

谢谢

亚伦

您好我的数据库中有一个点云（Sql server 2008 空间）。那是大约 600 万条记录。有 3 列：id、value、geom。在输入 lat long 处获得“价值”的最优化方法是什么？

我是 SQL Server 2008 中空间查询的新手。有人可以发布在 geom 列中查找点、匹配或最接近输入 lat long 的简单示例吗？

谢谢肖纳克

我在 SQL Server 2008 R2 Express 数据库中有大约 7500 万条记录。每个都是对应于某个值的 lat long。该表有地理列。我正在尝试为给定的纬度经度（点）找到一个最近的邻居。我已经有了一个带有空间索引的查询。但是根据记录在数据库中的位置，比如第一季度或上季度，查询可能需要大约 3 到 30 秒才能找到最近的邻居。我觉得这可以通过优化查询或空间索引来优化以提供更快的结果。现在应用了一些具有默认设置的空间索引。这是我的表和查询的样子。

我正在使用的空间索引：

这是我正在使用的查询：

这是我的数据库中的 lat longs 示例。给出准确度和密度的概念。所有 7000 万条记录都针对一个城市（激光雷达数据）

现在这个查询给了我上面描述的结果，但我想尽可能地提高性能。我的猜测是通过调整空间索引的默认值，我可能能够提高性能。这有什么线索吗？

我尝试将缓冲区从 10 更改为 1000，但结果几乎相同。

也欢迎任何其他改进性能的建议。

这是我现在使用的系统：

有人可以建议一种算法来找出最短距离的一对未排序的共线点吗？

我有一个解决方案可以在 O(nlogn) 中做到这一点，只需在 2D 中做最近的一对点并应用于该线。但是，这可以更有效地完成吗？

是否有一种已知的有效算法可以在云中找到最近的三点组？

这类似于最近的一对点问题，但我正在寻找三个点而不是两个点。

编辑
“最接近”的定义会影响算法的复杂性。正如杰克指出的那样，找到最小面积三角形是 3sum-hard 并且无论如何都不太适合我的应用程序。

我希望有一种更有效的算法来找到最小周长（即|AB|+|AC|+|BC|）三角形或类似的东西（例如最小|AB|²+|AC|²+|BC|². ) 我不知道为什么这应该是 3sum-hard，因为其他地方存在 3 个共线点不会影响结果。

注意：我的点有八个维度，所以任何限制在较少维度的算法都不适合。

我正在尝试实现该算法的更简单版本，但它比二次算法效果更好。我的想法基本上是仅通过 x 坐标对点进行排序并尝试从那里解决它。一旦我按 x 坐标对点数组进行排序，我想遍历数组并基本上跳过距离大于我所取的前两个点的点。

例如，我的 currentminDist = x;

如果我正在查看的两对点的距离 > x（仅通过其 x 坐标距离），我将忽略该点并在数组中移过它。

我有这个想法，但我有点坚持如何实际实现这一点（尤其是条件部分）。我有一个函数可以根据它们的 x 坐标返回两点之间的距离。

我对如何为循环实际编写条件感到困惑，因为如果距离恰好太远，我想忽略一个点，并且仍然填写我的数组，该数组将包含每个 i 的最近点的答案（我是当前点我在看）。

任何提示或方向将不胜感激。我对编码算法不是很了解，所以这很令人沮丧。

这是我的代码的一部分：

distbyX 是我的函数，它只返回两点之间的距离。

谢谢！

我有两个包含时间序列（unix 时间戳）的 numpy 数组。
我想找到差异在阈值内的时间戳对（每个数组中的 1 个）。

为了实现这一点，我需要将两个时间序列数据对齐到两个数组中，这样每个索引都有最接近的对。（如果数组中的两个时间戳与另一个数组中的另一个时间戳同样接近，我不介意选择其中一个，因为对的数量比实际值更重要。）

所以对齐的数据集将有两个大小相同的数组，加上一个较小的数组，其中填充了空数据。

我正在考虑使用timeseries包和align功能。
但我不确定如何为我的时间序列数据使用对齐。

示例考虑两个时间序列数组：

输出样本：

现在对于ts2[2] (1311257033.0)，它最接近的对应该是ts1[4] (1311251330.0)因为差异是5703.0，它在 之内threshold，并且它是最小的。既然已经配对ts2[2]，它们应该被排除在其他计算之外。ts1[4]

应该找到这样的对，因此输出数组可能比实际数组长

abs(ts1[0]-ts2[0]) = 16060
abs(ts1[0]-ts2[1]) = 15820 //对
abs(ts1[0]-ts2[2]) = 14212
abs(ts1[0 ]-ts2[3]) = 14273
绝对值(ts1[0]-ts2[4]) = 38444

---

abs(ts1[1]-ts2[0]) = 16121
abs(ts1[1]-ts2[1]) = 15881
abs(ts1[1]-ts2[2]) = 14151
abs(ts1[1]-ts2 [3]) = 14212
绝对值(ts1[1]-ts2[4]) = 38383

---

abs(ts1[2]-ts2[0]) = 17264
abs(ts1[2]-ts2[1]) = 17024
abs(ts1[2]-ts2[2]) = 13008
abs(ts1[2]-ts2 [3]) = 13069
绝对值(ts1[2]-ts2[4]) = 37240

---

abs(ts1[3]-ts2[0]) = 17384
abs(ts1[3]-ts2[1]) = 17144
abs(ts1[3]-ts2[2]) = 12888
abs(ts1[3]-ts2 [3]) = 17144
绝对值(ts1[3]-ts2[4]) = 37120

---

abs(ts1[4]-ts2[0]) = 24569
abs(ts1[4]-ts2[1]) = 24329
abs(ts1[4]-ts2[2]) = 5703 //对
abs(ts1[4 ]-ts2[3]) = 5764
绝对值(ts1[4]-ts2[4]) = 29935

---

abs(ts1[5]-ts2[0]) = 55794
abs(ts1[5]-ts2[1]) = 55554
abs(ts1[5]-ts2[2]) = 25522
abs(ts1[5]-ts2 [3]) = 25461
abs(ts1[5]-ts2[4]) = 1290 //对

---

abs(ts1[6]-ts2[0]) = 55853
abs(ts1[6]-ts2[1]) = 55613
abs(ts1[6]-ts2[2]) = 25581
abs(ts1[6]-ts2 [3]) = 25520
绝对值(ts1[6]-ts2[4]) = 1349

---

所以这些对是： ( ts1[0],ts2[1]), (ts1[4],ts2[2]), (ts1[5],ts2[4])
其余元素应该null作为它们的对
最后两个数组的大小为 9。

请让我知道这个问题是否清楚。

如何确定两个 uiviewimages 是否相交。我想做一个自动捕捉功能。当小图像与大图像相交或靠近它时（让我们说距离<= x），我希望小图像在它们相交的点自动捕捉（连接）到大图像。

我想知道什么是最好的解决方案。单击鼠标时返回并显示网页上最近的超链接。

本例中有 3DIV秒。它们每个都带有一个超链接。还有另一个超链接（超链接 D）本身没有DIV. 假设红点是鼠标点击。

例如

我能想到的解决方案就是遍历所有链接

然后使用距离方程计算距离c^2 = a^2 + b^2，所以很简单

这种方法当然需要 O(N) 时间复杂度，其中 N 是我们拥有的链接数。我们能做得更好吗？

我有一个二维数组：

前两个元素MyArray[0]和MyArray[1]是点的X和Y坐标。

对于数组中的每个元素，我想找到以X单位为半径返回其单个最近邻居的最快方法。我们假设这是在二维空间中。

让我们说这个例子X = 6。

我通过将每个元素与其他元素进行比较来解决了这个问题，但是当您的列表长度为 22k 点时，这需要 15 分钟左右。我们希望最终在大约 3000 万个点的列表上运行它。

我已经阅读了 Kd 树并理解了基本概念，但在理解如何编写它们时遇到了麻烦。