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!
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.