ON THE COMPLEXITY OF POINT-IN-POLYGON ALGORITHMS

Point-in-polygon is one of the fundamental operations of Geographic In formation Systems. A number of algorithms can be applied. Different al gorithms lead to different running efficiencies. In the study, the com plexities of eight point-in-polygon algorithms were analyzed. General and specific examples are studied. In the general example, an unlimite d number of nodes are assumed; whereas in the second example, eight no des are specified. For convex polygons, the sum of area method, the si gn of offset method, and the orientation method is well suited for a s ingle point query. For possibly concave polygons, the ray intersection method and the swath method should be selected. For eight node polygo ns, the ray intersection method with bounding rectangles is faster. (C ) 1997 Elsevier Science Ltd.