面向对象的复杂多边形裁剪实现算法
维普资讯 doc.guandang.net
第 2 6卷第 4期 20 0 3年 8月
Vo1 2 No 4 . 6, . Au 2 3 g. 00
面向对象的复杂多边形裁剪实现 郭功举 0济大学测量与国土信息工程学院,海 20 9)同上 0 0 2
摘
要
本文在已有多边形裁剪算法的研究基础之上,出了包含圆弧段的复杂多边型裁剪方法。该方法中的被提
剪切对象是较为复杂的几何实体,包括圆弧以及带有圆弧边界和带有洞的复杂多边形对象,中剪裁窗口可以为其 凹多边形或凸多边形。
关键词多边形剪裁剪裁窗口圆弧剪裁 中圈分类号: 0 P2 8文献标识码: B文章编号:6 24 9 (0 3 0—0 20 1 7~ 0 7 2 0 ) 40 1— 3
l引言 图形剪裁在 GI S领域中它也有重要的应用,如
设 I多边形 S和 C的一个交点。如果 S沿着是
其前进方向在 I点从 c的外部进入到 C的内部,则称 I c的一个进点。反之如果 s在 I为点从 C的内 部出到 C的外部,称 I C的一个出点。上述结则为
空间分析、 S制图等。目前人们研究最多的是由 GI 直线组成的凸多边形剪裁窗口,及由直线组成的以多边形被剪裁对象。其中 N t ln—Ho g ma u] ad mr de n算法、一 as y算法、 oe梁 B rk F ly算法及 Ma lt io l算法[要求裁剪多边形是矩形或凸多边形; e e— 6 W i r l At eno h r tn算法 (内裁剪 ) 一的裁剪多边形可以是凸多边形或凹多边形;勇奎对 Welr At eno刘 i— h r t n算 e
构中,tt s记录该顶点是进点还是出点,否与 sau是是 相交多边形的边或顶点相重合。F a lg表示此顶点
的类别,类别将在下文作进一步说明。Va是顶其 l点空间信息的描述,o接口指针类型,以是一般 cm可的空间点 (, )也可以是圆弧 (点 (, )中点 Xy,起 Xy, (, )终点 (, )。两个连续 (, )型的点构成 Xy, Xy) X y类 一
法进行了改进 l ( 2下称刘氏算法 )用了单向链表数 采据结构及错切变换的求交点方法,化了数据结构,简 提
高了运算速度。其被裁剪对象都不含有圆弧,由
条直线段,一个圆弧数据构成一段圆弧段。n x l et
指向本多边形的下一顶点。
3算法的基本思想及步骤 本文中主要讨论内剪裁,求 Cn s的区域。即 如图 1所示,设 C与 S都是顺时针方向,定义假即了多边形边的右边为多边形内域。
于实现圆弧对象的裁剪有一定难度,可以用短直并
线简化。但是,直线替代圆弧使数据量增加,短精度 降低,率减慢,许多 GI效在 S系统中一般不采用这种方法。因此,被裁减对象中加入圆弧对象是很在 必要的。本文借鉴并发展了刘氏算法中的一些数据结构,之能适合带有圆弧要素的多边形裁剪,使并且
算法分三步。第一步是调整裁剪多边形与被裁剪多边形的方向,明确定义多边形的内外域,一般情况我们是求内域的交集;二步做相交计算,次以第依被裁剪多边形的每条直线段或圆弧段与裁剪多边形进行相交计算,出交点,特殊交点,重合点,求对如进行处理,否则交点的进出性可能受到破坏;三步根第据交点的进出性,搜索出裁剪结果。 3 1调整裁剪多边形与被裁剪多边形的方向 .
更适合面向对象的程序实现。
2算法的数据结构 在含圆弧要素的多边形裁剪中,由于数据较复杂,录的信息较多,记因此设计适当的数据结构是比
较重要的。本文的算法同刘氏算法,用单向循环采链表,降低结构的复杂性以及节省存储空间。以下 的叙述中设裁剪多边形为 C,裁剪多边形为 S被。
从几何学可知,意多边形 (任由直线段组成 )的内角之和小于外角之和,因此可以间接通过判断内 角与外角,判断多边形的走向。如果左角之和大来于右角之和,左角为外角,角为内角,么多边则右那 形为顺时针走向,否则为逆时针走向。
多边形顶点数据结构 sr c an d{ tu t Ch iNo e b e s a yt t● t us; b e Flg; yt a I s t hPt a; Dipa c rV l Chai nNode * ne l: xt
对于有圆弧段的多边形,以把圆弧
简化成两可 条直线段,而与一般的多边形的判别方法一样,从而
且不影响判断的正确性。在这一步中,对裁剪多要

本文设想将复杂多边形划分为形态简 单的空间单元 ,在实现简单空间单元裁剪的基础...多边形分解为简单几何单元 ( 规则栅 格) ,以这些 “基元” 为空间运算对象来...
一种有效的复杂多边形裁剪算法_工学_高等教育_教育...“基元”为空间运算对象设计算法 (进行裁剪),最后...4 关键过程 实现 一、计算两个图层的交点两多边形...
裁剪掉被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分.多 边形愈复杂,其裁剪算法就愈难以实现.现有的解决方案或者局限于某一类多边形,或者...
被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分.多边形愈复杂,其裁剪算 法就愈难以实现.现有的解决方案或者局限于某一类多边形,或者结构复杂...
任意多边形裁剪算法的研... 3页 免费 一种有效的复杂多边形裁... 5页 1...? 为快速判断,采用如下编码方法: 实现方法: 1001 1000 Cohen-Sutherland裁剪 ...
实现简单多边形的裁剪;在简单图形的基础上建立复杂的多边形并实现对其的裁剪功能;...在多边形类数组 array_area 的对象逐一 取出,其基本过程为:依次读取每个对象,若...
等值线图的任意多边形裁剪算法_IT/计算机_专业资料...需要判断点 是否在多边形内,且计算交点时情况复杂。...在本算法的实现过程中,根据实际情况,将矩形网中的...
一个复杂的画面中可能包含有几千条直线,为 了提高算法效率,加快裁剪速度,应当...算法实现: 1、已知:多边形顶点数组 src,顶点个数 n, 定义新多边形顶点数组 ...
被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分.多边形愈复杂,其裁剪算 法就愈难以实现.现有的解决方案或者局限于某一类多边形,或者结构复杂...
关键词 按照处理对象的不同, 裁剪可以 分为线段裁 剪和多边 形 裁剪。线段 ...同原 算 法相比, 简化了实现过程, 避免了使用双 向指针等 复杂技术, 同时 ...
热门文档