On the complexity of point-in-polygon algorithms

Chong Wei Huang*, Tian-Yuan Shih

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

71 Scopus citations


Point-in-polygon is one of the fundamental operations of Geographic Information Systems. A number of algorithms can be applied. Different algorithms lead to different running efficiencies. In the study, the complexities of eight point-in-polygon algorithms were analyzed. General and specific examples are studied. In the general example, an unlimited number of nodes are assumed; whereas in the second example, eight nodes are specified. For convex polygons, the sum of area method, the sign of offset method, and the orientation method is well suited for a single point query. For possibly concave polygons, the ray intersection method and the swath method should be selected. For eight node polygons, the ray intersection method with bounding rectangles is faster.

Original languageEnglish
Pages (from-to)109-118
Number of pages10
JournalComputers and Geosciences
Issue number1
StatePublished - 1 Jan 1997


  • Complexity
  • Point-in-polygon
  • Ray intersection
  • Sign of offset method
  • Sum of angles method
  • Swath method


Dive into the research topics of 'On the complexity of point-in-polygon algorithms'. Together they form a unique fingerprint.

Cite this