在Javascript中快速查找点的多边形周长

同一示例现在可以在〜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/oCfDhI'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/BtdyjThe 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中快速查找点的多边形周长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！