A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk |
| |
| Authors: | Hershberger J Suri S |
| |
| Institution: | 1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China;2. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208, USA;3. Department of Computer Science, Brown University, Providence, RI 02912, USA;4. Department of Electrical and Computer Engineering, University of Illinois at Chicago, Chicago, IL 60607, USA;1. Laboratory of Anatomy-Histology-Embryology, School of Medicine, University of Crete, Heraklion, Greece;2. Laboratory of Cell Proliferation and Ageing, Institute of Biology, National Center of Scientific Research “Demokritos”, Athens, Greece;3. Biochemistry, Biochemical Analysis and Matrix Pathobiology Res. Group, Laboratory of Biochemistry, Department of Chemistry, University of Patras, 26110 Patras, Greece |
| |
| 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 multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
