2つのポリゴンの間に区切り線があり、それらが線の両側にあるような単純なアルゴリズムはありますか？あるいは、誰もがこの種のことをするライブラリを知っていますか？私はJTSを使用2つのポリゴンの間に区切り線を見つける
：http://www.vividsolutions.com/jts/JTSHome.htm
は、このライブラリを使用して2つのポリゴンを作成し、ポリゴン間の2つの最も近い点を見つけるために、DistanceOpを走った（
私の解決策：すべてのヘルプは
EDITをいただければ幸いです必ずしも頂点ではない）。次に、それらを結ぶ線の垂線を計算します。
とBを2つのポリゴンにすることができます。まず、それぞれconvex hull,C（A）およびC（B）を見つけます。 明らかに、BからAを分離する行は、C（A）をC（B）から分離します。 をC（A）上の点とし、b点をC（B）に設定してください。一つはとBが発見されたを通じて分離線までとB の周りに境界線を歩くことができます。これは、直線的な時間で達成される になる可能性がありますが、ここでは説明しません。
ポイントA1、B2、A3、...、ANを持つポリゴンAと、ポイントB1、B2、B3、...、BNを持つポリゴンBがあるとします。あなたは何ができるか
は、すべての可能な組み合わせ（A1 & B1、A1 & B2、... & BN）のためにBXにポイントAXから行を記述することです。
このような行はパラメトリック形式で記述することができます：SomePoint = InicialPoint + Direction * tとなり、可能なの「分離線」になります。それをつけろ！
ここでは、各ポリゴンの各点からこの候補線に別のベクトルを記述することです。これらの行のそれぞれには方向ベクトルがあります。
各行の方向ベクトルと候補の方向ベクトルとの外積が同じ方向（Z-正またはZ-負）の場合、それらの点が分離線の同じ側にあることを意味します）。
ここで、各ポリゴンの各点について記述したすべての線を確認します。ポリゴンAのすべての点が一方の側にあり、ポリゴンBのすべての点が他方の側にあるかどうかを調べることができます。次に、必要な線が見つかりました。そうでない場合は、次の候補ライン（AX-BX）を試してみてください。考えられるすべての候補行でこれらの組み合わせが見つからない場合は、ポリゴン間に交差点があることを意味します。
私はそれが最高/最速のアルゴリズムであるかどうかはわかりませんが、うまくいきます。