1樓：王贇 Maigo
求出折線與所有圓的交點，並按折線的走向排序；
給折線確定乙個方向，確定在每個交點處折線是進入乙個圓還是退出乙個圓；
計算折線的起點（如果是封閉的就任取乙個頂點）位於幾個圓內（記為變數n）；
沿折線方向掃瞄每乙個交點，並根據此處是進入還是退出圓更新變數n。變數n不為0時經過的長度之和就是答案。
2樓：
經典問題，計算幾何101。求所有焦點，離散化後排序掃一遍就好了，都是梯形+弓形。最壞情況立方複雜度，但是正常情況下遠達不到。
3樓：
這個問題可以轉化成求線段與圓的交點。
用ray shooting的資料結構儲存這些圓（可能需要把整個的圓打成幾段）。
另外可以考慮先求the arrangement of circles，然後在這個arrangment上用point location data structure，然後沿著線段的方向walk。
也可以考慮先求the boundary of the union of these disks，然後把邊緣在轉折處打斷，然後再ray shooting。
兩個凸多邊形的交是否是凸多邊形？
sinxl 我覺得題主關心的是凸集，多不多邊形倒是無所謂。對凸集來說，答案是對的 證明如下 假設凸集A和凸集B，交集為C。在C中任取兩點x y。顯然，x y屬於凸集A，因此x y的任意凸組合都屬於A，同理x y的任意凸組合也都屬於B，即x y的任意凸組合都屬於A交B C，因此C也是凸集 HumJ 凸...
多邊形自交的處理？
我在進行多邊形計算的時候也遇到了這個問題。通過將自交多邊形轉化成多個多邊形求並來解決這個問題的。原始碼位址 自交多邊形演算法 Henry King 用 Non zero 的方法掃瞄整個圖形的填充，把被填充的畫素點去掉。填充的時候只包括圖形裡面的點，而不包括圖形輪廓上的點。這樣輪廓和填充的交集就是要去...
劉徽怎麼算多邊形面積？
又按 為圖，以六觚之一面乘一弧半徑，三之，得十二觚之冪。若又割之，次以十二觚之一面乘一弧之半徑，六之，則得二十四觚之冪。割之彌細，所失彌少。割之又割，以至於不可割，則與圓周合體而無所失矣。觚面之外，又有餘徑。以麵乘餘徑，則冪出觚表。若夫觚之細者，與圓合體，則表無餘徑。表無餘徑，則冪不外出矣。以一面乘...