2

地形エディターを作成していますが、一連のポイントの境界ポリゴンを見つける必要があります。凸包だけが必要な場合は、速度は問題になりません。凹型の船体を作るには、いくつかのフープを通過する必要があります。ポイントを三角形分割し、ポイント間の既知の距離よりも長い辺を持つ三角形を破棄できることがわかりました。

次のステップは問題です: JSTS ジオメトリ ライブラリ ( http://github.com/bjornharrtell/jsts ) を使用して三角形 (ミニ ポリゴンとして) を 1 つの大きなポリゴンに結合するのは非常に遅いです。

可視化のスクリーンショット

完全なコードを参照してください: http://codepen.io/anon/pen/oCfDh

最終的なポリゴンを形成するためにマージされる配列 (ポリゴン) があります。問題は、552 ポイント (15k+ をサポートしたい) の場合、実行に約 3500 ミリ秒かかることです。あなたの速度については、codepen リンクのコンソールを見てください。

  var reader = new jsts.io.WKTReader(),
      merged = reader.read(polys[0]).union(reader.read(polys[1]));
  console.time('jsts mergization');
  for(var i = 2; i<polys.length; i++){
    try{
      merged = merged.union(reader.read(polys[i]));
    }catch(err){
      console.log('Error triangulating points!');
    };
  };
  console.timeEnd('jsts mergization');

三角形をポリゴンにマージするか、さらに広くして、まったく異なる方法でポイントのセットから凹型ポリゴンを構築するより高速な方法を知っている人はいますか?

4

1 に答える 1

0

ありがとうサイモンザック！

あなたの提案を使用してアルゴリズムを書き直しましたが、はるかに高速です!

コードペンのリワーク: http://codepen.io/anon/pen/Btdyj

同じ例が約 15 ミリ秒で実行されるようになりました。

function pointsToPolygon(points, triangles, maxEdgeLength){
  console.time('homebrewed mergization');
  var dist = function(a, b){
    if(typeof a === "number"){
      a = points[a];
    };
    if(typeof b === "number"){
      b = points[b];
    };
    return Math.sqrt(Math.pow(a[0] - b[0], 2) + 
            Math.pow(a[1] - b[1], 2));
  };
  if(!points.length){
    return undefined;
  };
  var pointFreq = [];
  points.forEach(function(v){
    pointFreq.push(0);
  });
  for(var i = triangles.length; i; i-=3){
    if(dist(triangles[i-1], triangles[i-2]) < maxEdgeLength &&
       dist(triangles[i-3], triangles[i-2]) < maxEdgeLength &&
       dist(triangles[i-1], triangles[i-3]) < maxEdgeLength){
      pointFreq[triangles[i-1]]++;
      pointFreq[triangles[i-2]]++;
      pointFreq[triangles[i-3]]++;
    };
  };

  // Keep points that are used in 3 or fewer triangles
  var output =[];
  pointFreq.forEach(function(freq, i){
    if(freq<4){
      output.push(points[i]);
    };
  });

  // Sort points by looping around by each next closest point
  var sorted = [];
  while(output.length>0){
    sorted.push(output.pop());
    output=output.sort(function(a,b){
      var distA =dist(sorted[sorted.length-1], a),
          distB =dist(sorted[sorted.length-1], b);
      if(distA < distB){
        return 1;
      }else if(distA === distB){
        return 0;
      };
      return -1;
    });
  };

  sorted=simplifyPath(sorted,0.1);

  console.timeEnd('homebrewed mergization');
  return sorted;

};

3 つ以下の三角形で使用されているポイントをフィルタリングして境界を見つけ、任意のポイントから次に近いポイントごとにループしてポイントを並べ替えます。

Douglas-Peucker 単純化アルゴリズム ( https://gist.github.com/adammiller/826148から適応) により 100% 正確ではないかもしれませんが、私には十分に思えます。

于 2014-08-28T01:15:54.277 に答える