基于网格划分的紧凑型复合图正交布局方法、计算机装置及计算机可读存储介质与流程

1.本发明涉及计算机图形的处理技术领域，具体的，涉及一种基于网格划分的紧凑型复合图正交布局方法、实现这种方法的计算机装置以及计算机可读存储介质。


背景技术：

2.在绘制电力设备调配图时，需要在图纸中显示诸如变电站、站房、开关设备、虚节点等设备节点，每种设备节点的大小不一，且每一个设备节点通常与另外一个或者多个设备节点存在连接关系，例如两个设备节点之间需要布置电力传输线或者信号传输线等。因此，电力设备调配图还需要体现各个节点之间的连接关系，连接两个设备节点之间的线通常被称为“边”。
3.通常，电力设备调配图被认为是由设备节点和边组成的数据结构，用于表示多个设备节点之间的关联关系。随着图形数据规模的增大，人们理解和推理图中蕴含的结构或知识变的越来越困难。如图1所示，如果简单的将具有连接关系的设备节点进行直接连接，将导致大量的连线相互交错并重叠布置，阅读效果非常差，人们往往难以辨识设备节点的位置，也难以看清楚具体的连线。为此，人们倾向于使用正交布局的图形来表示数据结构，如图2所示，每一个设备节点是一个大小均一的方块表示，且设备节点之间的连线均正交布置，即连线只能够沿横向或者竖直方向布置，连线的弯折处呈90
°
。正交布局的图形阅读体验更佳，在视觉上能够更加友好的呈现数据。
4.电力设备调配图的正交布局要求开关设备成组嵌套，且变电站及其一级设备周边节点也要足够邻近，这种正交布局的图形是带有自环情形的无向复合图正交布局，且设备节点具有实际的物理大小。
5.复合图正交布局是当前图形布局研究中新的热点方向，其不仅要求具有一般图形布局成图的美观性，还要求图形的各节点块大小可设定，所研究的对象是复合嵌套的图结构，即图中节点对可约束成组，同时图布局的走线必须正交。因此，相比于传统的图形布局方法，复合图正交布局因其允许节点从大小到结构嵌套的灵活变动而具有更大的应用前景。
6.目前，国内基于树图结构的图布局研究较多，多见于计算机图形学领域，但在正交图布局的研究方面较少。国外除了包含一般的正交图布局研究外，最新的研究兴趣已转向如何针对复合图的正交布局。如2021年zaman针对小型复合图，提出了基于tsm方法对节点不超过4度的图形给出正交布局算法。
7.复合图正交布局是具有多层嵌套的图形，在电力设备调配图的实际绘制时，需要解决两个关键的问题：一是设备节点位置的放置，二是设备间走线的正交路径规划。其中节点位置的放置是最重要的环节，它直接影响后续的节点交叉或美观，决定了最终成图的整体效果。在满足上述复合节点约束和图形美观度最佳的优化目标下，该问题的理论全局最优求解是极其困难的。
8.由于目前对于复合图正交布局的美观度评价都是人为主观的评价，并没有引入客观的评价标准，导致复合图正交布局的主观评价成分过高，影响最终获得的复合图正交布局的美观性。并且，依据人为主观评价的方式还导致难以实现自动化的图形布局计算，导致复合图正交布局方法执行效率不高。


技术实现要素：

