rotating_calipers
Rotating calipers 1.0
旋轉卡尺是Python模塊，該模塊實現了具有相同名稱的算法。
算法是由Michalel Shamos於1978年首次發明的，並獲得了“旋轉卡鉗”的名字，這要歸功於Godfried Toussant在1983年在他的論文中介紹了它。
該方法之所以如此命名，是因為該想法類似於將彈簧加載的游標卡鉗圍繞凸多邊形的外部旋轉。每當卡尺的一個刀片都平放在多邊形的邊緣時，它會形成一個抗雙相或邊緣，觸摸相反的刀片。圍繞多邊形的卡尺的完整“旋轉”檢測到所有抗蟲對；所有對被視為圖形的對組的集合形成了一個索。旋轉卡尺的方法可以解釋為掃描線算法的投影偶，其中掃描橫跨線的斜率而不是跨點或y顏色的點。
上面的描述從Wikipedia頁面進行了改編：https：//en.wikipedia.org/wiki/rotating_calipers
我為大學項目實施了“旋轉卡鉗”算法。令人驚訝的是，我在Python中找到了有效的解決方案遇到了很多麻煩。這就是為什麼我想與需要快速“旋轉卡鉗”實現的每個人分享的原因。
由於旋轉卡尺在線性時間內運行，因此在此處使用Graham的算法在此計算輸入WIHCH上的凸面船體，該算法在O（nlogn）中運行。總而言之
Linux：
使用的示例可以在此處找到
