# About the Point Location Problem

José Poveda (University of Texas, USA) and Michael Gould (Universitat Jaume I, Spain)
DOI: 10.4018/978-1-59140-995-3.ch013

## 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.
Chapter Preview
Top

## Point 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.

Figure 1.

Ray-crossings algorithm

## 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.

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.

## Complete Chapter List

Search this Book:
Reset
Chapter 1
Jose E. Córcoles, Pascual González
\$37.50
Chapter 2
Jose E. Córcoles, Pascual González
\$37.50
Chapter 3
Michael Vassilakopoulos, Antonio Corral, Boris Rachev, Irena Valova, Mariana Stoeva
\$37.50
Chapter 4
Patrik Skogster
\$37.50
Chapter 5
Carlos Granell, Michael Gould, Miguel Ángel Manso, Miguel Ángel Bernabé
\$37.50
Chapter 6
\$37.50
Chapter 7
Hervé Gontran
\$37.50
Chapter 8
Cognitive Maps  (pages 58-64)
Stephen Hirtle
\$37.50
Chapter 9
Map Overlay Problem  (pages 65-72)
Maikel Garma de la Osa, Yissell Arias Sánchez
\$37.50
Chapter 10
Mahbubur R. Meenar, John A. Sorrentino
\$37.50
Chapter 11
Yurai Núñez-Rodríguez
\$37.50
Chapter 12
Eric Delmelle, Raymond Dezzani
\$37.50
Chapter 13
José Poveda, Michael Gould
\$37.50
Chapter 14
\$37.50
Chapter 15
Network Modeling  (pages 113-121)
Kevin M. Curtin
\$37.50
Chapter 16
Xiaojun Yang
\$37.50
Chapter 17
Spatial Interpolation  (pages 129-136)
Xiaojun Yang
\$37.50
Chapter 18
Bo Huang, Magesh Chandramouli
\$37.50
Chapter 19
May Yuan
\$37.50
\$37.50
Chapter 21
Matthew Perry, Amit Sheth, Ismailcem Budak Arpinar, Farshad Hakimpour
\$37.50
Chapter 22
Yuqi Bai, Liping Di, Aijun Chen, Yang Liu, Yaxing Wei
\$37.50
Chapter 23
Peisheng Zhao, Liping Di, Wenli Yang, Genong Yu, Peng Yue
\$37.50
Chapter 24
Carlos Granell, Michael Gould, Miguel Ángel Esbrí
\$37.50
Chapter 25
Genong Yu, Liping Di, Wenli Yang, Peisheng Zhao, Peng Yue
\$37.50
Chapter 26
Peng Yue, Liping Di, Wenli Yang, Genong Yu, Peisheng Zhao
\$37.50
Chapter 27
Aijun Chen, Liping Di, Yuqi Bai, Yaxing Wei
\$37.50
Chapter 28
Yaxing Wei, Liping Di, Guangxuan Liao, Baohua Zhao, Aijun Chen, Yuqi Bai
\$37.50
Chapter 29
Alexander Klippel, Kai-Florian Richter, Stefan Hansen
\$37.50
Chapter 30
Péter Hegedüs, Mihály Orosz, Gábor Hosszú, Ferenc Kovács
\$37.50
Chapter 31
Routing  (pages 246-253)
Kevin M. Curtin
\$37.50
Chapter 32
Location Privacy  (pages 254-259)
Matt Duckham
\$37.50
Chapter 33
\$37.50
Chapter 34
Henrik Hanke, Alf Neumann
\$37.50
Chapter 35
Coupling GPS and GIS  (pages 277-284)
Mahbubur R. Meenar, John A. Sorrentino, Sharmin Yesmin
\$37.50
Chapter 36
Wei-Shinn Ku, Haojun Wang, Roger Zimmermann
\$37.50
Chapter 37
\$37.50
Chapter 38
Mohammed A. Quddus
\$37.50
Chapter 39
Andrés Pazos, José Poveda, Michael Gould
\$37.50
Chapter 40
Magesh Chandramouli, Bo Huang
\$37.50
Chapter 41
Iftikhar U. Sikder
\$37.50
Chapter 42
Arianna D’Ulizia, Fernando Ferri, Patrizia Grifoni
\$37.50
Chapter 43
Lionel Savary, Georges Gardarin, Karine Zeitouni
\$37.50
Chapter 44
Lyn Kathlene
\$37.50
Chapter 45
Edward Mac Gillavry
\$37.50
Chapter 46
Iftikhar U. Sikder, Santosh K. Misra
\$37.50
Chapter 47
George Kakaletris, Dimitris Varoutas, Dimitris Katsianis, Thomas Sphicopoulos
\$37.50
Chapter 48
Stelios C.A. Thomopoulos, Nikolaos Argyreas
\$37.50