1

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 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

q0987
  • 34,938
  • 69
  • 242
  • 387
  • possible duplicate of [Transformation to get rid of collinear points](http://stackoverflow.com/questions/2938464/transformation-to-get-rid-of-collinear-points) – Andreas Rejbrand Aug 19 '10 at 04:48
  • No. They are different. I have read that post first before I submit this question. Here, I have to remove the colinear points rather than simply add noise to the points to avoid removing colinear points. The major reason is that I have to get a smooth contour. The first step is to remove colinear points then next step I can adopt bezier smoothing method. thank you – q0987 Aug 19 '10 at 04:53
  • very similar: http://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear – Tom Sirgedas Aug 19 '10 at 05:54
  • @Anders, please do NOT try mathoverlow.net. It is for professional mathematicians only. You can try math.stackexchange.com, which is for everyone. (gee, the should have named professionalmathonly.net instead...) – Elazar Leibovich Aug 19 '10 at 10:25
  • look at Strilanc's answer in Tom's link. It's applicable for your use case as well. – Elazar Leibovich Aug 19 '10 at 10:27

1 Answers1

2

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

Tom Sirgedas
  • 3,208
  • 20
  • 17
  • There is one condition that I forgot specifically to mention is that all the points are in order. In other words, by connecting A1->A2->A3 .. AN, you get the contour of an object. thank you – q0987 Aug 19 '10 at 14:15
  • is the object convex? also, what if A2, A3, A99 are colinear? do you care, or do the points need to be consecutive? (if so, that makes the problem really simple). – Tom Sirgedas Aug 19 '10 at 15:10