SLICING AN EAR USING PRUNE-AND-SEARCH
SLICING AN EAR USING PRUNE-AND-SEARCH
复制标题
DOI：
10.1016/0167-8655(93)90141-y
复制
发表时间：
1993-09-01
影响因子：
5.1
通讯作者：
TOUSSAINT, G
中科院分区：
文献类型：
--
作者：
ELGINDY, H;EVERETT, H;TOUSSAINT, G
众所周知，简单多边形 P 的对角线可以通过简单且实用有效的算法在线性时间内找到。 P 的耳朵是一个三角形，其一条边是 P 的对角线，其余两条边是 P 的边。通过首先对 P 进行三角剖分，然后搜索三角剖分，可以很容易地找到 P 的耳朵。然而，尽管可以在线性时间内对多边形进行三角剖分，但这种过程在概念上很困难并且实际上效率不高。在这篇文章中，我们展示了可以通过一种简单、实用且高效的算法在线性时间内找到 P 的耳朵，该算法不需要对 P 进行预三角测量。
It is well known that a diagonal of a simple polygon P can be found in linear time with a simple and practically efficient algorithm. An ear of P is a triangle such that one of its edges is a diagonal of P and the remaining two edges are edges of P. An ear of P can easily be found by first triangulating P and subsequently searching the triangulation. However, although a polygon can be triangulated in linear time, such a procedure is conceptually difficult and not practically efficient. In this note we show that an ear of P can be found in linear time with a simple, practically efficient algorithm that does not require pre-triangulating P.