3

「与えられた4つの座標が正方形を形成するかどうかを確認する」に答えているときに、平行四辺形をチェックしてから直角をチェックするこの答えに出くわしました。これは機能しますが、入ってくるポイントが特定の順序になっている場合のみです。つまり、P1 と P3 は、隣接するのではなく、互いに「反対側」にある必要があります。

では、質問です。入ってくる 4 つの点が任意の順序である可能性がある場合、四角形を作成するための「正しい」順序になるようにそれらを並べ替えるにはどうすればよいでしょうか?

私が思いつくことができる最も簡単なことは次のようなものです：

for each valid permutation of points[]{ // see below for "valid"
    generate line segment for:
        points[0] -> points[1]
        points[1] -> points[2]
        points[2] -> points[3]
        points[3] -> points[0]
    if any line segment crosses another // use cross product
        continue
    return permutation
}

ほとんどの順列は単純な回転( )であることを知っている0123 == 1230ので、最初のポイントを「固定」しておくことができます。また、他の 2 つの順序は関係ないので、各順列スポットの0とにあるポイントだけを考えれば、それを減らすことができると思います。2たとえば、0123がポリゴンの場合は0321、同じセグメントを生成するためです。

これにより、確認する基本的な順列が 3 つだけ残ります。

  • [0,1,2,3]
  • [0,1,3,2]
  • [0,2,1,3]

各順列には 6 つのセグメント間チェックがあるため、合計 18 回の比較になります。

これを行う他の方法は考えられませんが、何かが足りないようです。これを行うより良い方法はありますか？四角形の質問に対する回答は適切ですが、ポイントが正しい順序であることを確認するためにさらに (最大で) 18 回のチェックを行う必要がある場合は、コーナー間の距離を使用する方が速くなります。

4

4 に答える 4

2

各順列には 6 つのセグメント間チェックがあるため、合計 18 回の比較になります。

すべてのセグメントをチェックする必要はありません。セグメント[0-2]と[1-3](つまり、2 つの対角線) が交差していることをチェックするだけで十分です。セグメントが属する線ではなく、セグメントが交差していることを確認する必要があります。つまり、セグメントの外側の交差はカウントされません。

開始点を修正すると"A"、最終的に 6 つの順列が考えられます。

ここに画像の説明を入力

それらのうちの 2 つ (A-B-D-CとA-C-D-B) は適切です。残りの4つは悪いです。次の 2 つのチェックだけで、適切なものに到達できます。

  • 初期順列を確認してください。良ければそのままにしておきます。それ以外は
  • ポイント 1 と 2 を交換し、順列を確認します。良ければそのままにしておきます。それ以外は
  • 元の順列に戻り、ポイント 2 と 3 を交換して、その順列を維持します。「いい」に違いない。
于 2013-08-06T16:10:29.567 に答える
1

isParallelAndEqual(p0,p1,q0,q1) というメソッドを実装します。これは、線 p1-p1 と q0-q1 が平行で長さが等しいかどうかをチェックします。

ポイント a、b、c、および d を指定すると、最終結果は次のようになります。

ifParallelAndEqual(a,b,c,d)||ifParallelAndEqual(a,c,b,d)

于 2013-08-06T15:45:37.560 に答える
1

正しいものが見つかるまで、以下のすべてを簡単に確認できませんか? (つまり、お互いの反対側の P1 を確認します)

P3 = P1 + (P2-P1) + (P4-P1)
P2 = P1 + (P3-P1) + (P4-P1)
P4 = P1 + (P2-P1) + (P3-P1)

正方形のバリアントの場合、それらが軸に沿って配置されている場合は、次のことができます: (つまり、反対側の点は、共通の座標を持たない点です)

if (P1.x != P3.x && P1.y != P3.y)
  check P3 = P1 + (P2-P1) + (P4-P1)

if (P1.x != P2.x && P1.y != P2.y)
  check P2 = P1 + (P3-P1) + (P4-P1)

if (P1.x != P4.x && P1.y != P4.y)
  check P4 = P1 + (P2-P1) + (P3-P1)

otherwise return false
于 2013-08-06T15:57:11.870 に答える
0

次のようにする方が簡単ではないでしょうか。

  1. ポイント0, 1と2スパンが三角形かどうかを確認します (それらが同一線上にある場合は、四角形も縮退しています)
  2. 次のセグメントの交差を確認します。

[0, 3] and [1, 2]
[1, 3] and [0, 2]
[2, 3] and [0, 1]

それらのどれも交差しない場合、四角形は非凸です。

それ以外の場合は、交差するケースが 1 つだけ必要です。そこに反対の頂点を見つけました。

于 2013-08-06T15:45:09.900 に答える