萨瑟兰-霍奇曼算法
计算机图形学算法
萨瑟兰-霍奇曼算法（英语：Sutherland–Hodgman algorithm）是裁剪多边形的算法。它通过轮流延长每个凸多边形的边，并且只选择在可见一侧的顶点来完成任务。
描述
编辑该算法从目标多边形中所有顶点的输入列表开始。接下来，剪裁多边形的一条边在两个方向上无限延伸，同时遍历目标多边形的边。如果输入列表中的顶点位于扩展的剪裁多边形线的可见侧，则它们会插入到输出列表中，并且目标多边形与剪裁多边形的延长后的边相交的顶点会添加到输出列表。
使用一个阶段的输出列表作为下一个阶段的输入列表，对每个剪辑多边形侧重复进行此过程。剪裁多边形的所有边都经过处理后，最终生成的顶点列表将定义一个完全可见的新单个多边形。请注意，如果目标多边形在剪裁多边形外部的顶点处凹入，则新多边形可能具有重叠的边缘——这对于渲染是可接受的，但不适用于其他应用程序，例如计算阴影。
伪代码
编辑给定一个剪裁多边形的一组边，和一个目标多边形的顶点列表，下面的过程将目标多边形根据剪裁多边形进行剪裁。
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[i];
Point prev_point = inputList[(i + inputList.count - 1) % inputList.count];
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当算法终止时，将在outputList中找到裁剪后多边形的顶点。请注意，如果它位于该边缘作为多边形的剩余部分的相同侧上的点被定义为边缘的内侧。如果剪裁多边形的顶点始终沿逆时针方向列出，那么这等效于测试该点是否位于直线的左侧（left表示内部，right表示外部），这可以通过简单地使用叉积 实现。
ComputeIntersection是函数，为清楚起见在此省略了该函数，它返回线段和无限边的交点。请注意，仅在已知存在这种相交的情况下才调用它，因此可以简单地将两条线都视为无限长。
参看
编辑参考文献
编辑- Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison Wesley. ISBN 0-201-62420-6.
- Ivan Sutherland, Gary W. Hodgman: Reentrant Polygon Clipping. Communications of the ACM, vol. 17, pp. 32–42, 1974