问题标签 [closest-points]

我有一个家庭作业，我完全卡住了（级别：初学者）。

我必须创建一个方法来找到距用户条目和数组中所有点最近的 3 个距离 - 我被困在这里。

方法是：public static int[] troisPlusProches(int x, int y, int[] coordonneesHabitations) 其中int x和int y是用户条目，数组int[] coordonneesHabitations是int[] coordonneesHabitations = {9, 30, 18、8、3、18、25、36}。所以点是（9,30），（18,8），（3,18）和（25,36）。

我使用公式：distance = Math.sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2))) 来计算距离。

现在我必须从用户条目中找到 3 个最短距离，并将它们的位置返回到一个新数组中。

因此，如果用户条目是 x=10，则 y=15。

最短的距离是距点 (3, 18) 的 7.616，下一个是距点 (18, 8) 的 10.630，第三个是距点 (9, 30) 的 15.033。在这种情况下，该方法应返回一个数组 int[] troisPlusProches = {3, 18, 18, 8, 9, 30}。

我知道我必须做什么，我只是不知道如何...

这是许多错误尝试之一：

我有一个带有布尔值的二维矩阵，它的更新频率很高。我想在矩阵中选择一个二维索引 {x, y}，并在表中找到最近的“真”元素，而不需要遍历所有元素（矩阵很大）。

例如，如果我有矩阵：

我选择一个坐标{x1, y1}，例如 {4, 3}，我想返回最接近的“真”值的位置，在本例中为 {5, 3}。使用标准毕达哥拉斯方程测量元素之间的距离：

distance = sqrt(distX * distX + distY * distY)哪里distX = x1 - x和distY = y1 - y。

我可以遍历矩阵中的所有元素并保留一个“真实”值列表并选择具有最短距离结果的那个，但它的效率极低。我可以使用什么算法来减少搜索时间？

详细信息：矩阵大小为 1920x1080，每帧大约进行 25 次查询。整个矩阵每帧更新一次。我正在努力保持合理的帧率，超过 7fps 就足够了。

在 O(nlgn) 时间内找到最接近的点对时，用于将排序列表拆分为两个排序列表的伪代码（CLRS 3rd ed pg 1043）据说在 O(n) 时间内运行。

但是，这假设第 4 行以恒定时间运行，我很难相信（如果它存储为二叉树，我假设它在 O(lgn) 时间内运行，总运行时间为 O(nlgn) .

Y 是一个排序数组，YL 和 YR 是两个新的子数组。PL 是随机顺序的 Y 的子集，而 YL 是相同的子集，但按排序顺序。

我的推理哪里出了问题？

I am trying to understand how to go from n log^2 n time to n log n time for the closet pair algorithm. I get the below part (from http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html)

1. Divide the set into two equal sized parts by the line l, and recursively compute the minimal distance in each part.
2. Let d be the minimal of the two minimal distances.
3. Eliminate points that lie farther than d apart from l
4. Sort the remaining points according to their y-coordinates
5. Scan the remaining points in the y order and compute the distances of each point to its five neighbors.
6. If any of these distances is less than d then update d.

Step 4 is a sort that takes O(n log n) time, which dominates all other steps and this is the one that needs to be reduced to O(n) in order for the overall algorithm to achieve O(n log n) time. And this is the part I am having a hard time understanding. The author proposes

Step 1: Divide the set into..., and recursively compute the distance in each part, returning the points in each set in sorted order by y-coordinate. Step 4: Merge the two sorted lists into one sorted list in O(n) time.

You still have to sort the points by the y-coordinate in the recursive step, which takes O(n log n) time. How can we avoid this? The merging is O(n), but we still have to sort somewhere.

我觉得问这个问题很愚蠢，但是...

对于“最接近的点对”问题（不熟悉的请看这个），为什么蛮力算法的最坏情况运行时间是 O(n^2)？

如果说 n = 4，那么如果我们还考虑从任一方向比较两个点，那么在搜索空间中将只有 12 个可能的点对进行比较。如果我们不比较两个点两次，那么它将是 6。

O(n^2) 不适合我。

我正在尝试解决 spoj 上的 CLOPPAIR 问题，我必须找到两点之间的最小欧几里德距离并打印这两个点的索引。我尝试使用扫描线来做到这一点，但我仍然得到 TLE 。请有人帮助我吗？

这是我的代码 http://ideone.com/Tzy5Au

我正在尝试使用 R 进行一些 GIS 工作。具体来说，我有一个空间点数据框（称为“点”）和一个空间线数据框（称为“线”）。我想知道离每个点最近的线。我这样做：

这工作正常。我的问题是我的数据大小。我有 450 万个点和大约 100,000 行。到目前为止，它已经运行了大约一天，并且只完成了 450 万个点中的 200,000 个（尽管计算机功能相当强大）。

我可以做些什么来加快速度吗？例如，如果我在 PostGIS 中这样做，我会添加一个空间索引，但这似乎不是 R 中的一个选项。

或者，也许我正在接近这个完全错误的？

python中是否有任何有效的库函数来查找最近/最远的一对点？输入是位于边大小为 1 的 k 维立方体中的点列表。为了找到最接近的点，以下代码花费了太多时间。TC: O( n**2 * k ) 其中 n 是输入的大小。就我而言，输入 n 约为 4000，k 的值约为 300。

我想对该算法进行一些澄清，以在一组点中找到最近的一对点。

所以解决这个问题的一种方法是将点递归地分成两半，在每一半中找到最接近的点对。然后我们必须检查点中间的条带，看看那里是否有更接近的对。

我解决这个问题的步骤是： 1. 取所有点并按 X 坐标排序，然后将点分成两半。2. 递归地找到每一半的壁橱对

3. 找到中心带中的点（通过取中点 x 坐标 +/- 到目前为止找到的最小距离来计算）并将它们分开

这是我的问题

4. 我按它们的 y 坐标对该条带内的点进行排序，然后通过它们检查是否有一组更靠近的点。

我感到困惑的部分 - 我应该将这些点与条带中的其他点进行比较以查看是否有更接近的一对，还是应该将这些点与来自步骤 1 的原始点集中的相邻点进行比较，这些点是按 x 坐标排序。

我知道有证据表明我只需要检查一定数量的邻居，但我很困惑“邻居”是否来自原始点集，或者我是否应该只查看中心地带的点。

我希望这是有道理的-感谢您的澄清。

编辑：我想说我想我只会比较条带本身内的点（因为当我们查看一半时，条带之外的任何东西都会被比较） - 我只是想澄清一下。也是的，这是算法的规范 D&C 版本，我只是想确保我正确理解它，中间带内的点让我有点困惑。

我有 n 个字符串，我想找到最近的一对。

找到这对的最快实用算法是什么？