问题标签 [closest-points]

你能想到任何维度和任何度量中最近的点对和最远的点对的任何用法吗？

这是我的想法。

最近的一对点：

• 测试- 我们有一组点，例如某些公司拥有的一些实验室；公司建有传送器；它只能在这些实验室中重建，因为例如他们的墙壁是用黄金建造的，并且出于某种原因需要将传送器封装在黄金房间中；但是一个传送器会产生磁场，如果他们在一个学院中建造 2 个传送器，磁场会干扰，它们将无法工作；并且他们想要测试它们，最好先测试它们尽可能小的距离；所以他们必须找到两个彼此最近的实验室
• 许多旅行- 点是医院；每家医院正好有 1 公斤青霉素（或任何药物）；X先生每天需要1.5公斤的青霉素才能生存；每家医院每天得到这1公斤的药物；因此，X 每天必须访问 2 家医院；他会搬到这个国家的任何地方，但他不想每天都去很远的地方
• 遗传学- 点是人；我们想找到两个 DNA 最接近的人（这并不符合我们如何计算两个人之间的距离）；为什么？因为例如他们想知道我们彼此之间的距离有多近，以及我们必须改变一个人的最少核碱基数量是多少才能使他足够不同
• 遗传学 II - 点是人，但我们用外表来衡量他们之间的距离；例如，我们快要毁灭了，我们需要派一个人去执行一个他可能会死的任务；我们有一个完成任务所必需的设备，但它只适用于它通过外观识别的一个人（并且它的验证机制非常精确）所以我们需要找到两个尽可能相似的人

最远的一对点：

• 测试——我们已经成功地测试了传送的最小距离，截止日期快到了，所以我们希望尽可能彻底地检查它；所以我们需要找到两个尽可能远的实验室
• 逃生/安全——后世界末日；只有一些地方（点）适合居住；人们可以住在其中一个上，因为他们需要彼此靠近以确保安全（他们很少）；但是生活在某个地方会产生化学云（致命的），它会扩大到未知的大小；由于某种原因，它可能只发生一次；所以他们必须住在这样一个他们可以找到尽可能远的其他栖息地的地方
• 遗传学- 我们希望找到两种尽可能不同的生物，以便对它们进行实验并获得更多种类的物种，或者只是为了检查哺乳动物的多样性

我知道这些“有点”牵强，但重要的用途是在破折号之前（测试、遗传学等）。除了传送器，可能还有其他东西，更有可能存在，但用法是一样的。找到两个可能有其他实际用途，因为可能有相似的生物，但我不得不问遗传学家。但是请随意为我的用法写更多实用的故事。

有一个更大尺寸的例子会很棒。

首先，我正在阅读有关扫描线算法的信息，以在 O(N lgN) 时间内找到最接近的点对topcoder。我主要了解该算法，但是当我查看此处提供的实现（复制并在下面更易读）时，我注意到一些显着的差异。

首先，在上面的实现片段中，保存点并表示边界矩形的 std::set 不是按 y 坐标（而是按 x 坐标）排序的，这与几乎所有其他来源所说的相反The set is ordered by y coordinate. (Topcoder)：

接下来，即使集合没有按 y 坐标排序，当迭代器用于 时consider points in the active set ... whose y coordinates are in the range yN − h to yN + h，它也会作为 的下界pll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar)。为什么y先来？我认为正确的顺序是pll(points[i].x, points[i].y - shortestDistSoFar)但是将其更改为这会破坏算法。

有人可以帮助解决这些看似不一致的事情吗？

首先；我这样做是作为学校的作业，这就是我使用扫描线算法的原因。我是基于我老师给出的伪代码。

我已经使用 TreeMap 而不是平衡的二叉搜索树完成了我自己的实现，有人告诉我它将提供相同的功能。（虽然不知道这是不是真的？）

但是我没有得到正确的最终结果，我真的不知道为什么。我一直盯着自己瞎了。

下面是我的代码中执行实际计算的部分。我省略了积分列表的创建和其他不重要的东西。

