如何從任意多邊形中減去圓

Question

給定一個任意多邊形，頂點以順時針/逆時針方式存儲（如圖中黑色矩形所示），我需要能夠減去任意數量的圓（紅色在該圖上）從該多邊形。去除一個圓可能會將多邊形分成兩個獨立的多邊形（如圖中第二行所示）。

我不確定從哪裏開始。

Example http://www.freeimagehosting.net/uploads/89a0276d9d.jpg

Answer 1

警告：讓代碼做到這一點絕對正確的是棘手的。 （從概念上講，這很好，但你可以很快陷入數字錯誤和邊緣情況。）你基本上要求一個2D版本的Constructive Solid Geometry。您可能想要查看是否可以使用由計算幾何中的專家編寫的現有庫。有一些圖書館here可能會做你想做的，但你必須選擇一個最適合你的表達方式，並將你擁有的表達方式轉換成表達方式。

Answer 2

這裏有一個免費的多邊形裁剪庫（寫在Delphi和C++），做什麼你問：盤被取出http://sourceforge.net/projects/polyclipping/