Point-in-polygon tests for geometric buffers
The point-in-polygon problem is often encountered in geographical information systems. The algorithms usually work on polygons defined by straight edges. In some situations, however, polygons containing circular arcs are applied. In geographical information systems these polygons are usually considered as geometric buffers, geodesic offsets, or geodesic parallels. This paper presents three algorithms suitable for providing information about the containment of a point in geometric buffers: the Ray-crossing method, the Cell-Based Algorithm and the Approximate approach. An extensive experimental section allows the reader to select the most efficient algorithm for practical problems. (C) 2005 Elsevier Ltd. All rights reserved.
geometric buffer geographical information systems circular arcs geodesic parallel containment test uniform plane subdivision computational geometry