Find number of rectangles from a given set of coordinates
I have to find max number of rectangles from a given set of coordinates.
Consider the following coordinates are given in an X Y coordinate system 3 10, 3 8, 3 6, 3 4, 3 0, 6 0, 6 4, 6 8, 6 10,
How can I find if the following coordinates form a rectangle (3,0) (3,4) (6,4) (6,0)
Running time constraint: 0.1 sec
Thank you
Answer
Separate your points in lists of 'y' coordinate, grouped by 'x' coordinate. In your case you would have two sorted lists:
3: [0,4,6,8,10]
6: [0,4,8,10]
Doing the intersection of both lists you get: [0,4,8,10]
Any two of those would form a rectangle:
[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...
This solution only works for orthogonal rectangles, this is, with sides parallel to x,y axis.