Heuristically Guided Polygon Finding

In this paper we present a new algorithm for grouping 2D line segments into open and closed polygons that correspond to feasible physical 3D structures. The algorithm starts by identifying junctions made of two line segments and then forms triples by combining pairs of junctions which share a common line. These triples are then scanned by a procedure which connects them into polygon structures. Heuristic rules are used to control the combinatorial explosion associated with unconstrained associations of junctions and triples. Physical rules are used to reject polygons which are incompatible with a single planar surface hypothesis. The algorithm does not require strict connectivity of end-points at junctions. The polygon finder is seen as a high level grouping step which will enable the recognition of 3D objects which contain flat polygonal faces. Its use is illustrated on real data.