Sutherland–Hodgman算法

✍ dations ◷ 2025-08-16 10:56:27 #计算机图形学,算法

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

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

相关

蚊源性疾病蚊子传播的疾病包括各种以蚊子为主要传播载体的疾病，包括有由病毒、寄生虫或其他病原体引起的疾病。在各种以动物为传播载体的疾病中，蚊子占有相当大的比重，从动物传动物、动物
台北市立天文科学教育馆坐标：25°05′46″N 121°31′06″E / 25.0960778°N 121.5184451°E / 25.0960778; 121.5184451台北市立天文科学教育馆（英语：Taipei Astronomical Museum），或称台北市立天文馆
章鸿钊章鸿钊（1877年3月11日－1951年9月6日），字演群（后改为爱存），笔名半粟。浙江省吴兴县人，中华民国及中华人民共和国地质学家、地质教育家、地质科学史专家，中国近代地质学奠基人之一。生
陆军防化学院中国人民解放军陆军防化学院，简称陆军防化学院，位于北京市昌平区，隶属中国人民解放军陆军，担负为全军培养中、初级防化指挥军官和中、高级防化工程技术军官的任务。2017年时，学院
童中白童中白（女，1961年－），祖籍中国浙江杭州，出生于台湾台北市。1984年进入中国电视公司新闻部，担任过《中视晚间新闻》主播，主持过台湾第一个夜间谈话性质的节目《今夜》，之后赴美国求学。
高淑珍高淑珍（1957年－）女，河北省滦南县司各庄镇洼里村人，常年为残疾儿童兴办学校，第十二届全国人民代表大会河北地区代表。高淑珍是河北省滦南县司各庄镇洼里村的一位普通农村妇女。高淑
玻那病毒科玻那病毒科（Bornavirus），又称博尔纳病毒科、鲍那病毒科，RNA病毒的一种，属单股负链病毒目。其下仅有()，目前只有一个病毒被发现，玻那症病毒(Borna disease virus，BDV)，它是博那病（Borna
自然进气发动机自然进气发动机（英语：naturally aspirated engine）为最基本的动力形式，在进入发动机汽缸前，以外界空气（1大气压）直接与喷油针喷岀之汽油混合而成汽油雾，最后进入燃烧室点燃。有别于
赐斐德赐斐德（Robert Harold Ainsworth Schofield，1851–1883）是一位英国在华医疗传教士。他在中国传教期间去世。在去中国之前，他曾在欧洲和中东的医院和诊所工作。1851年，赐斐德出生
北京莫斯科餐厅北京莫斯科餐厅建于1954年，由苏联中央设计院设计，属于北京展览馆建筑群之一，主要经营俄式西餐。北京人昵称其为“老莫”。该餐厅是中苏建交后为了体现社会主义同盟兄弟国家的友