🔒 Locked

What would you call this algorithm?

Started by llvllatrix Jan 14, 2004 at 2:58 PM 9 replies 1.1k views

Original Post

Jan 14, 2004 at 2:58 PM

I can describe it but i dont know its name... Basically i have a set of points in a 2d plane. There are four corner points and the set of point are garanteed to always land somewhere in between the corners. I want to generate a set of triangles to connect the set of points like a mesh. Sort of like this:

Im trying to do something like adobe illustrator''s gradiant mesh tool. Anyone know what the algorithm to do this is called? I want to see whats out there before i try to write a recursive something or other that crashes my computer.

Sneftel

Jan 14, 2004 at 3:04 PM

Note that this is NOT how Illustrator does gradient meshes. in a gradient mesh, each new point generates a new latitude and longitude line from one side of the patch to the other.

Anyways, this looks somewhat similar to polygon tesellation algorithms. You might be able to adapt one of those for your needs.

"Sneftel is correct, if rather vulgar." --Flarelocke

BitMaster

Jan 14, 2004 at 3:17 PM

You seem to be looking for triangulation algorithms. You might want to check Delaunay Triangulations and Voronoi Diagrams as well.

Crispy

Jan 14, 2004 at 7:34 PM

quote:
Original post by BitMaster
You seem to be looking for triangulation algorithms. You might want to check Delaunay Triangulations and Voronoi Diagrams as well.

I''d say not Voronoi. Most likely Delaunay triangulation. Voronoi is more suited for n-sided mesh tessellation, not specifically triangulation and generally leaves much nicer edge tiles.

BitMaster

Jan 15, 2004 at 2:31 AM

Voronoi Diagrams are the dual graph of Delaunay Triangulations. If you have one, you have the other. While they don''t help him with his immediate problem, they might be easier to implement for him and even if not, he still learned something while reading over them.

_DarkWIng_

Jan 15, 2004 at 2:42 AM

There is a bug in your picture. Lower-right triangle has T-junction. That is something you *don''t* want to have. As for building this, both Voronoi Diagrams and Delaunay Triangulations might work, but personaly I would first try to come up with something on my own.

You should never let your fears become the boundaries of your dreams.

Seyedof

Jan 15, 2004 at 2:43 AM

The algorithm to generate an optimal mesh from a set of points is called Delaunay Triangulation. This is where you should start, i dont know what the gradient mesh thing is illustrator is...

llvllatrix

Jan 15, 2004 at 7:27 AM

Thx guys

Luke Miklos

Jan 16, 2004 at 5:23 PM

I''m an idiot... here''s a better rep of the shape:


__________
|  ____  |
|  |  |  |
|__|  |__|

RenderTarget

Jan 16, 2004 at 5:52 PM

You might want to start by either chopping such objects up until they''re convex, or triangulating the convex hull and culling the outsiders when you''re done. It''s a little extra work, but might make the overall thing similar.

I like pie.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.