Information Gained By Probing ::

Classification of Points

The outcome of a probe will be used to classify each point in the plane into one of the following three sets.

Inside: The points in this set are known to be inside the shape.
Outside:  The points in this set are known to be outside the shape.
Maybe: The points in this set may or may not be part of the shape. The information available is insufficient to make a decision.

As we probe the shape, our goal in to reduce the uncertainty. In other words, we wish to reduce the size of the maybe set and increase the size of both the inside and the outside sets. Initially the maybe set contains all the points and the other two sets are empty. Ultimately we wish for the maybe set to be empty so that there is no uncertainty about the shape.

The following figure shows the legend that is used for the the diagrams in this section and often in the following sections. The inside, maybe and outside regions are shown in black, gray and white respectively. Contact points are shown as red dots. Probes are shown as blue arrows.

The convex hull of the contact point is shown as a red polygon with dotted lines. The convex hull can be visualized as a rubber band enclosing all the points in a set. More formally the convex hull is the smallest convex polygon enclosing all the points in a set [2]. More information about the convex hull can be obtained here. As we will soon see, much information can be learned from the convex hull of the contact points.

The following conventions will be follow in this section:


Information Gained by Probing

Contact Points Define the Inside Set