8

通常、ベクトル (2*1 または 1*2 行列) で CW または CCW にソートされた頂点を持つポリゴンで作業することが一般的です。しかし、ベクトルに穴が開いたポリゴンをどのように記述すればよいでしょうか?

これらのポリゴンにさまざまなプロセスを適用するので、簡単に、または効率的に作業できる表現方法が必要です (つまり、アルゴリズムを簡単にするために、プログラムでその種のポリゴンを記述する方法は?)

ポリゴンは 2D で、MATLAB でプログラミングしています。

EDIT 1 :これらのポリゴン (穴の有無にかかわらず) の可視性グラフを計算します。

4

6 に答える 6

6

他の人が述べたように、穴のあるポリゴンは、外部境界とゼロ以上の内部境界として表すことができ、それらはすべて相互に重なりません*。ゼロ以外の巻き数を使用して内側/外側を決定する場合は、内側の境界を外側の境界と反対方向 (外側の場合は反時計回り、内側の場合は時計回り、またはその逆) に指定して、輪郭積分が内側でゼロになるようにしてください。穴。

参考までに、この種の定義/表現は、OpenGIS Simple Features Specification ( PDF ) で形式化されています。

表現に関する限り：

おそらく、K Nx2 行列のセル配列があり、セル配列の最初の要素が外部境界であり、セル配列の残りの要素 (存在する場合) が内部境界です。各境界に同じ数のポイントがない可能性があるため、セル配列を使用します。

*重ならない = 個々の点を除いて、例えば四角の中のひし形:

代替テキスト 代替テキスト

于 2009-06-29T17:12:04.087 に答える
3

穴の開いた多角形を、穴のない 2 つの形状に分割できます。複雑な平面で輪郭の統合を行う場合、ポリゴンの 1 つのエッジから穴のエッジに到達する「カット」を作成できます。穴の片側と背面の周りを統合します。次に、2 番目のポリゴンの反対側をトラバースします。各カットに沿って、互いに打ち消し合う 2 つの経路積分が得られます。

「可視性グラフ」 - これはシェーディングを使用した放射形態係数の計算用ですか? それともレイ トレーシング グラフィックス アルゴリズムですか?

于 2009-06-26T00:19:03.450 に答える
1

おそらく、これをできるだけ一般的にしたい場合は、ツリー構造が必要になります（つまり、内部にポリゴンがあり、内部に穴があるポリゴンの穴のあるポリゴンなど）。Matlabは、ツリー構造を効率的に表現するのはあまり得意ではありませんが、ここに1つのアイデアがあります...

ポリゴンの構造体配列があります。

各ポリゴンは、「corners」と「children」の2つのフィールドを持つ構造体です。

'corners'フィールドには、「data {polyIdx} .corners（：、cornerIdx）」としてアクセスされる、コーナーの（x、y）座標のマトリックスが含まれています。

'children'フィールドは、ポリゴンの構造体配列です。

これは、穴である偽の子で三角形を作成するためのコードの例です（ただし、重複する可能性があるため、実際には有効ではありません。

polygon = struct;
npoints = 3;
polygon.corners = rand(2,npoints);
polygon.children = struct;
nchildren = 5;
for c=1:nchildren
    polygon.children(c).corners = rand(2,npoints);
    polygon.children(c).children = struct;
end

穴の作成と塗りつぶしを交互に繰り返す子を再帰的に定義し続けることができます。

于 2009-06-26T03:52:42.747 に答える
1

各穴は、ポリゴン自体の内側にある単なるポリゴンのように聞こえます。おそらく、外側のポリゴンについて説明したようなベクトルを保存してから、穴のポリゴン ベクトルのベクトルを保存できます。

于 2009-06-25T22:30:20.533 に答える
1

多角形と、多角形の穴のリスト。さまざまなポリゴンが交差しないようにしてください。

このことで何をするつもりですか？

于 2009-06-25T22:28:45.297 に答える
0

「可視性グラフ」の下で正確に何を意味しますか?

2 つの「完全な」ポリゴン。+1 または -1 の 2 つの状態が可能です。

穴を表している場合、状態 +1 の 1 つと状態 -1 の 1 つがあり、これは穴を表し、状態 0 になり
ます。ポリゴンが重なっている場合は、結果の状態になります。 >1。次に、新しいポリゴンの境界を計算できます。
穴が交差する 2 つのポリゴンがある場合は、最初に 2 つの古いポリゴンの外側の境界線で構成される新しいポリゴンの状態を計算してから、穴を処理します。

とにかく、... 一般的な原則は理解できたと思います。

matlabでそれを行う方法がわかりません。これまでのところ、ごくわずかしか使用しておらず、非常に単純なことでも使用していました。

于 2009-06-25T22:42:40.963 に答える