基于选中单元格的房间构建器：带孔洞形状轮廓计算问询

不用凸包算法的话，基于边计数的轮廓提取法是最适合你的场景的——它完全保留单元格的直角结构，资源消耗极低，还能同时提取外轮廓和内部孔洞的轮廓。

核心思路 #

每个单元格的四条边中，只有不被其他单元格共享的边才是轮廓的一部分。共享边（被两个相邻单元格同时拥有）属于内部结构，直接忽略即可。

具体实现步骤 #

1. 标准化存储所有单元格的边
   假设每个单元格是边长为1的正方形，用左上角坐标(x, y)标识单元格。列出它的四条边，并将每条边的两个端点按固定顺序排序（比如先比较x坐标，x小的在前；x相同则y小的在前），确保同一条边不管方向如何，都会被识别为同一个条目：

   • 上边：[(x, y), (x+1, y)]
   • 右边：[(x+1, y), (x+1, y+1)]
   • 下边：[(x, y+1), (x+1, y+1)]
   • 左边：[(x, y), (x, y+1)]

2. 统计边的出现次数
   用哈希表（或字典）统计每条边的出现次数：

   • 出现2次：这条边是两个单元格的共享边，直接丢弃；
   • 出现1次：这条边是轮廓边，保留下来。

3. 拼接闭合轮廓
   从任意一条保留的轮廓边开始，依次寻找下一条边：下一条边的起点必须是当前边的终点。循环这个过程，直到回到起始边的起点，就得到一个闭合的轮廓。

   • 如果存在多个闭合轮廓，最大的那个通常是外轮廓，其余的就是内部孔洞的轮廓；
   • 可以通过遍历方向区分内外：外轮廓一般是顺时针方向，内孔洞则是逆时针方向（反之亦然，取决于你存储边的顺序）。

为什么这个方法比凸包更适合 #

• 完全保留单元格的方形直角特性，不会像凸包那样把凹角拉平；
• 不需要生成每个单元格的网格，只处理边的计数和拼接，资源消耗远低于网格生成；
• 天然支持带孔洞的复杂形状，能同时提取内外轮廓。

内容的提问来源于stack exchange，提问作者Meowing