Main Page

The first step consists of probing the shape on two orthogonal lines from all four directions. Remember that the shape contains the origin. We are thus guaranteed to hit four distinct points by aiming towards the origin. The initial current hull H has four vertices. The shape is not empty and contains the origin so none of the vertex triplets are colinear. As a result all edges are initially unverified and V contains only the starting point p₀. The following figure illustrates the result of the initialization phase. See the previous section for the legend.

Remember that V contains a sequence of m points such that all edges including [p_m-1, p_m] are verified. Once the setup is completed, the algorithm repeatedly tries to extend the set V by verifying the next unverified edge [p_m, p_m+1]. The first iteration, for example, tries to verify the unverified edge [p₀,p₁]. An unverified edge is probed using the method described in the intuition section. Let's explain the method again, this time using the appropriate vocabulary that we defined in the previous section.

Consider the situation in the following diagram. The edge [a,b] is the last verified edge in the sequence V. We wish to verify the next edge, namely edge [b,c]. The edges [a,b] and [c,d] are first extended in the direction of the edge [b,c] until they meet at some point x. The probe is sent in the direction from point x to a point on the edge [b,c] such that the probe bisects the angle bxc. This choice of angle is not critical but is reasonable since the probe should be aimed to reduce uncertainty as much as possible.

Outcome 1 This case occurs when the probe hits the point x. This extends and verifies the edge [a,b] to [a,x] and the edge [d,c] to [d,x]. As a result the point b is no longer necessary in V and points x and d must be added. Similarly, point x must be added to the current hull H and points b and c must be removed because they are no longer vertices. The next step is to verify the edge [d,e] where e is the vertex following d.
*Outcome 2* This case occurs when the probe hits the edge [b,c] at point x'. This verifies the edge [b,c] and the point c must be added to V. The current hull H doesn't change. The next step is to verify the edge [c,d].
*Outcome 3* This case occurs when the contact point is somewhere else in the bcx triangle. The current hull H is extended to include the new point x''. The set V doesn't change. The next step is to repeat this operation at the new unverified edge [b,x''].

As explained in intuition, the orientation of the edges [a,b] and [c,d] may be such that they never join at a point x. In such a case the probe is sent in the direction of the edge [b,c] resulting either in the second or third outcomes as shown above.

Notice that at each iteration, either the current hull is extended (outcome 3) or the set V is extended (outcomes 1 and 2). In other words, we either add an unverified edges or verify an edge.

The iterations are repeated until there is no unverified edge. At that point, the set V has been extended so that it forms a closed polygon (p₀ = p_m).

Algorithm