Ray shooting in polygons using geodesic triangulations
Ray shooting in polygons using geodesic triangulations
复制标题
使用测地线三角测量在多边形中进行射线射击
DOI：
10.1007/bf01377183
复制
发表时间：
1991
期刊：
影响因子：
1.1
通讯作者：
J. Snoeyink
中科院分区：
文献类型：
--
作者：
B. Chazelle;H. Edelsbrunner;Michelangelo Grigni;L. Guibas;J. Hershberger;M. Sharir;J. Snoeyink
设P是n个顶点的简单多边形。我们提出了一个简单的分解方案，将P的内部划分为O（n）个所谓的测地线三角形，使得P内部的任何线段最多与这些三角形的2 logn相交。这种分解可以用一种非常简单的方式来预处理P，这样任何射线射击查询都可以在时间O（logn）内得到回答。该数据结构需要O（n）的存储空间和O（nlogn）的预处理时间。通过使用更复杂的技术，我们可以将预处理时间减少到O（n）。我们还扩展我们的一般技术的情况下，射线拍摄amidstk多边形障碍物，共ofn边，使查询可以回答在O（logn）时间。
LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.