DIMACS TR: 93-56

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

Authors: John Hershberger and Subhash Suri


We propose a very simple ray shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multi-connected polygon with k components and n vertices, so that a ray intersects at most O(\sqrt{k} log n) triangles.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-56.ps
DIMACS Home Page