2D Triangulation

category: code [glöplog]
Looking for a tiny code snippet for triangulation for a 2d pointcloud? All the code I can find on the web for delaunay triangulation is too large. I'm hoping there are some demoscene tricks to do this in a few LOC.
added on the 2015-02-06 18:08:22 by e64 e64
in what context? platform? cpu, gpu? do you need actual geometry out or just to achieve the visual effect of drawing triangles from the points?
added on the 2015-02-06 18:34:58 by smash smash
CPU, to generate the geometry. Platform independent would be ideal, but I am currently targeting OSX. I am not concerned with execution time or memory usage, but rather just looking for a short snippet easy to incorporate.
added on the 2015-02-07 07:03:47 by e64 e64
Bruteforce delaunay by just testing circles of all 3 point combinations against other points.
N^4 slowness so hope you don't have too many points.

Or just go for a big bounding triangle around all your points and keep splitting that up as you insert points and maybe split 2 up if you hit an edge.
added on the 2015-02-07 08:51:11 by Harekiet Harekiet
if you don't mind the quality of the topology, maybe you can do something fast and cheap by firsts sorting all the points from -x to +x and then iterating them in order and somehow connecting them as you go? not sure i know what i'm saying though.
added on the 2015-02-07 09:01:43 by iq iq
marching squares
added on the 2015-02-07 15:59:31 by lsl lsl
I don't know anything about this but I thought of convex enveloppe then removing it and repeating like peeling an onion and doing tristrips on layers somehow. Oh well.
you can easily calculate that discreetly and with local neighbours.
added on the 2015-02-07 23:46:15 by rudi rudi
iq: Mhmm. That way you'd get a very ugly triangle strip, with wide vertical spaces, unless the points are distributed sparsely and fairly evenly in x/y space. If you do it that way, you'd at least need a second pass, where you connect points that are not connected to "foreign" nodes in the adjacent triangle (so like bridges, would be still a weird looking triangle fan, though :)

I guess the delaunay brute force thing linked above is pretty much what OP wants, but of course very slow for N >> 100.
added on the 2015-02-08 11:49:07 by tomaes tomaes
Thanks for the ideas, I am basically trying what Harekiet said, starting with a big bounding tri and subdividing it as I go, similar to HeLLoWorld's idea. I'll let you know if it works out.
added on the 2015-02-08 15:52:21 by e64 e64
1) build convex hull
2) use sweep-line algorithm to do a triangulation of the convex hull
added on the 2015-02-08 21:04:01 by xTr1m xTr1m
I don't know what you wanna do and why but I suggest:

If your data is not important...

1) Build simple equilateral triangle grid.
2) Move the vertices randomly a litte bit.
3) Done.

If it is. Do what xTr1m said.

Or... combine both things. Make regular triangle grid. Detect density in your point cloud to move points in the regular grid. Then delete regular triangles unaffected.
added on the 2015-02-08 21:39:45 by ham ham