耳切法多岛洞画面

最新推荐文章于 2024-11-05 17:03:43 发布

置顶 JayW就是我

最新推荐文章于 2024-11-05 17:03:43 发布

阅读量283

点赞数

分类专栏：算法

本文链接：https://blog.csdn.net/qq_33994566/article/details/101532487

版权

算法专栏收录该内容

7 篇文章

订阅专栏

算法文档地址：英文版、中文翻译博客

多岛洞简介介绍如下：

Search the inner polygon for vertexMof maximumx-value.
Intersect the rayM+t(1,0) with all directed edges〈Vi,Vi+1〉of the outer polygon for which M is to the left of the line containing the edge (M is inside the outer polygon). Let I be the closest visible point to M on this ray.
If I is a vertex of the outer polygon, then M and I are mutually visible and the algorithm terminates.
Otherwise,I is an interior point of the edge〈Vi,Vi+1〉. Select P to be the endpoint of maximumx-valuefor this edge.
Search the reflex vertices of the outer polygon (not including P if it happens to be reflex). If all of thesevertices are strictly outside triangle〈M,I,P〉, then MandPare mutually visible and the algorithmterminates.
Otherwise, at least one reflex vertex lies in〈M,I,P〉. Search for the reflexRthat minimizes the anglebetween (1,0) and the line segment〈M,R〉. ThenMandRare mutually visible and the algorithmterminates. It is possible in this step that there are multiple reflex vertices that minimize the angle,in which case all of them lie on a ray withMas the origin. Choose the reflex vertex on this ray that is closest to M.

在第六步中算法告诉我们在组成的封闭三角区域〈M,I,P〉内寻找其他的顶点，如果有顶点，就去比较这些顶点和M点组成的方向向量和（1,0）的夹角，取夹角最小的。这里他少说了一种情况，那就是当闭合区域内有多个重复的顶点，我们需要选择排序靠后的顶点。所以我们在比较角度的时候是从后面的索引来比较的。这种情况多见于内部有多个岛洞。