Sutherland–Hodgman算法

✍ dations ◷ 2025-07-08 17:33:06 #计算机图形学,算法

Sutherland–Hodgman算法是裁剪多边形的算法。它通过轮流延长每个凸多边形的边,并且只选择在可见一侧的顶点来完成任务。

该算法从目标多边形中所有顶点的输入列表开始。接下来,剪裁多边形的一条边在两个方向上无限延伸,同时遍历目标多边形的边。如果输入列表中的顶点位于扩展的剪裁多边形线的可见侧,则它们会插入到输出列表中,并且目标多边形与剪裁多边形的延长后的边相交的顶点会添加到输出列表。

使用一个阶段的输出列表作为下一个阶段的输入列表,对每个剪辑多边形侧重复进行此过程。剪裁多边形的所有边都经过处理后,最终生成的顶点列表将定义一个完全可见的新单个多边形。请注意,如果目标多边形在剪裁多边形外部的顶点处凹入 ,则新多边形可能具有重叠的边缘——这对于渲染是可接受的,但不适用于其他应用程序,例如计算阴影。

给定一个剪裁多边形的一组边,和一个目标多边形的顶点列表,下面的过程将目标多边形根据剪裁多边形进行剪裁。

   List outputList = subjectPolygon;        for (Edge clipEdge in clipPolygon) do      List inputList = outputList;      outputList.clear();          for(int i = 0 ; i < inputList.count ; i += 1) do         Point current_point = inputList;         Point prev_point = inputList;             Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)             if (current_point inside clipEdge) then            if (prev_point not inside clipEdge) then               outputList.add(Intersecting_point);            end if            outputList.add(current_point);                  else if (prev_point inside clipEdge) then            outputList.add(Intersecting_point);         end if          done   done

当算法终止时,将在找到裁剪后多边形的顶点。请注意,如果它位于该边缘作为多边形的剩余部分的相同侧上的点被定义为边缘 。如果剪裁多边形的顶点始终沿逆时针方向列出,那么这等效于测试该点是否位于直线的左侧(left表示 ,right表示 ),这可以通过简单地使用叉积 实现。

是一个函数,为清楚起见在此省略了该函数,它返回线段和无限边的交点。请注意,仅在已知存在这种相交的情况下才调用它,因此可以简单地将两条线都视为无限长。

相关

  • 头孢克肟头孢克肟(Cefixime)是一种口服的第三代头孢菌素抗生素,通常用于治疗淋病、扁桃腺炎和咽炎。常用剂量为400毫克。头孢克肟在美国以“Suprax”的名称发售,直到2003年,当它的专利失
  • 航天飞机高传真科技航天飞机高传真资讯科技股份有限公司为台湾一家上市公司,为规模最大的各式电脑线材制造厂。最早1985年成立于土城,1989年赴大陆设厂,2000年成立光纤生产部并上市。该公司获得UL
  • 金门大桥坐标:37°49′10″N 122°28′43″W / 37.81944°N 122.47861°W / 37.81944; -122.47861金门大桥(英语:Golden Gate Bridge)是美国旧金山的地标。它跨越联接旧金山湾和太平洋的
  • 护理系护理学系简称护理系,主要的目的在培养护理专业人才,提升护理专业品质。护理学系的专业科目包含了医院各科病人的护理教学和护理学实习。有关人士通过考试、取得执照后,可在医疗
  • 救济世界饥饿组织救济世界饥饿组织(德语:Deutsche Welthungerhilfe e. V. )是一个非宗教、非政治、非营利、独立的非政府组织。总部位于德国波恩。自从1962年成立以来,该组织大约使用了20.3亿欧
  • 1776《1776》是一出1969年百老汇音乐剧和它的1972年电影版的总称。这是一出带恶搞风格的喜剧。剧本:Peter Stone词曲:Sherman Edwards演出时间:1969年3月16日-1972年2月13日,共1217场
  • 山东半岛城市群山东半岛城市群,指位于山东半岛及胶济铁路延伸带上的45个城市的集合。该城市群以青岛为对外开放的龙头城市,以青岛、济南为区域双中心城市,以烟台为区域副中心,以山东半岛地区(包
  • 计算复杂性理论计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题
  • 胯部人类的胯部是指骨盆底部,人类腿部(英语:Human leg)和躯干接合之处,一般也包括鼠蹊部及生殖器。在旧石器时代的艺术作品中就已经开始描绘女性的胯部,一般不包括胯部的毛发。古典的
  • 珍贵日子的梦想《珍贵日子的梦想》(韩语:소중한 날의 꿈),2011年上映的韩国动画电影。安载勋、韩惠珍执导,韩国Studio-Mwp、A One Entertainment、EBS、Seoul Animation Center、ICONIX摄制及发