問題タブ [polygon]

またしても、ポリゴンアルゴリズムに関していくつか質問があります。

私は私の問題を説明しようとします：

Geometric Tools（GT）と呼ばれるサードパーティのライブラリのサブセットを使用して、ポリゴンに対してブール演算を実行しています。これを実現するには、内部ポリゴン形式をGTが使用する形式に変換する必要があります。

内部ポリゴン形式は頂点配列で構成されていますが、GTポリゴンはインデックス付きの頂点配列で構成されており、各エッジはインデックスのペアで表されます。

明確にするための正方形の例：

内部フォーマット：

外部フォーマット：

ここで、ほとんどの場合に機能するアルゴリズムを作成しましたが、2つのエッジが同じ開始頂点を共有すると、クラッシュしてバーンします。私の現在のアルゴリズムがどのように機能するかを説明することから始めましょう。

キーが頂点インデックスを表す整数であるstd::mapを作成します。この値は、エッジ配列のどこに、開始インデックスとしてkey-indexを持つエッジがあるかを表します。

モックアップの例：

正しいエッジから正しいエッジにジャンプするには、whileループ内で次のことを実行できます。

このループ内でいくつかの最適化が行われ、頂点インデックスが配列に追加されます。

ポリゴンを閉じるたびに、最初のトラバースされていないエッジを見つけて、別のポリゴンの作成を開始します。GTPolygonにトラバースされていないエッジがなくなるまで、これを続けます。

したがって、各GTPolygonは、複数のPolygon（内部）オブジェクトになる可能性があります。

このアルゴリズムの欠陥は、開始頂点と同じ頂点を共有する2つのエッジがある場合に明らかです。例：

エッジをトラバースするとき、これらのエッジのどれが現在トラバースしているポリゴンに属しているかをどのように知ることができますか？このような重複した状況が発生した場合は、エッジを後方にトラバースしてみることができます。問題は、反転中に別の重複が見つかった場合に、トラバースが無限に前後に移動する可能性です。

私の質問は、どうすればこれを解決できますか？それはまったく解決可能ですか？BSPツリーを使用してこれを何らかの方法で解決できますか？コーナーケースの数は少し気が遠くなるほどで​​す。

5か月の作業はこの作業に依存するため、どんな助けでも大歓迎です。

編集：

明確にするために：Geometry Toolsが機能するポリゴンのインデックス付き表現から、リスト内の一連の接続された頂点である内部ポリゴン形式に変換したいと思います。

私の問題は「凸包」に関連していると思いますが、同じではありません。図面内のすべての形状は、幅と高さが同じ長方形です。多くは互いに隣接しています。これらの隣接する長方形をポリゴンに結合したい。「凸包」とは異なり、生成されたポリゴンは内部が「中空」になる可能性があります。

利用可能なオープンソースのアルゴリズムはありますか?

凹型 (非凸型) 多角形の対角線 (対角線は、隣接しない頂点を接続するセグメントです) は、完全に多角形の内側または外側にある場合があります (または、多角形のエッジと交差する場合があります)。完全にポリゴン内にあるかどうかを判断する方法は? (ポイント イン ポリゴン テストを使用しない方法)。

OpenGL で複雑な凹面ポリゴンを描画するには、それを三角形にテッセレートするか、ステンシル バッファーを使用する方がよいでしょうか? ステンシル バッファは 1 つのフレームの場合は高速になると思いますが、ポリゴンが変更されない場合は、複数のフレームの場合は三角測量の方が適しています。ただし、実際に試したことがないのでわかりません。

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

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

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

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

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

今回は賢明な質問だといいのですが...

上半分のテクスチャは問題ないように見えますが、下半分 (もう少し回転させた後) ではテクスチャが壊れていて、形状の内側が見えますか? ポリゴンが消えた？

この問題は何と呼ばれますか? 私は知る必要があるので、それを修正するときに何を探すべきかを知っています!

ちなみに、Papervisionでやっています。たまたま修正を知っている場合 (または可能であれば)、正しい方向に私を向けることができれば、自分自身についてさらに良い気分になることを許可します.

ありがとうございます！

ポリゴン(凹面または凸面)を使用するmatlabプログラムを開発しています。ポリゴンに対して imdilate や imerode などの画像処理関数を使用する必要があります。この目的のために、ポリゴンを画像に変換する必要があります。ポリゴンをバイナリ マトリックス (フォアグラウンドは 1、バックグラウンドは 0) で直接スケッチする方法があるかどうか疑問に思っています。

現在、「getframe」、「frame2im」、「im2bw」関数の順に使用しています。ただし、その欠点は、matlab がそのプロットをピクセル単位で表示しないため、最終的な画像 (= マトリックス) のサイズ (つまり、フレームを画像に変換するときのピクセル単位の画像のサイズ) を制御できないことです。 (?)。したがって、誰かがプロットを「ズームイン」または「ズームアウト」するたびに、結果のマトリックス (= 画像) は異なります。

私のコード:

ポイントのセット S (2D : x と y で定義) があり、セットのすべてのポイントを囲む最小の (つまり、ポイントの数が最小の) P を見つけたいと思います。P は順序付けられたサブセットです。 S.

これを計算するための既知のアルゴリズムはありますか? (この分野における私の文化の欠如は驚くべきことです...)

ご協力いただきありがとうございます

私は、NLCD データを使用して、森林と非森林の 7 つの州という広大な地域で作業しています。森林地帯の一部には区画があります (これは私が取り組んでいる修士論文です)。この大規模なデータセットで質問したすべての人を困惑させましたが、そこに解決策があると確信しています. 森林/非森林エリアは、署名された個別のラスターです。森林地帯をサブセット化することで、森林地帯をポリゴンにすることができました。非森林エリアをポリゴンにできません (大きすぎます)。そのため、森林に覆われたポリゴンの端までのポイント距離 (ポイントはポリゴン内にあります) を取得しようとしていました。ポイントから森の端までの距離を取得するための提案はありますか?