基于半边查环的面域生成方法、系统、设备及存储介质与流程

1.本发明涉及cad绘图领域，尤其涉及一种基于半边查环的面域生成方法、系统、设备及存储介质。


背景技术：

2.面域（region）实体是cad中比较常见的一种实体，可以通过选择平面上一系列的曲线实体构建。而现有的cad绘图过程中，面域的生成要求所选对象的所有线段需组成一个封闭图形才可完成，若线段间未完全闭合，则无法快速且准确地构成所需的面域实体。且传统的面域生成方法控制精度相对较差，导致存在极小的尖刺、小缝隙等不太理想的情况下不能正确求取环，甚至在求取环过程中环的数量不准确，导致无法准确构建面域的情况。


技术实现要素：

3.为了克服现有技术的不足，本发明的目的之一在于提供一种基于半边查环的面域生成方法，提升面域实体创建的效率和正确性。
4.本发明的目的之二在于提供一种cad绘制系统。
5.本发明的目的之三在于提供一种电子设备。
6.本发明的目的之四在于提供一种计算机可读存储介质。
7.本发明的目的之一采用如下技术方案实现：基于半边查环的面域生成方法，包括：响应于面域生成请求为非闭合的实体对象生成其对应的半边；其中，每条所述实体对象所属线段均包含两条起始方向相反的半边；按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件，将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。
8.进一步地，确定所述非闭合的实体对象的方法为：获取所述实体对象的起点坐标和终点坐标，将所述起点坐标和所述终点坐标进行比对，若二者重合，所述实体对象为闭合状态并直接形成环；若二者不重合则所述实体对象为非闭合的实体对象。
9.进一步地，查找下一条所述半边的方法为：将当前所述半边添加至当前查找环对应的栈中，判断是否存在任一所述半边与当前所述半边满足重合条件；所述重合条件为当前所述半边的终点位置与后一所述半边的起点位置之间的距离差在预设精度范围内；对满足重合条件的所述半边进行择优处理，将择优处理所得的所述半边进栈，并将其作为栈顶以继续查找其对应的下一条所述半边；其中，择优处理为计算满足重合条件的所述半边到当前所述半边的旋转角度，将旋转角度最小的所述半边作为择优处理结果；若当前所述半边不存在下一条所述半边，则将当前所述半边出栈。
10.进一步地，查找下一条所述半边时，若前一所述半边的终点位置与后一所述半边的起点位置之间的距离差在预设精度范围内，则自动对二者间的间隙进行填补。
11.进一步地，判断是否满足所述构环条件的方法为：判断所述栈中位于栈顶的所述半边的终点位置与位于栈底的所述半边的起点位置是否重合，若重合，则满足所述构环条件并将其所构成的环添加至环结果集中。
12.进一步地，若位于栈顶的所述半边的起点位置与位于栈底的所述半边的终点位置不重合，还包括：判断所述栈中位于栈顶的所述半边的终点位置是否与所述栈中其余所述半边的起点位置相重合，若重合，则构成子环并将其添加至所述环结果集。
13.进一步地，根据环生成对应的面域实体时，还包括：判断所述环结果集中是否存在多个环/子环重复，针对重复的环/子环仅生成一个所述面域实体。
14.本发明的目的之二采用如下技术方案实现：一种基于半边查环的面域生成系统，执行如上述的基于半边查环的面域生成方法，包括：半边构建模块，用于为非闭合的实体对象生成其对应的半边；所述实体对象所属线段包含两条起始方向相反的半边；构环判断模块，用于按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件；在构环过程中对不存在下一条半边的所述半边进行标记，并在顺序遍历过程中跳过存在标记的半边；面域生成模块，用于将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。
15.本发明的目的之三采用如下技术方案实现：一种电子设备，其包括处理器、存储器及存储于所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如上述的基于半边查环的面域生成方法。
16.本发明的目的之四采用如下技术方案实现：一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被执行时实现如上述的基于半边查环的面域生成方法。
17.相比现有技术，本发明的有益效果在于：本发明根据实体对象所属线段生成半边，通过半边对实体对象所属线段进行遍历递归以查找到所有的环，可提高面域实体创建效率；同时在查环过程中根据预设精度范围判断是否存在下一条半边，提高了半边查环的准确性。
附图说明
18.图1为本发明基于半边查环的面域生成方法的流程示意图；图2为本发明矩形实体对象的半边示意图；图3为本发明曲线对象的构环检测示意图；图4为本发明基于半边查环的面域生成系统的模块示意图。
具体实施方式
19.下面，结合附图以及具体实施方式，对本发明做进一步描述，需要说明的是，在不相冲突的前提下，以下描述的各实施例之间或各技术特征之间可以任意组合形成新的实施例。
20.实施例一本实施例提供一种基于半边查环的面域生成方法，通过对曲线的遍历递归查找到所有的环，并构建面域，从而提升面域实体创建的效率、正确性。
21.参照图1所示，所述方法具体包括如下步骤：步骤s1：响应于面域生成请求为非闭合的实体对象生成其对应的半边；步骤s2：按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件，将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。
22.面域生成请求是用户在cad绘画软件中选择需要生成面域的实体对象而生成的，用户选择的实体对象为包括直线段、圆、圆弧、椭圆弧、多段线、样条曲线等cad中的curve类型实体。由于用户选择的实体对象可能已经是闭合实体，因此需要对用户选择的实体对象进行分类，对于闭合实体直接根据其对应的线段生成面域；对于非闭合的实体，则获取其对应线段生成半边对象，并将其加入半边表中。
23.在一些实施例中，确定所述非闭合的实体对象的方法为：获取所述实体对象的起点坐标和终点坐标，所述起点坐标和所述终点坐标可根据所述实体对象的绘制顺序确定；将所述起点坐标和所述终点坐标进行比对，若二者重合，则说明所述实体对象为闭合状态，此时直接根据其线段形成环并生成对应面域；若二者不重合则所述实体对象为非闭合的实体对象，此时则使用本实施例方法进行半边查环。
24.本实施例中，每条所述实体对象所属线段包含两条起始方向相反的半边，举个例子，如图2所示，图2中带有箭头的线段则为半边；若所述实体对象为矩形，矩形端点包括a、b、c、d四个点，其所属线段包括四条矩形边；其中a、b两个端点所在线段对应的其中一条所述半边为以a点为起点、b点为终点的有向线段ab，另一条所述半边则是以b点为起点、a点为终点的有向线段ba；同理，其他矩形边所对应的半边则包括bc、cb、cd、dc、da和ad。
25.对于非闭合的实体对象获取其对应线段后生成半边，并将半边加入至半边表中；所述半边表除了用于存储半边对象，还需对半边表中所有半边进行排序，其排序方法为按照半边的起始点位置进行排序，以上述矩形的实体对象而言，其生成的八条半边经过排序后其顺序为ab、ad、da、dc、ba、bc、cb、cd。
26.遍历半边表，以当前半边为起始半边查找环，其具体方法为：将当前所述半边添加至当前查找环对应的栈中，所述栈用于存储查环过程中的半边，并将满足重合条件的半边加入至栈顶进行存储。
27.其中，判断是否满足所述重合条件的方法为：判断是否存在任一所述半边的起点位置与当前所述半边的终点位置之间的距离差在预设精度范围内；若当前所述半边的终点位置与一半边的起点位置临近且二者距离在预设精度范围内，则满足重合条件，将满足重合条件的所述半边进栈，并将其作为栈顶，将栈顶对象作为当前所述半边，继续查找当前所述半边的出边，即当前所述半边的下一条所
述半边；若当前所述半边不存在下一条所述半边，则对不存在下一条半边的所述半边进行标记，同时将当前所述半边出栈，查环计算过程中如果进行顺序遍历时发现该半边有标记则跳过该半边，不进行处理。
28.若在查找下一条所述半边时，找到两条或以上的所述半边与当前所述半边间满足重合条件，则分别计算每一条满足重合条件的所述半边旋转到当前所述半边的旋转角度，并将满足所述重合条件的多条所述半边进行旋转角度排序，优先选择旋转角度小的半边作为当前所述半边的下一条所述半边。
29.经过上述方法将满足条件的半边入栈后，每入栈一条半边都需对当前环对应的栈进行构环检测以判断是否满足所述构环条件，其方法为：判断所述栈中位于栈顶的所述半边的终点位置与位于栈底的所述半边的起点位置是否重合，若重合，则满足所述构环条件，代表栈中的有向半径可构成环，此时将其所构成的环添加至环结果集中。
30.若位于栈顶的所述半边的起点位置与位于栈底的所述半边的终点位置不重合，则进行子环检测，即判断所述栈中位于栈顶的所述半边的终点位置是否与所述栈中其余所述半边的起点位置相重合，若重合，则构成子环并将其添加至所述环结果集，并以所述栈中排列栈顶第二的所述半边作为当前半边，继续进行子环检测以找到其余子环；若不重合，则代表栈中的半边无法构成子环。
31.半边表中所有所述半边遍历完毕后，即可根据所述环结果集中记载的环或子环生成面域实体，若判断得知所述环结果集中存在多个环/子环重复，则可针对重复的环/子环仅生成一个所述面域实体，从而完成面域生成步骤。
32.在一些实施例中，查找下一条所述半边时，若前一所述半边的终点位置与后一所述半边的起点位置之间的距离差在预设精度范围内，则可自动对二者间的间隙进行填补，使得前一半边与后一半边连接起来，以便于后续面域填充等操作。
33.参照图2所示的矩形实体对象为例对上述面域生成方法进行说明：步骤1：对于矩形的实体对象而言，其四条线段生成八条半边，其经过排序后其顺序为ab、ad、da、dc、ba、bc、cb、cd；步骤2：置ab为当前半边，根据其终点b找到其可能的下一条半边为ba、bc，由于ba旋转到ab的旋转角度为180
°
，而bc旋转到ab的旋转角度为90
°
，根据旋转角度排序可选定下一条半边为bc，并将bc入栈；步骤3：将bc置为当前边，检查ab、bc是否构成环，因为c点和a点不重合，不构成环；再对二者进行子环检测，同样地两条半边不能构成子环；步骤4：根据bc的终点c点找到其对应的下一条半边为cd，检查d点和a点不重合，故ab、bc、cd不构成环，检查d点和b点不重合，不构成子环；步骤5：根据cd的终点d点找到其对应的下一条半边为da，由于da的终点与ab的起点重合，故ab、bc、cd、da构成环，并将其加入环结果集。
34.遍历完成可以获取两个环ab、bc、cd、da以及ba、ad、dc、ca两个环，由于两个环重复，故生成一个面域。
35.如图3所示，以曲线生成的部分半边为例，说明回溯和子环检测过程：步骤6：以a1b1为当前半边，根据其出点b1找到其可能的半边为b1c1、b1f1，以旋转
角规则选定下一条半边为b1f1，将b1f1置为当前半边；步骤7：根据当前半边b1f1的出点f1查找下一条半边，发现没有半边，故需要将b1f1丢弃，重新将a1b1设置为半边；步骤6、7过程即为回溯；步骤8：一直查找a1b1、b1c1、c1d1、d1e1、e1b1，当查找到e1b1时，将e1b1置为当前半边，发现b1和a1点不重合，故不构成环；发现e1b1和b1c1重合点为b1点，构成子环b1c1、c1d1、e1d1、e1b1，故将该子环加入结果集；步骤9：重新将a1b1设置为当前半边，重新查找下一条半边；步骤8、9即为子环检测过程。
36.本实施例通过半边的方式构建面域，一条曲线对应两条半边，通过半边进行查环；同时，基于半边的算法流程充分考虑了回溯、子环检测等情况，使得本实施例整体提高了面域生成方法的正确性以及效率。
37.实施例二本实施例提供一种基于半边查环的面域生成系统，如图4所示，包括：半边构建模块，用于为非闭合的实体对象生成其对应的半边；每条所述实体对象所属线段均包含两条起始方向相反的半边；构环判断模块，用于按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件；面域生成模块，用于将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。
38.本实施例的基于半边查环的面域生成系统执行如实施例一所述的基于半边查环的面域生成方法，可通过该系统进行cad绘制过程中自动对用户选择的实体对象生成对应的面域实体，提升面域实体创建的效率、正确性。
39.在一些实施例中，还提供一种电子设备，其包括处理器、存储器及存储于所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现实施例一中的基于半边查环的面域生成方法；另外，在一些实施例中还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被执行时实现上述的基于半边查环的面域生成方法。
40.本实施例中的系统、设备及存储介质与前述实施例中的方法是基于同一发明构思下多个方面，在前面已经对方法实施过程作了详细的描述，所以本领域技术人员可根据前述描述清楚地了解本实施例中的系统、设备及存储介质的结构及实施过程，为了说明书的简洁，在此就不再赘述。
41.上述实施方式仅为本发明的优选实施方式，不能以此来限定本发明保护的范围，本领域的技术人员在本发明的基础上所做的任何非实质性的变化及替换均属于本发明所要求保护的范围。

