CAD From Scratch [17] | Constrained Delaunay Triangulations

[For the impatient, go to 26:30 to see the results.] 17th video in a series on programming CAD utilities from scratch in C. In this video, we implemented an algorithm to adapt constraint edge requirements to our old Delaunay triangulations.

Comments, questions, and suggestions gladly appreciated.

[fnax]

Love this videos. Really inspiring project.

[daveyhu]

Very well presented, easy to understand and having the source code makes it the best tutorial on triangulation I'd come across. Will you be making an episode 18?

[johann]

Excellent explanation! It really helped me in implementing the triangulation. However, I think the routine for identifying all edge intersections on a given constraint isn't always correct. There's the possibility that two edges of a triangle have the constraint's endpoints on the right side.

[celinejost]

Awesome tutorial, thank you very much for sharing!
I wonder (I assume no constraints for simplicity), what would happen if the next point I place, P, is exactely on the edge where 2 already created (anticlockwise) triangles ABC and DEF meet? So AB and ED are the same edge and P is on that edge somewhere in between.
If I consider P to be inside ABC, then I can only make two 'real' triangles out of ABC, not three: PCA and PBC. "Triangle" PAB is 'degenerate' since P, A and B are on a line.
I would think that I must in addition treat P to be contained in DEF, and so I would make 2 'real' triangles here too: PEF and PFD (and here again, PED is 'degenerate' since P, E and D are on a line.
So in total I would end up with a total triangle count of +2 after placing my point P, which is similar as in the 'normal' case where I slice one triangle into 3 when my point is not on an edge but nicely inside the triangle.)
- Would this be the correct approach?
- Or would I really just pick either ABC or DEF to contain P? And if so, then how do I deal with the degenerate third triangle? Since the radius of the 'Delaunay circle' of that thing would be infinite...
- Does the code do the right thing in this case?
Thank you for any insights!!

[inginx]

Noticed the draft on 2.a says the non-convex edge is skipped instead of being added back. You did that in the code though

[lennutrajektoor]

I bet no one noticed it was presented in Paint!

[computerscience]

we learned what CAD stands for, but what does your username mean?

[LangDat]

hey how can i check time program run in win7

[ssss-sksl]

Test 4 : y-o-u-'-l-l n-e-v-e-r b-e -a r-e-a-l w-o-m-a-n

[ssss-sksl]

Test 6, same with black people, but in respond to this message

[ssss-sksl]

My comments are censored, all I can say is I really like trans people, but read it like it's the opposite, try it yourself, you are only allowed to like trans people by the AI