Abstract
In this chapter we present some well-known algorithms for the solution of the point location problem and for the more particular problem of point-in-polygon determination. These previous approaches to the problem are presented in the first sections. In the remainder of the paper, we present a quick location algorithm based on a quaternary partition of the space, as well as its associated computational cost.
TopPoint Location Problems In Simple Cases
Several algorithms are available to determine whether a point lies within a polygon or not. One of the more universal algorithms is counting ray crossings, which is suitable for any simple polygons with or without holes. The basic idea of the counting ray crossings algorithm is as follows:
Let L be the scan-line crossing the given point, Lcross is the number of left-edge/ray crossings and Rcross is the number of right-edge/ray crossings. First, we need to determine whether the given point is a vertex of the polygon or not; if not, we calculate Lcross and Rcross. If the parities of Lcross and Rcross are different (Figure 1 case B) then this point lies on the edge of the polygon. Otherwise, if Lcross (or Rcross) is an odd number (Figure 1 case A), the point must lie inside the polygon. If Lcross (or Rcross) is an even number (cases C, D, E), the point must lie outside the polygon.
Key Terms in this Chapter
Convex: Pertaining to a region or shape, such as a polygon, for which a straight line segment between any two points of the region is entirely contained within the region. Contrast with concave.
EDGE: For a polyline in a space of dimension n, each line between two vertexes.
Coordinate Systems: A particular kind of reference frame or system, such as plane rectangular coordinates or spherical coordinates, which use linear or angular quantities to designate the position of points within that particular reference frame or system.
Polyline: A set of coordinate points connected by a set of line segments. In programming, geometric objects as for instance: polylines, points, lines, etc are defined in an Application Programming Interface (API) as primitives with graphical output.
Quadtree: A data structure used, among other uses, to reduce the storage requirements of a raster by coding contiguous homogenous areas singly. A raster of 2n by 2n cells is recursively divided into four equal squares. Subdivision continues in each square until the square is homogeneous or subdivision is no longer possible or in general the final condition is reached.
Data Structure: (Data schema) The organization in memory of data, and, in particular, the reference linkages among data elements.
Vertex: The location at which vectors and polygon faces or edges intersect. The vertices of an object are used in transformation algorithms to describe the object’s location and its location in relation to other objects.
Point in Polygon: In a general formulation, the ability to superimpose a set of points on a set of polygons and determine which polygons (if any) contain each point.
Quadrilateral: A closed polygon with four vertices, and thus four sides. Quadrilaterals, or quads, can be planar, in which case all vertices lie on the same plane, or non-planar. With non-planar quadrilaterals (sometimes called bow ties, because of their shape), it is more difficult to calculate orientation and lighting, and thus many systems tessellate quads to triangles, which are definitively planar.
Quad-Tree: An abbreviation for quadrilateral tree.
Polygon: A planar shape created by a set of connected line segments (or vectors) that form vertices at their meeting points. Note that an n-gon is a polygon with an undetermined number of sides.