如何从点列表中删除共线点？

Question

给定一个点列表(A1，A2，A3，...，AN)，每个点Ai都有Ai_x，Ai_y，Ai_z分别表示x，y，z坐标。

假设给定三个点AONE，ATWO，ATHREE，名为checkColinear的函数存在，即，如果点AONE，ATWO和ATHREE共线，则checkColinear(AONE，ATWO，ATHREE)返回TRUE。

我正在寻找一种快速的方法来删除一些关键点在列表上的点。

谢谢

Answer 1

天真的方法是检查每组3个点，这是O(N^3)。我猜你想要更快的东西。

您可以通过创建一个坡度数组来做得更好(对于非退化情况，为O(N^2*log))。循环遍历每一对点，并将斜率存储在数组中(以及两个点的数组索引)。按坡度对数组进行排序。然后查看数组--例如，您可能会在斜率为2.5的一行中找到5个条目，分别来自(2,3)，(6,7)，(9,4)，(3,5)，(2,5)。点#2、#3和#5在这里共线。

(实现此检查的更简单/更快的方法可能是找到每个候选点的y截距，给定斜率，并以这种方式对候选点进行排序。如果三个或多个点具有相同的y-截距，则它们是共线的。)

我也用同样的基本方法找到了这个链接：http://lists.canonical.org/pipermail/kragen-hacks/2008-March/000482.html