text: 薩瑟蘭-霍奇曼演算法是裁剪多邊形的演算法。它透過輪流延長每個凸多邊形的邊，並且只選擇在可見一側的頂點來完成任務。描述.該演算法從目標多邊形中所有頂點的輸入列表開始。接下來，剪裁多邊形的一條邊在兩個方向上無限延伸，同時遍歷目標多邊形的邊。如果輸入列表中的頂點位於擴充套件的剪裁多邊形線的可見側，則它們會插入到輸出列表中，並且目標多邊形與剪裁多邊形的延長後的邊相交的頂點會新增到輸出列表。使用一個階段的輸出列表作為下一個階段的輸入列表，對每個剪輯多邊形側重複進行此過程。剪裁多邊形的所有邊都經過處理後，最終生成的頂點列表將定義一個完全可見的新單個多邊形。請注意，如果目標多邊形在剪裁多邊形外部的頂點處凹入，則新多邊形可能具有重疊的邊緣——這對於渲染是可接受的，但不適用於其他應用程式，例如計算陰影。虛擬碼.給定一個剪裁多邊形的一組邊，和一個目標多邊形的頂點列表，下面的過程將目標多邊形根據剪裁多邊形進行剪裁。List outputList = subjectPolygon;for (Edge clipEdge in clipPolygon) doList inputList = outputList;outputList.clear();for(int i = 0 ; i &lt; inputList.count ; i += 1) doPoint 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) thenif (prev_point not inside clipEdge) thenoutputList.add(Intersecting_point);end ifoutputList.add(current_point);else if (prev_point inside clipEdge) thenoutputList.add(Intersecting_point);end ifdonedone當演算法終止時，將在outputList中找到裁剪後多邊形的頂點。請注意，如果它位於該邊緣作為多邊形的剩餘部分的相同側上的點被定義為邊緣的內側。如果剪裁多邊形的頂點始終沿逆時針方向列出，那麼這等效於測試該點是否位於直線的左側，這可以透過簡單地使用叉積 實現。ComputeIntersection是函式，為清楚起見在此省略了該函式，它返回線段和無限邊的交點。請注意，僅在已知存在這種相交的情況下才呼叫它，因此可以簡單地將兩條線都視為無限長。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 薩瑟蘭-霍奇曼演算法
metadata: https://zh.wikipedia.org/wiki?curid=6790193