algorithm - 几何：计算几何，计算所有朋友点对

Question

给定 n 个点，它们中没有三个是共线的。i 和 j ，如果以 i &j 为直径的圆不包含任何其他点，则 2 个点是朋友。在 O(nlogn) 中给出所有这些点

Answer 1

您正在尝试计算文献中所谓的相对邻域图。由两点确定的月牙一定是空的。关于这个主题有相当多的文献。您可以从Wikipedia 文章开始。正如用户tmyklebu所说，它是 Delaunay 三角剖分的一个子集。

      

更正。正如 Asiri 友好地解释的那样，我误读了条件。相关图是Gabriel Graph，它也有相当多的文献：

      

Answer 2

计算 Delaunay 三角剖分。如果两点是朋友，则它们必须是 Delaunay 三角剖分中的邻居。

然而，反之则不然。您需要检查 Delaunay 三角剖分中的每条（线性多条）边，以查看另一个点是否位于圆内。为此，请遍历所有边。调用当前迭代的端点u和v。u的邻居可以从v开始按顺时针顺序枚举；让 a_1 成为 u 从 v 顺时针方向的下一个邻居，a_2 成为 u 从 v 逆时针方向的下一个邻居。您只需检查 a_1 和 a_2 是否不在以 uv 为直径的圆内。

Answer 3

我对这个答案不是很自信，如果我错了，请纠正我。

我们从前两点开始，所以只有一个圆圈。这个圆可以用圆(p1, p2, c, r)的中心c和r半径来表示（它们也可以即时计算）。

现在我们逐渐添加其余的点，同时根据需要打破/制作新的圆圈。

因此，在某个步骤，如果我们有m多个圆圈，并且我们试图引入点p，扫描m并查看是否p在任何圆圈内（可以有效地确定给定c和r）。如果p在某个圆圈内，则摧毁该圆圈并创建两个新圆圈（与p被摧毁的圆圈的两个点）。

另一方面，如果在p所有圆之外，那么我们需要找到最接近的点p并创建一个新圆。现在我不完全确定如何有效地找到“最接近的点p”，可能是这样的？

如果我完全偏离轨道，请道歉！

更新：如果有超过 1 个“最接近的点p”，不知道该怎么办。可能会创建那么多新圈子（？）。

Answer 4

将以下内容插入 Delaunay 三角剖分：

首先定义D(x,y)表示点x和之间的距离y。

属性-I：给定任意 2 个点p1和p2，第三个点p3在圆上或圆内，其中一个直径是由p1和p2iff形成的线段

D(p1,p3)^2+D(p2,p3)^2<=D(p1,p2)^2.

这是因为圆上的角度是它所看到的圆部分的度数的一半，因此看到直径的那个是正确的。

因此，任何p1和p2都是朋友，如果在 Delaunay 瓷砖中与它形成三角形的点（最多 2 个这样的点）都满足属性-I。