問題タブ [convex]

曲線があると想像してみてください。どうしたら直線にできますか？私を助けることができる論文やアルゴリズムを知っていますか? それを行う 1 つの方法は、エネルギー関数を定義することです。しかし、私は基準が何であるかについての考えを持っていません。私の問題は、半円のような単純な曲線ではありません。曲線の例を添付します。x 軸または y 軸上の線に点を投影することは良い選択肢ではないと思います。

ありがとう！

ポイントクラウドの配列があります（独自の領域にあると判断されたポイントのクラスター）。

目標は、これらの個々のクラスターを結合することです。

私。交差

ii. お互いからの最小距離内

チェックiiはこれをより困難にします。これらのポイント クラウドをすばやく処理するために、AABB (X 軸に沿って整列された軸整列バウンディング ボックス) を作成しています。

私の現在の方法は、分離軸定理のいくつかのプロパティを使用することです。

1. ポイントクラウドごとに AABB を作成する
2. 各 AABB について、これらをランダムな軸に射影し、これらの線形射影をこの行 o(nlog(n)) のどこにあるかによって並べ替えることによって、それらが重複しているかどうかを確認します。次に、このリストを調べて、SAT を使用して交差 O(N) を確認します。ほとんどの AABB の線形射影は重ならないため、交差しません。交差するものは手動で確認できます (1D で重ならないことは交差がないことを保証するためですが、その逆は当てはまりません)。

最後の部分は私が立ち往生しているところです。上記の 1D 投影は、交差の O(n^2) ペアワイズ チェックを回避するために行われました。しかし、特定のしきい値内にあるが交差していない凸多角形を結合するために、O(N^2) ペアワイズ チェックを回避する方法がわかりません。

各ペアごとの組み合わせをチェックせずに、特定の距離内にあるすべての凸多角形を組み合わせてツリーまたはグラフを作成する方法はありますか?

1 と 2 の私の手順を使用する場合、残りのポイント クラウド/AABB が交差していないと想定できます。

編集

threshold/2潜在的な解決策は、AABB幅と高さにを追加し、交差をチェックすることです。それらが交差する場合、実際の交差 (AABB では高速) と 2 つの間の最小距離の両方を確認できます。

Christer Ericson の衝突検出に関する著書では、次のアルゴリズムを使用して、凸多角形間の衝突を検出する高速化された GPU メソッドを提供しています。

私は OpenGL にまったく慣れていません。私の質問は、次の 2 つstd::vectorのポイントを考えると、次のとおりです。

std::vector<Point>これを次の関数に渡し、結果を C++ で返すにはどうすればよいですか? 私のベクトルは反時計回りの凸多角形です。

CH1 と CH2 を 2 つの凸多角形とする。2 つの多角形間の相互関係の考えられるすべての異なるケースで機能することを正当化する、頂点の数に線形の時間でそれらの結合の凸包を計算するアルゴリズムを与えます。

これを行う方法はありますか？

私は現在、ゲームの 2D 照明システムに取り組んでいます。マップは、特定のタグと特性を持つことができるタイルで構成されています。この場合、いくつかのタイルを「不透明」に設定し、不透明なタイルごとに一連の長方形を生成する関数を作成しました。長方形の大きなグループを凸多角形にマージすることにより、このジオメトリを最適化したいと考えています。

私の長方形は、配列内の線分のコレクションとして定義されています。

長方形ポリゴンの例:

私の質問は、長方形の大きなグループから凸多角形の小さなグループをどのように生成できますか? 私は決して専門家のコーダーではないので、回答に完全な説明と、可能であれば例を含めてください。私は自分でこれを理解しようとして数時間以上費やしました。

ありがとうございました！

Point が凸包 (C/C++) の内側/外側または境界 (エッジ) 上にあるかどうかを判断できるアルゴリズムが必要です。

凸包は、ポイント X、Y、整数の配列として記述され、接続は i から i+1 までです。

現在、ここで説明されている巻き数アルゴリズムを使用しています。 http://geomalgorithms.com/a03-_inclusion.html 関数「wn_PnPoly()」です。

ポイントが凸面の境界(エッジ)上に正確にある場合、巻き数アルゴリズムを検出させることは可能ですか? それを行う別のアルゴリズムはありますか？（intで作業する必要があります）。

ウェブカメラにかざした紙の写真があり、写真の領域を紙だけに最小化したいと考えています。このようにして、私の OCR プログラムは潜在的により正確になり、おそらくより高速になります。

これまでに、紙を背景から分離するためにいくつかの手順を実行しました。

まず、高いしきい値を設定した Canny Edge 検出を使用します。これにより、画像のエッジが 2 色で表現されます。その上に、背景に鋭いエッジを持つ他のアーティファクトの中に角丸長方形が表示されます。

次に、ハフ変換を使用して、黒の背景に極座標で 100 を超えるポイント ヒットを持つベクトルを描画します。結果の画像は次のとおりです。

中央にある大きな (最大の) ほぼ長方形の図が見えますか? それが私が持っている紙です。その台形を多角形として分離するか、何らかの方法でその頂点の座標を取得する必要があります。

元の画像でこれらの座標を使用して、紙の PNG だけを分離することができます。

また、これら 3 つのサブ質問のいずれかに回答していただければ幸いです。

-画像上でこれらの線の交点の位置をどのように見つけますか?

-中心の台形ポリゴンを形成しない線を取り除くにはどうすればよいですか?

-これらの点で、画像の台形/長方形の領域のみを取得できる凸包よりも優れたものはありますか?

私のプログラムがより良い画像を生成した別の例を次に示します。