Find an Online Tutor Now

Asked • 05/29/19

How do I check if cartesian coordinates make up a rectangle efficiently?

The situation is as follows: - There are N arrays. - In each array (0..N-1) there are (x,y) tuples (cartesian coordinates) stored - The length of each array can be different I want to extract the subset of coordinate combinations which make up a complete retangle of size N. In other words; all the cartesian coordinates are adjacent to each other. Example: findRectangles({ {*(1,1), (3,5), (6,9)}, {(9,4), *(2,2), (5,5)}, {(5,1)}, {*(1,2), (3,6)}, {*(2,1), (3,3)} }) yields the following: [(1,1),(1,2),(2,1),(2,2)], ..., ...(other solutions)... No two points can come from the same set. I first just calculated the cartesian product, but this quickly becomes infeasible (my use-case at the moment has 18 arrays of points with each array roughly containing 10 different coordinates).

1 Expert Answer

By:

Gene G. answered • 05/30/19

Tutor
5.0 (257)

Retired Electrical Engineer Helping People Understand Geometry

Still looking for help? Get the right answer, fast.

Ask a question for free

Get a free answer to a quick problem.
Most questions answered within 4 hours.

OR

Find an Online Tutor Now

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.