pouët.net

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.

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?

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.

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.
http://yoshihitoyagi.com/projects/mesh/delaunay/bruteforce/Delaunay.java

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.

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.

marching squares

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.

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.

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.

1) build convex hull
2) use sweep-line algorithm to do a triangulation of the convex hull

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.