一种基于两阶段网格索引和局部计算的AutoCAD图形裁剪方法、计算机设备及存储介质与流程

本发明涉及计算机辅助设计，特别是涉及一种在autocad环境中基于两阶段网格索引和局部计算的图形裁剪方法、计算机设备及存储介质。

背景技术：

1、在autocad等计算机辅助设计软件中，图形裁剪是核心编辑功能之一，用于删除指定裁剪边界之外的图形部分。传统的图形裁剪方法采用边界与对象逐一求交的算法，每一个候选对象都需要与复杂的裁剪边界进行精确几何求交，其计算复杂度为o(n×m)，其中n为图形对象数量，m为边界复杂度。该类方法存在计算效率低、cpu与内存占用高、对样条曲线与椭圆以及填充图案等复杂对象求交困难的问题。

2、现有的通用图形裁剪算法，如cohen-sutherland线段裁剪算法、liang-barsky算法、sutherland-hodgman算法、weiler-atherton算法、greiner-hormann算法以及vatti算法等，多采用全局遍历的方式，计算复杂度随图形对象数量线性甚至平方增长。研究表明，在多边形裁剪中求交计算往往占据总运行时间的约80%，且部分算法在处理顶点落于边上的退化相交时存在困难。在面对autocad中海量图形数据时，上述算法难以满足性能需求。

3、在所有基于网格的方法中，网格粒度即网格单元的尺寸对性能具有决定性影响：网格过密会浪费内存并增加网格枚举开销，网格过疏则会使每个网格内的边界线段过多、筛选失效。然而，现有技术对网格粒度的确定方式较为粗糙：其一，多采用单一变量的经验规则，例如以所有边的平均边长作为网格尺寸，或要求网格尺寸不小于最大对象尺寸的1.5倍；其二，少数方法采用数值最小化的代价函数，融合对象最小外接矩形尺寸、查询窗口尺寸与网格尺寸求取最优网格尺寸，但其为数值搜索而非闭式表达，且为各向同性的正方形网格，并未纳入边界复杂度密度、图形长宽比以及对象密度等物理量；其三，更简单的方案直接按图形范围是否超过某一固定阈值在两个固定网格尺寸之间二选一。此外，上述网格一经依据裁剪边界的静态属性建成后即固定使用，与后续的快速筛选及裁剪过程相互独立，无法依据运行时实际产生的剔除率、平均求交次数、网格负载分布等几何统计量对网格粒度进行反馈修正。

4、由此，现有技术至少存在以下缺点：

5、其一，网格粒度的评价准则维度单一、不精确：现有粒度确定方式多依据单一经验变量或数值搜索，未融合边界复杂度密度、图形长宽比与对象密度等多个物理量，且多采用各向同性的正方形网格，难以匹配狭长或形状复杂的裁剪边界，易导致网格过密或过疏；

6、其二，网格索引的构建与快速筛选及裁剪过程相互独立、缺乏反馈：网格一经建立即固定使用，无法依据运行时的剔除率、平均每对象求交的边界线段数与网格负载分布对网格粒度进行自适应修正，对图形对象空间分布不均的图纸适应性差，难以同时兼顾索引内存与剔除效率；

7、其三，经典裁剪算法采用全局遍历，复杂度随对象数量增长，求交计算占比高，且地理信息系统的网格方法面向栅格或点云数据，难以直接用于autocad多类型矢量图元的精确裁剪。

8、因此，研发一种网格粒度自适应、索引与筛选裁剪相互耦合、通用性强的autocad图形快速裁剪方法很有必要。

技术实现思路

1、本发明的目的在于克服现有技术的不足，提供一种基于两阶段网格索引和局部计算的autocad图形裁剪方法、计算机设备及存储介质，以解决现有网格类裁剪方法中网格粒度评价准则维度单一、不精确且多为各向同性，难以匹配狭长或复杂边界而造成网格过密或过疏的问题，以及网格索引一经建立即固定、与快速筛选及裁剪过程相互独立、缺乏运行时反馈，对图形对象空间分布不均的图纸适应性差、无法兼顾索引内存与剔除效率的问题。

2、为实现上述目的，本发明采用如下技术方案。

3、一种基于两阶段网格索引和局部计算的autocad图形裁剪方法，包括以下步骤：

