3

閉じた多角形を表す線分の配列を生成するライブラリ ( JavaScript-Voronoi ) を使用しています。これらのセグメントは、セグメントが表示される順序とセグメントの各端点の順序の両方で、順不同で表示されます。

（編集：以下のコメントに記載されているように、私は間違っていました：ライブラリのセグメントは適切に順序付けられています。ただし、質問は書かれているとおりです：セグメントには順序付けがないと仮定しましょう。これにより、より一般的に便利になります。 .)

例えば：

var p1 = {x:13.6,y:13.1}, p2 = {x:37.2,y:35.8}, p3 = {x:99.9,y:14.6},
    p4 = {x:99.9,y:45.5}, p5 = {x:33.7,y:66.7};
var segments = [
  { va:p1, vb:p2 },
  { va:p3, vb:p4 },
  { va:p5, vb:p4 },
  { va:p3, vb:p2 },
  { va:p1, vb:p5 } ];

最初のセグメントが最後のセグメント (共通点を共有する) と、最後から 2 番目のセグメントにどのようにリンクしているかに注意してください。すべてのセグメントがちょうど 1 つの他のセグメントと端を共有することが保証されています。

これをポイントのリストに変換して、適切な SVG ポリゴンを生成したいと思います。

console.log( orderedPoints(segments) );
// [
//   {"x":33.7,"y":66.7},
//   {"x":13.6,"y":13.1},
//   {"x":37.2,"y":35.8},
//   {"x":99.9,"y":14.6},
//   {"x":99.9,"y":45.5}
// ]

ポイントが時計回りか反時計回りかは関係ありません。

次のコードは私が思いついたものですが、最悪のシナリオではn^2+nポイント比較が必要になります。これらすべてを結合するためのより効率的なアルゴリズムはありますか?

function orderedPoints(segs){
  segs = segs.concat(); // make a mutable copy
  var seg = segs.pop(), pts = [seg.va], link = seg.vb;
  for (var ct=segs.length;ct--;){
    for (var i=segs.length;i--;){
      if (segs[i].va==link){
        seg = segs.splice(i,1)[0]; pts.push(seg.va); link = seg.vb;
        break;
      }else if (segs[i].vb==link){
        seg = segs.splice(i,1)[0]; pts.push(seg.vb); link = seg.va;
        break;
      }
    }
  }
  return pts;
}
4

3 に答える 3

3

ポリゴンが凸面の場合は、各線分の中点を選択し、凸包アルゴリズムを使用して、中間のアイテムごとに凸多角形を見つけることができます。これは、中央の配置がわかり、どの中央がどの中央に属するかがわかっているためです。セグメントでは、元の配列で配置を見つけることができます。

凸包を見つけたいだけの場合は、凸包アルゴリズムを直接使用します。これはO（n log n）で、十分に高速ですが、JavaScriptでQuickhullアルゴリズムを見つけることもできます。クイックハルもありますO(n logn)が、平均して最悪のケースはO（n ^ 2）ですが、定数係数が少ないため高速です。

しかし、一般的なアルゴリズムの場合：

各セグメントの一方の端を最初に設定し、もう一方の端を2番目に（ランダムに）設定します。

セグメントを最初の順に並べ替え、その後x配列に入れます。最初Firstに同じもののセグメントを最初に並べ替え、構造に2つ余分に追加して、同じ最初のアイテムの開始位置と終了位置を保存します。xyintx

次に、セグメントを2番目のx値....で再度並べ替え、配列を作成しsecondます。

上記のアクションは両方ともO（n log n）にあります。

次に、配列の最初のセグメントを選択し、両方の配列でFirst2番目の値を検索します。同様の値が見つかった場合は、関連するサブ配列でそれらの値を検索します（同じアイテムの開始位置と終了位置があります）。この順序のセグメントは1つしかない（現在のセグメントでもない）ので、次のセグメントを見つけるには時間がかかります。また、次のセグメントがあるため（前処理も）、。よりも非常に高速です。xFirstsecondyxO(log n)n-1O(n logn)O(n^2)

于 2013-01-10T10:08:44.307 に答える
2

凸多角形の場合、辺のセグメントを知る必要さえありません。たくさんの頂点が必要です。頂点を並べ替える手順は非常に簡単です。

  1. すべての頂点を平均して、ポリゴン内のポイントを取得します。これは重心である必要さえないことに注意してください。ポリゴン内のポイントである必要があります。この点を C とします。
  2. 各頂点 V[i] について、V[i] から C への線分が V[i] から V[i]+(1,0) への線分と形成する角度を計算します。これを a[i] と呼びます。
  3. 頂点を衛星データとして使用して、頂点の角度を並べ替えます。

並べ替えられた頂点は、ポリゴンの周りで整然としています。削除できる冗長性がいくつかあります。1 回は線形時間で実行し、2 回は線形時間で実行し、3 回は n log n で実行します。

于 2013-01-10T18:15:27.703 に答える
2

線形時間でポイントを（二重、順序付けられていない？）リンクリストに変換できるはずです：

for (var i=0; i<segments.length; i++) {
    var a = segments[i].va,
        b = segments[i].vb;
    // nexts being the two adjacent points (in unknown order)
    if (a.nexts) a.nexts.push(b); else a.nexts = [b];
    if (b.nexts) b.nexts.push(a); else b.nexts = [a];
}

これを反復して配列を構築できます。

var prev = segments[0].va,
    start = segments[0].vb, // start somewhere, in some direction
    points = [],
    cur = start;
do {
    points.push(cur);
    var nexts = cur.nexts,
        next = nexts[0] == prev ? nexts[1] : nexts[0];
    delete cur.nexts; // un-modify the object
    prev = cur;
    cur = next;
} while (cur && cur != start)
return points;

オブジェクトを変更したくない場合は、EcmaScript6Map (オブジェクト キー付き) が便利です。回避策として、ポイント座標の JSON シリアル化を通常のオブジェクトのキーとして使用できますが、その場合、座標が 2 回含まれていないポリゴンに制限されます。voronoiIdまたは、ライブラリが頂点を識別するために頂点に追加する一意のプロパティを使用するだけです。

于 2013-01-10T06:43:42.757 に答える