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

'''โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม''' ([[อังกฤษ]]:Polygon Triangulation) คือการแบ่ง[[รูปหลายเหลี่ยม]]เป็นเซ็ทของ[[สามเหลี่ยม]]ที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
== โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม ==
=== '''วิธีการตัดหู''' ([[อังกฤษ]]: Ear Clipping Method) ===
[[ไฟล์:Polygon-ear.png|thumb|หูของรูปหลายเหลี่ยม]]
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น O (n<sup>2</sup>) วิธีในการหาหูนั้นถูกค้นพบโดย [[Hossam ElGindy]], [[Hazel Everett]] และ [[Godfried Toussaint]] โดยในการหาหูจะใช้เวลาเป็น O (n)
กำหนดให้ GSP คือรูปหลายเหลี่ยมย่อยของ P ที่เกิดจากการลากเส้นทแยงมุมจากมุมหนึ่งไปสู่อีกมุมหนึ่งเพียงเส้นเดียว<br />
 
Function FindAnEar (GSP, pi)
# if pi is an ear then
# return pi
# Find a vertex pj such that (pi, pj) is a diagonal of GSP.Let GSP' be the good sub-polygon of GSP formed by (pi, pj). Re-label the vertices of GSP' so that pi = p0 and pj = pk-1 (or pj = p0 and pi = pk-1 as appropriate) where k is the number of vertices of GSP'.
# FindAnEar (GSP', floor (k/2))
End FindAnEar
 
=== '''วิธีรูปหลายเหลี่ยมทางเดียว''' ([[อังกฤษ]]: Monotone Polygons Method) ===
6,995

การแก้ไข