標題: On the complexity of point-in-polygon algorithms
作者: Huang, CW
Shih, TY
交大名義發表
土木工程學系
National Chiao Tung University
Department of Civil Engineering
關鍵字: point-in-polygon;complexity;ray intersection;sum of angles method;swath method;sign of offset method
公開日期: 1-二月-1997
摘要: 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. (C) 1997 Elsevier Science Ltd.
URI: http://hdl.handle.net/11536/749
ISSN: 0098-3004
期刊: COMPUTERS & GEOSCIENCES
Volume: 23
Issue: 1
起始頁: 109
結束頁: 118
顯示於類別:期刊論文


文件中的檔案:

  1. A1997WM15100010.pdf