萨瑟兰-霍奇曼算法

✍ dations ◷ 2025-09-14 09:20:16 #萨瑟兰-霍奇曼算法

萨瑟兰-霍奇曼算法（英语：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;         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

当算法终止时，将在outputList中找到裁剪后多边形的顶点。请注意，如果它位于该边缘作为多边形的剩余部分的相同侧上的点被定义为边缘的内侧。如果剪裁多边形的顶点始终沿逆时针方向列出，那么这等效于测试该点是否位于直线的左侧（left表示内部，right表示外部），这可以通过简单地使用叉积实现。

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

相关

亞當·斯密亚当·斯密（英语：Adam Smith，1723年6月5日（受洗）（新历6月16日）－1790年7月17日），又译亚当·史密斯、亚当·史密夫，苏格兰哲学家和经济学家，他所著的《国富论》成为了第一本试图阐述欧洲产
非机动车非机动车是指以人力或者畜力驱动在道路上行驶的车辆，包括自行车、三轮车、马车、牛车等。根据中华人民共和国法律，非机动车还包括虽有动力装置驱动但设计最高时速、空车质量、
彰化八景彰化八景，指的是彰化县的八大景色，但随着时代更迭，部分景色变迁而有所变异。又由于清朝时的彰化县范围包含今日之彰化、南投、云林，故部分景点现已不在现今的彰化县境内。雍正年
一剑浣春秋一剑浣春秋（1975年8月28日－），本名黄正，是台湾成人影片（AV）评论家及专栏作者，同时为AV资讯网站“PLAYNO.1玩乐达人”创始人，台北市出身。因熟悉日本AV文化（日语：アダルトビデオの歴史）及
中华职棒19年中华职棒19年是中华职棒2008年的球季，赛季从3月16日至11月结束，每队共进行100场例行赛，开幕战由La New熊作客迎战统一7-ELEVEn狮，结果La New熊以9比14败于统一7-ELEVEn狮。上半
女主角失格《女主角失格》（日语：ヒロイン失格）是日本漫画家幸田百子的日本漫画作品。于集英社漫画杂志《玛格莉特别册》2010年4月号开始至2013年4月号结束连载。单行本全10卷。2012年获讲
娇西少女队 (动画)《娇西少女队》（英文：Josie and the Pussycats，又名Josie and the Pussy Cats），是一套由1970年7月至1971年1月间，以及1972年9月至1972年12月间，于美国播放的动画。由汉纳-巴伯拉制
山道山道是在鞍部或山坳指穿越山脉或山脊的道路。汉语中用作地名时，一般用山口、陉、道、关等词，如唐古拉山口、太行陉、褒斜道、潼关，日语汉字则写做“峠”。山道通常会选择在鞍部
内森·贝德福德·福雷斯特内森·贝德福德·福雷斯特（英语：Nathan Bedford Forrest，1821年7月13日－1877年10月29日）是南北战争邦联军中的高级将领以及战后三K党的首任领袖。他指挥才华精湛，擅长统领骑兵，但同
现代发现的巨型动物列表以下是自19世纪初以来科学发现的巨型动物的列表（以及它们各自的发现日期）。其中一些可能是原住民已知的或已报导的轶事，但是在获得正式研究的确凿证据之前还没有得到科学界的普遍承认。在其他情况下，某些动物最初被认为是恶作剧——类似于在18世纪晚期欧洲的鸭嘴兽标本。巨型动物的定义各不相同，但此列表包括了一些更值得注意的例子。