Hi,
I have to make 2d triangles from a list of 2d points with a condition: length of any edge can't be longer than a predefined constant.
Something like this:
Do you know any algorithm that can do this? Or any advise?
Thanks!
+1
A:
First, generate all possible edges (i.e. connecting a pair of vertices that are closer than the constant). Then when two of them intersect, remove one of them. Repeat this step until there are no intersections.
This solution is quite primitive, it's probably possible to do it faster.
svick
2010-08-24 10:16:28
+1 this was what I was thinking.
Lazer
2010-08-25 09:46:48
+4
A:
Try Delaunay triangulation, then remove any edges which are too long.
From the above article, you see a link to CGAL's 2D triangulation page.
Andre Holzner
2010-08-24 10:18:48
+1 for Delaunay triangulation. This inherently forms well "balanced" triangles. This should do a reasonable job of minimizing the chances of overlong edges, but it doesn't make any guarantees about specific edge lengths. I don't think you can just remove overlong edges, but if there's a problem, it seems unlikely (though not impossible?) that there's an alternative triangulation that works. Trouble is, even if it's possible (not sure - my computation geometry is rusty) it will probably be hard to find. It may be a try-all-possible-triangulations kind of thing.
Steve314
2010-08-24 10:34:28