CN115526956A - 一种图形偏移方法 - Google Patents
一种图形偏移方法 Download PDFInfo
- Publication number
- CN115526956A CN115526956A CN202211121413.6A CN202211121413A CN115526956A CN 115526956 A CN115526956 A CN 115526956A CN 202211121413 A CN202211121413 A CN 202211121413A CN 115526956 A CN115526956 A CN 115526956A
- Authority
- CN
- China
- Prior art keywords
- arc
- polygon
- circular arc
- fitting
- tangent
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 20
- 230000005012 migration Effects 0.000 title abstract description 14
- 238000013508 migration Methods 0.000 title abstract description 14
- 238000004364 calculation method Methods 0.000 claims abstract description 19
- 230000001154 acute effect Effects 0.000 description 4
- 238000013461 design Methods 0.000 description 4
- 208000019300 CLIPPERS Diseases 0.000 description 1
- 230000004075 alteration Effects 0.000 description 1
- 208000021930 chronic lymphocytic inflammation with pontine perivascular enhancement responsive to steroids Diseases 0.000 description 1
- 238000011960 computer-aided design Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000001788 irregular Effects 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
- 238000013519 translation Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—2D [Two Dimensional] image generation
- G06T11/20—Drawing from basic elements, e.g. lines or circles
- G06T11/203—Drawing of straight lines or curves
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Analysis (AREA)
Abstract
本发明公开了一种图形偏移方法，包括以下步骤：步骤S1将带圆弧的第一多边形中的圆弧用直线段进行拟合，并将拟合圆弧与带圆弧的第一多边形中的直线段连接，形成直线的第二多边形；步骤S2对直线多边形做偏移计算，形成偏移后的第三多边形；步骤S3将第一多边形中的圆弧进行偏移形成缺口圆环；步骤S4将缺口圆环与第三多边形做相并运算。本发明可应用于EDA领域图形偏移运算的准确计算，可将原准确偏移运算的适用范围从直线段简单多边形推广到带圆弧的简单多边形，从而使得偏移的计算范围更大，精度控制更好。
Description
技术领域
本发明涉及电子设计自动化和计算机辅助设计领域，具体的涉及一种带圆弧多边图形的偏移方法。
背景技术
图形的偏移技术，是指输入一个任意合法多边形(例如为闭合的简单多边形)与一个偏移距离参数d，从而得到一个新的多边形，并且使得偏移后的多边形离偏移前的多边形的距离总是保持大于或等于给定的偏移距离参数d。
图形偏移技术在电子设计自动化(简称EDA)领域是非常重要的一环，比如设计规则检查DRC (简称DRC)检查会需要检查不同模块之间的距离从而满足最小距离的约束；一旦模块无法满足最小距离约束，就要对模块进行推挤，即减去当前模块的一部分甚至全部，从而满足最小距离约束。图形偏移技术能够保证尽量少的部分被减去，获得最佳被减大小。
图形的偏移会基于对每条边往偏移方向平移，来生成偏移后的多边形。单纯平移后，边与边之间无法相连形成完整多边形，通常需要利用圆弧过渡连接新的边得到带圆弧的多边形；或者通过延长平移后的边，求出边与边之间的新交点，通过夹角大小控制后再连接成完整多边形。比如Cadence公司的芯片设计软件Allegro Package Designer(简称APD)，是在对所有边往其法线方向进行外扩距离d平移，之后对于外凸的夹角，使平移后的边延长求出交点从而得到新的端点；而对于内凹的夹角，可以直接通过平移后的线段求出交点。在上述操作过后，可以得到一个初步的外扩多边形，之后APD对得到的多变形进行acute angle trim control(锐角控制)，即对于多边形的所有锐角，当锐角的两边间距超过一个预设好的阈值的时候，用自定义的形式来连接当前的间距，但无法保证外扩距离恒为d。
目前，已有图形运算库CGAL基于Minkowski sum(闵可夫斯基和)做成了理论意义上准确的多边形等距偏移。给定图形A,B∈R2，其Minkowski sum定义为：
即输入为2个多边形，然后基于其中一个多边形的所有端点为中心，画出另一个多边形的所有边，之后去除掉多余的边从而形成结果的多边形。基于Minkowski sum的offset是在以输入多边形为基础多边形，以外扩距离d为半径的圆为相加图形从而做成的准确版本偏移；而因为图形运算库 CGAL的所有边需要保证有理数(或有理代数数)的特性，而直接偏移圆弧会直接破坏有理特性，因此，图形运算库CGAL目前仅支持普通直线段多边形的偏移操作，并不支持带圆弧的多边形的偏移；类似的，图形库clipper本身只支持普通多边形，无法接受圆弧多边形作为偏移输入。
发明内容
本发明的目的在于克服现有图形偏移技术的缺陷，提供一种带圆弧多边图形准确偏移方法。不仅能够同时支持带圆弧多边形的偏移，而且偏移的圆弧也同样保证结果准确。
为了实现以上目的及其他目的，本发明是通过以下技术方案实现的：一种图形偏移方法，包括以下步骤：
步骤S1将第一多边形中的圆弧用直线段进行拟合形成拟合圆弧，并将所述拟合圆弧与第一多边形中的直线段连接，形成第二多边形；
步骤S2对第二多边形做偏移计算，形成偏移后的第三多边形；
步骤S3将所述第一多边形中的圆弧进行偏移形成缺口圆环；
步骤S4将所述缺口圆环与所述第三多边形做相并运算。
上述步骤S1中将带圆弧的多边形中的圆弧进行拟合，包括以下步骤：
步骤S11判断圆弧是否为外凸形态；
如果步骤S11的结果为是，执行步骤S12在圆弧上选取若干个端点，并将这些端点相连来拟合该圆弧，形成拟合圆弧；
如果步骤S11的结果为否，执行步骤S13在圆弧上选取若干个端点，做经过这些端点且与圆弧相切的切线，连接这些切线的交点来拟合该圆弧，形成拟合圆弧。
上述步骤S2中，圆弧为外凸形态，形成的拟合圆弧的偏移计算，包括如下步骤，在拟合圆弧每个端点上做以所述端点为圆心，偏移距离为半径的整圆，相邻两个圆切线，即为偏移后的边。
上述步骤S2中，圆弧为非外凸形态，形成的拟合圆弧的偏移计算，包括如下步骤，在拟合圆弧每个端点上做以端点为圆心的整圆上寻找连线起始点，经过起始点作整圆的切线，切线与整圆相切于起始点，且切线与整圆圆心的相连边平行；延长这条切线直到相交于下一个如此重复上述步骤的切线；对所有其他端点延续上述步骤，直到得到一个许多边以及整圆的集合。
本发明还提供一种系统，包括，至少一个处理器；以及
计算机可读存储介质，存储在由所述至少一个处理器执行时使所述系统执行以下操作的指令：
计算机可读存储介质，存储在由所述至少一个处理器执行时使所述系统执行以下操作的指令：
将第一多边形中的圆弧进行拟合，并将拟合圆弧与第一多边形中的直线段连接，形成第二多边形；
对第二多边形做偏移计算，形成偏移后的第三多边形；
将第一多边形中的圆弧进行偏移形成缺口圆环；
将缺口圆环与所述第三多边形做相并运算。
上述将带圆弧的多边形中的圆弧进行拟合，包括以下操作指令：
判断圆弧是否为外凸形态；
结果为是，在圆弧上选取若干个端点，并将这些端点相连来拟合该圆弧，形成拟合圆弧；
结果为否，在圆弧上选取若干个端点，做经过这些端点且与圆弧相切的切线，连接这些切线的交点来拟合该圆弧，形成拟合圆弧。
上述圆弧为外凸形态，形成的拟合圆弧的偏移计算，包括如下操作指令，在拟合圆弧每个端点上做以所述端点为圆心，偏移距离为半径的整圆，相邻两个圆切线，即为偏移后的边。
上述圆弧为非外凸形态，形成的拟合圆弧的偏移计算，包括如下操作指令，在拟合圆弧每个端点上做以端点为圆心的整圆上寻找连线起始点，经过起始点作整圆的切线，切线与整圆相切于起始点，且切线与整圆圆心的相连边平行；延长这条切线直到相交于下一个如此重复上述步骤的切线；对所有其他端点延续上述步骤，直到得到一个许多边以及整圆的集合。
与现有的技术相比，本发明的有益之处在于通过将所有圆弧拟合形成普通多边形，将被拟合的圆弧记录下来生成对应的偏移缺口圆环，对普通多边形采用偏移算法以后与偏移缺口圆环作相并运算得到最终图形，同时也是“闵可夫斯基和的准确值”，从而将原准确偏移运算的适用范围从直线段简单多边形推广到带圆弧的简单多边形，从而使得偏移的计算范围更大，精度控制更好。
下面结合附图对本发明作进一步的详细说明。
附图说明
图1显示为本发明图形偏移的方法步骤流程图。
图2显示为本发明将带圆弧的多边形中的圆弧进行拟合的的方法步骤流程图。
图3显示为本发明圆弧为凸形态偏移比对图。
图4显示为本发明圆弧为非凸形态偏移比对图。
图5显示为本发明一具体实施例中步骤S1和步骤S3的操作结果比对图。
图6显示为本发明一具体实施例中步骤S2的操作结果比对图。
图7显示为本发明一具体实施例中步骤S4的操作结果比对图。
图8显示为本发明带圆弧的第一多边形D1和偏移后的圆弧多边形D6的比对图。
具体实施方式
如图1所示，本发明一种图形偏移方法，所述图形为带圆弧的多边图形，包括以下步骤：
步骤S1：将所述图形中的第一多边形的圆弧用直线段进行拟合，并将拟合圆弧与带圆弧的多边形中的直线段连接，形成第二多边形。所述第一多边形为带圆弧的多边形，请参考图5，带圆弧的第一多边形D1中包含圆弧L11-L111等11条圆弧，这些圆弧被拟合后形成拟合圆弧 L12-L112，拟合圆弧L12-L112与带圆弧的多边形D1的直线段连接形成第二多边形D2，所述第二多边形D2为直线多边形。
如图2所示，步骤S1具体包括：步骤S11判断圆弧是否为外凸形态。该判断主要是相对于图形的内部来看，请参考图5，第一多边形D1中，相对与第一多边形D1内部，圆弧L11为外凸形态。圆弧L61为非外凸形态。
如果步骤S11的结果为是，执行步骤S12在圆弧上选取若干个端点，并将这些端点相连来拟合该圆弧，形成拟合圆弧。
如图3所示，在圆弧L11上选取若干个端点，例如端点P11、端点P21等，并将这些端点相连来拟合该圆弧，形成拟合圆弧L11’，而圆弧L12表示多边形往偏移后应该存在的位置；拟合圆弧L12’与圆弧L12为内接关系。
在拟合圆弧L11’每个端点上做以端点为圆心，偏移距离为半径的整圆，假如圆弧L11的半径为R，偏移距离为d，在理想状态下，对于外凸的圆弧L11，被偏移后的圆弧L12半径应为 R+d。
如果步骤S11的结果为否，执行步骤S13在圆弧上选取若干个端点，做经过这些端点且与圆弧相切的切线，连接这些切线的交点来拟合该圆弧，形成拟合圆弧。
如图4所示，在圆弧L61上选取若干个端点，例如端点P11、端点P21等，做经过这些端点且与圆弧相切的切线，连接这些切线的交点，形成拟合圆弧L61’，而圆弧L62表示多边形往偏移后应该存在的位置；拟合圆弧L62’与圆弧L62为外切关系。
偏移后的圆弧L62半径应为R-d。
在拟合圆弧L61’每个端点上做以端点为圆心的整圆上寻找连线起始点，经过起始点作整圆的切线，切线与整圆相切于起始点，且切线与整圆圆心的相连边平行；延长这条切线直到相交于下一个如此重复上述步骤的切线；对所有其他端点延续上述步骤，直到得到一个许多边以及整圆的集合，例如图4中拟合圆弧L62’。
将此过程中的所有切线边的端点设置为事件点，并将这些事件点存入到以x坐标从小到大的一个优先队列中，使用扫描线算法计算新的交点；
扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，把几何图形在计算机中的顶点表示法转换成点阵表示法，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。
将合法的边从而添加到结果图形中，并移除掉其他非法的边从而产生最终的结果图形。
合法的边是指切点及其周围的圆弧及和方偏移后的切线，其中以原本圆弧端点为圆心，半径为d的圆为非法的边；将合法的边添加到结果图形中以后，将以原本圆弧端点为圆心的圆移除，剩下的图形则为最终的结果图形。
步骤S2对第二多边形做偏移计算，形成偏移后的第三多边形。
请参考图6，第二多边形D2进行偏移后形成偏移后的第三多边形D4。该偏移算法使用例如闵可夫斯基算法，偏移后的第三多边形D4带有圆弧。
步骤S3将带圆弧的多边形中的圆弧进行偏移形成缺口圆环。
请参考图5，第一多边形D1进行偏移形成缺口圆环D3。
所有圆弧L11-L111，连接其圆心与圆弧端点(即原拟合线段的交点)并对线段进行延长，从而相交于偏移后应该形成的圆弧，将新相交的这两个交点分别与原本圆弧的端点相连接，同时连接上原本圆弧以及偏移后形成的圆弧，即将原本圆弧的位置向上偏移距离d，从而生成多个圆环L13-L113，并保留这些形状。
这里所说的即将原本圆弧的位置向上偏移d，仅是举出一个简单的例子。在具体的图形中，没有如此规范的圆弧形状，更多的是圆弧和线段所组成的不规则图形，在软件中无法对整体进行直接的上下偏移。
步骤S4将缺口圆环与第三多边形做相并运算；从而最终偏移图形会和缺口圆环因拟合弧线而产生锯齿边，最终形成完整版本的偏移后的圆弧多边形。如图7所示，第三多边形D4与缺口圆环D3做相并运算，最终形成完整版本的偏移后的圆弧多边形D6。为了更好的展现偏移效果，请参考图8。
尽管已经示出和描述了本发明的实施例,对于本领域的普通技术人员而言,可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型,本发明的范围由所附权利要求及其等同物限定。
Claims (8)
1.一种图形偏移方法，其特征在于，包括以下步骤：
步骤S1将第一多边形中的圆弧用直线段进行拟合形成拟合圆弧，并将所述拟合圆弧与第一多边形中的直线段连接，形成第二多边形；
步骤S2对第二多边形做偏移计算，形成偏移后的第三多边形；
步骤S3将所述第一多边形中的圆弧进行偏移形成缺口圆环；
步骤S4将所述缺口圆环与所述第三多边形做相并运算。
2.如权利要求1所述一种图形偏移方法，其特征在于，所述步骤S1中将带圆弧的多边形中的圆弧进行拟合，包括以下步骤：
步骤S11判断圆弧是否为外凸形态；
如果步骤S11的结果为是，执行步骤S12在圆弧上选取若干个端点，并将这些端点相连来拟合该圆弧，形成拟合圆弧；
如果步骤S11的结果为否，执行步骤S13在圆弧上选取若干个端点，做经过这些端点且与圆弧相切的切线，连接这些切线的交点来拟合该圆弧，形成拟合圆弧。
3.如权利要求2所述一种图形偏移方法，其特征在于，所述步骤S2中，圆弧为外凸形态，形成的拟合圆弧的偏移计算，包括如下步骤，在拟合圆弧每个端点上做以所述端点为圆心，偏移距离为半径的整圆，相邻两个圆切线，即为偏移后的边。
4.如权利要求3所述一种图形偏移方法，其特征在于，所述步骤S2中，圆弧为非外凸形态，形成的拟合圆弧的偏移计算，包括如下步骤，在拟合圆弧每个端点上做以端点为圆心的整圆上寻找连线起始点，经过起始点作整圆的切线，切线与整圆相切于起始点，且切线与整圆圆心的相连边平行；延长这条切线直到相交于下一个如此重复上述步骤的切线；对所有其他端点延续上述步骤，直到得到一个许多边以及整圆的集合。
5.一种系统，包括，至少一个处理器；以及
计算机可读存储介质，存储在由所述至少一个处理器执行时使所述系统执行以下操作的指令：
将第一多边形中的圆弧进行拟合，并将拟合圆弧与第一多边形中的直线段连接，形成第二多边形；
对第二多边形做偏移计算，形成偏移后的第三多边形；
将第一多边形中的圆弧进行偏移形成缺口圆环；
将缺口圆环与所述第三多边形做相并运算。
6.如权利要求5所述一种系统，其特征在于，将带圆弧的多边形中的圆弧进行拟合，包括以下操作指令：
判断圆弧是否为外凸形态；
结果为是，在圆弧上选取若干个端点，并将这些端点相连来拟合该圆弧，形成拟合圆弧；
结果为否，在圆弧上选取若干个端点，做经过这些端点且与圆弧相切的切线，连接这些切线的交点来拟合该圆弧，形成拟合圆弧。
7.如权利要求6所述一种系统，其特征在于，圆弧为外凸形态，形成的拟合圆弧的偏移计算，包括如下操作指令，在拟合圆弧每个端点上做以所述端点为圆心，偏移距离为半径的整圆，相邻两个圆切线，即为偏移后的边。
8.如权利要求7所述一种系统，其特征在于，圆弧为非外凸形态，形成的拟合圆弧的偏移计算，包括如下操作指令，在拟合圆弧每个端点上做以端点为圆心的整圆上寻找连线起始点，经过起始点作整圆的切线，切线与整圆相切于起始点，且切线与整圆圆心的相连边平行；延长这条切线直到相交于下一个如此重复上述步骤的切线；对所有其他端点延续上述步骤，直到得到一个许多边以及整圆的集合。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211121413.6A CN115526956A (zh) | 2022-09-15 | 2022-09-15 | 一种图形偏移方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211121413.6A CN115526956A (zh) | 2022-09-15 | 2022-09-15 | 一种图形偏移方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN115526956A true CN115526956A (zh) | 2022-12-27 |
Family
ID=84698475
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211121413.6A Pending CN115526956A (zh) | 2022-09-15 | 2022-09-15 | 一种图形偏移方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115526956A (zh) |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020035720A1 (en) * | 2000-09-19 | 2002-03-21 | Tamotsu Kitamura | Wiring editing method, for semiconductor package, capable of easily editing offset of wiring pattern |
| CN103970033A (zh) * | 2014-05-20 | 2014-08-06 | 河海大学常州校区 | 基于matlab实现机器人实体建模与叶片激光检测仿真的方法 |
| CN109887052A (zh) * | 2019-01-29 | 2019-06-14 | 广联达科技股份有限公司 | 一种二维多边形偏移方法 |
| US10627713B1 (en) * | 2018-10-19 | 2020-04-21 | Cadence Design Systems, Inc. | Checking minimum width, minimum distance and maximum curvature of planar region boundaries defined by arbitrary parametric curves |
-
2022
- 2022-09-15 CN CN202211121413.6A patent/CN115526956A/zh active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020035720A1 (en) * | 2000-09-19 | 2002-03-21 | Tamotsu Kitamura | Wiring editing method, for semiconductor package, capable of easily editing offset of wiring pattern |
| CN103970033A (zh) * | 2014-05-20 | 2014-08-06 | 河海大学常州校区 | 基于matlab实现机器人实体建模与叶片激光检测仿真的方法 |
| US10627713B1 (en) * | 2018-10-19 | 2020-04-21 | Cadence Design Systems, Inc. | Checking minimum width, minimum distance and maximum curvature of planar region boundaries defined by arbitrary parametric curves |
| CN109887052A (zh) * | 2019-01-29 | 2019-06-14 | 广联达科技股份有限公司 | 一种二维多边形偏移方法 |
Non-Patent Citations (2)
| Title |
|---|
| 潘意杰;陈晔;: "双重图形技术的优化设计", 机电工程, no. 12, 20 December 2008 (2008-12-20) * |
| 赵汝岩, 于胜春, 颜仙荣: "曲线偏移算法在CAD软件中的应用", 计算机工程与设计, no. 02, 28 February 2005 (2005-02-28) * |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20070080966A1 (en) | Appropriately rendering a graphical object when a corresponding outline has exact or inexact control points | |
| CN110689492B (zh) | 图像边缘平滑方法和装置 | |
| JP2008299627A (ja) | 情報処理方法及び装置、プログラム、記憶媒体 | |
| CN114266800B (zh) | 一种平面图形的多矩形包围盒生成方法及系统 | |
| CN103810739A (zh) | 一种图像文字变形动画的生成方法 | |
| US9922623B2 (en) | Emboldening of outline fonts | |
| JP4378208B2 (ja) | 情報処理装置及び情報処理方法 | |
| CN113096147B (zh) | 一种基于matlab的激光标记阴影的自动生成方法 | |
| CN115526956A (zh) | 一种图形偏移方法 | |
| US9779528B2 (en) | Text realization | |
| EP1600895B1 (en) | Rendering font characters when a corresponding outline lacks control points | |
| US7292249B2 (en) | Appropriately rendering a graphical object when a corresponding outline has excessive control points | |
| CN116843861A (zh) | 一种三维模型简化方法 | |
| JP2005079392A (ja) | 描画データ作成方法 | |
| CN115222579A (zh) | 一种扫描转换点阵数据的方法、装置及介质 | |
| CN115619915A (zh) | 三维模型贴图方法、装置、存储介质及电子设备 | |
| CN115359502A (zh) | 一种图像处理方法、装置、设备以及存储介质 | |
| CN114119708A (zh) | 生成树结构的方法、装置、计算设备及存储介质 | |
| West et al. | Multistage combined ellipse and line detection | |
| CN110599598A (zh) | 一种统一异构数据的方法和装置 | |
| US20050160390A1 (en) | Cloned and original circuit shape merging | |
| US20240419990A1 (en) | Computer-readable recording medium storing correspondence relationship determination program, correspondence relationship determination method, and information processing device | |
| CN110032718B (zh) | 一种表格转换方法、系统和存储介质 | |
| US20250124681A1 (en) | Method, System, Medium, and Device for Digitally Generating Protective Cases for Three-Dimensional Models | |
| US6995766B2 (en) | Hierarchical lattice generating method, apparatus, and storage device storing a program thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |