Sutherland–Hodgman算法

✍ dations ◷ 2025-11-25 13:12:20 #计算机图形学,算法

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

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

相关

词根词根（root）是基本构词的基本词素，与词缀相对并携带主要词汇信息。词根有两种，能够独立构词的为自由词根(Free Root)，必须与其他词素组合构词的是粘附词根（Bound Root).闪语系的词
大东部大区大东部（法语：Grand Est）是法国的大区之一，由阿尔萨斯、香槟-阿登、洛林3个大区合并而成，于2016年1月1日正式成立、同年9月28日改用现名。2014年，法国政府开始谋划行政区划改革方案
DNA纳米科技DNA纳米技术专门研究利用脱氧核糖核酸或其他核酸的分子性质（如自组装的特性），来建构出可操控的新型纳米尺度结构或机械。在这个领域，核酸被用作非生物的材料而不是在活细胞中那
卫康叔卫烈祖康叔（？－？），姬姓，名封，又被称为康叔封，是周武王的同母弟，获武王封畿内之康国。周成王平定三监之乱后，于前1042年在黄河和淇水之间的商朝故墟朝歌建立卫国，徙封康叔于卫。他赴任时，周
欧阳予欧阳予（1927年7月26日－），中国核反应堆及核电工程专家。1927年生于四川乐山。1948年毕业于国立武汉大学工学院电机系。1957年获苏联莫斯科动力学院技术科学博士学位。2000年当选
Dess-Martin过氧碘试剂2-碘酰基苯甲酸（IBX）是典型的高价碘试剂，在有机合成中用作氧化剂，用于将醇氧化为醛。以邻碘苯甲酸、溴酸钾（或过一硫酸氢钾复合盐）和硫酸为原料制取。它在空气中稳定，可以长期保存
联立制联立制（Mixed-Member Proportional representation，MMP）又称“补偿制”（Top-Up system；Compensatory system）、“德国制”，是单一选区两票制选举制度的一种，更接近于比例代表制，以第
血管摄影血管摄影，或称动脉摄影、血管造影，是一种医学影像技术，用x光照射人体内部，观察血管分布的情形，包括动脉、静脉或心房室。葡萄牙籍医师兼神经学家Egas Moniz（1949年诺贝尔奖的得主）
陈倬陈倬（1910年11月10日－1985年6月3日），字云昭，江苏金坛人。其父陈权为前清举人。他从国立交通大学毕业后至广东加入国民革命军，历任连长、营长。后留学日本，就读于日本陆军士官学校第
假小檗假小檗（学名：）是小檗科小檗属的植物，是中国的特有植物。分布在中国大陆的云南等地，生长于海拔1,800米至3,200米的地区，常生于山坡灌丛中和林中，目前尚未由人工引种栽培。