# Finding all points that are located in one line in 2D coordinate system

I have an array of points. Each point has two members - x and y.

I want to get any 3 points and check, are they located in single line in 2D coordinate system.

For example - 1x2, 2x3, 5x6:

If yes, I want to search for another point in my array which is located in that line (line has no start and no end). And so on, while I didn't check all remained points.

Then, I want to check next combination of 3 points and repeat while all 3-points permutations are no checked. For every of that permutations I want to tell how many points are located in single line (0 - if these 3 points are no located in single line, 3 - if they are, 4 - if they are and that's other point which also is located in that line, etc.). Is there any effective algorithm that can do it in complexity equal or less than O(n3)?

• What have you tried so far? What makes you think this is an (n^3)+ problem for instance? – World Engineer Aug 11 '13 at 17:32
• I have no idea other than brute-force. O(n^3) because max points count is 1000. 10^3 * 10^3 * 10^3 is 10^9 = I suppose the online checker won't accept anything more than that. But.. it's only a guessing. – user99295 Aug 11 '13 at 18:36
• Some hints can be found on Wikipedia's Dot Product. – mouviciel Aug 12 '13 at 12:05

For two points you can calculate the slope and the y intercept. If two different segments are part of the same line they will have the same slope and the same y intercept. If they have the same slope but different y intercepts they are parallel.

The only issue is when the line is vertical, the slope is infinite and the there is no y intercept, unless it is the line x=0.

Calculate all the pairs of points, and then cluster them by slope and intercept.

• which is related to hough transformation in a way, if a keyword for further research is needed – McMannus Aug 12 '13 at 20:28