A point-in-polygon method based on a quasi-closest point

This paper presents a numerically stable solution to a point-in-polygon problem by combining the orientation method and the uniform subdivision technique. We define first a quasi-closest point that can be locally found through the uniform subdivision cells, and then we provide the criteria for deter...

Full description

Saved in:
Bibliographic Details
Published in:Computers & geosciences 2010-02, Vol.36 (2), p.205-213
Main Authors: Yang, Sheng, Yong, Jun-Hai, Sun, Jiaguang, Gu, Hejin, Paul, Jean-Claude
Format: Article
Language:English
Subjects:
Closest point
Computer Science
Computer simulation
Criteria
Earth sciences
Earth, ocean, space
Exact sciences and technology
Graphics
Inclusions
Mathematical models
Orientation
Point-in-polygon
Polygons
Robustness
Singularities
Subdivisions
Uniform subdivision
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a numerically stable solution to a point-in-polygon problem by combining the orientation method and the uniform subdivision technique. We define first a quasi-closest point that can be locally found through the uniform subdivision cells, and then we provide the criteria for determining whether a point lies inside a polygon according to the quasi-closest point. For a large number of points to be tested against the same polygon, the criteria are employed to determine the inclusion property of an empty cell as well as a test point. The experimental tests show that the new method resolves the singularity of a test point on an edge without loss of efficiency. The GIS case study also demonstrates the capability of the method to identify which region contains a test point in a map.
ISSN:0098-3004
1873-7803
DOI:10.1016/j.cageo.2009.06.008