编辑：伪代码可以在这里找到：http: //pastebin.com/i0XbPp1a。它基于我老师在白板上写的笔记。

关于结果：使用以下点 (X, Y)：(0, 2) - (6, 67) - (43, 71) - (39, 107) - (189, 140)

我应该得到〜36，但我得到〜65。

我正在尝试使用分而治之的方式在 Python 中实现最接近的配对问题，除了在某些输入情况下出现错误答案外，一切似乎都运行良好。我的代码如下：

我通过递归函数调用上述函数，如下所示：

其中min_dist(P)是对具有 3 个或更少元素的列表 P 的最近对算法的蛮力实现，并返回一个包含最近点对及其距离的元组。

如果我的输入是P = [(0,0),(7,6),(2,20),(12,5),(16,16),(5,8),(19,7),(14,22),(8,19),(7,29),(10,11),(1,13)]，那么我的输出就是((5,8),(7,6),2.8284271)正确的输出。但是当我的输入是P = [(94, 5), (96, -79), (20, 73), (8, -50), (78, 2), (100, 63), (-14, -69), (99, -8), (-11, -7), (-78, -46)]我得到的输出时((78, 2), (94, 5), 16.278820596099706)，正确的输出应该是((94, 5), (99, -8), 13.92838827718412)

我正在尝试实现分而治之的最近点算法。作为标准，但我的头快要爆炸了，因为我的代码似乎（随机）给出了错误的答案。我使用 stl 编写了一个随机数生成器用于测试目的，我一直遇到的错误是，每隔几次运行该算法都会返回一个明显比最近的对相距更远的对（由我输入的 1 个距离单位分隔手动）。

请原谅全局变量，但这是我第三次重写它，我只是觉得使用起来稍微容易一些。喜欢在屏幕上查看更多内容的用户可以使用 Pastebin 链接：http: //pastebin.com/93dtj81z

[编辑] 不正确的值似乎来自 BruteCP 函数......我想......这让我很头疼......

我目前有一个代理组（端口）孵化另一个代理组（船舶）。这个想法是让船只面对离它们当前位置最近的港口。

[let target min-one-of ports [distance myself] face target].

不幸的是，这使得船只面对它们当前的位置，因为它们是在给定的港口孵化的。如果无法排除它们孵化的端口 - 我有一个位置（端口）的索引，并且可能将目标设置为索引中的以下项目，但是我不确定我将如何实现这一点。有什么建议么？

完整的代码示例

我必须设置点，比如说设置 A 和 B

• A 和 B 大小相等
• A 的每个元素都耦合到 B 的一个元素

A 的所有点都必须“移动”到 B 的一个点，但 B 的一个点不能耦合到 A 的多个点。

我需要找到最佳组合，其中总（步行）距离（从每对之间的距离相加）是最小的。

出于演示目的，我在 Java 中做了一个示例（目前暴力破解所有可能的组合并检查总距离最小的组合）

示例 1

示例 2

绿色矩形代表集合 A 中的一个点，青色矩形代表集合 B 中的一个点，忽略橙色方块

我将如何处理这个？

我目前被分配创建一个 c++ 程序来查找 (x,y) 坐标系中最近的一对点。但是，我在试图理解一件事时遇到了很多麻烦。

我读过的关于最近对问题的每个教程/指南都告诉我按 Y 坐标对点集进行排序，但我不明白这是什么意思？有人可以向我解释为什么我们按 Y 坐标对其进行排序，它的用途是什么？我知道我们按 X 对点进行排序以获得 L 和 X*，但我只是不明白为什么我们也必须按 Y 坐标对点进行排序。

我试图找到最近的一对点，但我的代码不起作用。我不是这方面的专家，请帮助我。这是我的项目T_T

我的代码是这样的：

所以在那里。我很糟糕，对吧？T_T

研究从鼠标光标位置到光线投射命中的第一个对象的世界点。也许 api func getClosestPoint 或 rayIntersect 可以完成这项工作？如果是这样怎么办？（谢谢你）