Planar Delaunay Triangulations | CAD From Scratch [16]

[For the impatient, go to 26:05 to see the results.] 16th video in a series on programming CAD utilities from scratch in C. In this video, we implemented an algorithm to create Delaunay triangulations from a 2D point set.
Comments, questions, and suggestions gladly appreciated.
Code on Github: github.com/xmdi/CAD-from-Scratch
If you found this content interesting, consider donating to Feeding America: www.feedingamerica.org/

Exactly this explanation + coding I am finding whole day... thank you!

[@ductriquyen9157]

The playlist is perfect. Can I look forward to a video of you making a simple/complex CAM (Computer Aided Manufacturing) tool path. It's something I'm constantly learning and being exposed to.

[@firesnake6311]

Wow awesome

[@evgeniinekhoroshev8204]

It is a bit unrelated to CAD-like modeling, but is there an efficient way to build a Delaunay triangulation for 3D simplices (4 vertices forming a tetrahedron) and even ND simplices (ND-hypertetrahedrons)? It seems like the algorithm would be similar, I am just not quite sure about the condition of diagonal swapping. Instead of the conditions proposed by Sloan (COSA, COSB, etc), I derived a more general condition that a couple of triangles must swap a diagonal if the centers of mass of the new triangles are going to be further from each other than in the original triangles. I implemented such triangulation, it seems to give nice triangles in 2D case similar to the classical algorithm. Now I am stuck at a multidimensional case, I cannot prove that maximizing the distances from the centers of mass is equivalent to the original Delaunay condition. For those who might wonder why would I need ND-simplices - they are related to phase diagrams and naturally appear if I have chemical compounds A, B, C, D mixed together forming a mesh of compositions AxByCzDw with x+y+z+w = 1. Even more, some compositions are joined by an equilibrium condition (for example, a complex liquid composition coexisting with a complex solid composition) which is identical to having constraining edges.

[@jaspa99]

Very impressive content on your channel. Who are you?

[@Alexander-bk6oy]

I'm doing a project where I have to find the MST with 205000 nodes with latitude and longitude coordinate, the only solution that I've found to avoid doing a complet graph is to implement this. I've tested your implementation with a part of my data and I don't understand why it stucks with some precise points ... Maybe we can discuss about this ? Thanks !
PS : By the way don't forget to free you malloc/calloc

[@Палитра]

Hi. Thanks for your video!
How do you handle the case when point is located on an existing edge, which belongs two triangles?

[@Палитра]

Now I know. The algorithm handle both point located within triangle and on triangle edge similarly. No modifications required

[@user-lk6su4xb3k]

What books do you use to create your CAD?

[@xmdi0]

no books explicitly, mostly academic papers on the different topics (check google scholar). i do have 1 very good book on "old-fashioned" computational geometry: "Computational Geometry for Design and Manufacture" by Faux & Pratt which I found in a dumpster. PM me on discord for a electronic copy: pacelli#5727

[@true_xander]

And here I am in 3:56AM watching how random guy has coded triangulation in ancient programming language. Why? Because I need proximity input mode for my VR keyboard.