计算设计与工程：建筑物空间布局问题的形式化和自动生成技术

可在ScienceDirect上获得目录列表计算设计与工程杂志首页：www.elsevier.com/locate/jcde计算设计与工程学报4（2017）318计算机生成的加号形布局及其建筑应用克里希南德拉·谢卡瓦BITS，印度阿提奇莱因福奥文章历史记录：2016年12月7日收到2017年5月22日收到修订版，2017年2017年6月1日上线关键词：邻接算法建筑设计布局矩形A B S T R A C T本文研究的直线排列问题是在给定的直线多边形框架内，考虑每个矩形的尺寸、位置以及矩形之间的邻接关系，将给定的不同尺寸的矩形物体排列在框架内的问题目前的工作是一个更大的工作的一部分，旨在自动生成的直线安排，同时满足给定的尺寸和拓扑约束。本文提出了一套获得加号形排列的算法。此外，我们提出了一些启发式技术，用于减少所获得的安排内存在的额外空间的大小。最后，我们展示了所提出的工作的建筑应用。©2017计算设计与工程学会Elsevier的出版服务这是一个开放在CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）下访问文章1. 目的和意义1.1. 动机本工作讨论了一个问题，在建设几何，这是最初提出的建筑师。这 个 问 题 涉 及 建 筑 物 中 生 活 空 间 的 分 配 ， 是 一 个 研 究 项 目“Formalisation et sens du projet architectural” （ Pellegrino etal.，2008年），其目标是开发建筑概念的形式化，并提供适合建筑组成过程的计算机辅助推理系统。这项研究涉及到建筑学，空间符号学，数学和计算科学之间的衔接。这个问题（以其一种形式）可以表述如下：给定一个房间列表和一个加权邻接矩阵（它定义了房间之间所需接近度的相对权重），所有空间都必须包围在由五个矩形组成的十字形内。分配的限制是十字架的每个臂必须至少有一个露台，每个房间都应该直接或通过露台与外界接触。这个问题很少用数学方法来解决。因此，我们试图推广这个问题，并应用数学方法来解决它。由计算设计与工程学会负责进行同行评审。电子邮件地址：krishnendra. gmail.com1.2. 导言和相关工作组合学是对安排的研究：配对和分组，排名和排序，选择和分配，而建设性组合学是设计和研究用于创建具有特殊属性的安排的算法（Harris，Hirst，Mossinghoff，2008）。因此，矩形物体的排列可以被看作是构造性组合学的一个分支，它受到来自许多研究领域的问题和应用的推动。一组对象的布置动作具有三个基本组成部分，即，对象的几何形状（位置）和拓扑结构（相似性）以及尺寸。 换句话说，可以容易地观察到，在布置中，具有相似形状、反作用、功能、取向或方向的元件在考虑它们的位置和尺寸时经常被分组在一起。一些有趣的和众所周知的几何排列的例子是以最实用的方式组织的家具，著名的魔方，或黄金矩形中的正方形排列。类似地，拓扑布置的示例是如果它们具有一些共同的数学属性（平面图、二分图等）则被分组在一起的图，在元素周期表中，惰性气体根据它们共有的化学性质排列在一起，等等。在文献中，许多研究人员都对这个问题进行了研究在预定义的轮廓形状内的给定对象的布置下面列出了一些相关的工作http://dx.doi.org/10.1016/j.jcde.2017.05.0032288-4300/©2017计算设计与工程学会Elsevier的出版服务这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318319×¼SSS¼在1925年，Moron'（1925年）给出了第一个例子的dissittion1的3233矩形成9不等的广场。然后在1940年，Brooks，Smith，Stone和Tutte（1940）使用由电流，电压和电阻组成的电网络获得了一个这是C.J. Bouwkamp谁第一次成为感兴趣的问题，完美的平方矩形在20世纪40年代初。此外，Bouwkamp和Duijvestijn（1992）还在1978年3月利用计算机发现了第一个简单的完美平方它有最低可能的阶数，n21，并且它是唯一的一个。在上述问题中，矩形的尺寸根据问题的需要而演变如果已知矩形的维数和个数，则相关问题称为packing问题。矩形装箱问题的目标是将一组矩形物品按最小的浪费分配到更大的矩形标准化单元在二维装箱问题中，这些单元是有限的矩形，目标是将所有物品包装成最小数量的单元，而在二维条带装箱问题中，存在给定宽度的单个标 准 化 单 元 ， 目 标 是 将 所 有 物 品 包 装 在 最 小 高 度 内 （ Lodi ，Martello，Monaci，2002）。有关包装问题的一些最新工作，请参阅（Bortfeldt，2006; Cui，Yang，Cheng，Song，2008; Cui，Yang，&Chen，2013; Huang Korf，2012; Wei，Zhang，Chen，2009）。从上面的讨论中可以清楚地看出，填充和平铺问题仅限于尺寸约束。在本文中，我们感兴趣的维数和拓扑约束。因此，我们转向空间分配问题，这是关于平面图中房间（空间）的计算安排。在整个文献中，许多研究人员都在使用算法图论方法自动生成建筑平面图。这种方法首先由Levin（1964）提出，其中提出了一种将图转换为空间布局的方法。1970年，Teague（1970）用网络中的弧表示矩形空间.然后在1980年，Baybars和Eastman（1980）证明了从给定的底层极大平面图获得建筑安排（不一定是矩形的）的系统过程。1982年，Baybars（1982）提出了在平面图中列举流通空间的方法，以及构建具有流通空间的平面图的方法。在1987年，Rinsma（1987）证明了对于任何给定的最大外平面图，最多有四个顶点的度为2，它并不总是可能找到一个矩形布局满足邻接和面积条件。在1997年，Irvine和Rinsma-Melchert（1997）提出了一种生成正交布局的图论方法。 在2004年，Kalay（2004）谈到了解决这个问题的两种方法，即加法方法和置换方法（详见MarchSteadman，1971）。作为这方面的一项最新工作，2011年，阿尔瓦雷斯、里奥、雷库埃罗、和Romero（2011）开发了一种用于自动绘制二维平面图的工具。2012年，Regateiro、Bento和Dias（2012）提出了一种基于拓扑代数和约束满足技术的正交隔室放置方法。在这项工作中，作者提出了169种方式，其中两个矩形或房间可以相邻，这给了一个新的规模涉及到定义房间之间的相邻关系的问题。在2013年，Kotulski和Strug（2013）使用了一类特殊的图，称为超图，作为表示建筑布局的方法。2017年，Ham和Lee（2017）提出了一种算法方法为定量评价结构相似性1矩形剖分是指将一个大的矩形分割成更小的矩形块。一个长方形被分割成正方形，所有正方形都有不同的大小（面积），这就是完美的。建筑平面图之间的关系，并创建分析的建筑平面图的系统发育树。在大多数上述工作中，输出仅限于矩形排列。只有在少数情况下，正 交 排 列 是 从 一 类 特 殊 的 图 中 构 造 出 来 的 ， 即 极 大 平 面 图（IrvineRinsma-Melchert，1997）。除此之外，在一些方法中，布局的形状得到了发展，这是非矩形（Baybars Eastman，1980）。此外，要么不考虑邻接约束，要么用图来表示。显然，在这种情况下，很难在给定对象之间的邻接关系在本文中，我们考虑在给定的特定无量纲轮廓形状中填充n个给定对象的问题，同时满足给定的维度和拓扑约束，其中拓扑约束由流矩阵（加权邻接矩阵）给出（Jokar Sangchooli，2010），即，给定对象之间的邻接要求用权重来表示，而尺寸约束用给定对象的面积（长度和高度）来表示换句话说，问题是在满足给定约束的同时包装n个给定对象，使得包装的最终形状应该类似于给定的特定直线框架。所做的工作是一个更大的工作，旨在自动生成的直线安排，同时满足给定的尺寸和拓扑约束的一部分在本文中，作为一种说明，我们提出了一套算法，获得一个加号形状的安排，为给定的对象，虽然其他形状的安排也可以构建。为了顺利阅读更多的文本，这里是论文中经常使用的符号列表：n：给定矩形对象的数量，Ri：第i个对象，‘RAn：一个有n个物体的矩形排列，RAn：具有n个对象的基于螺旋的矩形排列Li和Hi：RAi的长度和高度PAn：一种基于螺旋的加号形排列，有n个对象。1.3. 例如为了更好地理解本文将要讨论的问题及其解决方案，让我们考虑下面的例子。例1.假设我们给出了16个对象，用R i;i 1; 2;.表示。16.问题是在满足给定的尺寸和拓扑约束的同时，以这样的方式分配给定的对象，使得对象的最终布置应该是类似于图1A中所示的“加号”的尺寸约束由表1给出，拓扑约束由如表2所示的加权邻接矩阵给出。对应于表1和表2的加号形排列如图1所示. 2其中绿色矩形是额外的空间。在构造加号形布置中涉及的步骤如下：1. 在建筑上，一个加号形的多边形可以被看作是一个具有五个不同翼的建筑物，如图1B所示，其中它被分成五个矩形区域（数学上，想法是将给定的多边形分成最大数量的矩形区域，使得每个区域至少包括给定多边形的3个角）。因此，下一步是寻找每个矩形区域的对象。2. 每个区域的对象都是使用第2.2节中介绍的算法从给定的加权邻接矩阵导出的。属于每个区的物体如下：320K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318Fig. 1.一个无量纲的正多边形及其5个矩形区域的划分。1区：R1;R2;R6;R7;R15，2区：R3;R4;R5;R8，3区：R9;R16，4区：R10;R11，5区：R12;R13;R14。3. 接下来是获得对应于每个区域的矩形布置，如图3所示（更多细节，参见第2.3节）。4. 下一步是在得到的矩形排列中尽可能多地消除多余的空间（见2.4节），然后将它们邻接起来，得到图2所示的预期结果（见2.5节）。备注1.在这个阶段，我们不考虑布局的大小，即，最终布局的大小将根据给定对象的排列自动生成，但这将在将来进一步考虑。2. 加号形布置的构造构造加号形排列的步骤如下：图二.一个计算机生成的加号形状的安排，为给定的对象对应于表1和2。1. 将给定的对象分为五组（第2.1节和第2.2节）2. 为每组画一个矩形排列（2.3节）3. 减少矩形排列内部的额外空间面积（第2.4节）4. 构建一个加号形排列（2.5节）2.1. 将给定的加权邻接矩阵转换为邻接矩阵要将给定的对象划分为五个组，第一步是将给定的加权邻接矩阵转换为邻接矩阵表1给定对象的长度和高度R1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R16长度9048905440504530721059050606612028高度603260816075302010870607590998042表2一个16阶的加权邻接矩阵。R1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R16R10866869645322286R28066869645322286R36608686944366446R46680686944344446R588660691022222242R666886010962222242R799669100622222242R866991096066444446R94444262608666669R1055442226801044464R1133332224610022244R1222642224642081029R1322642224642801029R14224422246421010026R158844444466422202R166666222694499620K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318321fg fg fg fg fgfg fg¼ð Þfg fg图3.第三章。基于螺旋的矩形排列，对应于第2.2节中形成的组。矩阵 从数学上讲，一加权邻接矩阵n目标如下：3. 将t减1，并选择对应于数字st的对象对。为了避免重复并降低复杂性，在接下来的每个步骤中，我们跳过与由在上述步骤中形成的对覆盖的对象相对应的行（例如，在第5行中，我们具有与对fR5;R7g相对应的数字9，但是我们排除了该对，因为在对fR5;R8g中存在R 5）。以下是对应于st¼9的所需对象对R1;R7;R2;R7;R3;R8;R4;R8;R9;R16.4. 继续重复步骤2，直到所有对象都被获得的邻接对覆盖。我们可以看到，R15不属于上述两个步骤中形成的任何对。因此，我们查找对应于表2中的编号8的对象对，同时跳过对应于已经覆盖的对象的下面是所需的对象对：R15;R1，R15;R25. 由于在上述三个步骤中识别了所有给定对象，因此算法在此终止。从上面获得的邻接对，可以容易地构造邻接矩阵，如表3所示。2.2. 群体的形成在本节中，我们将看到在第2.1节中获得的邻接矩阵的基础上，给定对象的五个组的形成。这将使用下面给出的算法2来算法2.AWn ai j naji n nkij2I当i0，当i½j：1. 设ki是在2.1节中得到的邻接矩阵的行A i中1的个数M是所有ki2. 查找与M对应的行。 例如在设A W n中不同元素的个数为r，记为s1;s2;.。. ;sr使得s1s2<···sr。<将给定的AW n变换为邻接矩阵的算法的步骤如下：算法1.1. 让t½r。2. 寻找对应于数字st的成对对象。例如，对应于表2，st10，我们有以下对应于数字10的对：fR5;R8g;fR6;R7g;fR10;R11g;fR12;R14g;fR13;R14g。在表3中，对应于R7和R8的行有三个10.3. 形成一个组，对应于上面所述的每行步对应于第i行的所形成的组由对象Ri和与Ri相邻的所有对象组成。4. 如果两个组有任何共同的对象，则将它们合并以形成一个新组。例如，以下两组分别直接从表3的第8行和第9行得出。R1; R2; R6; R7; R3; R4; R5; R8.5. 将M减1，并查找与M对应的行，同时跳过与所形成的组中已经覆盖的对象对应的行。表3由给定的加权邻接矩阵导出的邻接矩阵。R1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R16R10000001000000010R20000001000000010R30000000100000000R40000000100000000R50000000100000000R60000001000000000R71100010000000000R80011100000000000R90000000000000001R100000000000100000R110000000001000000R120000000000000100R130000000000000100R140000000000011000R151100000000000000R160000000010000000（322K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318FGfg fgSSðÞ¼ ðÞ联系我们--SSS6. 转到步骤3。例如，以下组直接从表3的第15和第16行得出。fR12;R13;R14g;fR1;R2;R15g。这里我们将群fR1;R2;R6;R7g和fR1;R2;R15g合并为一个新的群R1;R2;R6;R7;R15。7. 继续重复步骤5和6，直到所有的对象都被所形成的组覆盖。 如果识别出所有对象，则转到下一步。例如，以下组直接从表3的第10和第11行得出。R9;R16;R10;R11。8. 如果形成的组的数量小于5，则要增加组的数量，请搜索具有最大对象数量的组。我们把这个群命名为G。为了进一步进行，在加权邻接矩阵中寻找属于G的具有最小权重的一对对象。设这一对为<$R1; R2<$。将G分成两组，G1和G2，使得G1包含R1，G2包含R2。为了找到G1和G2的其他对象，将G中每个对象的权重与R1和R2进行比较。如果所获得的任何对象对应于R1的权重大于对应于R2的权重，则该对象将属于G1，否则它属于G2。9. 如果形成的组的数量大于5，则为了减少组的数量，选择具有最小数量的对象的两个组并将它们邻接。10. 如果形成的组的数量是五个，则终止算法，否则转到步骤8。所需的组如下：组1：R1;R2;R6;R7;R15，组2：R3;R4;R5;R8，组3：R9;R16，组4：R10;R11，组5：R12;R13;R14。2.3. 矩形排列在本节中，我们的想法是构建与所形成的组相对应的矩形排列。矩形排列是平面的边界和每个给定对象都是矩形的排列它可以有一些空的或额外的空间。对应于每一种排列，我们可以构造一个图，其中顶点表示对象，并且当对应的对象相邻时，两个顶点由一条边连接。这种图被称为对偶图（Earl March，1979）。如果我们只局限于-用于构造最佳连接矩形布置的算法（称为基于螺旋的算法）的步骤如下（使用基于螺旋的算法构造的矩形布置称为基于螺旋的矩形布置，表示为（RA）：算法3.在这里，我们处理3种矩形，其中每种类型由其位置（左上角顶点）和大小（由其长度和高度组成）在构造过程的每个阶段i，我们有以下矩形：i. 一个新的对象Ri，其位置为xi;yi，大小为'i ; h i。ii. 一个额外的空间Ei;，其位置为ti;ui，大小为ki;li。iii. 一个新的矩形组合R A<$i <$，其位置为<$Xi; Y i<$，大小为<$Li;H i<$.第一步是根据它们的大小以升序排列所有给定的对象在四个步骤的每一个中，如果A O> A I，那么我们交换相应R i的长度和高度，其中A O是在用长度'i和高度hi绘制R ii> 1 i之后绘制的额外空间的面积（即， 如最初给出的）并且A1是在绘制具有长度h1和高度“i”的R1i> 1之后绘制的额外空间的面积（即，交换长度和高度）。以上两个操作的重要性将在下一节中说明。该过程从i开始1通过将R1放 置 在0的左边; 0.其余对象的放置方式如下：i1mod4：Ii2mod4：xi;yii3mod4：xi;Yii0mod4：xi;yiXi-1;Yi-1Hi-1，Xi;YiXi-1;Yi-1如果i是奇数，如果hi H i - 1，则H i - 1;如果h i H i - 1，则H i - 1;如果h i-1，则H i-如果我是偶数，i如果：i> L i-1。很容易证明一个RA与其他7个RA全等，在第3节中，我们将看到，任意矩形排列的对偶图的最小边数为3n7其中n是对象的数量，n>3。因此，我们说，一个矩形安排是最好的连接，如果它的对偶图有3n 7边。现在，对于上一节中形成的每个组，我们需要获得矩形排列。在上一节中，我们看到，可以通过使用四个映射中的任何一个从另一个导出，即，平移、反射、旋转和滑动反射（最后一个是平移和反射的组合用于为了更好地理解，我们参考具有八个全等的RA的图4。这些RA被称为spiral1，spiral2，spiral3，spiral4，spiral5，spi。分别为ral6、spiral7和spiral8RNA。 对于RA对应的我们得到一个加权邻接矩阵，但是对于所形成的组，没有关于其对象的图表一种方法是为每个组驱动一个图，然后为每个组构造一个矩形排列在这种情况下，可能发生的是，可能不存在用于对应组的矩形布置因此，为了使该过程自动化，我们考虑更一般化的布置，即，在对象之间具有最大连接性的最佳连接矩形布置，使得可以在稍后阶段建立适当的连接。对于第2.2节中形成的组，参见图3，其中螺旋2、螺旋5、螺旋3、螺旋1和螺旋6RA分别用于中心、左、上、右和下位置2.4. 减少额外空间的面积很明显，如果不同大小的矩形对象需要分配在矩形的一个帧中，那么就会有一些额外的空间。在本节中，我们提出了一种优化技术，K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318323SSSSSSSSSSSSSSSSSS见图4。 八个全等无量纲螺旋为基础的矩形安排。减小RA中的额外空间的大小，使得保持RA的连通性1. 分配顺序使用基于螺旋的算法排列对象以获得矩形排列的顺序称为分配顺序。显然，对于n个对象，通过考虑分配，n！可以得到RAn，并且由于额外空间的存在，每个RAn可以具有不同的面积2. 交换长度和高度显然可以看出，对象Ri可以被定位为具有长度我们可以在计算中，我们对给定的对象使用升序分配，因为：1. 数学上证明了，与降序分配相比，升序分配总是给出2. 通过尝试许多例子，我们发现，在大多数情况下，分配顺序提供最小面积RA。如已经讨论的，对于较小的n值，在2n个解中挑选具有最小面积的解是可行的，但是，我我我交换每个对象的长度和高度，而不改变对象的面积，这反过来又产生了两个面积不同的RA如果长度和高度可以交换，然后我们可以得到2 nR An。3. 使用以上两个步骤，n！×2nRAn可以从基于螺旋的算法中获得。现在，为了减少额外空间的面积，我们可以选择其中面积最小的一个，你好！×2 nR An.显然，如果我们为每个群构造一个具有最小额外空间面积的RA，那么对于大的n值，计算将非常复杂。因此，在下一节中，我们将提出两种启发式技术来减少额外空间的大小，n的值增加，它变得非常复杂。因此为了降低复杂性并获得可接受的解决方案，我们提出以下方法。在绘制每个对象Rii>1之前，我们计算与Ri对应的AO和AI的值。如果AO>AI，我们交换它的长度和高度，否则不交换。2.5. 加号形排列在为第2.2节中形成的每个群构建RNA之后，一个加号形的安排可以通过邻接五个RA，并通过引入必要的额外空间，如图2所示。为了区分额外的空间，内部一RA是称为内额外空间而可能不会给出最佳解决方案（就额外的最小面积用于邻接RA的额外空格到有一个加号形空间），但将提供可接受的解决方案。2.4.1. 减少额外空间大小的启发式技术在本节中，我们提出了一个特殊的分配顺序，用于n！分配的命令。此外，我们还定义了一些交换对象的长度和高度的所有对象按面积递增的顺序排列的分配顺序称为分配的升序。相反，如果所有对象都按递减区域的顺序排列，我们称之为降序分配。我们已经看到，通过改变分配顺序，n个对象，我们可以有n个！ R An. 因此，为了降低这种排列称为外部额外空间（见图2）。所形成的加号形布置被称为基于螺旋的加号形布置，并且由PAn表示，其中n是物体的数量。对于图2中对应于示例1的输入的PA16，所使用的组和螺旋的位置如下：i. 中心组：R3;R4;R5;R8，（组2，螺旋2）ii. 左组：R1;R2;R6;R7;R15，（组1，螺旋5）iii. 上组：R10;R11，（组4，螺旋3）iv. 右组：R9;R16，（第3组，螺旋1）v. 下组：R12;R13;R14（组5，螺旋6）324K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318S3. 邻接图五、图 16中示出了PA 16的对偶图。 二、在这一节中，我们定义了矩形之间的邻接在没有和存在额外的空间。在这里，矩形代表对象和额外的空间。墙是矩形的四条边之一任何两个矩形是相邻的，如果他们共享一面墙或一部分墙，这是不够的，他们接触的一点只。一个额外的空间是一个虚拟的一部分，任何矩形，如果它共享一个完整的墙与矩形，它是一个真正的一部分，一个矩形，如果它是合并到该矩形。如果两个对象之间有额外的空间，那么为了获得对象之间的相邻性，使虚拟部分真实。 例如图 2，通过考虑R1实数的虚部，我们可以说，R1与R3相邻。如果一个额外的空间不是任何矩形的虚拟部分，那么它将是一个以上矩形的虚拟部分让我们见图6。 CPAR的GUIK. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318325SS-----S-SSSS假设它是k>1个矩形的虚部分。为了得到对象之间的邻接，将额外的空间分成k个部分，使得这些k个部分将分别是k个矩形的虚拟部分。然后将所有虚拟零件视为真实零件，计算各零件之间的邻接关系。例如，在图2中，R3和R9之间的外部额外空间不是图1中的任何矩形的虚拟部分。P A16，但如果我们把它分成3部分，那么它将是R 5的虚部分和两个对应于R3和R8的内部额外空间。通过考虑虚拟部分的真实性，我们可以验证R9与R3、R5和R8相邻，而R16与R5相邻。应用上述定义，给出了PA_（？）图2示出在图1中。 五、从欧拉此外，一个矩形排列（没有额外的空间）的对偶图，其中所有的面都是三角形，除了外面是四边形，有3个n 7个边缘。这意味着当n>3时，没有额外空间的矩形排列的对偶图最多可以有3n 7条边。现在，从经由额外空间的对象之间的邻接的定义，清楚的是，即使当虚拟部件被变换为真实部件时，对象之间的邻接也保持不受影响。这意味着具有额外空间的矩形排列的对偶图最多有3n7个边缘。因此，我们称之为以3n 7边的矩形排列为最佳连接。此外，使用数学归纳法对物体的数量，它可以很容易地证明，一个RA<$n <$;n>3的对偶图，3n 7边，因此它们是最佳连接的矩形排列。4. 原型CPAR我们对自动化系统的最大期望是提供满足一般要求的各种设计，以便其中一个或多个可以作为用户的灵感因此在见图7。 使用CPAR将对象从一个组移动到另一个组。3. 每个组如在2.3节和图4中已经讨论的，RA可以以八种不同的方式构造。用于每个组的螺旋可以直接从GUI中选择。在完成上面讨论的所有三个操作之后，将自动生成一个屏幕，其中包含所需的PA及其对偶图在这一部分，我们的目标是自动生成所需的加形安排，同时满足给定的拓扑和尺寸约束。为了验证第2节中提出的算法，我们开发了一种称为CPAR（计算机生成的矩形加形排列）的原型，该原型是用处理计算机语言编写的（有关处理的详细信息，请参阅http://www.processing.org;Terzober，2009）。CPAR有16个pde（处理源代码）文件和两个外部文件，即input.txt和output.txt。文件input.txt包含一个加权邻接矩阵，每个给定对象的长度和高度，文件output.txt由与所获得的加号形状排列相关联的协变量组成。对象的数量（n）通过输入.pde文件给出。当我们运行CPAR时，会显示一个GUI，如图6所示。在这个获得的GUI的顶部，我们有对象和已形成的组的列表。该GUI的功能如下：1. 将对象从一个组移动到另一个组为了得到一个PA，我们把给定的对象分成给定的组。组的形成是通过算法完成的，因此用户可能对所形成的组不满意。此GUI提供了将对象从一个组移动到另一个组的选项。例如，在图7中，组1的R1被移动到组3。2. 群体的地位在PA中，任何组可以具有图1B中所示的5个可能位置中的位置。这些位置可以直接从GUI中选择，无需重复。（见图。 8）。4.1. 安装处理（版本2.2.1）和所需的库（controlP5，Jama，jgrapht）可 以 从 （ http://www.processing. org ） 。 CPAR 及 其 文 档 可 从（ http://krishnendrashekhawat.weebly.com/downloadable.html）下载。5. 建筑应用从数学上讲，平面图是一个多边形，平面边界，由直线划分为称为房间的组件多边形。循环是指人们在建筑物内移动和互动的方式。诸如走廊、电梯、楼梯等结构通常被称为循环元素。露台是户外的生活空间.对应于一个加号形的安排，我们认为一个额外的空间毗邻外部世界作为一个露台，否则作为一个循环。建筑平面布置图的生成是建筑设计中的一项基本活动，建筑师需要在给定的平面布置图（有尺寸或无尺寸的几何模式）中安排给定的空间（或房间），以满足特定的要求或约束。两个最基本的制约因素是：1. 根据房间面积（参见表1）给出的尺寸或尺寸限制，326K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318S见图8。 用CPAR生成的一个PA_（16）图2. 邻接或拓扑约束，或者由称为邻接图的图给出（参考Roth，Hashimshony，&Wachman（1982）），或者由所有房间对之间的预期行程数给出（参考Sjanov Gali（1974））。这些行程可以以矩阵的形式给出，称为加权邻接矩阵（参见表2）。房间之间以及与外部的互连，以及进入房间的自然照明或通风，往往是这种限制的原因。众所周知，计算机辅助建筑设计（CAAD）是一个广泛的研究领域，其中提出了新的基于计算机的算法方法来促进建筑师的工作（Kalay，2006; Mitchell，1975）。对于建筑物的平面图的自动生成 问 题 ， 基 本 上 存 在 两 种 公 知 的 方 法 ： 优 化 （ 直 接 方 法 ）（Baybars& Eastman，1980; Roth等人，1982）和组合（迭代法）（Galle，1981; Steadman，1973）。在本文中，使用直接方法，我们提出了一种数学方法来解决在给定的预定义轮廓形状（无量纲）内安排给定房间（尺寸）的问题，同时满足由加权邻接矩阵给出的邻接约束和尺寸约束（详细解释，请参阅第2节）。如果我们考虑复杂的建筑结构，如医院，学校，办公室等，那么我们可能需要除了长方形以外的平面图。此外，在具有大量房间的复杂建筑物的情况下，似乎重要的是要考虑成对房间之间的距离，以及建筑物的居住者沿着不同路线预期进行的行程的频率。针对平面布置图设计的复杂性，本文采用启发式方法，提出了一套由加权邻接矩阵给出邻接约束的直线形平面布置图的自动生成算法。为了演示直线平面图的自动生成，在第2节中呈现了加号形平面图（或布置）的构造。在建筑上，i. 它可以被划分成5个区域，其中4个区域可以彼此完全独立但与中心区域良好连接（例如，在图2中，考虑上部和下部区域，其中R10可以是图书馆，R12可以是播放区域;两者可以在同一建筑物中同时起作用而不会相互干扰），ii. 它能够使大部分房间与外部相邻，同时允许其它房间位于中心核心中并由此容易地从其余区域进入，iii. 它的对称性使它在视觉上令人愉悦。显然，本文提出的工作可以在生成候选直线平面图，特别是加号形平面图，可以由建筑师根据他们认为重要的其他设计标准，如美学，视图，舒适度等进行修改，是6. 结论在本文中，我们提出了一个算法，生成一个加号形状的安排，同时满足给定的尺寸和拓扑约束。在这里，为了演示的目的，我们考虑了加号形的安排，但这项工作将进一步推广到其他直线安排。例如，参考图9，其具有对应于表1和表2的垂直翻转的T形和水平翻转的L形布置。这项工作显示了建筑平面规划的直接应用，是自动生成直线布置的第一步。未来的目标是产生最小的额外空间，同时考虑许多其他相关的限制直线安排。K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）318327--11利益冲突见图9。对应于表1和表2的垂直翻转的T形和水平翻转的L形布置。其他断言可以通过使用基于螺旋的序列以相同的方式证明H提交人声明不存在利益冲突确认本研究得到了Birla技术科学研究所（Pilani，333031）研究启动基金的支持。附录A为了构造定理1的证明，我们首先给出一个计算所有Li和Hi值的数学方程，然后给出引理1和引理2.为了继续下去，让我们假设L0¼0引理2. 如果对于每个偶数i6n，我们有Ln<$'n对于n奇数：Ln¼如果对于每一个奇数i6n（i- 1）Hn<$hn1hn3· ··h2h1;H=0。- -对于i 1; 3; 5;.Li¼Li-1对于i¼ 2; 4; 6;.. .Li¼maxLi1;对于n even：Hn<$hnHn-1<$hnhn-2hn-4···h2h1：证据我们用数学归纳法证明了这个结果。- -初始时n 1;L 1/4和H1/4小时。 对于n1/2，从引理1. 对于n，我们有：Ln¼maxHn<$hn最大值Hn-1;Hn-2最大值H3;h2最大值H1：对于n奇数：螺旋形底座 序列，L2¼maxL1;和H2<$H1<$h2<$h1<$h2。对于n<$3; L3<$L2<$“3 <$”1 <$“3和H 3 <$max <$H 2 ; h 3 <$$> max <$h 1 <$h 2 ; h 3 <$$> h 1<$h 2。因此，对于n1/2和n1/3，让结果对所有n都成立。<现在我们证明结果为n. 如果n是奇数，对于偶数n-1，我们有Ln-11/4Ln¼Hn-11/4hn-1 歼-3歼-5···第一章：Hn<$maxhn;hn-1maxhn-2;hn-3··· maxh3;h2h1证据从基于螺旋的序列，对于n，我们甚至有Lnmax Ln-1;' n。现在对于Ln-1;n1将是奇数，因此从基于螺旋的序列中，我们将有：Ln¼maxn¼max'¼max'..¼max'<$max'从奇数n的基于螺旋的序列，我们有Ln<$Ln-1'和Hn¼maxHn-1;hn最大值hn-1hn-3hn-5h···h2h1;hn��hn-1�hn-3�hn-5�···�h2�h1因为fhig是一个非递增序列，所以：如果n是偶数，对于奇数n-1，我们有Ln-1/4 ′我们称这种序列的L i和H i的螺旋基序列。11328K. Shekhawat/ Journal of Computational Design and Engineering 4（2017）31822¼·第一次n第一次-n-nnn-2n-41--Hn-1hn-2hn-4···h2h1：从基于螺旋的序列中，我们有从2.1开始，H0n<$hnhn-1hn-3· ··h1。Hn和H0n中的最大项数是1n<$1。很容易Ln<$maxLn-1;对于每个i，Hn的第i项小于或等于第i项H0的项，这意味着H6H0。¼和因为3.2为了证明当n是偶数时，Ln6L0n，根据Ln¼maxHn<$Hn-1hn<$hn<$hn-2hn-4···h2h1：因此，通过数学归纳法，结果对n成立。H定理1. 假设我们有n个房间，由它们的面积和它们的长度和高度之间的比率的假设给出固定，即所有房间都一样 然后，R A n的面积为从2.1开始，L0n1/2 n 1/2 n 1/4 n 1/2。Ln和L0n中的最大项数为1n. 很容易看出，对于每个i，Ln的第i项小于或等于L0 n的第i项，这意味着Ln6L0n。现在我们考虑n是奇数的情况我们知道每个h 升根据引理1，我们有S分配的升序最多等于RA ni我1=k·H最大值“;最大值”;最大值“分配的降序SN N最大值"n-1n-2n-3证据设R i为i<$^1; 2;.的第i个房间。n，Ri 的面积为Si，hi与hi<$k·也考虑S16S26···6Sn，这意味的'1 6 ' 2 6 ··· 6 ' n和h 1 6 h 2 6 ··· 6 h n。 证明是结构化的和Ln1/4 ′ n n 1/2 ′ n 1/2 ′ n 1/2 ′ n