rotating_calipers

回転キャリパーモジュール

回転キャリパーは、同じ名前のアルゴリズムを実装するPythonモジュールです。

回転キャリパーアルゴリズム

アルゴリズムは1978年にミカレル・シャモスによって最初に発明され、1983年に彼の論文でそれを取り上げたゴッドフリード・トゥーサントのおかげで、「回転キャリパー」という名前を獲得しました。

この方法は、凸型ポリゴンの外側にスプリングに搭載されたバーニエキャリパーを回転させることに類似しているため、この方法の名前が付けられています。キャリパーのブレードがポリゴンの端に平らに横たわるたびに、反対側の刃に触れるポイントまたはエッジとアンチポダルペアを形成します。ポリゴンの周りのキャリパーの完全な「回転」は、すべての抗極端なペアを検出します。グラフと見なされるすべてのペアのセットは、スラックを形成します。キャリパーを回転させる方法は、スイープラインアルゴリズムの射影デュアルとして解釈できます。このアルゴリズムでは、スイープがXまたはY担当者のポイントまたはY座標ではなく、線の斜面に並んでいます。

上記の説明は、wikipediaページ：https：//en.wikipedia.org/wiki/rotating_calipersから採用されています

モチベーション

「回転キャリパー」アルゴリズムは、大学プロジェクトのために私によって実装されました。驚くべきことに、私はPythonで効率的なソリューションを見つけるのに多くの問題を経験しました。だからこそ、Pythonで迅速な「回転キャリパー」実装が必要なすべての人と共有したかったのです。

複雑

回転キャリパーが線形時間に実行されると、入力式に凸式船体が必要です。ここでは、O（nlogn）で実行されるGrahamのアルゴリズムを使用して計算されます。すべてのAlgorihm（Grahamのアルゴリズム +回転キャリパー）時間の複雑さはO（nlogn） + O（n）= o（nlogn）です

インストール方法

Linux：

1. ターミナルを開く
2. 実行：ピップインストール回転カリパー

使い方

使用の例はこちらをご覧ください