Planar Delaunay Triangulations | CAD From Scratch [16]

Рет қаралды 8,284

2 жыл бұрын

[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/

Пікірлер: 10

Жыл бұрын

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

@ductriquyen9157 2 жыл бұрын

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.

@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.

@firesnake6311 2 жыл бұрын

Wow awesome

@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

@Палитра 9 ай бұрын

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

@Палитра 7 ай бұрын

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

@jaspa99 2 жыл бұрын

Very impressive content on your channel. Who are you?

@user-lk6su4xb3k 2 жыл бұрын

What books do you use to create your CAD?

@xmdi0 2 жыл бұрын

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