找到一个点与一个平面中的所有其他点非共线

Question

给定一个平面中的N点在一般位置（没有三个是共线的）的列表，找到一个新点p与任何一对N原点不共线点。

我们显然无法搜索到飞机上的每一个点，我开始寻找可以用给定点形成的所有线的重合点，或者用它们圈起一个圆圈..我没有任何线索如何检查所有点。

问题在http://introcs.cs.princeton.edu/java/42sort/

发现我找到了一个著名的算法书，这意味着它回答的这个问题，但我不认为最佳的解决方案的，这就是为什么这样，如果一些人知道它，我在这里张贴他/她可以回答它

Answer 1

我能想出的最好的是N^2算法。这里所说：

1. 选择一个宽容ê来控制你如何接近你愿意来从该组中的点形成的线。
2. 计算您的一组积分的convex hull。
3. 选择一条线L平行于凸包的一侧，在远处3e外侧船体。
4. 在L上选择一个点P，使得P在凸包的投影之外。凸包在L上的投影是L的间隔.P必须放置在该间隔之外。
5. 测试集合中的每对点。对于由2个测试点形成的特定线M与围绕P的半径的圆盘相交，沿着L进一步移动P直到M不再与光盘相交。通过构造L，不会有与L平行的平行线相交，所以这总是可以完成的。
6. 如果M超过P超过L，则将P移动超过该交点，再次足够远以致M不通过光盘。
7. 完成这一切后，选择距离为e的点，在垂直于P处的垂线上。它可以是共线的，没有一组线。

我会留下的如何选择沿L P等的步骤5到你的下一个位置的细节，

有一些明显的琐碎拒绝测试，你可以这样做，你做更昂贵的检查只有在测试线M对于L“足够平行”的情况下才有效。

最后，我应该提到，可能可以将P推得足够远以至于出现数字问题。在这种情况下，我可以建议的最好方法是在凸包外部尝试另一条线，距离至少为3e。

Answer 2

你实际上可以使用一个简单的O（nlogn）算法来解决它，然后我们将改进为O（n）。名称最底部的点（如果选择了x坐标较小的那个）。现在可以使用CCW按照顺时针顺序排列其余点。现在，当从排序的顺序处理每个点时，可以看到在任意两个连续点与点A具有不同角度并且底部轴（让它们是U，V）之间没有具有角度c的点，其中U < = c < = V.因此，我们可以在本节中添加任何一点，并保证它不会与该集合中的任何其他点共线。因此，所有你需要的是找到一对相邻的点，你就完成了。因此，在O（n）时间内用A（这些应该是不同的）找到最小和第二个最小角度并选择它们之间的任意点。