4、一种基于两阶段网格索引和局部计算的autocad图形裁剪方法，获取autocad数据库中的一条封闭的二维多段线作为裁剪边界，将所述裁剪边界离散为边界线段并计算所述裁剪边界的外接矩形；根据待裁剪的图形对象的数量以及所述边界线段和所述外接矩形的几何量确定网格粒度，以所述网格粒度在所述外接矩形上建立二维网格，并建立将网格坐标映射到穿过该网格的边界线段的网格索引关系表；对所述待裁剪的图形对象中的至少一部分进行试处理，依据试处理得到的几何筛选统计量按预设的反馈修正公式更新所述网格粒度并重建所述网格索引关系表，重复所述更新直至所述网格粒度的相对变化小于收敛阈值或迭代次数达到上限，使所述网格粒度的确定与所述图形对象的筛选和裁剪形成闭环耦合；遍历所述待裁剪的图形对象，对于每一图形对象，将其包围盒覆盖的网格集合与所述外接矩形的网格坐标范围进行比较，或查询所述网格索引关系表，判定并删除位于所述裁剪边界之外的图形对象；对未被删除的图形对象，查询所述网格索引关系表以获取与其所占网格相关的边界线段子集，仅针对所述边界线段子集执行与该图形对象的精确几何求交与裁剪操作。

5、优选地，确定所述网格粒度的公式：

6、

7、式中，gbase为基准粒度，abox为所述外接矩形的面积且满足，wbox与hbox分别为所述外接矩形的宽与高，lb为各所述边界线段的总长，nseg为各所述边界线段的总数，nobj为所述待裁剪的图形对象的数量，κ为整定系数，其取值为0.6至1.4；

8、所述基准粒度依据所述外接矩形的长宽比按下式分解为x方向粒度δx与y方向粒度δy：

9、

10、

11、该分解保持网格单元的面积等于基准粒度的平方，并使所述二维网格在行方向与列方向上的网格数量相当，从而在狭长边界下显著减少空网格；其后将δx与δy分别取整并限制在预设的粒度下限gmin与粒度上限gmax之间。

12、优选地，所述反馈修正公式为：

13、

14、式中，gbase(t)为基准粒度的第t次迭代值，为基准粒度的第t+1次迭代值，二者按上式更新，mavg、ηrej、dload分别为第t次迭代统计得到的平均每对象求交的边界线段数、剔除率与命中网格负载方差，mtar、ηtar、dtar分别为其目标值，γ为反馈增益系数；当满足下式时停止迭代：

15、

16、式中，εconv为收敛阈值；所述剔除率的目标值取值为0.80至0.90，所述平均每对象求交的边界线段数的目标值取值为8至16，γ取值为0.2至0.5，所述收敛阈值取值为0.02至0.05，迭代次数的上限取值为2至3。

17、优选地，所述图形对象包括填充图案，针对所述填充图案的所述精确几何求交与裁剪操作进一步包括：提取所述填充图案的至少一个边界环；将每一个所述边界环作为一条封闭的二维多段线，递归地应用本发明所述的边界离散、网格索引构建与精确求交裁剪的处理方法进行裁剪，得到裁剪后的至少一个新边界环；以及利用裁剪后得到的全部新边界环重新生成一个新的填充图案对象，并设置与所述填充图案相同的样式属性。

18、优选地，所述将每一个所述边界环作为一条封闭的二维多段线递归地应用所述边界离散、网格索引构建与精确求交裁剪的处理方法进行裁剪，具体为一种双向顺序裁剪法，包括：第一裁剪步骤，以所述边界环为裁剪对象、以所述裁剪边界为裁剪边界执行裁剪；第二裁剪步骤，以所述裁剪边界为裁剪对象、以所述边界环为裁剪边界执行裁剪；以及环合成步骤，合并两次裁剪所得的全部边界段以形成裁剪后的新边界环。

19、优选地，在计算所述外接矩形之前还包括图元标准化步骤：将所述autocad数据库中的三维多段线对象与二维多段线对象转换为轻量化的多段线对象，以统一后续求交计算的数据格式。

20、优选地，在判定位于所述裁剪边界之外的图形对象时，通过并行计算同时对多个所述待裁剪的图形对象进行网格覆盖判断与筛选。

