Sutherland–Hodgman算法

✍ dations ◷ 2025-11-19 05:06:21 #计算机图形学,算法

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

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

相关

牙刷牙刷是用于刷牙的一种刷子。它的结构，是将嵌满一束束高密度刷毛的刷头安装在握把上，促进清洁口腔中难以触及的区域。一般刷牙时都会在牙刷上加上牙膏以提高刷牙的功效。市面上
群速度波的群速度（group velocity），或简称群速，是指波振幅外形上的变化（称为波的“调变”或“波包”）在空间中所传递的速度。想象一下我们将一块石头投入一个平静的池塘中激起一个波浪，随
民生医院高雄市立民生医院位于高雄市苓雅区凯旋二路上、临港线铁路旁。其前身为1914年台湾总督府创立的“打狗病院”，位于山下町，首任院长为右田吉人。1920年，医院随打狗改名高雄而改称
非法砍伐非法砍伐，是指违反法律进行的木材砍伐、运输、购买和销售行为。非法的砍伐行为，包括使用破坏性的手段进行砍伐；在没有许可的情况下进行砍伐；砍伐受保护的树种；或者砍伐森林超过许
帝王总统帝王总统（Imperial Presidency）是美国一些媒体和民众在1950年至1970年代给予当时美国总统的称号。因为那时第二次世界大战结束不久，美国正在和苏联进行冷战，而美国总统自富兰克
私人飞行执照私人飞行执照（英语：Private Pilot Licence，简称PPL，美国称之为Private Pilot Certificate）是一种执照，持有人可以以机长身份、不受雇用的形式驾驶私人航空器进行飞行活动。由该国
节理节理（英语：joint）是地质学名词。当岩层受力而变形、断裂，会产生破裂面。若破裂面两侧的岩块，没有明显沿着破裂面发生明显位移，称为节理，有时也称为裂隙；若有明显位移，则称为断层。岩
黎遂球黎遂球（1602年－1646年），字美周，号迦陵，番禺（今广州番禺板桥乡）人。于广东省城豪贤路出世。自幼聪慧，师从陈子壮。天启六年（1626年）县试冠其曹，天启七年（1627年）举人，再试不第。与徐汧、吴伟
刘捷 (台湾作家)刘捷（1911年－2004年），使用笔名有郭天留、张猛三，屏东县万丹乡人，写作以评论为主，有“台湾的藏原惟人”之称，且也写新诗。作品散见《台湾新民报》、《台湾新闻》、《台湾文艺》、《台
立方氧化锆立方氧化锆（Cubic Zirconia，简称CZ），亦称作锆立晶、方晶锆石、高碳钻、泛美钻、俄罗斯钻、碳钻、Sona钻、苏联钻或苏联石，是二氧化锆（Zirconia，ZrO2）晶体的一种。氧化锆天然存在时大