How to detect quadrilaterals in a point cloud?
There is one possible solution which is roughly $O(n\cdot (n-1)\cdot log(n))$ where $n$ is the number of points.


Build 2-dimensional k-d tree from all the points
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.