9.本发明的第一目的是提供一种能够客观评价复合图正交布局美观性的基于网格划分的紧凑型复合图正交布局方法。
10.本发明的第二目的是提供一种实现上述基于网格划分的紧凑型复合图正交布局方法的计算机装置。
11.本发明的第三目的是提供一种实现上述基于网格划分的紧凑型复合图正交布局方法的计算机可读存储介质。
12.为实现本发明的第一目的，本发明提供的基于网格划分的紧凑型复合图正交布局方法包括获取图形初始数据，图形初始数据包括图形的节点数量、节点位置限制信息；对图形初始数据进行预处理；并且，根据图形初始数据对各个节点进行初始化布局，自适应计算对图形进行布局所需要划分的网格大小以及单元格的大小，更新网格标记矩阵的信息；对初始化布局后的初始图形的美观度进行评分，对初始图形进行迭代优化计算，直到初始图形的美观度的评分不再提升，获得最终优化的图形中各个节点的位置坐标信息；根据各个节点的位置坐标信息生成各节点之间的边关系的正交线路规划，并进行标注以及渲染后获得正交布局图。
13.由上述方案可见，通过设置了对初始图形的美观度进行评分，尤其是通过设定美观度评分函数进行客观的美观度评分计算，避免人为进行美观度评分而导致美观度评价过于自由的问题。此外，本发明还对节点的布局进行迭代优化，保证了图形布局的全局性，生成的图形布局紧凑而有序，从弯折数，交叉数，边长和等美观度指标上都有很好的改善。
14.一个优选的方案是，对初始化布局后的初始图形的美观度进行评分包括：计算初始图形中任意两个节点之间的距离函数值，并对初始图形中所有节点中任意两个节点之间的距离函数值求和，以求和值进行美观度评分。
15.由此可见，依据对任意两个节点之间的距离进行美观度评分，可以使得计算获得的复合图各个节点之间的距离不会过长，确保最终形成的图纸紧凑、有序。
16.进一步的方案是，对初始化布局后的初始图形的美观度进行评分包括：计算每一节点的弯折函数值，一个节点的弯折函数值为该节点以及与该节点具有拓扑连接的节点之间的弯折函数，计算所有节点的弯折函数值总和，以弯折函数值总和进行美观度评分。
17.可见，除了考虑节点之间的距离，还考虑节点之间的连线所形成的弯折情况，以弯折函数值总和进行美观度评分，使得最终获得的复合图弯折数量较少，能够尽量减少交叉的情况。
18.更进一步的方案是，对初始图形进行迭代优化计算包括：确定一个目标节点的当前位置后，选取目标节点的更佳布局位置，计算目标节点在更佳布局位置下初始图形的美观度的评分值。
19.由此可见，通过对单个节点的位置进行调整，例如将单个节点的位置调节至空白
位置，从而查找出各个节点更佳的布局位置，提升图形的美观度。
20.更进一步的方案是，对初始图形进行迭代优化计算包括：将初始图形中距离小于预设值的两个节点进行位置互换，计算进行节点位置互换后的初始图形的美观度的评分值。
21.可见，通过对两个距离较小的节点进行位置互换来进行迭代计算，可以查找出各个节点更加的布局位置。
22.更进一步的方案是，对初始图形进行迭代优化计算包括：构建带约束的二次型压实模型函数，对二次型压实模型函数进行求解，根据求解结果重新确定节点的位置，并根据重新确定的节点位置对初始图形的美观度进行评分。
23.这样，通过引入了大规模矩阵的稀疏求解方法，即二次型压实模型函数进行求解，能够在可控时间内离线处理上万个节点的自动化成图，从而大大降低了人工绘图的繁琐，提高绘图效率。
24.更进一步的方案是，对初始图形进行迭代优化计算时，模拟退火算法进行迭代求解。
25.由此可见，采用模拟退火算法进行迭代求解，能够逐步降低温度，迭代计算收敛效果佳，能够保证迭代计算的效率。
26.更进一步的方案是，网格标记矩阵的信息包括网格标记矩阵的大小、每一节点在网格标记矩阵的位置、网格标记矩阵的空白区域、每一节点在横纵方向上的可视节点。
27.可见，通过网格标记矩阵的信息可以确定网格单元的大小，并且可以了解矩阵内的空白区域在哪里，对于快速定位画布空白的区域索引、搜索能否交换多个节点是非常有帮助的。
28.为实现上是的第二目的，本发明提供的计算机装置具有处理器以及存储器，存储器存储有计算机程序，计算机程序被处理器执行时实现上述基于网格划分的紧凑型复合图正交布局方法的各个步骤，或者执行上述基于网格划分的紧凑型复合图正交布局方法的各个步骤。
29.为实现上是的第三目的，本发明提供计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现上述基于网格划分的紧凑型复合图正交布局方法的各个步骤，或者执行上述基于网格划分的紧凑型复合图正交布局方法的各个步骤。
附图说明
30.图1是随机布局的图形示例。
31.图2是正交布局的图形示例。
32.图3是本发明基于网格划分的紧凑型复合图正交布局方法实施例的流程图的第一部分。
33.图4是本发明基于网格划分的紧凑型复合图正交布局方法实施例的流程图的第二部分。
34.图5是本发明基于网格划分的紧凑型复合图正交布局方法实施例中网格标记矩阵的示意图。
35.以下结合附图及实施例对本发明作进一步说明。
具体实施方式
36.本发明的基于网格划分的紧凑型复合图正交布局方法应用于对复合图进行正交布局，以便于绘制诸如电力设备调配图等复合图。本发明的计算机装置具有处理器以及存储器，存储器上存储有计算机程序，处理器通过执行该计算机程序实现基于网格划分的紧凑型复合图正交布局方法。
37.基于网格划分的紧凑型复合图正交布局方法实施例：
38.本实施例针对复合图进行正交布局，在复合图中需要布置多个设备，本实施例称为节点，在电力设备调配图中，各个节点均是实际的设备，因此，各个节点不能重叠。为了提高复合图的美观性，各个节点之间的连接线需要正交，且节点之间的总体连接线需要少交叉、少弯折。为了适应常见的显示器的显示需求，复合图的长宽比例接近16：9，需要成图美观、可读性要好。此外，根据电力设备的实际使用需要，例如开关类设备最好位置靠近且距离固定，在复合图中的一些节点是具有位置成组约束的要求，在这种情况下仍然需要复合图正交布局方法能够给出美观的布局图。
39.现有的布局方法中对于布局的美观性评价较为主观，因为涉及到图的美观性度量通常是一个很开放的问题，没有统一的标准。本实施例考虑到如果成图的边交叉少，图形阅读起来对人的视觉干扰就会小很多。如果不得不交叉，那么当交叉的角度最大，即90
°
正交交叉时，图的可读性会好很多。因此，本实施例基于总结出一些图的美观性评价的客观指标，如成图的边交叉数、相交的角度、边弯折数、边的总长度、图的对称度、图纸的充实度、图纸比例等，设定了客观的、可计算的美观度评价函数，利用该美观度评价函数对复合图的布局的美观度进行评价，从而使得图纸的美观度评价更加客观。
40.下面结合图3与图4对本实施例进行详细的说明。首先，执行步骤s1，获取图形初始数据。对复合图进行布局前，首先需要获取该复合图的基础数据，也就是图形初始数据，图形初始数据包括图形中节点的数量、节点属性、节点的约束关系、复合嵌套约束条件等，其中节点属性包括该节点与其他节点之间的连接关系、节点是否为实际上班节点还是虚拟节点、该节点能否与其他节点重叠等，当然，如果对节点的显示属性有要求，节点属性还包括节点的显示大小等。节点的约束关系包括节点之间的组合近邻，例如当前节点是否需要设置在另一节点一定范围内，或者当前节点与其他节点的位置之间的约束关系等。
41.然后，执行步骤s2，对图形初始数据进行预处理。对图形数据进行预处理时，需要对节点的大小进行处理，例如，对于有些节点大小是非整形的，采用向上取整函数，将节点的大小进行调整以使得节点大小为整形。此外，由于后续的计算引入了紧凑的压实函数全局优化，会导致节点之间完全没有间隔，同时也为了预留出一定的标注空间。在预处理时，设定了一个虚拟宽高操作的设置参数δ。例如，原先真实的节点的大小为宽20.4，高10.7，设定参数δ＝4，则预处理后的节点宽高分别为：宽＝21+δ＝25；高＝11+δ＝15。
42.然后，执行步骤s3，根据图形初始化数据对各个节点进行初始化布局。进行初始化布局时，并不需要将节点对齐，只需满足节点不重叠即可。例如，可以采用现有的力导向初始化法，还可以使用增量的方式广度优先放置带节点大小的初始化，以及尽可能保持节点间的邻接关系的拉普拉斯映射获取初始化布局。
43.进行了初始化布局之后，将依据各的节点初始位置坐标和大小，自适应地计算所要划分网格的大小以及单元格的大小，并更新网格标记矩阵gridmark。
44.具体的，参见图5，假设网格的大小就为8
×
18，即单元格的数量为8行、18列，在网格内有九个节点，其中网格内标有数字“1”的为第一个节点所在的位置，标有数字“2”的为第二个节点所在的位置，以此类推。这样，通过设置网格标记矩阵并且获取网格标记矩阵的信息，可以确定网格内哪些区域是空白区域，也就是哪些区域没有布置节点，这对于快速定位图形中空白的区域索引，搜索能否交换多个节点非常有帮助。
45.另外，在图5中画了两条虚线，这两条虚线均是以第一个节点左上角的单元格作为基准，沿横向和纵向画出的两条虚线，从图5可以看出，从第一节点沿横向看，可以看到第二节点、第四节点以及第五节点，而从第一节点沿横向看，可以看到第九节点，这些信息将记录为网格标记矩阵的信息，从一个节点沿横向、纵向所能够看到的节点被称为节点之间的相对可视信息，本实施例将该信息作为约束传入压实函数得到的全局优化，以便于能得到更好的布局解。
46.接着，执行步骤s4，对初始化布局后的图形进行美观度评分。本实施例采用两个函数对图形美观度进行评价，分别是距离函数以及弯折函数。
47.首先，本实施例需要计算初始图形中任意两个节点之间的距离函数值，并对初始图形中所有节点中任意两个节点之间的距离函数值求和，以求和值进行美观度评分。以两个节点xi以及xj为例，在获取两个节点xi、xj的坐标后，采用下面的距离函数计算两个节点之间的距离函数值：
[0048][0049]
其中，x
i1
表示节点xi在网格标记矩阵上的中心点横坐标，x
i2
表示节点xi的中心点纵坐标。w
i’表示节点xi在网格标记矩阵上所占的宽度，该宽度等于节点实际宽度wi+δ除以c，然后向上取整后所占的网格宽度整数，δ是最小间隔参数，c是网格的一个单元格的宽度，优选的，一个单元格是一个正方形，可以根据节点块输入的大小自适应的调整。式1中，h
i’表示节点xi在网格标记矩阵上所占的高度数，α是预设的超参数，用于调节欧式距离和对齐功能之间的比例。节点xj表示的含义类似，不再赘述。
[0050]
式1所计算的距离函数值越大，表示美观度越差，所计算的距离函数值越小，则表示美观度越好，这是因为距离函数的第一部分体现了两个具有拓扑连接的节点之间的欧式距离，若欧式距离太大，表明布局本身就会存在拓扑结构上局部近邻与实际位置相隔太远的矛盾，这种矛盾更会潜在的带来后续的弯折和交叉数的增多；第二部分是针对网格上所设计的对齐美观度量。
[0051]
针对复合图的其他节点，也采用式1计算其他任意两个节点之间的距离函数值，并且将所有的任意两个节点的距离函数值相加获得距离函数值总和，根据距离函数值总和考虑美观度。
[0052]
一个单元格的宽度c可以采用下面的公式计算：
[0053][0054]
其中，lmin＝min(min(wi+δ),min(hi+δ))，lmax＝max(max(wi+δ),max(hi+δ))，wi和hi分别是节点xi的宽度和高度，δ是最小间隔参数。进而，可以限制所有节点的总面积占整个网络画布的面积占比，例如是20％，在此基础上继续计算网格画布的长度、宽度，并计算画布需要多少个单元格，并且，每一行、每一列的单元格数据取整数。
[0055]
在计算距离函数值后，本实施例还计算每一节点的弯折函数值，其中，一个节点的弯折函数值是该节点以及与该节点具有拓扑连接的节点之间的弯折函数，本实施例需要计算所有节点的弯折函数值总和，以弯折函数值总和进行美观度评分。
[0056]
以设定的节点xi和xj为例，假设节点xi和xj具有拓扑连接关系，则需要计算节点xi、xj的弯折函数值。具体的，可以采用式2的公式计算：
[0057][0058]
其中，degree(vi)表示节点xi的度，即与其他节点连接的数目。e是图形的所有边的集合，β是预设的权参数。式3中，求和内分式表示节点xi、xj形成的向量与节点xi、x
j’形成的向量之间的夹角的正弦值，其中分子是两个向量的外积计算的模，分母是两个向量各自的模的乘积。节点x
j’是另一个与节点xi具有拓扑连接的节点。
[0059]
式3体现了多个点与节点xi连接时夹角的计算，若没有弯折则式3的结果最小，为0。
[0060]
通过上述两个函数，可以针对当前在网格标记矩阵上的节点位置的布局，因而能给出具体的美观度量化值，因此本实施例能够根据该可观的评分持续的对各个节点的布局进行优化。
[0061]
然后，执行步骤s5，对各个节点的位置的布局进行迭代优化。具体的，本实施例采用两种局部优化策略和一种全局压实优化模型对各节点的布局进行优化。
[0062]
其中，第一种局部优化策略是单点局部优化，就是针对单个节点，查找可能更加合适的位置，并进行优化。例如，在确定每个节点当前的布局位置后，假定每个节点下一步有更好的位置，这些位置与其具有拓扑结构连接的那些节点之间有非常大的近邻性质。换言之，节点xi的下步优化位置由当前与节点xi连接的所有节点的某种加权表示，同时为了不丢失上一步节点xi的信息，在下一步优化节点xi的位置时，只做局部范围内的搜索。本实施例中，搜索所有局部可放置节点xi的空白区域集合，并挑出比之前的位置具有最好的美观度对应的空白位置即可。
[0063]
第二种局部优化策略是多点交换局部优化，就是距离小于预设值的两个节点中，如果将两个节点的位置进行互换，计算位置互换后的两个节点后，美观度是否更佳。具体的，搜索与节点xi距离较近的局部区域内的其他节点，将搜索获得的其他节点与节点xi逐一
尝试交换，并挑出最佳交换的节点组，得到多点交换后的新的各个节点的位置。
[0064]
由于单独局部的优化策略很可能在少数次操作后，获得的解的质量就不再发生变化，因此，本实施例引入全局压实优化模型进行迭代优化。由当前各节点布局的相对位置，例如根据可视图的信息构造带多个约束的二次型压实模型，以横轴x方向压实为例，采用下面的公式进行计算：
[0065][0066]
其中s.t是约束条件，由图5所示的可视图的信息得到，当节点xi自左向右看到节点xj时，彼此应当保持的最小间隔距离为节点xi宽度的r倍。可以理解，该模型属于带约束的稀疏对称正定的二次型求解，因此优化代价很小，也就是计算量并不大。
[0067]
进行一次迭代计算后，执行步骤s6，对当前布局的图形进行美观度评分，也就是采用步骤s4的两个函数进行评分，并执行步骤s7，判断经过优化后，新的布局的美观度评分是否不再提升，例如，当前布局的美观度评分相比前一次评分更低，或者当前布局的美观度评分相比之前一次的美观度评分提升不超过3％，则可以认为美观度评分不再提升。如果当前迭代计算后美观度评分有明显提升，也就是步骤s7的判断结果为否，则返回执行步骤s5，继续进行优化迭代计算。如果当前迭代计算后的美观度评分不再提升，则是执行步骤s8，确定当前布局下各个节点的位置坐标信息。
[0068]
优选的，在循环迭代的过程中，还可以采用模拟退火算法进行迭代求解。本实施例中，模拟退火算法迭代求解是结合之前布局位置迭代优化时的局部优化和全局压实优化进行的。例如，在初始化布局后获得多个节点的初始位置坐标后，需设置初始的温度t，本实施例以力导向初始化为例，将初始温度设置，其中n为图形中节点的总数量。当然，如果相信初始化的布局效果已经很好，则初始温度t可设置的更小些。
[0069]
此后，在布局位置迭代优化时，局部优化策略搜索的范围为自身当前节点位置xi+rand(-t,t)的范围内做局部布局优化，其中rand为满足均匀分布的随机函数，取值在-t到t之间。同时，一次布局位置迭代结束后，温度t开始自动下降，t＝k
×
t，下降的系数其中maxiters为迭代器最大的迭代步数，可以看出k是一个大于0小于1的小数，在多次迭代后t的温度会衰减到0(退火)。
[0070]
此时，局部扰动的格式xi+rand(-0,0)就为上一步的xi。因此，当温度t＝0，全局优化也不再有布局改进，对于美观度评价整体上也不再有优化和提升，整体布局的迭代计算就会停止，并输出优化器给出的节点位置坐标。
[0071]
最后，执行步骤s9，根据得到的最优的节点位置坐标，结合正交路径连接器生成节点间边关系的正交走线规划，例如可以采用国际通用的已知的正交路径连接器进行正交走线规划，该正交路径连接器基于c++编写并且，内部实现基于a*算法。在获得正交线路规划后，执行步骤s10，对图形进行标注以及渲染，例如对各个节点进行标记，如标记节点的电力设备名称等，并执行步骤s11，输出最终的复合图。
[0072]
应用本发明的方法，由于采用了一个计算代价较小、代码实现容易的图布局美观度评估函数，因而能够快速、客观的对布局的美观度进行评价，并基于评价结果能够进行迭代计算，并能够确定迭代计算的终止条件，使得布局美观度评价更加客观，也便于自动化实现布局的迭代计算。另外，本发明基于网格划分法，采用了网格标记矩阵可快速定位空白区域位置和各节点的周边节点的放置情况，为布局优化提供了基础。此外，本发明给出了节点的单点局部优化策略和多点交换局部优化策略，由美观度反馈得分不断地优化迭代节点的布局位置，同时采用了压实函数的设计，考虑了可视图的相对位置约束，通过对压实函数二次型的优化产生紧凑的布局。
[0073]
需要说明的是，本实施例的复合图的正交布局应用成果并不限于绘制电力设备调配图，还可以应用于绘制其他的复合图，例如绘制流程图、软件工程中的uml类图、数据库管理中的er图、交通网络图、社交网络图、生物信息学或化学分子键构成图等，都可基于正交布局的方式自动化生成。同时，本实施例还可以用于创建vlsi(非常大规模的集成)设计，也可以用于pcb或电子元器件的设计布局。
[0074]
另外，本实施例在应用是还可以有更多的变化，例如，针对复合嵌套的节点的约束条件的满足，在优化的过程中采用局部空白区域的位置搜索下，将原本不满足的嵌套约束条件投影到局部约束位置解空间中，例如一组开关设备要求固定长度且只能同时沿横向或者竖直放置，则在局部搜索时确定该开关设备对投影到空白的向或者纵向的网格解当中。
[0075]
正交路径连接时，在获取上述的节点位置优化坐标后，执行边的正交布线操作，再经实际渲染和标注，得到最终的电网正交布局图纸。实际效果可以发现，结合全局压实优化以及局部优化策略下，整体对齐的效果、走线少交叉以及提高画布图纸的充实感等方面得到了很好的保证。
[0076]
计算机装置实施例：
[0077]
本实施例的计算机装置可以是计算机装置，例如是台式计算机、智能手机等，优选的，该计算机装置设有控制器以及存储器，存储器中存储有可在控制器上运行的计算机程序，且控制器执行计算机程序时实现上述基于网格划分的紧凑型复合图正交布局方法的各个步骤。
[0078]
例如，计算机程序可以被分割成一个或多个模块，一个或者多个模块被存储在存储器中，并由处理器执行，以完成本发明的各个模块。一个或多个模块可以是能够完成特定功能的一系列计算机程序指令段，该指令段用于描述计算机程序在终端设备中的执行过程。
[0079]
该控制器器可以是中央处理单元(central processing unit，cpu)，还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现成可编程门阵列(field-programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等，处理器是电器的控制中心，利用各种接口和线路连接整个电器的各个部分。
[0080]
存储器可用于存储计算机程序和/或模块，处理器通过运行或执行存储在存储器内的计算机程序和/或模块，以及调用存储在存储器内的数据，实现电器的各种功能。存储器可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能
所需的应用程序等；存储数据区可存储根据电器的使用所创建的数据等。此外，存储器可以包括高速随机存取存储器，还可以包括非易失性存储器，例如硬盘、内存、插接式硬盘，智能存储卡(smart media card,smc)，安全数字(secure digital,sd)卡，闪存卡(flash card)、至少一个磁盘存储器件、闪存器件、或其他易失性固态存储器件。
[0081]
计算机可读存储介质：
[0082]
计算机装置的存储器所存储的计算机程序如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明实现上述实施例方法中的全部或部分流程，也可以通过计算机程序来指令相关的硬件来完成，该计算机程序可存储于一计算机可读存储介质中，该计算机程序在被处理器执行时，可实现上述基于网格划分的紧凑型复合图正交布局方法的各个步骤。
[0083]
其中，计算机程序包括计算机程序代码，计算机程序代码可以为源代码形式、对象代码形式、可执行文件或某些中间形式等。计算机可读介质可以包括：能够携带计算机程序代码的任何实体或装置、记录介质、u盘、移动硬盘、磁碟、光盘、计算机存储器、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、电载波信号、电信信号以及软件分发介质等。需要说明的是，计算机可读介质包含的内容可以根据司法管辖区内立法和专利实践的要求进行适当的增减，例如在某些司法管辖区，根据立法和专利实践，计算机可读介质不包括电载波信号和电信信号。
[0084]
最后需要强调的是，本发明不限于上述实施方式，例如迭代优化的具体方法改变、或者单元格宽度的计算方法的改变等，这些改变也应该包括在本发明权利要求的保护范围内。

技术特征：
1.基于网格划分的紧凑型复合图正交布局方法，包括：获取图形初始数据，所述图形初始数据包括图形的节点数量、节点位置限制信息；对所述图形初始数据进行预处理；其特征在于：根据所述图形初始数据对各个所述节点进行初始化布局，自适应计算对图形进行布局所需要划分的网格大小以及单元格的大小，更新网格标记矩阵的信息；对初始化布局后的初始图形的美观度进行评分，对所述初始图形进行迭代优化计算，直到所述初始图形的美观度的评分不再提升，获得最终优化的图形中各个所述节点的位置坐标信息；根据各个所述节点的位置坐标信息生成各所述节点之间的边关系的正交线路规划，并进行标注以及渲染后获得正交布局图。2.根据权利要求1所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对初始化布局后的初始图形的美观度进行评分包括：计算所述初始图形中任意两个所述节点之间的距离函数值，并对所述初始图形中所有所述节点中任意两个所述节点之间的距离函数值求和，以求和值进行美观度评分。3.根据权利要求1所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对初始化布局后的初始图形的美观度进行评分包括：计算每一所述节点的弯折函数值，一个所述节点的弯折函数值为该节点以及与该节点具有拓扑连接的节点之间的弯折函数，计算所有所述节点的弯折函数值总和，以所述弯折函数值总和进行美观度评分。4.根据权利要求1至3任一项所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对所述初始图形进行迭代优化计算包括：确定一个目标节点的当前位置后，选取所述目标节点的更佳布局位置，计算所述目标节点在更佳布局位置下所述初始图形的美观度的评分值。5.根据权利要求1至3任一项所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对所述初始图形进行迭代优化计算包括：将所述初始图形中距离小于预设值的两个节点进行位置互换，计算进行节点位置互换后的所述初始图形的美观度的评分值。6.根据权利要求1至3任一项所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对所述初始图形进行迭代优化计算包括：构建带约束的二次型压实模型函数，对所述二次型压实模型函数进行求解，根据求解结果重新确定节点的位置，并根据重新确定的节点位置对所述初始图形的美观度进行评分。7.根据权利要求1至3任一项所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：对所述初始图形进行迭代优化计算时，模拟退火算法进行迭代求解。
8.根据权利要求1至3任一项所述的基于网格划分的紧凑型复合图正交布局方法，其特征在于：所述网格标记矩阵的信息包括所述网格标记矩阵的大小、每一所述节点在所述网格标记矩阵的位置、所述网格标记矩阵的空白区域、每一所述节点在横纵方向上的可视节点。9.计算机装置，其特征在于，包括处理器及存储器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时实现如权利要求1至8任一项所述的基于网格划分的紧凑型复合图正交布局方法的各个步骤。10.计算机可读存储介质，其上存储有计算机程序，其特征在于：所述计算机程序被处理器执行时实现如权利要求1至8任一项所述的基于网格划分的紧凑型复合图正交布局方法的各个步骤。

技术总结
本发明提供一种基于网格划分的紧凑型复合图正交布局方法、计算机装置及计算机可读存储介质，该方法包括获取图形初始数据；对图形初始数据进行预处理；根据图形初始数据对各个节点进行初始化布局，自适应计算对图形进行布局所需要划分的网格大小以及单元格的大小，更新网格标记矩阵的信息；对初始化布局后的初始图形的美观度进行评分，对初始图形进行迭代优化计算，获得最终优化的图形中各个节点的位置坐标信息；根据各个节点的位置坐标信息生成各节点之间的边关系的正交线路规划，并进行标注以及渲染后获得正交布局图。本发明还提供实现上述方法的计算机装置及计算机可读存储介质。本发明能客观评价布局的美观度，且实现代价较小。小。小。


技术研发人员：黄军军 吴勇涛 吴士泓 王志刚
受保护的技术使用者：远光软件股份有限公司
技术研发日：2023.05.23
技术公布日：2023/10/7