問題タブ [convex]

平面、おそらく地図上に多数の凸多角形があるとします。これらのポリゴンは互いに衝突してエッジを共有できますが、重なり合うことはできません。

2 つのポリゴンPとQがオーバーラップしているかどうかをテストするには、まずPの各エッジをテストして、 Qのいずれかのエッジと交差するかどうかを確認します。交差が見つかれば、 PとQが交差すると宣言します。交差しない場合は、PがQに完全に含まれているか、またはその逆かをテストする必要があります。次に、 P == Qの場合です。最後に、いくつかのエッジを共有しているが、すべてではないケースがあります。(これらの最後の 2 つのケースは、おそらく同じ一般的なケースと考えることができますが、それは重要ではないかもしれません。)

2 つの線分が交差する場所を検出するアルゴリズムがあります。2 つのセグメントが同一線上にある場合、私の目的では交差しているとは見なされません。

ケースを適切に列挙しましたか？これらのケースをテストするための提案はありますか?

交差点である新しい凸多角形を探しているわけではないことに注意してください。交差点が存在するかどうかを知りたいだけです。交点を見つけるための十分に文書化されたアルゴリズムが多数ありますが、すべての作業を行う必要はありません。

C++ ライブラリを探していて、凸の目的関数と制約関数を扱っています。

私は、2Dの任意のポイントのセットのモーショントラッキングなど、いくつかのコンピュータビジョン技術を研究して実装しようとしています。私は、知っているポイントのセットに対して凸包を作成し、マップできる可能性のあるポイントのセットに対して凸包を作成しています。2つの船体がどれほど似ているかを比較するのに役立つリソースを探しています。十分に似ている場合は、実際に互いにどのようにマッピングされますか？このスタイルのアルゴリズムと、この分野で潜在的により複雑なアルゴリズムについて説明している優れたリソース/書籍をどこで見つけるかについての情報をいただければ幸いです。

凸多角形 P と P の境界上の点 A が与えられた場合、AB が P を所定の比率の 2 つの領域に分割するように、P の境界上の点 B を計算するにはどうすればよいですか?

理想的には、分析ソリューションが必要です。最後の手段として、ポリゴンの任意の場所に線を描画し、比率が所定の精度になるまで徐々に移動します。

ポリゴン上のどの 2 点間を移動すべきかがわかったら、B を計算する方法を考え出しました。したがって、どのポイントの間を進むべきかを調べる方法があれば、そこから取ることができるはずです!

私はAndroidアニメーションが初めてなので、誰かが私を助けることができれば、オブジェクトを変換したいと思います。長方形を凸状に見せたいとしましょう。いくつかの関数でそれを行うことはできますか?たとえば、スキューや...誰かがアイデアやサンプル コードを持っていれば、本当に感謝しています。よろしくお願いします

点で表現された凸多角形があります。点はx 座標の配列と y座標の配列で表されます。

例えば：

このポイントを時計回りに並べ替えるにはどうすればよいですか? ポイントの数は常に同じではありませんが、ポリゴンは依然として凸状です。

atan2 またはmath.hの他の関数を使用しない解決策はありますか?

2D空間に2つの凸多角形がある場合、線上の任意の点で、いずれかの凸多角形の最も近い点から等距離にある線分をどのように作成しますか？

点ではなく凸多角形のボロノイ図の実装を検討していますが、2つの多角形だけの線の計算を開始する方法がわかりません。だから私はこれを一度に一歩踏み出してここから始めると思いました。

編集質問をもう少し明確にするために、平面（またはそのサブセット）を二等分したいと思います。

左側にポリゴンA、右側にポリゴンBがあるとします。平面を左側の点と右側の点に分割する二等分線があります。線上のすべての点は、どちらのポリゴンからも等距離にあります。線の左側のすべての点は、ポリゴンBよりもポリゴンAに近くなります。線の右側のすべての点は、ポリゴンBに最も近くなります。

