DIMACS TR: 93-56
A Pedestrian Approach to Ray Shooting: Shoot a Ray,
Take a Walk
Authors: John Hershberger and Subhash Suri
ABSTRACT
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