Phase 3: Extension

The third phase consists of extending the set V by probing until the entire shape S has been found. To do so we will define three properties and prove that these hold at the beginning of phase 3 and are maintained until the end of the algorithm.

The first and third properties has been shown to hold at the end of the second phase. The second property can be shown to hold as follows. Note that the semi-verified edge(s) of phase 1 have a single internal contact point. The second phase adds a single contact point, the verified vertex. The total number of internal contact points is thus two. The only exception is the first semi-verified edge. Imagine that first phase finds a single verified edge. That edge has two unverified vertices and an internal contact point. The verification process adds a verified vertex on each side, resulting in three internal contact points. Thus the three properties hold at the beginning of this phase.

The third phase proceeds to verify an unverified edge adjacent to the set of verified edges with vertices in V. The method used is the same as in phase 1 and as in the original algorithm. The goal is thus to extend the set V. As usual there are three possible outcomes:

1. The probe hits somewhere inside the 'triangle'. The current hull H is extended but V stays the same. The three properties still hold.

2. The probe hits the unverified edge or the apex of the triangle and creates a semi-verified edge which breaks property 1. The algorithm applies the verification algorithm of the second phase and restores the first property.

3. The probe creates a fully verified edge. This occurs only when 'closing' the shape S by probing between p₀ and p_m. The probe hits the edge between p₀ and p_m and thus creates a closed polygon. This signals the end of the algorithm. The set V contains all the vertices of the shape S. The algorithm halts at this point. (Note that property 3 is broken at this point.)

Phase 2: Verification

Conclusion