0

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:

Image

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
2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.