假设你有一组三角形，如下图所示，其中黑色是三角形边，红色是三角形，绿色是需要找到的多边形，蓝色是多边形的点 .
描述的多边形可以是凹的，也可以不是凹的 . 它中的三角形将始终相邻（与集合中的其他三角形共享所有三个点） . 生成这样一组三角形描述的多边形有哪些算法？多边形应采用顺时针或逆时针顺序的点列表的形式 .
怎么样关注一个简单的 GrahamScan 算法...那应该做的伎俩 .
GrahamScan
假设您有N个不同的点Pi和M三角形 . 我们通过3个索引i，j和k来定义每个三角形 . 每个三角形将具有3个边缘，定义为E（i，j），E（j，k）和E（i，k） . 找到"polygon"的方法如下：
1）循环通过所有三角形 . 对于每个三角形，将3条边添加到集合中 . 具有两个相同点指数的边应该被视为相同的边 . 即，E（i，j）= E（j，i） . 遇到这种情况后，从集合中移除E（i，j）和E（j，i），因为这些是内部边缘 .2）集合中的剩余边缘应该是形成多边形的边缘 .3）通过点索引对集合中的边缘进行排序，如下所示：
（3a）从集合中选择任何边缘，例如E（i，j） .（3b）将索引i和j添加到std :: vector中，然后从集合中删除E（i，j） .（3c）从集合中找到共享std :: vector中最后一个点索引的边（现在是j） . 将此边缘表示为E（j，k） . 将索引k添加到std :: vector中并从集合中删除E（j，k） .（3d）重复步骤（3c），直到该组不包含边 . std :: vector中的点索引将是多边形的点顺序 .
如果您只有三角形顶点的M个三角形和3 * M（x，y）值，那么您需要进行一些预处理以删除相同的点，并按照上述点指数重新定义三角形 .
2 回答
怎么样关注一个简单的
GrahamScan算法...那应该做的伎俩 .假设您有N个不同的点Pi和M三角形 . 我们通过3个索引i，j和k来定义每个三角形 . 每个三角形将具有3个边缘，定义为E（i，j），E（j，k）和E（i，k） . 找到"polygon"的方法如下：
1）循环通过所有三角形 . 对于每个三角形，将3条边添加到集合中 . 具有两个相同点指数的边应该被视为相同的边 . 即，E（i，j）= E（j，i） . 遇到这种情况后，从集合中移除E（i，j）和E（j，i），因为这些是内部边缘 .
2）集合中的剩余边缘应该是形成多边形的边缘 .
3）通过点索引对集合中的边缘进行排序，如下所示：
（3a）从集合中选择任何边缘，例如E（i，j） .
（3b）将索引i和j添加到std :: vector中，然后从集合中删除E（i，j） .
（3c）从集合中找到共享std :: vector中最后一个点索引的边（现在是j） . 将此边缘表示为E（j，k） . 将索引k添加到std :: vector中并从集合中删除E（j，k） .
（3d）重复步骤（3c），直到该组不包含边 . std :: vector中的点索引将是多边形的点顺序 .
如果您只有三角形顶点的M个三角形和3 * M（x，y）值，那么您需要进行一些预处理以删除相同的点，并按照上述点指数重新定义三角形 .