Ray Shooting in Polygons Using Geodesic Triangulations
Report ID: TR-350-91Author: Grigni, Michelangelo / Chazelle, Bernard / Edelsbrunner, Herbert / Guibas, Leonidas / Hershberger, John / Sharir, Micha / Snoeyink, Jack
Date: 1991-09-00
Pages: 16
Download Formats: |PDF|
Abstract:
Let $P$ be a simple polygon with $n$ vertices. We present a simple decomposition scheme that partitions the interior of $P$ into $O(n)$ so-called geodesic triangles, so that any line segment interior to $P$ crosses at most 2 log $n$ of these triangles. This decomposition can be used to preprocess $P$ in a very simple manner, so that any ray-shooting query can be answered in time $O(log^n)$. The data structure required $O(n)$ storage and $O(n$ log $n)$ preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time to $O(n)$. We also extend our general technique to the case of ray-shooting amidst $k$ polygonal obstacles with a total of $n$ edges, so that a query can be answered in $O( sqrt k$ log $n$) time.
- This technical report has been published as
- Ray Shooting in Polygons Using Geodesic Triangulations. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink, Algorithmica, 12, 1994, pp. 54-68.