4

私のスレッドへの拡張と部分的な答えとして、与えられたポイントのセット(xy座標を持つ)が自己交差しないポリゴンを形成できる単純なアルゴリズムを書きました。

主張: 異なる座標を持つ任意の点のセットが与えられると、規則的または不規則な、自己交差しない多角形を構築することが常に可能です。

アルゴリズム:

すべての頂点を含む集合 V があると仮定します

1) V のすべての頂点を x 座標で並べ替える

2) x 軸に平行な直線 (これを「分割線」と呼びます) を想像してください。最初のノードから始まり、無限に拡大し、頂点を 2 つのセットに分割/分割します。

3) 次に、2 つのセットを考えます。

A = 分割線の上または上にあるすべての頂点のセット

B = 残りのすべての頂点のセット

4) A の左端の頂点から始めて、A のすべての頂点を右端に到達するまで接続します。

5) ソートされたセット V の右端の頂点 (最大の x 座標を持つ頂点) が A にない場合、その最後の頂点 (A の右端) をそれと接続します。

6) ソートされたセット V の右端の頂点 (最大の x 座標を持つ頂点) から始めて、逆方向に作業し、B にあるすべての頂点を接続します。

7) B の最初 (B の左端の頂点) の頂点を A の左端の頂点に接続します。

アルゴリズムは正しく、失敗するテストを見つけることができないと思いますが、何かが欠けている可能性があります。

見ていただき、もしあればうまくいかない例を教えていただければ幸いです（きっとあるはずです）。

4

5 に答える 5

3

これが反例です。手順 5 で線が引けない場合は、自己交差が可能です。

反例

于 2011-03-12T00:57:54.963 に答える
2

あなたがやろうとしていることを正しく理解しているかどうかはわかりません。他のスレッド、およびmath.SE の対応するスレッド（それが私をここに連れてきました）、あなたは多角形を持っていて、その重心を見つけようとしていたと言いました。ここでは、一連の点があり、それから交差しない多角形を作成したいとします。これらは2つのまったく異なるものです。math.SE で述べたように、多角形が凸面であることがわかっていない場合、一連の点は多角形を一意に定義しません。したがって、ここで提案するアルゴリズムは、自己交差しない任意の多角形を構築する可能性があります (私はそれが成功するかどうかはチェックしていません)しかし、それはあなたが最初に興味を持っていたポリゴンとは何の関係もないかもしれません.または、私はmath.SEであなたの質問を誤解しましたか?それらからの非自己交差ポリゴンと、これに対するいくつかの不等解があるかもしれないことを気にしませんか?

于 2011-03-11T22:42:17.207 に答える
2

そのようなポリゴンを作成するより単純なアルゴリズムがあると思います。ソフトウェアで実装するのは難しいかもしれませんが、言葉で説明するのははるかに簡単です。

  • セット内の任意のポイントを開始点として選択します。そこから角度 0 の線を作成します。
  • ポイントを中心に線を回転させ始めます。他の点に出会った瞬間に、始点から新しく見つかった点までエッジを引きます。
  • 始点を中心に回転を続け、新しく見つかったポイントを最後に見つかったポイントに接続します。
  • 回転が終了したら、開始点に合わせて形状を閉じます。

一方向に複数の検索結果がある場合は、一方向を選択してそれらを接続します (たとえば、最も内側から始まり、最も外側で終わります)。

形状は通常、やや星のようなものですが、要件を満たしています。

計算実行は次のようになります。

  • ポイントの 1 つで原点 [0,0] で設定された座標にすべてのポイントを変換します。
  • すべての点を極座標セットに変換します
  • 並べ替え: 角度の昇順、半径の昇順。
  • 並べ替え順にすべてのポイントを接続します。
  • 最後に最初の ([0,0]) ポイントに接続します。
于 2011-03-11T22:45:47.327 に答える
1

「分割線」を x 軸に平行ではなく、左端と右端の間の接続として設定することにより、少し異なる方法で証明します。x に平行な線の下または上に点がなく、証明に問題が生じる可能性があります。

また、接続 (5) は、ポイント (6) で生成された接続との自己交差につながる可能性があります。

すべてのポイントが同一線上にあり、ポリゴンが線に劣化する特殊なケースもあります。

頂点のセット V は有限であると仮定します;)

それ以外は、あなたの主張は正しいと思います。

于 2011-03-11T22:33:05.903 に答える
0

javascript と OpenLayers ライブラリで同じ問題が発生しました。これは、「ベクター」レイヤーのポリゴンの有効性を OpenLayers.Layer.Vector として検出するための私のソリューションです。

var ps = vectors.features[0].geometry.getVertices(), i, j, inx, x1, x2, x3, x4, y1, y2, y3, y4, x43, x21, y21, y43, y31, maxx12, maxx34, minx12, minx34;
ps.push(ps[0]);
for(i = 0; i < ps.length -1 ; i++ ) {
  x1 = ps[i].x; x2 = ps[i+1].x;
  y1 = ps[i].y; y2 = ps[i+1].y;
  for(j = i + 2; j < ps.length -1 ; j++ ) {
    x3 = ps[j].x; x4 = ps[j+1].x;
    y3 = ps[j].y; y4 = ps[j+1].y;
    x43 = x4 - x3; x21 = x2 - x1; y21 = y2 - y1; y43 = y4 - y3; y31 = y3 - y1;
    inx = ( x43*y21*x1 - x21*y43*x3 + y31*x21*x43 )/( x43*y21 - x21*y43 );
    if( x1 < x2 ){
      minx12 = x1; maxx12 = x2;
    } else {
      minx12 = x2; maxx12 = x1;
    }
    if( x3 < x4 ){
      minx34 = x3; maxx34 = x4;
    } else {
      minx34 = x4; maxx34 = x3;
    }
    if (minx12 < inx && inx < maxx12 && minx34 < inx && inx < maxx34 ){
      console.log('intersected!'+' ,x1: '+x1+' ,x2: '+x2+' ,inx: '+inx+' ,i: '+i+' ,j: '+j);

      return;
    }
  }
}

楽しんでくれると良いです！！

于 2013-06-13T15:54:47.903 に答える