21、优选地，所述建立网格索引关系表包括采用射线步进法计算各所述边界线段所穿过的全部网格，所述网格索引关系表将网格坐标映射到穿过该网格的边界线段的索引的集合。

22、优选地，所述判定并删除位于所述裁剪边界之外的图形对象包括：当该图形对象所覆盖网格集合的最大行坐标小于所述外接矩形的最小行坐标、或最小行坐标大于所述外接矩形的最大行坐标、或最大列坐标小于所述外接矩形的最小列坐标、或最小列坐标大于所述外接矩形的最大列坐标时，判定该图形对象位于所述裁剪边界之外并删除；当不满足上述条件时，进一步查询所述网格索引关系表，若该网格集合与记录有边界线段的网格均无交集，则判定该图形对象位于所述裁剪边界之外并删除。

23、优选地，所述精确几何求交与裁剪操作包括：计算所述图形对象与所述边界线段子集的交点，对所述交点进行去重，当两个交点之间的距离小于容差阈值时删除其中一个交点；根据去重后的交点对所述图形对象进行分割，得到分割后的子对象；以及计算所述子对象的中点，通过判断所述中点与所述裁剪边界的位置关系决定所述子对象的保留或删除。

24、优选地，所述图形对象还包括圆、圆弧、样条曲线、椭圆、文字、图块中的至少一种。

25、优选地，建立所述网格索引关系表时还建立排序索引字典，所述排序索引字典的键为网格行坐标，值为该行坐标在所述网格索引关系表中的起始查找位置，用于加速网格查询。

26、本发明还提供一种计算机设备，包括存储器、处理器及存储在所述存储器上并能够在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述任一项所述方法的步骤。

27、本发明还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述任一项所述方法的步骤。

28、本发明的有益效果如下：

29、其一，显著提升性能：快速预筛选阶段可排除百分之七十至百分之九十的图形对象，极大减轻精确计算负担；通过网格索引将o(n×m)的全局求交复杂度降低为近乎o(nlogm)或更优的局部求交，在面对大量图形对象或复杂边界时性能提升尤为明显。

30、其二，普适性强：该方法不依赖于特定图形类型，可处理直线、曲线、文字、填充等各种autocad图元，具有广泛的适用性。

31、其三，准确性高：快速筛选阶段仅用于排除明显位于外部的对象，精确裁剪阶段仍采用严格的几何算法，保证了裁剪结果的准确性。

32、其四，资源友好：减少了大量不必要的复杂计算，降低了cpu与内存的峰值消耗，内存占用减少百分之六十以上，显著降低cpu峰值占用率。

33、其五，网格粒度自适应且各向异性：所述网格粒度公式融合外接矩形面积、边界线段总数与总长、对象数量并经各向异性分解纳入长宽比，输出在行列方向网格数相当的各向异性网格，相比单变量经验规则、数值搜索代价函数及各向同性网格的现有粒度确定方式更为精确，可显著减少空网格。

34、其六，闭环自整定：依据运行时的剔除率、平均每对象求交的边界线段数与命中网格负载方差反向修正基准粒度并重建索引，无需人工设定网格尺寸即可对任意图纸自整定。

35、尤其需要指出的是，所述网格粒度公式与所述闭环反馈调整步骤相互耦合所产生的整体技术效果，超越了二者单独实施时效果的简单加和。单独使用所述网格粒度公式时，其仅依据外接矩形与边界的静态属性以及对象总数计算粒度，无法感知待裁剪图形对象相对裁剪边界的实际空间分布，对分布不均的图纸往往欠筛或过密；单独使用所述闭环反馈而从任意初值如固定经验阈值起调时，每次迭代均需付出一次完整的索引重建与试处理代价，且在命中网格负载方差较大时易发生振荡、收敛缓慢。而二者耦合后，所述网格粒度公式为反馈环提供了一个已捕获图纸静态结构即幅面尺度、边界复杂度与对象规模的近最优初值，反馈环仅需校正所述公式无法观测的对象分布残差，因而通常在一至二次迭代内即收敛，并同时达到索引内存最小与剔除率最高的双优状态，即获得一种无需人工设定网格、对任意图纸自整定的网格索引；这一近最优初值加少量反馈校正的协同效果，是单独实施所述网格粒度公式或单独实施所述闭环反馈所无法获得的。