这个功能确实非常实用，我在过去开发地面分区编辑器时就曾应用过这一算法。最近，在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过，但由于长时间未接触，对算法的具体细节有所遗忘，导致重新编写时耗费了不少时间。
起初，我尝试采用广度优先搜索来解决问题，却发现这种方法需要遍历所有可能性以找到最小面积的解，性能上显得过于低下。经过一番考量后，最终决定回归之前所用的更为高效的算法。这种算法不仅能够满足性能要求，还能有效减少开发时间和资源消耗。
如下图示例：
想要求出图中所有闭合区域，首先要收集这些线段，并绑定他们的关系。
private static Dictionary<Vector3, HashSet<Vector3>> BuildAdjacencyList(List<LineSegment> segments)
{
var graph = new Dictionary<Vector3, HashSet<Vector3>>();
foreach (var segment in segments)
{
AddVertexToGraph(segment.Start, graph);
AddVertexToGraph(segment.End, graph);
graph[segment.Start].Add(segment.End);
graph[segment.End].Add(segment.Start);
}
RemoveSingletonVertices(ref graph);
return graph;
}如上，构建无向图邻接表。将顶点收集并绑定相邻的顶点。我们要移除那些顶点相邻顶点只有一个的数据。他是组成不了闭合区间的。
接下来，我们需要分别计算出最小闭合区间和最大闭合区间。核心算法如下：
-
选择起始顶点：
- 选出一个 x 值最小的顶点作为第一个顶点。
- 如果有多个顶点的 x 值相同，则选择 y 值最小的顶点。
-
逆时针选择顶点：
- 从选定的起始顶点开始，沿着逆时针方向选择下一个顶点。
- 重复此过程，直到找出的顶点和第一个顶点相同，形成最小闭合区间。
-
计算最大闭合区间：
- 最大闭合区间算法与最小闭合区间相似。也是逆时针选出。但是从第三个点开始选最外围的也就是夹角最大的顶点。注意：需要用叉乘判断是凸角还是凹角。若是凹角，则角度=360-夹角。
-
移除边缘顶点：
- 遍历最小闭合区间的顶点，检查每个顶点的相邻顶点数是否为 2。
- 如果某个顶点的相邻顶点数为 2，并且该顶点同时存在于最大闭合区间中，则将其视为边缘顶点并移除。
- 移除顶点的同时，解除其他顶点与该顶点的相邻关系。
-
循环操作：
- 重复上述步骤，直到所有顶点都被移除。
通过这些步骤，我们就可以找出最小闭合区间啦。
