一个任意多边形的裁剪算法浅析.ppt

一个任意多边形的裁剪算法指导教师:姓名:学号:专业:班级: 一、课题名称与要求?一个任意多边形的裁剪算法?内容及要求: 基于 Weiler-Atherton 算法实现凹凸多边形内裁剪(即交集)、外裁剪(即差集)、并集裁剪。二、基本概念 AB CD ab c 1 4 23入点和出点: 当两个多边形相交时,交点必然成对出现,其中一个是从被裁剪多边形进入裁剪窗口的交点,称为“入点”, 另一个是从被裁剪多边形离开裁剪窗口的交点,称为“出点”。三、算法流程图以内裁剪为例将交点分别和被裁剪多边形及裁剪窗口顶点放入数组 3、4中数组 3中有入点结束将入点录入到数组 Q中沿数组 3取顶点顶点是出点沿数组 4取顶点顶点是入点顶点录入到Q中顶点=起始点输出数组 Q四、算法的实现及原理由 MFC 建立一个空文档,然后对界面进行手动操作,代码由微软 MFC 提供自动生成,添加一些 windows 消息响应函数,生成的主界面如下图: 1、界面其中显示多边形,显示裁剪窗口和被裁剪多边形。有三种选择方式:交集(即内裁剪)、并集、差集(即外裁剪),可选择进入的三种不同的结果。 2、多边形裁剪 Picture Frame 1、内裁剪:从一个被裁减的多边形的一个顶点开始,沿被裁剪多边形以顺时针方向, 经过“入”点继续沿多边形顺时针方向,经过“出”点沿着裁剪窗口的顺时针方向。 B ACD abc 2 314 2内裁剪的裁剪结果: 2 、外裁剪:从被裁剪多边形的一个“出”点开始,碰到“出”点,沿着被裁剪多边形按顺时针方向搜集顶点序列;而当遇到“入”点时,则沿着裁剪窗口按逆时针方向搜集顶点序列。 A B C D ab c 14 2 3 外裁剪的裁剪结果: