问题标签 [closest-points]

我有一组点，我想从这些点创建线/道路网络。首先，我需要确定每个点的最近点。为此，我使用了 KD 树并开发了如下代码：

该代码可以返回周围最近的点。但是，我需要确保没有创建双线（例如（x，y）到（x1，y1）和（x1，y1）到（x，y）），并且我需要确保每个点只能是用作线的起点和线的终点，尽管该点与其他点最近。

下面是结果的可视化： 代码的结果

我想要的： 我想要的

我还尝试将原点和目标坐标分开，并这样做：

但这会返回错误

谁能帮我这个？非常感谢！

是否有可能在一组 n 点中找到k 对最近点比 快O(n^2)？

我知道我可以计算 中最近的点对O(nlogn)，但是使用该算法，并非所有距离都被计算，因此我无法返回前k 个最近的点对。

如果使用“蛮力”方法计算点的所有边缘的距离，这个问题是微不足道的，但这具有复杂性[n * (n-1)]/2，我想找到更有效的方法。

编辑：在此处查看最接近的配对算法： https ://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/

如何在 Java 的数组中找到 2 个最近的点？

我的意见是，

我的输出是，

有什么大惊小怪的？

我试图找到点之间的最小距离（二维平面中2个点之间的距离：距离(x1, y1) to (y1, y2))，存储在数组中arr，然后计算并返回这些距离的最小值。

但是，问题是我的源代码会产生随机垃圾输出。

这个想法是(x1, y1) and (x2, y2)用公式得到点之间的距离： sqrt((x1 - x2)^2 + (y1 - y2)^2)。为此，我为每次迭代选择 4 个元素： x1 = arr[0], x2 = arr[1], y1 = arr[2], y2 = arr[3]. x1并且x2在每次迭代 ( 的 ) 中保持不变，同时计算和( 的每次唯一迭代时变化i) 之间的距离。最后，选择两点之间的最短距离并返回到。x1, x2y1, y2jmain()

我做了什么来解决这个烂摊子？

在源代码中包含调试语句表明罪魁祸首是随机垃圾值（从字面上看，它甚至不应该存在！）。

另一个罪魁祸首是sqrt(arg)给出一个随机的垃圾值。例如，计算 和 之间的距离时(4, 4)，(1, 100)结果为sqrt(0 + (-99)^2) = 99。但相反，它输出-2147483648.

这是我的代码：

我知道这种方法是幼稚的并且 O(n^2)，但是要转向更快的算法，我必须首先用最基本的方法来解决它，以保持精神健全。

对于输入：

输出应该是0。

实际输出如下： The minimum distance between the array of points entered is -2147483648.

我在这里做错了什么？也欢迎替代（和更有效的算法）！提前致谢！:)

我最近尝试使用 C++ 实现最近对算法，我的大部分代码都受到了我在 GeeksforGeeks 上发现的启发。但是，我似乎无法运行具有较大 n 值的代码。我之前尝试输入 5,000,000 作为 n 值，然后进程在几秒钟后终止，没有显示任何输出。我需要能够达到至少 n = 5,000,000。现在，我的程序似乎停留在 n = 100,000 左右。它确实可以生成直到 n = 250,000 的随机数，但它会在进行最接近的配对计算之前终止。

这是我的代码。我真的更喜欢使用数组来收集值，但如果不可能，请赐教（我应该使用向量还是其他任何东西）。

更新：感谢您的建议！我修复了我的代码并使用了向量。它工作得很好。但是，当我尝试在大 n 值上使用大边框进行点随机化时，有时它们会显示非常不准确的结果。它只会计算点的 x 坐标之间的距离，而不是考虑 y 坐标。这是我修改后的代码。我想知道错误可能在哪里。提前致谢！

我有两个数据集（shp 文件（转换为 csv）），其中一个包含火灾历史，另一个包含雷击。两个数据集都有纬度和经度坐标（相同的投影）和火灾/雷击年份。我希望能够选择某年引起火灾的雷击。因此，我需要... 1）选择火灾一定半径内的雷击 2）从这些雷击中选择同一年内的雷击。

附加：每个火灾区域（1300 个区域）我都需要它，所以是自动化的，因为手动选择需要太长时间。此外，我将火区的所有雷击都包括在距离火区外部 1 公里的缓冲区内。所以就坐标而言，我们不是在谈论超过 0.1 或 0.2 的变化。时间不确定性可能更大，因为闪电数据集自身内部变化很大。假设有 3 到 4 周的不确定性。哦，输出不太重要，最好是形状文件。感谢您的关注。——</p>

我尝试过使用 gpd.sjoin，但是，这只加入了两个数据集。

使用 PostGIS 数据库，我想从点列表（存储为表中的几何图形）中过滤最接近传递给查询的某个点的点。
我已经尝试过ST_3DClosestPoint，但他们总是谈论线上的一个点。
如何过滤我的列表，以便仅确定最接近给定点的点云的 3D 点？PostGIS（2.5版）有没有机会做到这一点？

编辑 表结构和一些示例数据：

然后，查询应该询问传递给查询的最近点，例如，4571547, 5800297, -246,0312。我希望我的示例值的条目号 2 是此查询的结果。

我有一个图，其中每个节点都有二维坐标（它实际上是一个地理图，有纬度和经度。）我需要验证如果两条边之间的距离小于 MAX_DIST 则它们共享一个节点。当然，如果它们相交，那么它们之间的距离为零。

蛮力算法很琐碎，有没有更高效的算法？

我正在考虑尝试使https://en.wikipedia.org/wiki/Closest_pair_of_points_problem适应图形边缘（并忽略具有共享节点的边缘对），但这样做并非易事。

我试图从几个不同的数据集中找到最接近的对。到目前为止，它适用于具有 12 个点的 SmallerSet 但是当我更改具有 100 个点的数据集时。它在我在循环之前添加“--->”的那一行给出了 NullPointer Excepiton。我不知道要解决这个问题。

给定平面上的点，找到一对两个（不同）点之间的最小距离。回想一下，点 (1, 1) 和 (2, 2) 之间的距离等于 sqrt((x1-x2)**2 + (y1-y2)**2)。

我在 Python 代码（Divide & Conquer）下面写了，但是在一些隐藏的测试用例上给出了错误的答案，我不知道出了什么问题。任何代码更正方面的帮助都将得到衷心的感谢。PS：我已经检查了网络上的其他答案，但是这段代码在哪里做错了？