在建筑施工图中，我们使用 CAD 建筑基础图元构建出具有各种语义含义的构件，而一些特定的构件，例如墙体、门、窗户、栏杆等等，会将图纸空间分割成一个个彼此联通的“物理空间”。
空间的轮廓可以用多边形来表示。需要指出的是，空间内部出现的障碍性元素 -- 例如住宅核心筒中的公区部分内部的电梯井 -- 可能在空间轮廓多边形中引入孔洞。因此，我们需要使用含孔多边形来表示空间。类似的表示方式在墙体等线性构件上。延绵的墙体也可以被表示为含孔的多边形。墙体上的孔可以是管井甚至是其他空间。
△以多边形形式表示的墙体与空间
直接从图纸上得到的多边形表示，无论是墙体还是空间轮廓，通常都是曲折而复杂的。从人类的视角来看，在进行绘图操作时，我们可以自然地理解空间或者墙体的空间拓扑特点。在这个潜意识的过程中，设计师可以直觉性地完成空间分割与轮廓骨骼线的提取。例如将户内公区分割成餐厅、客厅、玄关以及走廊，又例如将一个段数十米长的曲折走廊分解为多个段，并获取各个段的走廊中线走势。
这个潜意识思考过程对于人类来说轻而易举，单从算法设计角度得到一个契合建筑场景的语义特征的多边形分解方案则较为困难。
多边形分割
多边形分割是计算几何领域汇总的经典问题，其在各个领域都有广泛的应用。模式识别领域将多边形分割作为一种识别工具，通过将待识别元素表示为多边形并将其拆解成更加简单的块的组合，可以对其组成特征进行分析进而实现类型划分；在集成电路设计领域，多边形分割算法可以用于将路由空间分割成走线通道。在筑绘通平台中，我们将图纸中的空间与线性构件进行拆解，进而进行结构化，为空间和构件的组件赋予高度语义化的含义。多边形分割的其他应用场景还包括数据压缩，数据库系统，图像处理以及计算机视觉等等。
在计算几何领域，多边形分割问题根据场景（输入形状特征）和拆分目标不同可以划分成多种不同的类型。在这些不同类型的问题中，多边形分割过程一般可以被分解成两个步骤：
1
将多边形分割成最简单的基础图形，一般而言这些基础图形是三角形和凸多边形。
2
将基础图形进行重组以适应我们的分割目标。
01
将多边形分割成最简单的基础图形
「三角剖分」
将多边形分割成三角形是最为简单直接的分割方法，学术界和工业界在这一领域的研究较为充分。Delaunay 三角剖分是一种应用十分广泛的三角形剖分方法。
严格来说 Delaunay 三角剖分不是一种算法，而是评估一种三角分割是否是一个好的分割的定义，其核心思想是空圆特性和最大化最小角。这两个特性避免了过于狭长的三角形的产生。所谓空圆特性，是指对于任意两个工边的三角形，其中任意一个三角形的完结圆都不能包含另一个三角形的定点，基于这个原则生成的三角剖分能够实现最小角最大的目标。
△Delaunay 分割过程示意图
△随着点的变化而导致的不同Delaunay三角剖分结果
在筑绘通中，我们尝试使用三角剖分进行了连线问题场景中的路由空间剖分，从而实现将路由空间离散化。经典的路由算法，例如 A 算法，采用栅格化的方法对路由空间进行离散化，这意味着网格数量的规模与图纸的大小成正比，这导致在大型图纸中，网格数量过于庞大，进而导致路由算法收敛缓慢，并显著提高了路由算法的内存资源占用。而如果采用三角分割方法对路由空间进行分割，并基于三角形相邻关系构建拓扑图，我们可以在这个图的基础上应用经典路由算法。
三角分割方法得到的图的节点数量只与空间轮廓与障碍物的顶点数量有关，而与图纸空间的绝对大小没有关系，因此可以显著降低搜索空间，大大提高算法收敛速度（约 3 个数量级），并降低资源占用。
△基于三角剖分的大空间尺度快速路由
三角剖分的优势在于算法成熟，实现效率高，求解稳定，但是其缺点对于我们的应用场景来说非常明显：建筑物一般不是以三角形的方式来修建空间的。
对于一个规整的矩形的房间，我们不希望将其分割成两个直角三角形来处理，而是希望能够以整个矩形的形态来处理。这时我们需要考虑四边形拆分方法。
「四边形拆分」
△一个凸多边形分割的例子，其内部引入了 Steiner 点
四边形拆分的一般是直接将多边形分割成凸四边形。相比于三角剖分，凸四边形剖分更加困难，这种困难一方面在于相比于三角剖分，四边形剖分中的凸形保证是一个新的问题，另一方面在于四边形剖分难以界定一个好的目标。
在实践过程中，我们一般不会像三角剖分问题中的 Delaunary 三角剖分方法一样求解一个一般意义上的多边形拆解问题，而是需要引入额外的假设，并更加具体化我们对于分割出来的基础四边形的要求来明确问题边界。这是因为不同的假设条件下四边形拆分问题的理论复杂度有显著的区别。
△不同的多边形类型，从上至下从左到右依次是 convex, monotone, star-shaped (with kernel), orthogonal, orthogonally convex, histogram, spiral, crescent, pseudotriangle 等。三角分割时我们可以无视这些区别，但是在一般的多边形分割中，这些初始形状的假设对于我们的结果和求解难度有显著的影响。
现有理论研究证明了将无孔多边形分割成凸四边形的问题，以及将可能含孔的正交多边形（即其相邻边正交）分割成矩形的问题都属于 NP-Complete 的问题，这意味着我们可以找到多边形时间内可行的求解方法。这类方法一般是利用了 Steiner 点结合分治或者动态规划思想。反之，将含孔多边形分割成凸四边形的问题是 NP 难的。
△正交多边形分割相对简单
考虑到建筑施工图场景中我们需要分割的空间或者墙体一般都近似符合正交多边形的特点，在设计倾向来说，大多数场景下我们会把房间设计成矩形，将墙体视为多个矩形段的组合。在这些场景下，我们可以将这些问题建模成正交多边形向矩形拆解的问题。但是建设设计过程中的不少情形下会出现非正交多边形形态的空间和墙体。因此我们的拆解目标也必须考虑凸四边形拆解的情况，同时避免我们陷入含孔多边形拆解到凸四边形的复杂场景。一些额外的建设有助于我们简化问题。例如在墙体拆解中，我们可以假设拆解形成的凸四边形的所有顶点都应该位于原轮廓上，而不应该在多边形内部引入新的点（这一假设在空间分割上则不一定成立）。
02
子多边形重组
在建设施工图自动画图场景中，我们对空间和墙体进行拆解通常是从建筑视角出发，而是非纯粹地去求解一个计算几何问题，因此我们需要将多边形拆解形成的基础元素进行重整，以形成具有建筑语义含义，符合建筑直觉的划分方法。
子多边形重组并非是一个必须的过程。在合适的场景下通过设计初始分割算法就可以得到预期内的结果。但是这在建筑空间和墙体拆解的过程中通常是一种奢望。直接正向地设计分割算法过程难以直接贯彻我们对分解结果的要求，其执行过程也受到众多 Corner case 的干扰。因此我们通常采用初始分割 最细小的块然后进行重组的方法。
分割形成的子多边形重组问题是一个组合优化问题，我们有很多现成的运筹学工具可以进行求解，包括启发式算法，混合整形规划以及机器学习等手段。利用这些手段的核心问题是如何量化地度量一个分割方案的好坏。这种度量方法需要结合场景来进行针对性的设计。例如在墙体拆解中，我们希望分割产生的多边形应该尽可能是矩形，而且分割产生的块越少越好的；在空间拆解中，产生尽可能少的分块的思想则不一定是正确的。例如在下面的空间过程中，我们可以利用基础分割算法产生最基础的矩形子块组成（左图）， 共计四个组块。若按照最少分割数量的原则，进行基础子块的重组，那么会得到中图的结果。从空间认知角度来说，这个分割方案显然没有右图中的方案好，因为右图中的方案突出了空间出图，将空间的两个零碎部分拆解下来。
针对这种场景，我们可以采用 Minimum Ink，或者说最短分割线的长度，以最小化分割线的长度为目标，我们可以在中图和右图中遴选出右图作为最优解。事实上，在正交多边形上实现 Minimum ink 切割是一个 P 问题，我们可以找到时间复杂度是O(n4) 的分割方法。如果多边形上出现孔，则问题演变成 NP -Complete 问题。如果进一步将问题前提一般化，则问题的复杂度就向 NP-hard 发展。
△筑绘通中墙体拆解的效果
结语
本文我们着重阐述轮廓多边形分割问题的在建筑施工图自动绘制场景中的呈现。多边形分割方法在筑绘通平台中发挥着基础行动作用，基于有效的分割我们才能有效的建立起空间、墙体以及更复杂构件的形状结构和拓扑关系，更是后续我们进行构件放置，连线布置以及参数计算的重要基础。
参考文献：
[1] Polygon Decomposition by J.Mark Keil
[2] Everett H, Lenhart W, Overmars M, et al. Strictly convex quadrilateralizations of polygons[C]//Proceedings of the 4th Canadian Conference on Computational Geometry. 1992: 77-83.
[3] O'Rourke J, Supowit K. Some NP-hard polygon decomposition problems[J]. IEEE Transactions on Information Theory, 1983, 29(2): 181-190.
[4] Handbook of discrete and computational geometry[M]. CRC press, 2017.
©版权归品览所有
未经授权请勿转载
RECOMMENDED
一键试用 筑绘通
点击阅读原文或扫码
即刻预约
AlphaDraw筑绘通正逐步上线施工图领域各专业的新模块：包含建筑、结构、暖通、电气、给排水、室内六大专业，47个一级系统，共计180个二级模块。同时，小览也会陆续更新新模块内容及操作教程，敬请期待吧！
品览是AI建筑设计智造者，专注于建筑设计AI服务，致力于为地产企业和设计院客户提供AI设计出图服务。自主研发的建筑AI智能设计云平台AlphaDraw「筑绘通」，基于计算机视觉技术，建筑设计知识库和生成式强化学习算法帮助客户自动完成施工图设计。仅需上传建筑方案图纸就可以自动完善成套施工图，并符合各地设计规范，助力企业标准化出图、效率质量双提升。
本文来自微信公众号“品览Pinlan”（ID：pinlandata）。大作社经授权转载，该文观点仅代表作者本人，大作社平台仅提供信息存储空间服务。
