3

一連の頂点 (反時計回りの順序であると仮定できます) で表される凸多角形が与えられた場合、この多角形をどのように分割して、脚が X 軸と Y 軸に整列する一連の直角三角形にできますか?

私はおそらくいくつかの数学用語を欠いているので、斜辺ではない2 本の線を「足」と呼んでいます(数学用語を顔に突き刺してしまった場合は事前にお詫びします。簡単な訂正は追加のクレジットです)。

4

6 に答える 6

1

これを行うためのアルゴリズムを書くことについてはよくわかりませんが、紙上の任意の凸多角形に対してこれを行うことは完全に可能であるようです。各頂点に対して、その頂点から垂直または水平の線を別の垂直線または水平線と交わるまで投影します。角度の変化が小さく、隣接する辺が両方とも x と y に関して同じ方向に移動している頂点の場合、頂点から水平線と垂直線の 2 本の線を追加する必要があります。これを行うと、元のポリゴンの中心にポリゴンが残りますが、元のポリゴンの頂点から引かれた線によって辺が形成されているため、辺は垂直または水平になります。これらの側面は垂直または水平のいずれかであるため、

于 2009-02-11T16:17:15.863 に答える
1

上で説明したように頂点を既に並べ替えており、それらが実際に凸多角形を定義していると仮定しています。

各頂点は水平線を定義します。V頂点の場合、一連のVラインがあります。次の基準のいずれかを満たす行を破棄します。

  • その線を定義する頂点または頂点は、最高または最低の Y コンポーネントを持っています (1 つの頂点の場合、その線はその点でのみポリゴンと交差します。2 つの場合、その線はポリゴンのエッジと一致します)。
  • 2 つの頂点の Y 座標が等しい場合は、それらの線の 1 つだけを保持します (複製されます)。

結果は、ポリゴンの「バンディング」に似ています。

各水平線は 2 点で多角形と交差します。1 つはその定義頂点です。もう 1 つは、別の頂点か、2 つの頂点によって定義されるセグメント上の点です。Y座標を単純に比較するだけで、どちらが該当するかを簡単に判断できます。セグメントとの交点の座標も簡単な計算です。お任せします。

各交点は、垂直セグメントを定義します。セグメントはポリゴン内に含まれ (エッジと一致する場合は破棄できます)、もう一方の端は別の水平線、またはエッジ自体が水平である場合はポリゴンのエッジと交わります。ケースを決定することは、座標の単なる比較の問題です。最後に、0 ～ 2 個の追加の垂直セグメントが存在する場合があり、いずれかが 1 つしかない場合は、Y 座標が最大または最小の頂点によって定義されます。

結果のダイアグラムでは、可能であれば各端から切り取られた直角三角形を含む各バンドが表示されます。各三角形は、基準を満たす必要があります。残りの領域は長方形です。任意の対角線を引いて、それぞれを基準を満たす 2 つの直角三角形に分割します。

あなたは終わった。

于 2009-02-11T17:24:43.627 に答える
0

これは一般的なケースでは不可能だと思います。

ポリゴン{（0、1）、（1、0）、（2、0）}を考えてみましょう。

.
 ..

あなたが説明するように、この三角形を有限数の三角形に分割することはできません。

于 2009-11-23T18:10:09.610 に答える
0

提起された質問に対する一般的な解決策があるとは確信していません。問題は、X 軸と Y 軸のビットの位置合わせです。つまり、各頂点を X 方向と Y 方向の両方でポリゴンの反対側に投影し、それらの交点に新しい頂点を作成する必要があります。ただし、そのプロセスは、その方法で追加された新しい頂点ごとに続行する必要があります。運が良ければ、このプロセスが終了する可能性があります (反対側に頂点が適切に配置されているため)。

その制限を捨てれば、Neil N の提案は私には良さそうに思えます。

于 2009-02-11T15:59:01.617 に答える
0

これが可能かどうかはわかりません。X 軸と Y 軸の辺が既に揃っている正方形について考えてみましょう。X、Y 軸に位置合わせされた頂点を使用して、どのように三角形を描画しますか?

または、ポリゴンの実際の辺が x、y 軸に沿っていることを許可されていますか。つまり、正方形の対角線に沿って線を引くことができます。その場合、一部の辺が軸に整列し、他の辺が整列していない、より複雑な多角形を処理するのは難しい場合があります。

于 2009-02-11T15:39:11.603 に答える