The Data Model

Lists are a natural mechanism for representing ordered sets of elements, such as way-points along a route. A list of a route Lr consists of a set of n ordered waypoints {wp1, wp2, …, wpn}. The navigator N travels along the route by moving from waypoint to waypoint. We will use the same data type for both, navigator and waypoints. The data type used has a central point in two-dimensional space (x, y) called pivot, and a circle with radius r around this point, which describes the positional accuracy or the way-points decision area. This data type is conceptually similar to a Spatially Extended Point (SEP) (Lee and Flewelling 2004) except that the region around the pivot is always circular We will use the term Circular Spatially Extended Point (CSEP) to refer to the data type associated with navigator and waypoint (Figure 4).

Figure 4. CSEP Data type for navigator and waypoint.

Topological Relations between a Navigator and a Waypoint

The relation of a navigator’s location to the location of a waypoint can be described qualitatively or quantitatively. A quantitative approach defines different relations based on metric distance thresholds. In order to define these metric thresholds, quali-tative measures are applied and, therefore, we only analyze qualitative, binary, topo-logical relations between a user’s location and a waypoint.

16-Intersection Model

Egenhofer and Herring (1990a, 1990b) formalized the topology of binary relations between two geographic features using point-set topological relations. Lee and Flewelling (2004) further described binary topological relations between a region and a SEP. Here we describe the topological relations between two CSEPs. Any such relation can be described with the 16-intersection model (Equation1). The 4x4-matrix defines the possible topological relations between a navigator A and waypoint B based on their parts, i.e. pivot A• interior A°, boundary A∂ and exterior A¯.

Theoretically, the 16-intersection matrix can have 162 possible combinations of empty (Ø) and non-empty (¬Ø) fields. The top left three columns and rows, however, describe the intersections between the two circles around each pivot, resulting in only eight possible topological relations (Egenhofer and Herring, 1990b). Further, a pivot is a one-dimensional geometric object and, therefore, can intersect only one other element (exterior, boundary, or interior) at once. These constraints in addition to the constraints given by the data type lead to 26 possible topological relations between two CSEPs (Figure 5).

Figure 5. 26 possible topological relations between two CSEPs ordered by the topological relation between the two circles around their pivot.