ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"

=== '''วิธีการตัดหู''' (Ear Clipping Method) ===
[[ไฟล์:Polygon-ear.png|thumb|หูของรูปหลายเหลี่ยม]]
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น <math>O (n<sup>^2)</supmath>) วิธีในการหาหูนั้นถูกค้นพบโดย [[:en:Hossam ElGindy|Hossam ElGindy]], [[:en:Hazel EverettHazel Everett|Hazel EverettHazel Everett]] และ [[:en:Godfried Toussaint|Godfried Toussaint]] โดยในการหาหูจะใช้เวลาเป็น <math>O (n)</math>
{{clear}}
==== รหัสเทียม ====
6,995

การแก้ไข