基于橡皮筋划线后的多边形区域填充算法(有序边表)
2021/5/20 14:27:49
本文主要是介绍基于橡皮筋划线后的多边形区域填充算法(有序边表),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
如图对围出的多边形进行填充:
图(1)
结果如下:
图(2)
填充利用到扫描线算法
扫描线算法基本思想:
用水平扫描线从上到下(从下到上)扫描多条首位相连的线段构成的多边形,每根扫描线与线段产生交点。将交点按x坐标排序两两一对作为端点,将其中的点进行填色。多边形扫描完毕后,颜色填充完成。
填充基本步骤:
1⃣️:求交点
2⃣️:交点排序
3⃣️:颜色填充
这里求交点方法很多,我使用的是以斜率的倒数作为增量的方法求扫描线与多边形的交点(此方法避免了多次求交运算,大大减少计算量)
观察上图多边形,这里以上图多边形为例建坐标系,如下图,简单介绍一下增量求交的算法,绿色代表扫描线
图(3)
例如现在扫描线1与多边形有一个交点p1,用增量的方法求交点p2的坐标,我们发现y轴方向坐标变化很简单直接加1,而x轴方向两坐标之间的区别就是p2.x = p1.x + 1/k(p1,p2),及两交点之间横坐标差值为所在直线斜率的倒数k(p1,p2)=(y2-y1)/(x2-x1).
从一般的直线表达式推导一下,假设多边形某条边所在的直线方程是:ax + by + c = 0,
扫描线yi和下一条扫描线yi+1与该边的两个交点分别是(xi,yi)和(xi+1,yi+1),
则可得到以下两个等式: axi + byi + c = 0 (等式 1)
axi+1 + byi+1 + c = 0 (等式 2)
由等式1可以得到等式3: xi = -(byi + c) / a (等式 3)
由等式2可以得到等式4: xi+1 = -(byi+1 + c) / a (等式 4)
由等式 4 – 等式3可得到: xi+1 – xi = -b (yi+1 - yi) / a
由于扫描线存在yi+1 = yi + 1的关系,
将代入上式即可得到:xi+1 – xi = -b / a 即△x = -b / a,是个常量(直线斜率的倒数。
下面利用适当的数据结构对多边形的边、点进行存储,首先介绍“活动边表”AET,AET中存储当前交点的横坐标 x,斜率的倒数(增量)△x,以及当前扫描线与多边形相交的边的最高点ymax。每条边都和扫描线有个交点,扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时,根据△x直接计算出新扫描线与边的交点x坐标,可以避免复杂的求交计算。一条边不会一直待在“活动边表”中,当扫描线与之没有交点时,要将其从“活动边表”中删除,判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐标值,为此,需要记录边的y坐标的最大值。
设置边表集的如下结构体:
typedef struct XET { float x; float dx,ymax; struct XET* next; }AET,NET;
扫描线5对应的“活动边表”由P4P3 、P4P2组成对应的“活动边表”如下图:
图(4)
为了方便活动边表的建立与更新,我们为每一条扫描线建议一个“新边表”NET,新边表与活动边表之间的具体操作:当算法处理到某条扫描线时,将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。
而建立“新边表”的规则就是如果某条边的较低端点(y坐标较小的那个点)的y坐标与扫描线y相等,则该边就是扫描线y的新边,应该加入扫描线y的“新边表”(内容与活性边表的内容一样 x △x ymax)。上例中各扫描线的“新边表”如下图所示:
图(5)
更新的例子:观察扫描线5 所对应的活动边表(图4),不难发现,对应的交点横坐标x正是上一个扫描线4对应AET节点的x +△x ,扫描线4所对应的交点横坐标为:1 、23/3 —>扫描线5所对应的交点横坐标为:(1+1)、(23/3 - 2/3)
AET NET初始化代码如下:
//初始化AET表,即初始化活跃边表 AET *pAET = new AET; pAET->next = NULL; //初始化NET表,即初始化边表 NET *pNET[1024]; for( i = MinY;i <= MaxY; i++ ) { pNET[i] = new NET; pNET[i]->next = NULL; }
AET更新代码以及填充代码如下:
//建立并更新活性边表AET for( i = MinY; i <= MaxY; i++ ) { //i表示每一个扫描线 //计算新的交点x,更新AET NET *p = pAET->next; while( p != NULL ) { p->x = p->x + p->dx; p = p->next; } //更新后新AET先排序/ AET *tq = pAET; p = pAET->next; tq->next = NULL; while( p != NULL ) { while( tq->next != NULL && p->x >= tq->next->x ) { tq = tq->next; } NET *s = p->next; p->next = tq->next; tq->next = p; p = s; tq = pAET; } //先AET表中删除ymax==i的结点,对多边形顶点的处理,将顶点排除在填充区间外,删除边的终点以平衡交点的奇偶个数 AET *q = pAET; p = q->next; while( p != NULL ) { if( p->ymax == i) { q->next = p->next; delete p; p = q->next; } else { q = q->next; p = q->next; } } //扫描线遇到端点,将NET中的新点加入AET,并用插入法按X值递增排序 p = pNET[i]->next; q = pAET; while( p != NULL ) { while( q->next != NULL && p->x >= q->next->x) { q = q->next; } NET *s = p->next; p->next = q->next; q->next = p; p = s; q = pAET; } //配对填充颜色 p = pAET->next; while( p != NULL && p->next != NULL ) { for(float j = p->x;j <= p->next->x; j++) { glVertex2i(static_cast<int>(j),i); } p = p->next->next;//考虑端点情况,解决端点填充出界问题 } }
这篇关于基于橡皮筋划线后的多边形区域填充算法(有序边表)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)