A PEDESTRIAN APPROACH TO RAY SHOOTING - SHOOT A RAY, TAKE A WALK

We propose a very simple ray-shooting algorithm, whose only data struc ture is a triangulation. The query algorithm, after locating the trian gle containing the origin of the ray, walks along the ray, advancing f rom one triangle to a neighboring one until the polygon boundary is re ached. The key result of the paper is a Steiner triangulation of a sim ple polygon with the property that a ray can intersect at most O(log n ) triangles before reaching the polygon boundary. We are able to compu te such a triangulation in linear sequential time, or in O(log n) para llel time using O(n/log n) processors. This gives a simple, yet optima l, ray-shooting algorithm for a simple polygon. Using a well-known tec hnique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(root k log n) triangles. (C) 1995 Academic Press, Inc.