正规的合肥网站建设价格,企业形象标识设计,wordpress 后台 留言,网页设计对板式的要求这个功能确实非常实用#xff0c;我在过去开发地面分区编辑器时就曾应用过这一算法。最近#xff0c;在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过#xff0c;但由于长时间未接触#xff0c;对算法的具体细节有所遗忘#xff0c;导致重新编写时耗费了不少时…这个功能确实非常实用我在过去开发地面分区编辑器时就曾应用过这一算法。最近在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过但由于长时间未接触对算法的具体细节有所遗忘导致重新编写时耗费了不少时间。
起初我尝试采用广度优先搜索来解决问题却发现这种方法需要遍历所有可能性以找到最小面积的解性能上显得过于低下。经过一番考量后最终决定回归之前所用的更为高效的算法。这种算法不仅能够满足性能要求还能有效减少开发时间和资源消耗。
如下图示例 想要求出图中所有闭合区域首先要收集这些线段并绑定他们的关系。 private static DictionaryVector3, HashSetVector3 BuildAdjacencyList(ListLineSegment segments){var graph new DictionaryVector3, HashSetVector3();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并且该顶点同时存在于最大闭合区间中则将其视为边缘顶点并移除。移除顶点的同时解除其他顶点与该顶点的相邻关系。 循环操作 重复上述步骤直到所有顶点都被移除。
通过这些步骤我们就可以找出最小闭合区间啦。
