On the complexity of point-in-polygon algorithms

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

1997-02-01

類型

期刊名稱

COMPUTERS & GEOSCIENCES

卷期與頁次

第 23 卷,頁 109–118

ISSN

0098-3004

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Huang, C., & Shih, T. (1997). On the complexity of point-in-polygon algorithms. COMPUTERS & GEOSCIENCES, 23, 109–118. https://doi.org/10.1016/S0098-3004(96)00071-4

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/149452