论文标题
计算直线线障碍物的骨骼
Computing skeletons for rectilinearly-convex obstacles in the rectilinear plane
论文作者
论文摘要
我们介绍了障碍骨架的概念，该障碍物是多边形障碍物内部的一组线段$ω$，可以代替$ω$在飞机上进行避免障碍物网络问题的相交测试时。与原始障碍物边界中的线段数量相比，骨架的线段可能会大大减少，因此在骨骼（而不是原始障碍物）上进行相交测试可以大大减少算法为避免障碍问题计算解决方案所需的CPU时间。最小骨骼是一个可能数量最少的线段段的骨骼。我们提供了一个精确的$ O（n^2）$算法，用于计算直线平面的直线障碍物的最小骨架，该直线平面是直线式连接的。我们表明，与原始障碍物边界中的边数相比，最小骨骼中的边数通常很少，它通过对最多1000个顶点的随机直线线障碍物进行随机直接直线式障碍物进行实验。
We introduce the concept of an obstacle skeleton which is a set of line segments inside a polygonal obstacle $ω$ that can be used in place of $ω$ when performing intersection tests for obstacle-avoiding network problems in the plane. A skeleton can have significantly fewer line segments compared to the number of line segments in the boundary of the original obstacle, and therefore performing intersection tests on a skeleton (rather than the original obstacle) can significantly reduce the CPU time required by algorithms for computing solutions to obstacle-avoidance problems. A minimum skeleton is a skeleton with the smallest possible number of line segments. We provide an exact $O(n^2)$ algorithm for computing minimum skeletons for rectilinear obstacles in the rectilinear plane that are rectilinearly-convex. We show that the number of edges in a minimum skeleton is generally very small compared to the number of edges in the boundary of the original obstacle, by performing experiments on random rectilinearly-convex obstacles with up to 1000 vertices.
