找到最接近3点的算法,当三角测量覆盖另一点时

Question

想象一下画布上有一堆随机散布的画布.现在选择其中一个点.你如何找到距离它最近的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. 如果小号 ≤| P(1)| + | P(2)| + | P(i)|,停止.
6. 如果i = n,停止.
7. 否则,递增i并返回步骤4.

显然,在最坏的情况下,这是O(n³).

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

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

在最坏的情况下,这也是O(n³),但是访问对(A,B)的合理顺序应该在许多问题实例中产生早期退出.