Phase 2: Verification

In this second phase the set of verified edge vertices V is re-introduced. The set V = (p₀,p₁,...,p_m) contains a sequence of vertices such that each pair of consecutive points in the set are such that the edge between them is verified. At first the input to this phase is the result of the first phase thus V contains either two or three points. This verification phase will also be re-used as part of the third phase.

The goal of this phase is to verify the end points of the set V, namely p₀ and p_m. Here the definition of verified vertex is slightly more general than that used previously. A verified vertex is a vertex that is known to be a vertex of the shape S. Verifying a vertex of a semi-verified edge of H is simple. Consider the verification of the vertex p_m. The edge [p_m-1,p_m] is verified which means that it is part of a true edge of the shape S but that the edge of S may be longer. In this phase we send a probe towards p_m in the direction of the edge [p_m-1, p_m]. The point at which the probe makes contact gives the extent of the edge in S and thus a vertex of S. This new vertex is by consequence a verified vertex. This phase is illustrated in the following diagrams. Notice that the new verified vertex u replaces p_m in V.

There are two additional special cases. The first one is when p_m=u, in other words when p_m is a true vertex of the shape S. This situation is highly unlikely so Cole and Yap assume that p_m is 'infinitesimally displaced' so that p_m is never equal to u. The other special case is when u is colinear with an unverified edge of the current hull H. When this happens, a new semi-verified edge is added. The second phase must be repeated for the new unverified phase. Consider following example.

This verification process is executed for both end points in the set V, namely p₀ and p_m. The process is repeated until the verification doesn't generate new semi-verified edges. It is interesting to note that if the contact point u is above the x-axis then there can be no colinear unverified edges. Thus this process must halt before verifying the entire shape S. Note also that once this process is finished all the points contained in V are verified vertices.

Phase 1: Initialization

Phase 3: Extension