• Advertisement

Archived

This topic is now archived and is closed to further replies.

What would you call this algorithm?

This topic is 5154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
You seem to be looking for triangulation algorithms. You might want to check Delaunay Triangulations and Voronoi Diagrams as well.

Share this post


Link to post
Share on other sites
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.






Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
what if I had a set of vertices that are all on the outside edge of some object that lies in a 2D plane... & I wanted a triangulation algorithm to generate polys for me that filled the inside of this object up without crossing any of the polys into the space outside of the object. For instance... what if I had the vertice info for the corners of this shape (all 8):
__________
| ____ |
| | | |
|__| |__|

& wanted to generate that shape with polys.

Delaunay???
Voronoi???
Myself? :/

fyi - the shapes get MUCH more coplex than this, but I will definitely be able to traverse through them in a [counter]clock-wise manner if needs be. Thanks.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement