Sutherland–Hodgman算法

✍ dations ◷ 2025-11-25 19:10:32 #计算机图形学,算法

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表示），这可以通过简单地使用叉积实现。

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

相关

白化症白化症（Albinism、albino）是由于体内黑色素缺乏，导致眼呈红色、毛发与皮肤颜色呈现白色；若虹膜并非红色而呈蓝或灰色，且肤色及毛发偏淡或颜色不均而非纯白，则是白色亚种而非白化症
动作电位动作电位（英文：action potential），指的是静止膜电位状态的细胞膜受到适当刺激而产生的，短暂而有特殊波形的跨膜电位搏动。细胞产生动作电位的能力被称为兴奋性，有这种能力的细胞如
蛮南蛮，原是上古三代王朝或中原一带的人对南部一些部落的称呼。由九州境内各部落演变而来的汉族，继承这种称呼，用来代指南方非汉的外族，在中国中心主义的天下观中，西戎和东夷、北狄
千分尺千分尺，中国大陆称为千分尺(中国大陆的初中课本称其螺旋测微器或千分尺)、台湾称为螺旋测微器、测微器、分厘卡，一种测量工具，用于精密测量小尺度的长度。从原理上，螺旋测微器可
加州大学董事会诉巴基案加州大学董事会诉巴基案（Regents of the University of California v. Bakke），438 U.S. 265 (1978)是美国联邦最高法院裁决的一个里程碑式案件，支持了肯定性行动（又称平权法案），允
人民议会 (缅甸)人民议会（缅甸语：ပြည်သူ့လွှတ်တော်），是1974年至1988年期间缅甸联邦社会主义共和国的一院制立法机关。它根据1974年《缅甸宪法》成立，在1988年被解散后由国家和平
山县伊三郎山县伊三郎（1858年2月6日－1927年9月24日），日本政治人物。曾任递信大臣、韩国副统监等职。为元老山县有朋之养子，后来继承了其公爵之位。旧姓胜津。妻为加藤弘之之女隆子。儿子是
人工合成宝石人工合成宝石是相对于天然宝石而言的，是为缓解天然宝石供需矛盾而产生和发展的产物，是人工制作而非天然产出的宝石。人工合成宝石，可简称为人工宝石，是指人们运用现代科学技术的
需要仙女车仁杓、沈慧珍、黄雨瑟惠《需要仙女》（韩语：선녀가 필요해，英语：Need Taoist Fairy）是韩国KBS自2012年2月27日起播出的日日情境剧，改编自古典神话《仙女和樵夫》，讲述丢失仙女服的
戴燕妮戴燕妮（1993年7月29日－），中国内地女歌手、演员，生于辽宁沈阳。2009年参加《加油！东方天使》获得全国第三名和最佳亲和力奖。2010年，出演话剧《囧男传》，在其中饰演“娇娇”。2013年，