三维三角剖分凸包的顶点得到后 ，怎么得到包络线

一种常见的方法是通过将凸包的所有边按照极角排序，然后按照排序后的顺序遍历所有的边。在遍历每条边时，将该边与前一条边和后一条边的法向量进行叉积，以此得到该边对应的平面法向量。然后，检查该边对应的平面法向量是否指向凸包外部，如果是，则该边对应的两个顶点即为包络线上的点。

具体步骤如下：

1. 将凸包的所有边按照极角排序。

2. 遍历所有的边，对于每条边，计算它与前一条边和后一条边的法向量，以此得到该边对应的平面法向量。

3. 检查该边对应的平面法向量是否指向凸包外部，如果是，则该边对应的两个顶点即为包络线上的点。

4. 将所有包络线上的点按照顺序连接起来，即可得到凸包的包络线。

需要注意的是，对于存在共面点的情况，可能会出现多个包络线的情况。此时需要进行一些额外的处理，例如将所有的包络线都找出来，然后对它们进行合并或者选择其中一个作为最终的包络线。

相关问题

cgal 3D三角剖分

CGAL是计算几何算法库的缩写，它提供了许多用于处理和操作几何数据结构的算法和数据结构。在CGAL中，3D三角剖分是一种用于将三维空间中的点集划分为三角形面片的方法。根据引用中所述，CGAL的3D三角剖分基于四面体结构。每个四面体包含四个顶点，其中一个顶点是一个辅助顶点，称为无限顶点，用于处理无界单元。通过这种方式，每个面片对应两个四面体，同时可以处理凸包边界上的特殊情况。请注意，无限顶点没有具体的坐标意义，也没有几何谓词可以应用于它。你可以在引用提供的链接中了解更多关于CGAL 3D三角剖分的详细信息。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [CGAL 二维三角剖分](https://blog.csdn.net/dayuhaitang1/article/details/128783294)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [CGAL 三维三角剖分](https://blog.csdn.net/dayuhaitang1/article/details/128881509)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

画出Delaunay三角剖分算法的流程图

### 回答1：
很抱歉，作为语言模型，我无法直接画图。但是，我可以为您描述Delaunay三角剖分算法的流程，希望可以帮助到您。

Delaunay三角剖分算法流程：

1. 对给定的点集进行排序，以便于后续处理。

2. 选取一个超级三角形包含所有的点，使其成为三角剖分的初始三角形。

3. 将每个点依次插入到三角剖分中，每次插入一个点，找到其在三角剖分中所属的三角形。

4. 对该三角形进行Delaunay检查，即判断该三角形是否满足Delaunay条件，若不满足则进行翻转操作。

5. 将新点与三角形共同构成新的三角形，并将该三角形加入到三角剖分中。

6. 重复步骤3-5，直到所有点都被插入到三角剖分中。

7. 删除超级三角形及与其相关的三角形，得到最终的Delaunay三角剖分结果。

注意：在Delaunay检查和翻转操作中，需要用到计算几何相关的知识，如计算三角形外接圆心、判断点是否在三角形内等。

### 回答2：
Delaunay 三角剖分算法是一种用于将二维点集进行三角剖分的算法。下面是Delaunay 三角剖分算法的简单流程图：

1. 输入二维点集P，求解包围P的凸包C。
2. 在凸包C上构建一个超级三角形T，该超级三角形包含所有的点P。
3. 将超级三角形T加入到一个三角形数组中。
4. 遍历点集P中的每一个点p：
4.1 找到包含点p的三角形t。
4.2 将点p与三角形t的三个顶点连接，得到三条边，将这些边上没有形成其它三角形的点的边形成连接的边组成的三角形删除。
4.3 将点p与连接的边形成的三角形加入三角形数组。
5. 遍历三角形数组中的每一个三角形t：
5.1 如果三角形t的顶点包含在超级三角形T中，则删除三角形t。
6. 返回剩余的三角形数组作为最终的三角剖分结果。

这个算法的核心思想是通过不断地连接点和边来构建最终的三角剖分，保证剖分的三角形都满足Delaunay 三角剖分的性质，即任意一个三角形的外接圆不包含任何其他点。最终的三角剖分结果是一组无重叠的三角形，用于分析和处理二维点集。

### 回答3：
Delaunay三角剖分算法的流程图如下：

1. 输入待剖分的点集P。
2. 构建超级三角形（Super Triangle）：在点集P的外部选取一个大三角形，确保点集P全部位于这个大三角形的内部。超级三角形的选择不会影响最终的三角剖分结果。
3. 根据点集P和超级三角形，构建一个初始的三角网格，将超级三角形作为初始的剖分之外的三角形。
4. 对P中的每个点进行逐个处理：
1) 找到点p所在的三角形t。
2) 如果p位于t的外接圆内部，那么从t中删除三条边，然后将p与每条边的另外两个顶点连接，构建新的三角形。
3) 如果p位于t的外接圆外部，那么不做任何操作。
5. 循环上述步骤，直到P中的所有点都被处理完毕。
6. 删除超级三角形及其相关的边。
7. 返回剖分得到的三角形结果。

简要说明：
Delaunay三角剖分算法的基本思想是通过不断地将点插入到三角形中并进行局部调整来构建三角剖分。在每次插入一个点时，需要判断它是否位于其所在三角形的外接圆内部，如果是，则删除该三角形的三条边，并连接该点与该边的另外两个顶点构成新的三角形。这个操作称为突变。通过不断地突变操作，最终得到三角剖分结果。

注意事项：
1. 根据具体的应用场景，可能还需针对特定的要求进行额外的处理，例如限制最大和最小角度，或者进行平滑处理等。
2. 在具体的实现中，有多种方法可以选择，例如使用递归或迭代进行突变操作。
3. 流程图只是给出了算法的基本框架，具体的实现可能还需要考虑其他细节。