โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม

โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม (อังกฤษ:Polygon Triangulation) คือการแบ่งรูปหลายเหลี่ยมเป็นเซ็ทของสามเหลี่ยมที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน

โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม

วิธีการตัดหู (อังกฤษ: Ear Clipping Method)

หูของรูปหลายเหลี่ยม

วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น O(n²) วิธีในการหาหูนั้นถูกค้นพบโดย Hossam ElGindy, Hazel Everett และ Godfried Toussaint โดยในการหาหูจะใช้เวลาเป็น O(n)

รหัสเทียม

กำหนดให้ GSP คือรูปหลายเหลี่ยมย่อยของ P ที่เกิดจากการลากเส้นทแยงมุมจากมุมหนึ่งไปสู่อีกมุมหนึ่งเพียงเส้นเดียว

Function FindAnEar(GSP, pi)

1. if pi is an ear then
2. return pi
3. 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'.
4. FindAnEar(GSP', floor(k/2))

End FindAnEar

วิธีรูปหลายเหลี่ยมทางเดียว (อังกฤษ: Monotone Polygons Method)

การแบ่งรูปหลายเหลี่ยมเป็นรูปหลายเหลี่ยมทางเดียว

เราสามารถแบ่งรูปหลายเหลี่ยมให้กลายเป็นรูปหลายเหลี่ยมทางเดียวได้

อัลกอริทึม

1. แยกรูปหลายเหลี่ยมให้กลายเป็นสี่เหลี่ยมคางหมู

กำหนดให้ S คือเซ็ทของเส้นขอบของรูปหลายเหลี่ยมที่ไม่ใช่เส้นแนวนอนและไม่ตัดกัน อัลกอริทึมแบบสุ่ม (อังกฤษ: Randomised Algorithm) จะถูกใช้เพื่อสร้างสี่เหลี่ยมคางหมูจากเส้นตรงใน S ซึ่งจะทำโดยจะดึงเส้นตรงใน S ออกมาทีละเส้นแบบสุ่มเพื่อสร้างเป็นสี่เหลี่ยมคางหมู วิธีนี้จะแบ่งรูปหลายเหลี่ยมเป็นสี่เหลี่ยมคางหมูจำนวนหนึ่งตัวสี่เหลี่ยมคางหมูนี้สามารถลดรุปเป็นสามเหลี่ยมได้ถ้ามีขอบด้านใดด้านหนึ่งมีความยาวด้านนอนเป็นศูนย์ สำหรับเงื่อนไขที่ว่าเส้นในเซ็ทจะต้องไม่เป็นเส้นนอนนั้นมีขึ้นเพื่อจำกัดจำนวนที่ต้องทำให้ลดน้อยลง แต่ก็ไม่ได้ส่งผลอะไรต่อผลลัพธ์ที่จะได้ ซึ่งจากที่ Siedal ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น O(n log n)

2. แยกสี่เหลี่ยมคางหมูออกเป็นรูปหลายเหลี่ยมทางเดียว

รูปหลายเหลี่ยมทางเดียวคือรูปหลายเหลี่ยมที่มีสายโซ่ทางเดียวในแกน y 2 สาย รูปหลายเหลี่ยมเหล่านี้จะถูกคำนวณจากการแบ่งรูปเป็นสี่เหลี่ยมคางหมูโดยการตรวจสอบว่ามุม 2 มุมหนึ่งๆของรูปหลายเหลี่ยมเดิมนั้นอยู่บนฝั่งเดียวกันหรือไม่ ขั้นตอนนี้ใช้เวลาเป็นเชิงเส้น O(n)

3. แยกรูปหลายเหลี่ยมทางเดียวเป็นสามเหลี่ยม

รูปหลายเหลี่ยมทางเดียวสามารถแยกเป็นสามเหลี่ยมได้โดยใช้อัลกอริทึมเชิงละโมบ โดยให้ตัดมุมเว้าไปเรื่อยๆ ซึ่งในส่วนนี้จะใช้เวลาเป็น O(n)

รหัสเทียม

Input: Monotone polygon P
Output: Set of triangles

Sort the n vertices belonging to polygon P with respect to x-coordinate and store them in V.

Initialize sweep-line active list L

L = a list with the first two points of V

WHILE V is not empty DO

/* Extract the next vertex from V */

p = MIN(V)

IF (p is opposite to points in L) THEN

WHILE |L| > 1 DO

Output Triangle {First(L), Second(L),p}

REMOVE (FIRST(L))

Add p to L

ELSE

WHILE (Angle{Last(L), Previous (Last(L)), p}is convex .AND. |L| > 1) DO

Output Triangle {last(L), Previous (last), p}

REMOVE last (L)

/* The angle is reflex or cardinality of L is 1 */

Add p to L

ความซับซ้อนในการคำนวณ

โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า O(n log n) ได้หรือไม่ ในปี 1990 นั้น David G. Kirkpatrick,Maria M. Klawe, Robert E. Tarjan ได้ค้นพบอัลกอริทึมที่ใช้เวลาเพียง O(n log log n) สำหรับวิธีใช้อัลกอริทึมแบบสุ่มนั้นเช่นอัลกอริทึมของ Seidel's or Clarkson et al.'s, ใช้เวลาเป็น O(n log* n) ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ O(n) เลย

นอกจากวิธีการข้างต้นแล้ว Bernard Chazelle ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมนั้นมีความซับซ้อนมาก

ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น O(n) ก็ได้ถูกค้นพบและตีพิมพ์โดย Alexey V. Skvortsov และ Yuri L. Kostyuk โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม

ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω(n log n)