Implementation aspects

First we introduce the following definitions:

polyline

- a line of multiple connected straight segments,

polygon

- a closed polyline (first and last coordinate of the polyline are equal).

For testing if two points are at the same side of a given boundary, we use the line-of-sight test (fig. B.2).

Figure B.2: Line-of-sight test

An (imaginary) segment goes from the estimation point to each data point in question. If the number of segment intersections is even, then both points are supposed to be at the same side of the boundary, if the number of intersections is odd, they are separated by the boundary.

In this example, the line -1 has 0 intersections with the edge, the lines -2 and -3 have only one intersection and the line -4 has two intersections with the edge. So the data points 1 and 4 are assumed to be at the same side of the edge as the estimation point.

There are some special cases in the test, like:

1.

an estimation point or a data point lies on the edge

2.

the segment goes exactly through a vertex of the edge (fig. B.3)

Figure B.3: Special case: the segment goes exactly through a vertex of the edge

In the first case, the edge is completely ignored. In the second case, the intersection of the segment does not count and testing will be continued.

The results of the test depend heavily on the topological connectivity of edges (cf. fig. B.4).

Figure B.4: Different results of line-of-sight test

Here at the left subfigure (boundaries are slightly shifted for better overview) both points are connected, whereas in the right subfigure, the points are disconnected by both line segments.

The line-of-sight test does not work for more complicated cases, for instance in case of spiral boundaries (fig. B.5).

Figure B.5: Line-of-sight test does not work in case of spiral edges

Here the line-of-sight test gives wrong results. Point 1 is actually at the same side as the estimation point and point 2 is at another side.

Concerning the question of finding the shortest path between two points (see section B.6), we are looking for the complete solution of this problem. For now, the line-of-sight test should sufficiently work in most of the usual cases.

For point-in-polygon test of points we have used the InPoly routine, which is a part of the code in [19].

InPoly test is written by Joseph O'Rourke, contributions by Min Xu, June 1997.

For a given point it can define, if the point

• lies strictly inside or outside of a polygon,
• is a vertex of a polygon,
• lies exactly at the edge between vertexes.