A pedestrian approach to ray shooting: shoot a ray, take a walk
A pedestrian approach to ray shooting: shoot a ray, take a walk
复制标题
行人进行射线射击的方法：射击射线，散步
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
S. Suri
中科院分区：
文献类型：
--
作者：
J. Hershberger;S. Suri
我们提出了一种非常简单的射线射击算法，只有数据结构是三角形的。到达纸的关键结果是一个简单的多边形的施泰纳三角剖分，射线最多可以在到达多边形边界之前与射线最多可以相交的o（log n）三角形。我们能够使用O（n/log n）处理器在线性顺序时间中计算这种三角剖分，或者在o（log n）并行时间中提供了简单而最佳的射线射击算法我们可以将三角剖分程序扩展到具有k个组件和n个顶点的多边形多边形的技术，因此射线最多在O（√κlog n）三角形上相交。
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(√κ log n) triangles. © 1995 Academic Press, Inc.