How to group a cluster of points from a set such that it matches the edges of a specific geometric template whose dimensions are know?

Question

Let's say there is cartesian 2D space with many points scattered around. I now have a geometric template as shown in the attached image. I know for sure there are some points in the space that can definitely align with this template's edges. are there any efficient and fast algorithm to find these points?

Thanks in Advance !

Answer 1

To the best of my knowledge, you have to loop on every point of the cluster, match it to some vertex of the template, then find a second point that matches the distance to another vertex of the template. These two points define a rigid transformation, and you can predict the remaining vertices. Then find all remaining matches.

Assuming that you use an efficient data structure that tells a matching point at a known distance in sublinear time D(n), and a matching point at known coordinates in sublinear time P(n), the total cost will be like

m.n.(D(n)+(m-2).P(n))

where m is the number of vertices of the template. (By brute-force, the complexity is m²n².)

Possible data structures include a grid, a kD-tree and a vantage-tree.