Polygon Triangulation [1] - Overview of Ear Clipping

How to divide polygons into triangles. This is the first video which will go over the algorithm by describing how it works. The next video will start coding a function and give practical implementation of polygon triangulation.
GitHub Flat Engine source code: github.com/two...

[@AsperTheDog]

I've been searching for a proper polygon triangulation algorithm explanation for days. I don't know how I stumbled upon this but im so glad I did, this explanation is absolutely wonderful. Thank you

[@two-bitcoding8018]

You're welcome. Glad I could help!

[@Yes-Man]

Thanks very much. To find an actual explanation that doesn't stay on an academical levell wasn't easy.

[@two-bitcoding8018]

Glad it was helpful!

[@harilalmn]

Very good explanation. Straight forward and no digressions. Thanks a lot..!

[@ghos7bear]

Thanks for visual explanation, helped me understand it completely now.

[@two-bitcoding8018]

Sure thing!

[@harperrhett]

Incredibly well explained. Thanks you.

[@adamc3607]

Thank you so much! This explanation was really useful, now I can complete my project using procedurally generated meshes :)

[@two-bitcoding8018]

Awesome! Glad I could help.

[@radioactium]

Thank you very much for this video, the algorithm I wrote was having a hard time with concave simple polygons and this fixed it.

[@two-bitcoding8018]

You're welcome! Glad it helped!

[@radioactium]

@@two-bitcoding8018 Just as a fix for being limited to a clockwise winding order, I wrote my code in such a way that if it receives a list that's counter-clockwise and gets to the end of the list without being able to turn all points into triangles, it just re-writes the list backwards and starts from the beginning, which fixes the problem (: For my code, it would need to flip the list since if the points were in the opposite direction it would be reading the angles on the outside of the polygon instead of the ones on the inside. I thought about writing something where it initially takes the sum of all the angles and flips it based on whether or not that's correct for a polygon with the given number of sides, but I figured I wouldn't be dealing with polygons complex enough for that to make it run any more efficiently. I didn't watch your next video because I'm writing my code in Java, not C#, so I'm not sure if you figured this out in part 2.

[@two-bitcoding8018]

@@radioactium thanks! Sounds great! Did you have to change some of the signs on the ear tests when you were testing for concave or reflex vertices?

[@radioactium]

@@two-bitcoding8018 Nope, if it detected it needed to read the list backwards it just flipped it around, all of the other code stayed the same.

[@two-bitcoding8018]

@@radioactium gotcha. That is really cool!

[@MichaelYYQ]

Thanks for posting this algorithm and the tutorial , very patient speech, really enjoy it !

[@piyushnitnaware]

Very informative. Thank you 👍

[@two-bitcoding8018]

You're welcome!

[@stm91]

Beautifully explained!

[@two-bitcoding8018]

Glad you liked it

[@002jeevan]

Very Good Explanation, Thanks a lot !!

[@redstone_mason]

Thanks, this was very useful. Only thing I'm stuck on is determining if a angle is convex based on just the vertices of the points for the polygon.
turns out my issue gets addressed in the next video.

[@two-bitcoding8018]

You're welcome. Thanks for watching!

[@Zaidguess]

thank you very good explanation

[@t2g4_channel]

Thank you very much for a good step-by-step explanation!

[@JeremyWilliams1]

Priceless. Thank you for this explanation!

[@readyok8230]

Thank you, that was really helpful!

[@yuutsukariyuzuki6904]

thank you! it was very helpful!

[@two-bitcoding8018]

Glad it helped!

[@nahbruhwhat]

Very clear thanks!

[@two-bitcoding8018]

You're welcome!

[@vrgamestudio294]

Great video and as always very well described. Thank you, subscribed.

[@StarContract]

Very useful, thanks

[@ShubhamKumar-me7xy]

This method is O(n^3). We can solve the triangulation problem in O(nlogn)

[@BSOD.Enjoyer]

can you make a video about merging polygons? i was searching for "polygon union" and this video appeared in the recommend list. i like the way you explain things
edit: nvm i figured it out

[@shresthsomya7419]

Awesome Content

[@local-admin]

Omg thank you!

[@tianxiangxu2288]

good

[@user-bz3wd8cm4y]

what would happen if the polygon started from the 5th vertex? It isn't a convex angle anтd there are no vertices inside.

[@two-bitcoding8018]

Great question. It will move on to the next vertex until a valid ear is found.

[@aryoseno11]

Could you make a video about rectilinear polygon breaking down into rectangles? Thanks

[@two-bitcoding8018]

I had to look up rectilinear polygons. That is an interesting topic that I had not considered but will be unable right now. I would love to hear some practical applications.

[@Naeddyr]

What would happen if you generate a polygon with a 180-degree angle when removing the triangles? Is that just impossible because of some quirk of the process? Like when you have the 1-5-8 triangle, the 1's angle could have been 180 if it had been exactly in-between 5 and 8.

[@youssefelkamili1891]

I think you should treat it as non convex and skip it, then point 5 will be removed, and 1 will be connected to 6, so not 180° anymore.
I don't know why he assumed the 180° rule as illegal.

[@doomood]

I love you

[@two-bitcoding8018]

Thanks for watching!

[@WelshGuitarDude]

Damn I needed to know how to do holes

[@two-bitcoding8018]

lol, sorry.

[@wisdoww2382]

me too

[@pervognsen_bitwise]

You could take a look at Eric Veach's GLU triangulation code, which is available in an optimized, cleaned up version as libtess. Robust triangulation (with or without holes) is notoriously difficult to get right and only a handful of truly robust, production quality implementations are in existence, especially with performance in mind.