算法找到最近的 3 个点，当三角测量覆盖另一个点

Question

想象一个 Canvas ，周围随机散布着一堆点。现在选择其中一个点。您将如何找到离它最近的 3 个点，以便如果您绘制一个连接这些点的三角形，它会覆盖所选的点？

说明:“最近”是指到该点的距离的最小总和。

---

这主要是出于好奇。我认为如果一个点是未知的，但周围的点是已知的，这将是一个估计点“值”的好方法。通过 3 个周围的点，您可以推断出该值。我以前从未听说过这样的问题，看起来不是很微不足道，所以我认为这可能是一个有趣的练习，即使它不是估计某些东西的最佳方法。

Answer 1

您的问题描述不明确。在这个图中，你想要哪个三角形，红色的还是蓝色的？

蓝色三角形基于点距离的字典序比较更接近，而红色三角形基于点距离之和更接近。

编辑:您对其进行了澄清以明确表示您希望距离总和最小化(红色三角形)。

那么，这个素描算法怎么样？

1. 假设所选点位于原点(使算法描述简单)。
2. 按距原点的距离对点进行排序:P(1) 最近，P(n) 最远。
3. 从 i = 3, s = ∞ 开始。
4. 对于点 P(a)、P(b)、P(i) 和 a <b <i，如果三角形包含原点，令s = min(s, | P(a)| + |P(b)| + |P(i)|).
5. 如果 s ≤ |P(1)| + |P(2)| + |P(i)|，停止。
6. 如果 i = n，停止。
7. 否则，递增 i 并返回到第 4 步。

显然这是最坏情况下的 O(n³)。

这是另一种算法的草图。考虑所有点对 (A, B)。对于构成包含原点的三角形的第三个点，它必须位于下图中的灰色阴影区域:

通过在极坐标 (r, θ) 中表示点并根据 θ 对它们进行排序，可以直接检查所有这些点并选择最接近原点的点。

在最坏的情况下，这也是 O(n³)，但在许多问题实例中，访问对 (A, B) 的合理顺序应该会导致提前退出。