How to detect quadrilaterals in a point cloud?

How can I detect a quadrilateral in a point cloud that looks almost like a rectangle? How do I set the criteria (i.e orientation, size etc) to get the shape for example in the image below? • Is the rectangle allowed to be arbitrarily rotated or should it be axis-aligned? The latter case is much easier to solve using lookup tables. – Libor Dec 25 '13 at 16:58
• It axis-aligned but the top and bottom sides don't have to be exactly horizontal all the time (e.g Side 1-2) – askingtoomuch Dec 26 '13 at 5:38

There is one possible solution which is roughly $O(n\cdot (n-1)\cdot log(n))$ where $n$ is the number of points.

1. Build 2-dimensional k-d tree from all the points
2. For each pair of unmarked (undiscovered) points

2.1 Determine two areas (based on rectangle criteria) where the other two points can possibly lay

2.2 Find nearest point to center of each of the areas (using the k-d tree)

2.3 If each nearest point is unmarked and lays within its respective area, store new rectangle, mark all four points as discovered

The algorithm can be optimized by keeping undiscovered points in a set, picking new ones from the, progressively reducing its size.

Another speedup would be removing discovered points from the KD-tree so the algorithm does not have to check them in step 2.3.

• I understand how kd-tree works but I don't really get what you mean by "determining two areas based on rectangle criteria" in step 2.1. Do you mean the area where P1, P3 lie, and the area where P2, P4 lie? – askingtoomuch Dec 26 '13 at 5:34
• and how do I filter other possible shapes like 1-2-4-5, 1-2-6-5 etc? – askingtoomuch Dec 26 '13 at 5:43
• You may define a threshold by determining how likely it is to find such a rectangle (as defined by the algorithm) in a set of randomly positioned dots – meduz Dec 27 '13 at 15:37