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

Question

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

Answer 1

Check the slopes of the lines that form the perimeter. (y2-y1) / (x2-x1).

Opposite sides should have the same slope. They're parallel.

There will only be two different slopes. They should be the negative reciprocal of each other. That means they're perpendicular.

Bingo! It's a rectangle.