scipy内の交差していない2つのポリゴンの凸包を計算する

交差していない2つのポリゴンの凸包を計算するscipyメソッドはありますか？私は2組の点P1とP2とその凸包CH（P1）とCH（P2）を持っています。船体は交差していません。私はP1とP2の点の和集合の凸包の船体を見つけたいと思っています。 scipyにメソッドのビルドがありますか？scipy内の交差していない2つのポリゴンの凸包を計算する

出典

2016-11-03 Sudipta Roy

特定のプログラミングライブラリや言語に関するコーディングに関する質問や質問は、CS.SEではトピックになっていませんが、スタックオーバーフローに関する質問があります。私たちの[ヘルプ/トピック]を参照してください。 CS.SEは、概念、アルゴリズム、科学についての質問です。 –

Scipyの凸包の実装のドキュメントはhereです。 2つの点の配列を連結して結合を得るだけです。この集合を凸包アルゴリズムに与える。

各ポリゴンの各点は、そのポリゴンの凸包内にあります。次に、両方の多角形の凸包は、大きな凸包内に完全に含まれています。したがって、各ポリゴンのすべての点は、大きな凸包内にあります。つまり、ポリゴン点の完全な結合にも有効です。

出典

2016-11-03 19:55:47 Arthelais

しかし、メソッドのポイントの和集合をフィードすると、複雑さはnlognですが、ユニオンの凸包は線形時間で決定できます。 –

問題を解決するための[線形アルゴリズム]（http://cs.smith.edu/~orourke/books/compgeom.html）が存在することは間違いありません。しかし、これはSciPyに実装されていない非常に特殊な最適化です。あなたは本当に線形に問題を解決する必要がありますか？大量のポイントがない限り、それほど速くはありません。 – Arthelais

私の課題の1つに必要です。これは課題の主要な部分ではありません。私はそれと一緒に暮らすことができると思う。それはアルゴリズムnlognを作成しません。 –

scipy内の交差していない2つのポリゴンの凸包を計算する

答えて

関連する問題