Geometrical Algorithms to Detect Patterns from a Set of Points

摘要

This article presents a new approach for detecting patterns, such as lines, parabolas and circles, from a two-dimensional cloud of points S. This scheme transforms the problem of detecting the patterns from S, to the problem of detecting simpler patterns from a set of points S' computed from the Voronoi and Delaunay diagrams of S. It is based on the differential properties of the Voronoi diagram that reflect the patterns to be retrieved. For example, in the case of parabolas, the patterns to be detected in S' are straight lines. The general idea of using the Voronoi diagram to detect patterns is an alternative and a complementary approach to the Hough Transform. It does not need to code a space of parameters and can be generalized to higher dimensions, with some adaptations.