将基于2D平铺的形状转换为简化多边形

Question

如上图所示,我有一个2D阵列的瓷砖,每个瓷砖在我的游戏世界中有4个点.我正在寻找一种方法,将从单个瓷砖构造的这些形状转换为简化的(没有不必要的顶点,只有形成轮廓所需的那些)多边形.

我一直在四处寻找,在这里和其他地方,运气很少.但也许我不知道要搜索的正确术语.任何帮助表示赞赏.

额外信息:我希望用它来优化动态照明.如果某人有一种不同的方法来在基于图块的世界中完成快速动态阴影,那么这也将回答这个问题.

Answer 1

我建议下一个算法：

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

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