Polygon Triangulation [1] - Overview of Ear Clipping

Рет қаралды 21,850

3 жыл бұрын

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/twobitcoder101/Fla...

Пікірлер: 49

@AsperTheDog 3 жыл бұрын

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 3 жыл бұрын

You're welcome. Glad I could help!

@harilalmn 2 жыл бұрын

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

@harperrhett 27 күн бұрын

Incredibly well explained. Thanks you.

@Yes-Man 2 жыл бұрын

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

@two-bitcoding8018 2 жыл бұрын

Glad it was helpful!

@ghos7bear 2 жыл бұрын

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

@two-bitcoding8018 2 жыл бұрын

Sure thing!

@MichaelYYQ Жыл бұрын

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

@adamc3607 3 жыл бұрын

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

@two-bitcoding8018 3 жыл бұрын

Awesome! Glad I could help.

@JeremyWilliams1 Жыл бұрын

Priceless. Thank you for this explanation!

@stm91 2 жыл бұрын

Beautifully explained!

@two-bitcoding8018 2 жыл бұрын

Glad you liked it

@t2g4_channel Жыл бұрын

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

@vrgamestudio294 Жыл бұрын

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

@radioactium 3 жыл бұрын

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 3 жыл бұрын

You're welcome! Glad it helped!

@radioactium 3 жыл бұрын

@@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 3 жыл бұрын

@@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 3 жыл бұрын

@@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 3 жыл бұрын

@@radioactium gotcha. That is really cool!

@piyushnitnaware 3 жыл бұрын

Very informative. Thank you 👍

@two-bitcoding8018 3 жыл бұрын

You're welcome!

@readyok8230 8 ай бұрын

Thank you, that was really helpful!

@shresthsomya7419 Жыл бұрын

Awesome Content

@Zaidguess 2 жыл бұрын

thank you very good explanation

@redstone_mason 3 жыл бұрын

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 3 жыл бұрын

You're welcome. Thanks for watching!

@StarContract 4 ай бұрын

Very useful, thanks

@nahbruhwhat 3 жыл бұрын

Very clear thanks!

@two-bitcoding8018 3 жыл бұрын

You're welcome!

@yuutsukariyuzuki6904 2 жыл бұрын

thank you! it was very helpful!

@two-bitcoding8018 2 жыл бұрын

Glad it helped!

@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

@Naeddyr 2 жыл бұрын

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 2 жыл бұрын

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.

@aryoseno11 2 жыл бұрын

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

@two-bitcoding8018 2 жыл бұрын

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.

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

@tianxiangxu2288 Жыл бұрын

good

@ShubhamKumar-me7xy Жыл бұрын

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

@WelshGuitarDude 3 жыл бұрын

Damn I needed to know how to do holes

@two-bitcoding8018 3 жыл бұрын

lol, sorry.

@wisdoww2382 3 жыл бұрын

me too

@pervognsen_bitwise 2 жыл бұрын

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.