c# - 将基于 2D Tile 的形状转换为简化的多边形

Question

如上图所示，在我的游戏世界中，我有一个二维方 block 阵列，每​​个方 block 有 4 个点。我正在寻找一种方法来将这些由单个图 block 构建的形状转换为简化的(没有不必要的顶点，只有形成轮廓所需的顶点)多边形形状。

我一直在四处寻找，这里和其他地方都没有运气。但也许我不知道要搜索的正确术语。感谢您的帮助。

额外信息:我希望使用它来优化动态光照。如果有人有不同的方法在基于图 block 的世界中实现快速动态阴影，那也将回答这个问题。

Answer 1

我建议下一个算法:

1. 将所有边缘位置存储到二维数组中(边缘位置是边缘的中心)。
2. 计算此数组中的重复边(1 表示没有重复，2 表示与另一条边相交。其他值是不可能的)。
3. 从重复计数为 1(无重复)的数组中选取第一个未标记的边，并在特定方向(例如顺时针)应用简单的递归填充算法，直到到达第一个边。所有这些边将形成一个简化的多边形。如果没有建立未标记边，则转到 5。
4. 将步骤 3 中的所有边标记为已使用。转到第 3 步。
5. 结束。

为了更直观地表示算法，我在下面贴了一张图片。