Explaining Algorithms Using Metaphors by Michal Forišek & Monika Steinová

Author:Michal Forišek & Monika Steinová
Language: eng
Format: epub
Publisher: Springer London, London

3.3 Winding Number

3.3.1 Overview

In this section and the next one we will be dealing with polygons and polylines.

A closed polyline is a polyline that starts and ends in the same point. Sometimes, we will assign direction to a polyline. Then, a closed polyline can be seen as a sequence of directed line segments such that each segment starts where the previous one ends, and the last segment ends where the first one started.

A polygon is a closed polyline that never touches or intersects itself. The word “polygon” is also used for the entire area enclosed inside such a polyline, including the boundary. (The intended meaning will always be clear from the context.)

We will consider another traditional problem in two-dimensional computational geometry: testing whether a given point is contained in a given polygon.

Point in polygon inclusion test Instance: A point and a polygon (in a two-dimensional plane). Problem: Check whether the point lies inside, on the boundary, or outside of the polygon.

Checking whether a point lies on the boundary of a polygon can easily be done in linear time: for each side, check whether it contains the point. Below, we shall assume that this test has already been made and that the outcome was negative. That is, the given point is either strictly inside, or strictly outside the polygon.

The canonical solution that distinguishes between those two cases is the “ray casting” algorithm: Pick any ray (i.e., a half-line) starting at the given point. Count the number of times it crosses the polygon boundary. If this number is odd, the point is inside, otherwise it is outside the polygon.

While the idea behind this solution is simple and its correctness obvious, there is a reason we do not really like it: the implementation has too many special cases. Note that we are not counting the number of intersections between the ray and the polygon. In some cases, such an intersection counts as crossing the boundary, in others it does not, and in yet other cases there can even be an infinite number of intersections. Some of the tricky cases are shown in Fig. 3.15. In fact, even the original publication of the algorithm [14] contains a bug [9].

Fig. 3.15Some of the special cases in the ray casting algorithm: We are checking whether lies inside the polygon. At the ray crosses an edge to get out of the polygon. At the ray hits a vertex and reenters the polygon. At the ray hits another vertex, but this time it stays inside the polygon. Between and the ray even goes along polygon boundary, before finally leaving the polygon

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.