问题标签 [closest-points]

给定二维空间中的点列表，您想在 Haskell 中执行一个函数来查找两个最近点之间的距离。示例：输入：项目 [(1,5), (3,4), (2,8), (-1,2), (-8.6), (7.0), (1.5), (5.5), (4.8 ), (7.4)] 输出：2.0

假设列表中最远的两个点之间的距离最多为 10000。

这是我的代码：

我可以像示例中那样运行程序，也可以使用生成器，如下所示：

在 haskell 解释器中必须输入“生成器”，程序将在此处询问包含一千个点的文件名。并且在Haskell解释器中生成文件后必须写main，并请求一个文件名，这是你用“generator”创建的文件的名称。

问题是我的程序随机生成 1000 个点需要很长时间，在双核处理器的计算机上大约需要 3 分钟。我究竟做错了什么？如何优化我的代码以更快地工作？

我真的需要代码方面的帮助。用户需要输入 10 个整数，程序必须显示最接近的对。我可以使用 itertools 来完成，但我的教授不会接受 .sort()、min()、enumerate() 等......我需要手动完成。这是我能够使用 itertools 制作的代码：

对于手动最近配对程序，这是我到目前为止的代码：

无论我多么努力和研究，我都无法完成它。我将不胜感激任何帮助......

谢谢，艾琳

我正在寻找有效的算法来找到最接近点 P(x, y, z) 的顶点。顶点集是固定的，每个请求都带有新的点 P。我尝试了 kd-tree 和其他已知方法，但我到处都遇到同样的问题：如果 P 更接近则一切都很好，只对少数树节点执行搜索. 但是，如果 P 足够远，那么应该扫描越来越多的节点，最终速度变得无法接受。在我的任务中，我无法指定一个小的搜索半径。这种情况有什么解决方案？

谢谢伊戈尔

我应该使用蛮力算法确定最近的点。我无法编译它。

该算法是该网页上的第一个算法。

最近对问题的时间复杂度为 T(n) = 2T(n/2) + O(n)。我知道 2T(n/2) 来自这样一个事实，即该算法应用于 2 组原始大小的一半，但为什么其余的结果为 O(n)？谢谢。

我知道这可能是重复的，但它似乎是“最近点对”算法的一种变体。

给定单位正方形中的一组N个点 (x, y) 和距离d，找到所有点对，使得它们之间的距离最多为d。

对于大N，蛮力方法不是一种选择。除了“扫线”和“分而治之”的方法，还有更简单的解决方案吗？这对点是无向图的边缘，我需要遍历它并说出它是否连接（我已经使用 DFS 做过，但是当 N = 100 万时它永远不会完成！）。

欢迎任何伪代码、评论或想法，谢谢！

编辑：我在 Sedgewick 的书上找到了这个（我现在正在查看代码）：

当 N 足够大时，程序 3.18 使用一个二维的链表数组将程序 3.7 的运行时间提高了大约 1/d2。它将单位正方形分成大小相等的较小正方形的网格。然后，对于每个正方形，它建立一个包含所有落入该正方形的点的链表。二维数组提供了立即访问靠近给定点的点集的能力；链表提供了存储它们可能落入的点的灵活性，而我们不必提前知道有多少点落入每个方格中。

我想获得 10 个最近的经度和纬度位置。我将经度和纬度存储为双倍。我试过这个：

但我收到此错误：

如何解决这个错误？

让我稍微解释一下这个项目。我们有大量带有地址的商店列表。数据库中的每个地址都有一个地理位置。

现在我的问题是：当用户填写他的地址和邮政编码等时，我们有他的位置和他的地理位置，是否可以根据用户的位置在谷歌地图中找到最近的商店。如果不是通过地理位置，那么可能基于邮政编码？

我查看了谷歌地图 api，但没有找到喷气机来做这件事。重要的是它会搜索我们添加到谷歌地图的商店。我宁愿不使用谷歌地图，而只使用：http ://maps.googleapis.com/maps/api/geocode/json ？

如果可能的话，我们可以将谷歌地图排除在外，而只是根据地理位置搜索数据库，这样会更好。

那么唯一的问题是你如何根据地理位置或其他东西进行匹配？你只是检查女巫一个更小还是更大，或者还有更多然后比较两者？

如果有人能很好地指导我如何做到这一点，那就太好了。

我有两组 2D 点，它们在平面上被一条线分开。我想有效地找到一对点，​​由每组中的一个点组成，它们之间的距离最小。Radu Litiu 有一篇非常方便的论文，最近对两个分离的点集，但它使用 L1（曼哈顿）距离度量而不是欧几里得距离。

有谁知道适用于欧几里得距离的类似算法？

我几乎可以看到标准分治最近对算法的扩展——将这两个集合除以垂直于原始分割线的中线，在两侧递归，然后寻找由一个点组成的更接近的对中位数的每一边。如果与递归步骤的最小距离为 d，则中值一侧的点的伴星必须位于尺寸为 2d*d 的框内。但与原始算法不同的是，我看不到任何方法来限制该框内的点数，因此整个算法就变成了 O(m*n)。

有任何想法吗？

给定一个包含 N 个点的数组，在 2D 平面中找到离原点最近的 K 个点。您可以假设 K 远小于 N 并且 N 非常大。

这是我到目前为止所拥有的：

帮助表示赞赏