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?
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.Sign up to join this community
There is one possible solution which is roughly $O(n\cdot (n-1)\cdot log(n))$ where $n$ is the number of 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.