第18卷 第1期1998年2月北京理工大学学报Jo urnal of Beijing Instit ute o f T echnolog y V ol.18 N o.1Feb.1998收稿日期:1996-09-25
确定两个任意多边形的并的算法
周培德 王文明
(北京理工大学计算机科学与工程系,北京 100081)
摘 要 目的 设计并分析求两个任意多边形的并的一种新算法.方法 利用分治思想设
计算法,即根据P ,Q 凸壳及P 与Q 的凸壳的不同位置关系,分6种情况分别求并P ∪Q 的
边界.结果 成功设计出新的算法并分析出该算法的时间复杂性为O (n +m )次判断两条线
段是否相交,其中n ,m 分别是多边形P 与Q 的顶点数.结论 该算法优于逐次判断P 的每
条边是否与Q 的边相交的方法.
关键词 简单多边形;两个多边形的并;复杂度
分类号 T P 301
求两个任意多边形的并是计算几何中的基本问题之一,该问题的一种特殊情况是求两个矩形的并及多个矩形的并[1]
.在超大规模集成电路的辅助设计和数据库中的并发控制等领域中常出现上述问题.因此研究这一问题的快速解法具有实际的应用价值.求两个任意多边形的并的一种方法是逐次判断多边形P 的每条边是否与多边形Q 的边相交,这种方法需要nm 次判断两条线段是否相交.本文中提出的算法是基于分治思想设计的,该算法首先求出P ,Q 及P 与Q 的凸壳,然后分6种不同情况分别求P ∪Q 的外围边界及P ∪Q 内空洞的边界.特别是第6种情况,把P 与Q 的凸壳顶点及求出的交点分成两种不同类型来处理.这种方法只需要O (n +m )次判断两条线段是否相交,因而减少了所需要的计算时间.另外,该算法比采用求解线性方程组的方法也优越得多.
给定多边形P 的顶点序列p 1,p 2,…,p n 及多边形Q 的顶点序列q 1,q 2,…,q m ,它们的边界分别为p 1p 2,…,p n -1p n ,p n p 1及q 1q 2,…,q m -1q m ,q m q 1.通常,多边形表示边界和内部区域的并.若简单多边形P 的内部区域是凸集,则此简单多边形是凸的.如果P 和Q 是两个任意简单多边形,那么P 和Q 的并定义为
P ∪Q ={z z ∈P 的内域及边界或者z ∈Q 的内域及边界}1 算法描述
算法1 确定两个任意简单多边形的并的算法
输入 多边形P 的顶点序列(p 1,p 2,…,p n )与多边形Q 的顶点序列(q 1,q 2,…q m ).输出 P ∪Q 的顶点序列
88北 京 理 工 大 学 学 报第18卷
步1 求P的凸壳C1[2],Q的凸壳C2及P与Q的凸壳C.设C1={p1,p2,…,p i-1,P i},求P′={p i,p i+1,,…,p n,p1}的凸壳C′1,求P′与Q的凸壳C′.
步2 if‖C1‖=n∧q1,q2,…,q m全在C1内 then P∪Q=P,终止.
步3 if C={p i,p i+1,…,q j,q i′,q i′+1,…,q j′}∧{p1,p2,…,p i-1,p j+1,…,p n}中点不在 C2[3]内∧{q1,q2,…,q i′-1,q j′+1,…,q m}中点不在C1内[3]
then P∪Q=p与Q,终止.
else if p k(k=1,i-1,j+1,n)在C2内∨q k′(k′=1,i′-1;j′+1,m)在C1内
then 求p k-1p k,p k p k+1与Q边的交点[3];q k′-1q k′,q k′q k′+1与P边的交点;p k-1p k, p k p k+1,与q k′-1q k′,q k′q k′+1的交点.从p i出发,沿P边行进,碰到交点,改
沿Q边行进,再碰到交点,改沿P边行进,直至回到p i(称巡回方法).
此点列即P∪Q的边界点序列.从Q外剩余的P点出发,用巡回方法找回
空洞边界点列.终止.
如无交点,则P∪Q=P与Q,终止.
步4 if q1,q2,…,q m在C1内∧‖C1‖ else if C′中轮流出现P′与Q的顶点 then 用步7中方法求P′边与Q边的交点.从C1中的P边出发,用巡回方法找点序列;再由剩余P点出发,用巡回方法找点序列(后者为空洞部分). 上述点序列围成的域即所求的并,终止. 如无交点,则P∪Q=P,终止. 步5 if q1,q2,…,q m不在P内∧p1,p2,…,p n不在Q内∧‖C1‖=n∧‖C2‖=m∧‖C‖=n+m then 在C中求相邻P,Q顶点关联的边的交点,用巡回方法找并.终止. 步6 if‖C1‖=n∧‖C2‖=m∧‖C‖ 步6.1w hile p i与q j+h(p i+l与q j)是C中相邻的顶点 do if 与p i(p i+l)关联的P边和与q j+h(q j)关联的Q边相交 then 求出交点r k;p i r k q j+h(p i+l r k q j)组成子点列.go to 步6.2 else if 与p i关联的点p i′(∈C1)首次出现在Q内∧与q j+h关联的点q j′+h(∈C2)首次出现在P内 then 与p i′,q j′+h关联的边相交,求出交点r k;r k与p i,q j+h等组成子点列: p i,…,r k,…,q j+h go to步6.2 else if p1,p2,…,p i-1,p i+l+1,…,p n不在C2内∧q1,q2,…,q j-1,q j+h+1,…, q m不在C1内 then P∪Q=P与Q,终止. 6.2if p i,…,p i+l(或q j,…,q j+h)是C中连续点列 then p i,…,p i+l(或q j,…,q j+h)是P∪Q的部分边界点列 步6.3 从C中p i出发,所有相互连接的子点列组成P∪Q的顶点序列,终止. 步7if‖C1‖ 步7.1i←1,C=(v1,v2,…,v h),C i←C,h 步7.2 w hile p i =v i ∧q j =v i +1 do if 与p i 关联的P 边和与q j 关联的Q 边相交 then 求出交点r k ,p i r k q j 组成子点列,goto 步7.3 else if p i ′,q j ′,分别是C 1与C 2中相交边的端点∧p i ′在C 2内∧q j ′在C 1内 then 判断与p i ′ ,q j ′关联的P ,Q 边是否相交if 相交 then 求出交点r k ′,p i ,…,r k ′,…,q j 组成子点列. else 判断p i ′,q j ′相邻P ,Q 顶点所关联的边是否相交,如果相交,则求出交点, 产生子点列;否则,P ∪Q =P 与Q ,终止. 步7.3if r k 关联的边与p i (或p i -1,q j ,q j -1)关联的边相交 then 求出交点r k ″ if r k ″关联的边与v i -1(或v i +2)关联的边相交 then 求出交点r k if 与r k (r k ′ ,r k ″,r k )相邻点关联的边相交then 求出交点,并删去r k (r k ′,r k ″,r k )及相邻点 步7.4重复7.3,直到r k 关联的边与p i (或q i )关联的边不相交∧r k ″关联的边与v i -1(或 v i +2)关联的边不相交∨与r k (r k ′ ,r k ″,r k )相邻点并联的边不相交.步7.5 if 与p i (或q j )关联的两条边都已处理(已求过交点) then 删去p i (或q j ) 步7.6 if C i 中有连续的P 点(或Q 点)∨P (Q )的凹点形成的三角形内无Q (P )的顶 点∨△的顶点都在另一多边形的同一侧 then 删去连续点列或△的顶点. 步7.7 i ←i +1 步7.8 求P ,Q ,C 中剩余点集与剩余交点组成的点集的凸壳C i . 步7.9 重复步7.2(找出C i 中新的相邻的顶点,处理新的相邻顶点)至步7.8,直至剩余点 集为空. 步8从C 中任一点p i (或q j )出发,所有相互连接的子点列组成P ∪Q 的外围边界;从剩 余在Q 外的某P 点出发,沿与该P 点关联的P 边进行,用巡回方法寻长空洞的边界;从剩余的交点r k 出发,沿与r k 关联的P 边行进,用巡回方法寻找空洞的边界.如沿P 边行进一周,没有遇到交点,则P ∪Q =P 与Q ,终止.2 算法分析 定理 给定平面上两个任意多边形P (p 1,p 2,…,p n )和Q (q 1,q 2,…q m ),算法1正确地求出P ∪Q 的边界顶点序列,而且该算法的时间复杂性为O (nm )次比较和O (n +m )次判断两条线段是否相交. 证明 平面上两个任意多边形P 与Q 的位置关系只有三种不同情况:P 与Q 分离;P 与Q 相交;P Q 或P Q .这三种不同情况的出现依赖于P 与Q 的顶点分布,这是算法1的依据. 算法1首先求出P ,Q 及P 与Q 的凸壳C 1,C 2及C .如果C 1={p 1,p 2,…,p i -1,p i },则还要求出p ′={p i ,p i +1,…,p n ,p 1}的凸壳C ′1,P ′与Q 的凸壳C ′.其作用是在某些情况下将考查P ,Q 的全部顶点转化为考查C 1,C 2,C ,C ′1及C ′的顶点,以减少判断线段89第1期周培德等:确定两个任意多边形的并的算法 相交的次数.当算法中步2的条件成立时,显然有P Q ,即P ∪Q =P .步3完成的工作是:如果P 与Q 的位置关系属于分离关系,则P 的顶点不可能位于C 2内,Q 的顶点也不可能位于C 1内,或者P ,Q 的某些顶点p k 和q k ′分别位于C 2,C 1内,但与p k 和q k ′关联的边不相交;当与p k 和q k ′关联的边相交时,则求出交点,利用巡回方法找出并的边界点列.如果Q 的顶点 都在P 内,并且C ′代替C ,C ′ 1代替C 1之后,C ′1中的P 点不在C 2内,C 2中的Q 点不在C ′1内,则C ′1与C 2分离,即P Q .否则,如果C ′中P 点与Q 点轮流出现,则用步7方法求交点,把问题转化为求P ′与Q 的交点.然后用巡回方法找并的边界.算法中的步5处理P 与Q 都是凸多边形并且‖C ‖=n +m 的情况,这时只要求出C 中相邻的P ,Q 顶点关联的边的交点,然后用巡回方法找出并的边界点列即可.两个凸多边形相交时,至多有n +m 个交点,一般情况有2个交点(退化情况时只有1个交点),步6.1至多循环执行2次便可求出2个交点,再按步6.3的方法就可以找出P ∪Q 的边界顶点序列.如果没有交点,则P 与Q 分离.难以处理的是相交的P ,Q 为任意简单多边形,这时P ,Q 边界的相交情况可以归纳为步7.2与7.3的条件部分所描述的,见图1与图2所示 . 图2 步7.3的示意图 算法的步7.2与7.3循环若干次之后便执行步7.5与7.6,删去已处理过的点.然后求剩余点集的凸壳,再重复步7.2至7.8的工作,求出所有相交边界的交点.由于算法1是逐点考查逐点删去,因此不可能遗漏相交的边.算法中的步8求出P ∪Q 的外围边界的顶点序列及内部空洞的边界顶点序列.总之,算法1正确地求出了P ∪Q 的边界顶点序列. 算法1中的步1耗费不超过O ((n +m )lb (n +m ))次比较.步2需要O (nm )次比较.步3的前半部分可以利用步2的结果,不需要新的开销.步3的后半部分需要2(a +b ) 90北 京 理 工 大 学 学 报第18卷 条线段是否相交,其中C 是常数.步7.5与7.7所需时间可以忽略不计.步7.6耗费O (n )或O (m )次比较.执行步7.8不会超过O ((n +m )lb (n +m ))次比较.由于每执行步7.3到7.6的一次循环可以删去大约一半多的顶点与交点,所以步7.9的循环执行常数次便可使剩余点集为空.步8的时间可以忽略不计.算法1所需要的比较次数为 max [O ((n +m )lb(n +m ))+O (nm ),O ((n +m )lb(n +m ))+(n +m ), O ((n +m )lb (n +m ))+(n +m )+O (n )+O (m )+O ((n +m )lb (n +m ))]= O ((n +m )lb (n +m ))+O (nm ))=O (nm ) 判断两条线段是否相交的次数为 max [n +m ,O (n +m ),n +m ,(n +m )+C (n +m )]=O (n +m ) 证毕 参考文献 1 P repar ata F P ,Shamos M I .Computatio nal geo metr y an int ro ductio n .New Yo rk :Springer -V erlag ,19852 周培德.求凸壳顶点的一种算法.北京理工大学学报,1993,13(1):69～72 3 周培德.算法设计与分析.北京:机械工业出版社,1992 Algorithm for Determining the Union of Two Polygons Zhou Peide Wang Wenming (Depar tment of Co mputer Science Eng ineering ,Beijing I nstitute of T echno lo gy ,Beijing 100081) Abstract Aim Desig ning and analysing a new algorithm for so lving the union of tw o arbi-tr ary po lyg ons.Methods T he alg orithm w as desig ned according to the divide-andconquer idea ,that is ,to consider six cases and so lve the boundary o f the union P ∪Q respectively in ter ms of the distinct positional r elation o f the convex hulls of poly gons P ,Q as w ell as the co nvex hulls of P and Q .Results To succeed in designing a new alg orithm and find that the time co mplex ity o f this algo rithm is O (n +m )tim es of decisi o n w hether two segm ents inter-sect or no t,in which n ,m are the number s of v ertices of po lyg ons P and Q respectively.Conclusion T his alg orithm is m uch better than the approach deciding one by o ne whether each edg e of P intersects the edg es o f Q . Key words simple polyg on;union of tw o polygo ns;complexity 91第1期周培德等:确定两个任意多边形的并的算法 多边形的扫描转换 图形学中多边形有两种表示方法：多边形的顶点表示与点阵表示。顶点表示用多边形的顶点序列来刻画多边形；点阵表示则是用位于多边形内的像素的 集合来刻画多边形。 扫描转换多边形或多边形的填充：从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存中相应单元的过程。 x-扫描线算法 基本思想：如下图所示，按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的所有像素。 图5-8 x-扫描线算法填充多边形 算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。填充过程可分为四个步骤： a.求交：计算扫描线与多边形各边的交点； b.排序：把所有交点按照递增顺序进行排序； c.交点配对：交点两两配对，表示扫描线与多边形的一个相交区间； d.区间填色：将相交区间内的像素置成不同于背景色的填充色。 存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。如下图所示，在扫描线y=1，y=5和y=7时，扫描线过多边形的顶点，若不加以处理，交点配对时会发生错误。 图5-9 与多边形相交的交点的处理 解决方法：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。实际处理时，只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 改进的有效边表算法 由于x-扫描线算法在处理每条扫描线时，需要与多边形所有的边求交，效率很低，因此需要加以改进，形成改进的有效边表算法。 改进原理： (1)处理一条扫描线时，仅对有效边求交。 (2)利用扫描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似。 (3)利用多边形边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线也相交：若边的直线斜率为k，这样边与两条相邻扫描线的交点有如下关系：xi+1=xi+1/k。 图5-10 与多边形边界相交的两条连续扫描线交点的相关性 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点为： 13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516 5 6 7 8 9 10 具体编程实现如下： 第1步：(1) 根据输入的五个顶点坐标找到y 值最小的点(例如点D ，此时y=2)，并找到与D 有边关系的两个顶点(此时为E 和C)，在y=2处建立ET 边表记录(ymax 、xi 和m 值均可通过顶点坐标间的计算得到，例如DE 边的建立，特别注意：当D 点和E 点y 坐标值相同时，也即是DE 与x 轴平行，该边不能计入ET 边表)，之后标记D 点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET 表建立完善。 [注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET 边表采用邻接表的数据结构 第2步：根据ET 表构建AET 表，并逐行完成多边形填充，具体的C++代码如下： (1) 建立头文件base_class.h ，主要是边表结点结构体和ET 边表类的实现 enum ResultCode{Success, Failure}; template /// 正多边形的有关计算 一、素质教育目标 (一)知识教学点 使学生学会将正多边形的边长、半径、边心距和中心角、周长、面积等有关的计算问题转化为解直角三角形的问题． (二)能力训练点 1．通过定理的证明过程培养学生观察能力、推理能力、概括能力； 2．通过一定量的计算，培养学生正确迅速的运算能力； 3．通过用不同方法求正多边形的内角，培养学生的发散思维能力和选优意识； 4．从具体边数的正n边形得到一般正n边形的计算图培养学生化归、转化的数学思想． (三)德育渗透点 1．由具体边数的正多边形计算图过渡到一般计算图，渗透了“从特殊到一般，再由一般到特殊”的辩证唯物主义认识观； 2．正多边形计算图的得出渗透了化繁为简、化难为易二矛盾相互依存、相互转化的思想； 3．通过正多边形的有关计算，培养学生仔细认真、一丝不苟、严谨的科学态度； 4．通过正多边形有关计算公式的推导，培养学生不断探索科学奥秘的创新精神． 二、教学重点、难点、疑点及解决方法 1．重点：1．化正多边形的有关计算为解直角三角形问题定理．2．正多边形计算图及其应用． 2．难点：正确地将正多边形的有关计算问题转化为解直角三角形的问题解决、综合运用几何知识准确计算． 3．疑点及解决方法：学生对只画出正n边形的一部分图形的计算图生疏，用它分析、计算有疑虑．为此计算图的抽象应由具体边数的正多边形计算图逐步过渡． 三、教学步骤 (一)明确目标 前几课我们学习了正多边形的定义、概念、性质，今天我们来学习正多边形的有关计算． (二)整体感知 大家知道正多边形在生产和生活中有广泛的应用性，伴随而来的有关正多边形计算问题必然摆在大家的面前，如何解决正多边形的计算问题，正是本堂课研究的课题． (三)重点、难点的学习与目标完成过程 哪位同学回答，什么叫正多边形．(安排中下生回答：各边相等，各角相等的多边形．) 什么是正多形的边心距、半径？(安排中下生回答：正多边形内切圆的半径叫做边心距．正多边形外接圆的半径叫做正多边形的半径．) 正多边形的边有什么性质、角有什么性质？(安排中下生回答：边都相等，角都相等．) 什么叫正多边形的中心角？(安排中下生回答：正多边形的一边所对正多边形外接圆的圆心角．) 正n边形的中心角度数如何计算？(安排中下生回答：中心角的度数 正n边形的一个外角度数如何计算？(安排中下生回答：一个外角度 哪位同学有所发现？(安排举手学生：正n边形的中心角度数=正n边形的一个外角度数．) 实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include 实验三区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0或win-TC实现区 域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 四连通图的实现: 程序代码： #include 计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院 专业名称计算机科学与技术 学生姓名刘柯 学生学号201213030112 任课教师梅占勇 设计（论文）成绩 教务处制 2015年9 月28 日 目录 一、设计内容与要求 (3) 1.1设计题目 (3) 1.2 设计内容 (3) 1.3 设计目标 (3) 二、总体设计 (3) 2.1 多边形的表示 (3) 2.2 x-扫描线算法 (4) 2.3 改进的有效边表算法 (4) 2.3.1 改进的有效边表算法 (4) 2.3.2 有效边表 (5) 2.3.3 边表 (6) 三、详细设计 (8) 3.1 改进的有效边表算法的实现 (8) 3.2 有效边表算法程序流程图 (9) 四、测试结果 (9) 五、总结 (15) 六、源代码 (15) 参考文献 (26) 一、设计内容与要求 1.1设计题目 用改进的有效边表算法实现多边形的填充 1.2 设计内容 使用OpenGL实现用改进的有效边表算法填充多边形 1.3 设计目标 参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。 二、总体设计 2.1 多边形的表示 在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转 华北水利水电大学 计算机图形学 实验报告 2017--2018学年 第一学期 2014级 计算机科学与技术 专业 指导老师 曹源昊 班级 2014157 学号 201415717 姓名 李卫朋 实验四、画圆与凸多边形填充算法 1. 实验目的 练习对Bezier 曲线的绘制和Bezier 曲线的de Casteljau 算法。 2. 实验内容和要求 按要求完成以下一个作业。提交纸质实验报告，同时提交实验报告和源代码的电子版。 实现Bezier 曲线的de Casteljau 递推算法，能够对任意介于0和1之间的参数t 计算Bezier 曲线上的点，然后把Bezier 曲线绘制成首尾相连的直线段。 要求： (1). 对[0,1]参数区间进行100等分。 (2). 控制点的数目至少为5个，即Bezier 曲线的次数不低于4次。 (3). 同时绘制控制多边形。 (4). 至少绘制两条Bezier 曲线，具有不同的次数，颜色和曲线宽度。 形如： 3. 算法描述 使用vs2012编译环境，使用OpenGL 进行绘图操作。 4. 源程序代码 // 实验4.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include 简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。 三、新算法设计 1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。 2、主要数据结构 多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示， 课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日 湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日 一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。 实验四区域填充算法的实现 班级 08信计2班学号 20080502088 姓名许延恒分数 一、实验目的和要求： 1、理解区域的表示和类型。 2、能正确区分四连通和八连通的区域 3、了解区域填充的实验原理。 4、利用C++实现区域填充的递归算法。 二、实验内容： 1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。 2 取（x，y）为种子点将整个区域填充为新的颜色。 3 进行递归填充。 三、实验结果分析 区域填充属性包括填充样式，填充颜色和填充图案的类型。C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充 . 程序代码 #include Weiler－Atherton任意多边形裁剪 Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。 一、Weiler－Atherton任意多边形裁剪算法描述： 在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。 裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 1、被裁剪多边形为主多边形，记为A； 2、裁剪窗口为裁剪多边形，记为B。 主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域： 1、A∩B（交：属于A且属于B）； 2、A－B（差：属于A不属于B）； 3、B－A（差：属于B不属于A）； 4、A∪B(并：属于A或属于B，取反；即：不属于A且 不属于B)。 内裁剪即通常意义上的裁剪，取图元位于窗口之内的部 分，结果为A∩B。 外裁剪取图元位于窗口之外的部分，结果为A－B。 观察右图不难发现裁剪结果区域的边界由被裁剪多边形的 部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边 界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界， 或者反之。由于多边形构成一个封闭的区域，所以，如果被裁 剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类： 一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e； 一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。 二、Weiler－Atherton任意多边形裁剪算法思想： 基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 310027) An Efficient Method for Surface Simplification Based On Variational Shape Approximation* JIN Yong, WU Qing-biao+, LIU Li-gang (Department of Mathematics, Zhejiang University, Hangzhou 310027, China) + Corresponding author: E-mail:qbwu@https://www.doczj.com/doc/d517242853.html, Abstract:Providing fast and accurate simplification method for large polygon mesh is one of the most important research focuses in computer graphics. Approximating mesh model with a few polygons can improve the rendering speed, and reduce the storage of the model. The paper presents a local greedy algorithm to minimize the energy defined by variational shape approximation. The algorithm simplifies the mesh by controlling the number of the target polygons, while attempting to get ideal effect by adaptive seed triangles selection. The algorithm has intuitive geometric meaning. The method is efficient enough to be efficiently adopted in the geometric modeling system. Key words: Polygon mesh simplification; variational shape approximation; greedy algorithm; geometric modeling 摘要: 为大型的多边形网格模型提供快速、准确的简化算法是计算机图形学中的一个重要的研究方面.以较少的多边形逼近表示网格模型,能够提高模型的绘制速度,减小模型的存储空间.本文根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法,该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取以达到理想的简化效果,具有直观的几何意义.本文方法计算量少,效率较高,能够有效应用于几何造型系统中. 关键词:多边形网格简化;变分网格逼近;贪心算法;几何造型 中图法分类号: TP391文献标识码: A 1 引言 三维多边形网格模型,包括三角形网格、四边形网格等,在计算机辅助几何设计、计算机动画、虚拟现实、计算机游戏和医学影像等领域有着大量的应用.随着三维扫描技术的发展,顶点数为数万的模型已经非常常见, ?Supported by the National Natural Science Foundation of China under Grant No.10871178, 60776799 (国家自然科学基金); Technology Department of Zhejiang Province Grant No. 2008C01048-3(浙江省重大科技创新项目) 作者简介: 金勇(1985－),男,上海人,博士研究生,主要研究领域为数字几何处理和计算机辅助几何设计;吴庆标(1963－),男, 浙江台州人,博士,教授,博士生导师,主要研究领域为图形与图像处理,数值计算方法,高性能并行计算和计算机模拟; 刘利刚(1975－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理. Lync.in Link the world. Home About Projects SimpleDark 2009-09-24 / Chris posted in A lgorithm / 397 Views / 16 Comments 前些天在考虑一个几何算法，关于如何判断一个点是否在一个给定的多边形内部。这应该是一个比较常规的算法，我以前对几何算法了解的不多，所以既然想到了就稍微研究了一下。 查了一下相关的资料，目前有几个O(N)的算法，其中N是多边形的顶点数。 第一个叫做交替（Alternative）算法。如下图所示 算法检查所给定的点和在该点右边的多边形区域的边界的交点数，若交点数为奇数，则该点在多边形内部，若交点数为偶数，则该点在多边形外部。可以想象成从一个点向右发出一条射线，然后计算这条射线与多边形边界的交点数。从上图中标出的蓝色点向右射出的射线与多边形有1个交点，故判定其在多边形内部，而从标出的白色点向右射出的射线则有偶数个交点，故判定其在多边形外部。 这个算法的叙述起来很平常，但实现起来却有两个略带Tricky的地方。 其一是坐标精度引起的，因为计算机对于坐标的描述是离散的，在计算向右射出的射线与多边形交点的时 候很容易出现射线与多边形的某几条边平行的情况，对于这种情况，我们的算法需要向前多看几个点，以确定射线是确实与多边形相交还是只是“擦过”而已。 其二是对于非常靠近多边形边界的点的判定，你可以认为这些点是在多边形外，也可以认为是在多边形内，但你必须在算法中描述这些情况。 感兴趣的可以了解一下我的算法实现，附在文末。 这个算法在多边形为简单多边形的情况下是没有异议的，但在复杂多边形的情况下会有一些疑问，这涉及到“在多边形内还是多边形外”的定义问题。如下图 图中，如果用Alternative算法，则被多边形包围的那个点被判断为在多边形外部。 如果你认为这种定义不符合你的需要，那么有另外一种算法，称为Winding算法。 Winding算法的思路是这样的，将你置身于所给定的点上，然后让你的视线从多边形边界上的一点开始，选择一个方向绕着多边形的边界转一圈，如果你发现你的身体在这个过程中转了360度的非零整数倍，那么你所站在的这个点在多边形的内部，如果你的身体并没有转动（事实上你转动了，只是正向和逆向的转动抵消了），那么就在多边形的外部。 这个算法我没有去实现，一般来说它要比Alternative算法慢，因为它需要计算每条多边形的边与多给定的点之间的夹角。 关于算法实现： 程序的界面是用WTL写的，如果你想要编译源代码，请在Visual Studio中指定WTL的include文件夹位置。 算法核心代码如下，其中vSelectionPoints是多边形 扫描线算法（Scan-Line F illing） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏 和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种 常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断 算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但 是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交 算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之 间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这 个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能 是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由 多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列 交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个 端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤： （1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进 行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然 后转第1步继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是 线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出 显示。 实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。 再经典不过的算法了： // 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount) { int nCross = 0; for (int i = 0; i < nCount; i++) { POINT p1 = ptPolygon[i]; POINT p2 = ptPolygon[(i + 1) % nCount]; // 求解y=p.y 与p1p2 的交点 if ( p1.y == p2.y ) // p1p2 与y=p0.y平行 continue; if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; // 求交点的X 坐标-------------------------------------------------------------- double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x; if ( x > p.x ) nCross++; // 只统计单边交点 } // 单边交点为偶数，点在多边形之外--- return (nCross % 2 == 1); } private void scanLineFillingToolStripMenuItem_Click(object sender, EventArgs e) { slf.ScanLinePolygonFill(P,g,XiangSu); } private void label2_Click(object sender, EventArgs e) { } private void四联通填充ToolStripMenuItem_Click(object sender, EventArgs e) { tempp.X = tempP[3].X + XiangSu;//选取第4个点内侧（随机猜测） tempp.Y = tempP[3].Y + XiangSu; checkBox.Enabled = false;//让绘制过程中不能改变选择 do_check();//也要检查一遍，不然会出现错误 FloodSeedFill(tempp); checkBox.Enabled = true;//恢复 } /// 实验三区域填充种子算法实现 实验目的： 1、熟练在Visual C＋＋中程序实现及调试的能力。 2、通过程序的设计熟练区域填充种子算法过程； 3、掌握堆栈在数据结构中的应用 实验内容： 1、visual c＋＋中菜单的修改，点的输入及鼠标函数的控制； 2、复习数据结构中堆栈的建立，入栈，出栈等函数； 3、实现整个多边形的区域填充种子算法，与扫描转换算法进行区分； 实验步骤： 预处理：多边形点列的输入，存储于数组中P[100]，种子点的输入，确定为point（x，y） 确定多边形的边界色（旧画笔色），初始色（背景色），填充色（新画笔色）； 数据结构的建立：建立堆栈，包括数组stack[100],及一个指标top，用来指向当前堆栈的最外面的栈口的元素。 步骤：1、堆栈置为空，top=0; 2、将初始的种子点point进栈，push(x,y); 3、填色堆栈非空即top>0时，一直循环下列步骤 取栈顶的元素，出栈pop(x,y)，savex=x; 从当前点开始沿当前扫描线往右检验，若有未填新色的，则填色。 然后同样往左检验。 当前扫描线俩个方向都检查完后，检验上一条扫描线y=y+1; 若有未填新色的，则把所有未填新色区间的右端点压入堆栈。 同理检验下一条扫描线y=y-2; 实验指导： 一、 在实验二的基础上进行编程 ； （1） 引入实验二代码 scanline.dsw 二、 编辑菜单资源 选中窗口左边栏的“ResourceView ”，其中的“Menu ”，双击“IDR_MAINFRAME ”，右边即为菜单，在菜单上空处双击，出项如图所示窗口，其中弹出不选中； 如上，同样创建其余菜单项。(如下表)； 三、 添加消息处理函数 由菜单的“查看”，“建立类向导”，打开ClassWizard （也可CTRL+W ）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏选中CScanLineView 类，根据表建立。 输入菜单项名称，（如显示多边形） 双击，出现如下窗口 实验报告 一、实验目的 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、算法原理介绍 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容 1.x -当前扫描线与这条边交点的x坐标； 2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3.ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。 当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */多边形扫描转换(简化)
多边形区域填充算法
区域填充算法运行代码
正多边形的有关计算一
区域填充算法的实现
实验三 区域填充算法的实现
计算机图形学课程设计-有效边表填充算法的实现
画圆与凸多边形填充算法
计算机图形学(简单多边形裁剪算法)
计算机图形学 多边形裁剪与填充 计算机图形学课程设计
计算机图形学 区域填充算法的实现
Weiler-Atherton任意多边形裁剪算法
基于变分网格的曲面简化高效算法
多边形区域算法
扫描线填充算法讲解
多边形的有效边表填充算法-
点在多边形经典算法
多边形填充算法运行代码
区域填充种子算法实现
最新《计算机图形学》有序边表填充算法讲课教案
相关主题
文本预览