これは、私が書いたMatlabスクリプトによって生成された、ブルートフォース近似を強制する画像です。

問題は、2つのポリゴンの「間」のスペースを調べるほど単純ではないと思います。これは、線が2つの形状の間の領域を直接超えて延びる必要があるためです。そして理想的には、2つ以上の形状に一般化する解決策を見つけたいと思います。これは、私には、問題をさらに複雑にしているように見えます。これは、それがどのように見えるかについての（明らかに非常に大まかな）概算です：

凸型の最適なライブラリをお勧めしますか？

理想的にはオープンソース。半正定値計画法とQCQPのアプリオリ。

（私はfsharpで使用するつもりですが、どのdotnetでも使用できます）

Android で libgdx を使用するアプリを作成しています。

エンド ユーザーがテクスチャの可視部分のみをクリックしたときのタッチ リスナーを追加する必要があります。

どうやってやるの？

テクスチャごとに固有の色を指定し、実際のコンテンツを描画する前に、その可視部分にこの色で描画し、タッチが完了した場合に、テクスチャごとに独自の色を指定するという良いアイデアがあることを覚えています (ただし、その実装は見たことがありません)。色で、エンドユーザーが画像をクリックしたことを意味します。libgdx に同じ手法を使用することは可能ですか? もしそうなら、どのように？

もちろん、回転/スケーリングするように選択した画像についても同じことが言えます。

おそらく、これはプログラミングの質問というよりも数学の質問ですが、XNA で回転キャリパー アルゴリズムを実装しようとしています。

ウィキペディアで詳述されているように、モノトーンチェーンを使用して、ポイントセットから凸包を推測しました。

ここで見つかった OBB の後に OBB を見つけるアルゴリズムをモデル化しようとしています: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

ただし、最終ページで言及されている DOTPR および CROSSPR メソッドが何を返すことになっているのかわかりません。

2 点の内積と 2 点の外積を取得する方法は理解していますが、これらの関数は 2 つのエッジ/線分の内積と外積を返すことになっているようです。私の数学の知識は確かに限られていますが、これはアルゴリズムが何を探しているかについての私の最善の推測です

ただし、コードのこの部分で指示されているようにこれらのメソッドを使用すると...

..ポイントのテスト セットを指定すると、j、k に対して同じインデックスが返されます。

perdue.edu の技術文書に示されているように、これらのポイントを反時計回りの順序で配置するために polygon.Reverse を呼び出すことに注意してください。ポイントセットの凸包を見つけるための私のアルゴリズムは、反時計回りの順序でポイントのリストを生成しますが、y < 0 が y > 0 よりも高いと仮定します。 . リストを逆にするだけで十分なようです。最後に重複したポイントも削除します。

このプロセスの後、データは次のようになります。

• ベクトル 2(115, 14)
• ベクトル 2(129, 0)
• ベクトル 2(131, 0)
• ベクトル 2(204, 63)
• ベクトル 2(199, 68)
• ベクトル2(150, 110)
• ベクトル 2(1, 138)
• ベクトル2(0, 138)

i が 0 で j が 3 の場合、このテストは最初のループで失敗します。 (115,14) から (204,63) への線分と (204,63) から (199,68) への線分の外積は次のようになります。 ) は 0 です。次に、同じ行の内積も 0 であることがわかります。したがって、j と k は同じインデックスを共有します。

対照的に、このテスト セットが与えられた場合: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C% 282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

私のコードは、この OBB を正常に返します 。 2C%285%2C3%29

http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cppにある C++ アルゴリズムを読んだことがありますが、あまりにも複雑すぎて完全に従うことができません。また、上記の論文で詳述されている他のものとは大きく異なるようです。

2 つの線分の内積と外積を見つけるために、スキップしているステップを知っている人や、コードにエラーが表示されている人はいますか? 以前にこのコードを C# で正常に実装し、例を持っている人はいますか?