Shape Discovery :: A Simple Algorithm ::

Terminology and Data Structures

This section describes some of the terminology and data structures used by the first shape from probing algorithm.

Shape S: The shape S is the polygon under investigation.
Current Hull H: The current hull H is the convex hull of the contact points obtained by probing. All the points inside the current hull are known to be part of S.
Verified Edge: A verified edge of H is an edge that has at least one contact in its interior. As explained here, three colinear contact points are sufficient to prove that all the points on that line segment are part of the boundary of the shape. Thus a verified edge of H is either an edge or a segment of an edge of S.
Unverified Edge: An unverified edge of H has only two contact points: one at each extremity. The point on the unverified edge may or may not be part of the boundary of S.
Verified Vertex: A verified vertex of H is a vertex that connects two verified edges. A verified vertex is thus a vertex of the shape S.
Fully-Verified Edge: A fully-verified edge of H is a verified edge bounded by two verified vertices. A fully-verified edge of H is an edge of S.
Semi-Verified Edge: A semi-verified edge of H is verified edge that is not fully-verified. It may be an edge of S but it may also be only a segment of a larger edge.
Set V: The set V is a sequence of vertices in H such that each pair of successive vertices forms a verified edge of H. More formally, V = (p0, p 1, p2, ..., pm-1, pm) where pi is a vertex of H and m >= 0. Moreover, the edge [pi-1, pi ] is verified for each i from 1 to m. In other words, consider a sequence of contiguous verified edges starting at p0 and ending at pm: the set V contains all the vertices in this sequence of edges. Initially V contains only p0 since no edge is verified. In the end, V should contain all the vertices of S and have p0 = pm.

The following diagrams illustrate these terms. The same graphical notation will be used in the rest of the diagrams of this section.

 

Intuition

Algorithm