How to remove colinear points from a list of points?

Given a point list (A1, A2, A3, ...., AN), each point Ai has Ai_x, Ai_y, and Ai_z indicates the x, y, z coordinate respectively.

Assume开发者_如何学C that given three point AONE, ATWO, ATHREE, a function named as checkColinear exist, i.e. checkColinear(AONE, ATWO, ATHREE) returns TRUE if points AONE, ATWO and ATHREE are colinear.

I am looking for a quick method to remove points that are colinars with some key points on the list.

Thank you

The naive way is to check every set of 3 points, which is O(N^3). I assume you want something faster.

You can do a little better (O(N^2*log N) for non-degenerate cases) by creating an array of slopes. Loop over every pair of points and store the slope in the array (along with the array indexes of the 2 points). Sort the array by slope. Then look through the array -- e.g. you might find 5 entries in a row with slope 2.5, from pairs (2,3), (6,7), (9,4), (3,5), (2,5). Points #2, #3, and #5 are colinear here.

(An easier/faster way to implement this check might be to find the y-intercept of each candidate point, given the slope, and sorting the candidate points that way. If three or more points have the same y-intercept, they are colinear.)

I also just found this link with the same basic approach: http://lists.canonical.org/pipermail/kragen-hacks/2008-March/000482.html