The inner workings of Delaunay Triangulation

Hi,

I am hoping for a more compelling description of the Delaunay Edges component than is found within its help menu. For instance how does the component determine which points to are included in the triangulation process and how does one decode the topological connectivity diagram? I have been testing out strategies with various tree components and looking into what happens and how the pieces involved are indexed but the more I explore the more this becomes obscure. I was hoping that one of the many experts in arcane operations might offer advice.

Thanks,

robin

▶ Reply to This

Replies to This Discussion

Permalink Reply by Damien Alomar on February 14, 2010 at 6:14pm

As far as how the Delaunay triangulation is calculated, I'd take a look on wikipedia as its got a pretty decent explanation... http://en.wikipedia.org/wiki/Delaunay_triangulation

In regards to the output, you have all of the lines which make the edges. The topolopgy connectivity outputs the indices of the original point list that are connected to that particular index. Each point has the indicies of the points that its connected to organized in a separate sub branch.

Take a look at the attached definition and it will hopefully clear it up for you. I've basically taken only the connectivity output from the Delaunay component and through a little juggling recreated only the lines from a given point to the other points to which its connected. Move the slider and it should move the test point through the different points, so you can see this visually.

Attachments:

delaunayConnectivity.ghx, 137 KB

▶ Reply

Permalink Reply by Alpha222 on February 14, 2010 at 10:06pm

You also can do something similar in this way：

▶ Reply

Permalink Reply by Alpha222 on February 14, 2010 at 10:23pm

And a tiny modification:

▶ Reply

Permalink Reply by Alpha222 on February 14, 2010 at 10:46pm

Hi Robin,
I realize Demien's Def is more clear in logic ,but we can remove some components to do the same thing.see below:

▶ Reply

Permalink Reply by Robin Dripps on February 15, 2010 at 7:37am

Alpha,
I too am a fan of keeping componentry to a minimum. Thanks for adding this to the discussion. The replies from you and Damien plus some work I had been doing to get rid of redundant connections and invalid lines has turned the Delaunay module into a very useful analytic tool.

▶ Reply

Permalink Reply by Robin Dripps on February 15, 2010 at 7:32am

Damien,
Thanks so much. I now see from the Wikipedia site that the Delaunay is more complicated than I had realized but with this understanding it also becomes more powerful. Your def does clear up matters and in itself is quite neat although the juggling you performed seemed something other than little.
Robin Dripps

▶ Reply

Permalink Reply by Damien Alomar on February 15, 2010 at 9:23am

Let me explain what got "juggled" then. The key to all of this is properly organizing the path structure so that things match up in the way they need to, and this all centers around the resulting path structure of the Delaunay component.

The Delaunay component wants to take each item of the source list of points and give it its own branch in the tree. That branch then contains all the indicies of the points that the source point is connected to. If you just pass the original list of points and the output of the delaunay componet to the line component, the paths won't match up and it will make some nonsense.

The reason why is that the points are all in one branch, yet the indicies that they are trying to connect to are all in separate branches. Therefore GH will try to connect the original list to each of the items in each branch. I used the Lexical Mapper to change the tree structure of the original point list so that each item was in its own branch and so the branch path matched the structure of the output from the Delaunay component. The list item component is there so that I'm no longer working with the indices of the points, but rather, the points themselves.

All of the other stuff (the function and branch components) are just there so that only a single element from the point structure has its lines created. In theory, this is similar to the list item component in the sense that it will extract only the items that are specified. However, this needs to work on the tree structure, not the items within the tree, hence the different components and function needed to assemble the path (which could have possibly been done differently).

Hope that explains it a little better. Remember that paths (or trees or whever you want to call them) are key to working with complex data organizations in GH. Recognizing how a components works with trees and how they creates their own trees are very important to being able to utilize them effectively. The tool that makes managing all these trees possible is the Lexical Mapper. It allows you to restructure, reorganize, and clean a tree exactly how you need it and it does so in a very sucinct way.

▶ Reply

Permalink Reply by Robin Dripps on February 15, 2010 at 5:17pm

Damien,
Thanks for taking the time to explain the mapping issues of the Delaunay component. I could see that this was the nature of your juggling, but at the time had not been able to fully process your specific actions. This is now clear and allows me to use the component in the analytical way I had imagined.

▶ Reply

Permalink Reply by Shkattii on April 27, 2012 at 6:30am

Hi, i am very interested in using delaunay edge, but i want it to draw triangles the same way as trigrid component does. (ie i could do a area component where i can obtain all the center points of the individual triangles). Is that possible?

Please help

Thank you