来自一组边的最外层多边形
Outermost Polygon from a set of Edges
假设我有一组全部相连的二维线段。我需要一种算法来找到集合中最外层的片段。即，限定同一区域的最小子集。
注意：这与查找构成线段的点的凸包不同。
编辑：
顶部是初始的一组段。
下面是删除了内部段的相同轮廓。
（请忽略灰色的小十字，它们只是用来标记交叉点。）
以下是一种从 convex hull 开始然后向内推进的方法。直觉是你从船体上的边缘开始，然后你通过找到最近的点来填充间隙 "along" 沿着你的边缘集中的最短路径填充间隙。
- 计算点的凸包。
- 将外壳集与您的边集相交。这将为您留下一系列可能断开连接的边缘路径。
- 任何没有两条边的点（即，图形术语中的 leaf）通过在原始边集中找到最短路径连接到它最近的叶子。
- 任何连接都可以被一条路径打破，该路径在被船体关闭时面积最小。
给定一个三角非凸多边形，您可以指定顶点遍历的方向（CCW 的顺时针方向）。使所有的三角形都具有相似的导向 WRT 遍历其顶点。将所有三角形分解为有向边。每个三角形的每条边都是两个顶点 (a, b) 的元组。对于每个相邻的三角形，您有两个相反方向的边 (a, b) 和 (b, a)。您可以简单地将这样的一对边从进一步考虑中排除。最后你会得到一组专属的外边。
如果您的多边形由非单纯部分组成（但您仍然可以指定顶点遍历的方向），则不会失去通用性。
源段构造的多边形的三角剖分是明显的步骤：将顶点拉伸到$d + 1$抛物面和三角剖分，然后排除三角形，包含至少一条与任何源段都不匹配的边。
另一种可能的方法稍加修改Gift wrapping algorithm。
你会如何用铅笔做...？
- 找到最左边的顶点（最小x）。如果不止一个，则选择其中最低的（最小 y）。当前下方没有顶点，所以以方向'downwards'为参考
- 找到从当前顶点出发的所有边并计算它们的方向（方位角）。找到与参考方向成最小正角（逆时针）的那个。那将是大纲部分。
- Select 它的另一端作为你的新 'current' 顶点，并将 从那个顶点到最近的 的方向设置为新的参考方向。
- 从第 2 步开始，直到到达起始顶点。
- 删除所有未访问的段。
- 删除所有孤立的顶点（如果在第 5 步中出现的话）。
注意：这与查找构成线段的点的凸包不同。
编辑： 顶部是初始的一组段。 下面是删除了内部段的相同轮廓。 （请忽略灰色的小十字，它们只是用来标记交叉点。）
以下是一种从 convex hull 开始然后向内推进的方法。直觉是你从船体上的边缘开始，然后你通过找到最近的点来填充间隙 "along" 沿着你的边缘集中的最短路径填充间隙。
- 计算点的凸包。
- 将外壳集与您的边集相交。这将为您留下一系列可能断开连接的边缘路径。
- 任何没有两条边的点（即，图形术语中的 leaf）通过在原始边集中找到最短路径连接到它最近的叶子。
- 任何连接都可以被一条路径打破，该路径在被船体关闭时面积最小。
给定一个三角非凸多边形，您可以指定顶点遍历的方向（CCW 的顺时针方向）。使所有的三角形都具有相似的导向 WRT 遍历其顶点。将所有三角形分解为有向边。每个三角形的每条边都是两个顶点 (a, b) 的元组。对于每个相邻的三角形，您有两个相反方向的边 (a, b) 和 (b, a)。您可以简单地将这样的一对边从进一步考虑中排除。最后你会得到一组专属的外边。
如果您的多边形由非单纯部分组成（但您仍然可以指定顶点遍历的方向），则不会失去通用性。
源段构造的多边形的三角剖分是明显的步骤：将顶点拉伸到$d + 1$抛物面和三角剖分，然后排除三角形，包含至少一条与任何源段都不匹配的边。
另一种可能的方法稍加修改Gift wrapping algorithm。
你会如何用铅笔做...？
- 找到最左边的顶点（最小x）。如果不止一个，则选择其中最低的（最小 y）。当前下方没有顶点，所以以方向'downwards'为参考
- 找到从当前顶点出发的所有边并计算它们的方向（方位角）。找到与参考方向成最小正角（逆时针）的那个。那将是大纲部分。
- Select 它的另一端作为你的新 'current' 顶点，并将 从那个顶点到最近的 的方向设置为新的参考方向。
- 从第 2 步开始，直到到达起始顶点。
- 删除所有未访问的段。
- 删除所有孤立的顶点（如果在第 5 步中出现的话）。