技术特征：
1.基于半边查环的面域生成方法，其特征在于，包括：响应于面域生成请求为非闭合的实体对象生成其对应的半边；其中，每条所述实体对象所属线段均包含两条起始方向相反的半边；按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件，将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。2.根据权利要求1所述的基于半边查环的面域生成方法，其特征在于，确定所述非闭合的实体对象的方法为：获取所述实体对象的起点坐标和终点坐标，将所述起点坐标和所述终点坐标进行比对，若二者重合，所述实体对象为闭合状态并直接形成环；若二者不重合则所述实体对象为非闭合的实体对象。3.根据权利要求1所述的基于半边查环的面域生成方法，其特征在于，查找下一条所述半边的方法为：将当前所述半边添加至当前查找环对应的栈中，判断是否存在任一所述半边与当前所述半边满足重合条件；所述重合条件为当前所述半边的终点位置与后一所述半边的起点位置之间的距离差在预设精度范围内；对满足重合条件的所述半边进行择优处理，将择优处理所得的所述半边进栈，并将其作为栈顶以继续查找其对应的下一条所述半边；其中，择优处理为计算满足重合条件的所述半边到当前所述半边的旋转角度，将旋转角度最小的所述半边作为择优处理结果；若当前所述半边不存在下一条所述半边，则将当前所述半边出栈。4.根据权利要求3所述的基于半边查环的面域生成方法，其特征在于，查找下一条所述半边时，若前一所述半边的终点位置与后一所述半边的起点位置之间的距离差在预设精度范围内，则自动对二者间的间隙进行填补。5.根据权利要求3所述的基于半边查环的面域生成方法，其特征在于，判断是否满足所述构环条件的方法为：判断所述栈中位于栈顶的所述半边的终点位置与位于栈底的所述半边的起点位置是否重合，若重合，则满足所述构环条件并将其所构成的环添加至环结果集中。6.根据权利要求5所述的基于半边查环的面域生成方法，其特征在于，若位于栈顶的所述半边的起点位置与位于栈底的所述半边的终点位置不重合，还包括：判断所述栈中位于栈顶的所述半边的终点位置是否与所述栈中其余所述半边的起点位置相重合，若重合，则构成子环并将其添加至所述环结果集。7.根据权利要求5或6所述的基于半边查环的面域生成方法，其特征在于，根据环生成对应的面域实体时，还包括：判断所述环结果集中是否存在多个环/子环重复，针对重复的环/子环仅生成一个所述面域实体。8.一种基于半边查环的面域生成系统，其特征在于，执行如权利1~7任一所述的基于半边查环的面域生成方法，包括：半边构建模块，用于为非闭合的实体对象生成其对应的半边；其中，每条所述实体对象所属线段包含两条起始方向相反的半边；
构环判断模块，用于按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件；在构环过程中对不存在下一条半边的所述半边进行标记，并在顺序遍历过程中跳过存在标记的半边；面域生成模块，用于将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。9.一种电子设备，其特征在于，其包括处理器、存储器及存储于所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现权利要求1~7任一所述的基于半边查环的面域生成方法。10.一种计算机可读存储介质，其特征在于，其上存储有计算机程序，所述计算机程序被执行时实现权利要求1~7任一所述的基于半边查环的面域生成方法。

技术总结
本发明公开了基于半边查环的面域生成方法、系统、设备及存储介质，所述方法包括：响应于面域生成请求为非闭合的实体对象生成其对应的半边；其中，每条所述实体对象所属线段均包含两条起始方向相反的半边；按照所述半边的起始点位置顺序遍历每个所述半边，根据当前所述半边的终点位置查找下一条所述半边并判断是否满足构环条件，将满足所述构环条件的所述半边构成环，再根据环生成对应的面域实体。本发明根据实体对象所属线段生成半边，通过半边对实体对象所属线段进行遍历递归以查找到所有的环，可提高面域实体创建效率；同时在查环过程中根据预设精度范围判断是否存在下一条半边，提高了半边查环的准确性。提高了半边查环的准确性。提高了半边查环的准确性。


技术研发人员：夏峰 孙凌云 张化伟 邹成伟 蔡爱平 何祎
受保护的技术使用者：广州中望龙腾软件股份有限公司
技术研发日：2022.04.21
技术公布日：2022/5/25