在Javascript中快速查找点的多边形周长 [英] Find polygon perimeter of points quickly in Javascript

问题描述

我正在制作地形编辑器，我需要找到一组点的外围多边形.如果我只需要凸包，那么速度就没问题了.要制作凹壳，我必须经过几圈.我发现我可以对这些点进行三角剖分，然后丢弃边长于这些点之间的已知距离的三角形.

下一步是问题:使用JSTS几何库将三角形(作为迷你多边形)组合成一个大多边形( http://codepen.io/anon/pen/oCfDh

我有一个数组(多边形)，可以合并成最终的多边形.问题是，使用552点(我想支持15k +)时，需要约3500ms的时间才能运行.在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');

有人知道有什么更快的方法可以将三角形合并成一个多边形，或者甚至更宽一些，从而以完全不同的方式从一组点构建一个凹面多边形吗?

解决方案

感谢simonzack！

我已经根据您的建议重写了算法，而且速度更快！

重做的代码笔: http://codepen.io/anon/pen/Btdyj

同一示例现在可以在〜15ms内运行！

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 )，但对我来说似乎已经足够了.

I'm making a terrain editor and I need to find the perimeter polygon of a set of points. If I just needed a convex hull then the speed would be no issue. To make a concave hull, I must go through a few hoops. I've figured out that I can triangulate the points and then throw away any triangles with a side longer than the known distance between the points.

The next step is the problem: Combining the triangles (as mini polygons) into one large polygon using the JSTS geometry library (http://github.com/bjornharrtell/jsts) is really slow.

See the full code: http://codepen.io/anon/pen/oCfDh

I've got an array (polys) that gets merged to form the final polygon. The problem is that with 552 points (I want to support 15k+), it takes ~3500ms to run. Look at the console in the codepen link for your speed.

  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');

Does anybody know of any faster way to either merge triangles into a polygon or to go even wider and build a concave polygon from a set a points in a whole different way?

解决方案

Thanks simonzack!

I've rewritten the algorithm using your suggestion and it's much faster!

Reworked codepen: http://codepen.io/anon/pen/Btdyj

The same example now runs in ~15ms!

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;

};

I can find the boundary by filtering the points that are used in 3 or fewer triangles then sort points by looping around by each next closest point from any arbitrary point.

Maybe not 100% as accurate due to the Douglas-Peucker simplification algorithm (adapted from https://gist.github.com/adammiller/826148) but it seems good enough for me.

这篇关于在Javascript中快速查找点的多边形周长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！