ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"
ลไม่มีความย่อการแก้ไข |
|||
บรรทัด 12: | บรรทัด 12: | ||
if pi is an ear then |
if pi is an ear then |
||
return pi |
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'. |
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).<br/> 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)) |
FindAnEar (GSP', floor (k/2)) |
||
End FindAnEar |
End FindAnEar |
รุ่นแก้ไขเมื่อ 13:52, 18 กันยายน 2554
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม (อังกฤษ:Polygon Triangulation) คือการแบ่งรูปหลายเหลี่ยมเป็นเซ็ทของสามเหลี่ยมที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม
วิธีการตัดหู (Ear Clipping Method)
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น วิธีในการหาหูนั้นถูกค้นพบโดย Hossam ElGindy, Hazel EverettHazel Everett และ Godfried Toussaint โดยในการหาหูจะใช้เวลาเป็น
รหัสเทียม
กำหนดให้ GSP คือรูปหลายเหลี่ยมย่อยของ P ที่เกิดจากการลากเส้นทแยงมุมจากมุมหนึ่งไปสู่อีกมุมหนึ่งเพียงเส้นเดียว
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)
เราสามารถแบ่งรูปหลายเหลี่ยมให้กลายเป็นรูปหลายเหลี่ยมทางเดียวได้
อัลกอริทึม
1. แยกรูปหลายเหลี่ยมให้กลายเป็นสี่เหลี่ยมคางหมู
กำหนดให้ S คือเซ็ทของเส้นขอบของรูปหลายเหลี่ยมที่ไม่ใช่เส้นแนวนอนและไม่ตัดกัน อัลกอริทึมแบบสุ่ม (อังกฤษ: Randomised Algorithm) จะถูกใช้เพื่อสร้างสี่เหลี่ยมคางหมูจากเส้นตรงใน S ซึ่งจะทำโดยจะดึงเส้นตรงใน S ออกมาทีละเส้นแบบสุ่มเพื่อสร้างเป็นสี่เหลี่ยมคางหมู วิธีนี้จะแบ่งรูปหลายเหลี่ยมเป็นสี่เหลี่ยมคางหมูจำนวนหนึ่งตัวสี่เหลี่ยมคางหมูนี้สามารถลดรุปเป็นสามเหลี่ยมได้ถ้ามีขอบด้านใดด้านหนึ่งมีความยาวด้านนอนเป็นศูนย์ สำหรับเงื่อนไขที่ว่าเส้นในเซ็ทจะต้องไม่เป็นเส้นนอนนั้นมีขึ้นเพื่อจำกัดจำนวนที่ต้องทำให้ลดน้อยลง แต่ก็ไม่ได้ส่งผลอะไรต่อผลลัพธ์ที่จะได้ ซึ่งจากที่ Siedal ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น
2. แยกสี่เหลี่ยมคางหมูออกเป็นรูปหลายเหลี่ยมทางเดียว
รูปหลายเหลี่ยมทางเดียวคือรูปหลายเหลี่ยมที่มีสายโซ่ทางเดียวในแกน 2 สาย รูปหลายเหลี่ยมเหล่านี้จะถูกคำนวณจากการแบ่งรูปเป็นสี่เหลี่ยมคางหมูโดยการตรวจสอบว่ามุม 2 มุมหนึ่งๆของรูปหลายเหลี่ยมเดิมนั้นอยู่บนฝั่งเดียวกันหรือไม่ ขั้นตอนนี้ใช้เวลาเป็นเชิงเส้น
3. แยกรูปหลายเหลี่ยมทางเดียวเป็นสามเหลี่ยม
รูปหลายเหลี่ยมทางเดียวสามารถแยกเป็นสามเหลี่ยมได้โดยใช้อัลกอริทึมเชิงละโมบ โดยให้ตัดมุมเว้าไปเรื่อยๆ ซึ่งในส่วนนี้จะใช้เวลาเป็น
รหัสเทียม
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
ความซับซ้อนในการคำนวณ
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า ได้หรือไม่ ในปี 1990 นั้น David G. Kirkpatrick,David G. Kirkpatrick, Robert E. Tarjan ได้ค้นพบอัลกอริทึมที่ใช้เวลาเพียง สำหรับวิธีใช้อัลกอริทึมแบบสุ่มนั้นเช่นอัลกอริทึมของ Seidel's or Clarkson et al.'s, ใช้เวลาเป็น ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ เลย
นอกจากวิธีการข้างต้นแล้ว Bernard Chazelle ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมนั้นมีความซับซ้อนมาก ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น ก็ได้ถูกค้นพบและตีพิมพ์โดย Alexey V. Skvortsov และ Yuri L. Kostyuk โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น
อ้างอิง
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0
{{citation}}
: CS1 maint: multiple names: authors list (ลิงก์) Chapter 3: Polygon Triangulation: pp.45–61. - Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301
- Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," Pattern Recognition Letters, 2 (March) :155–158.
- Meisters, G. H., "Polygons have ears." American Mathematical Monthly 82 (1975). 648–651
- ElGindy, H., Everett, H., and Toussaint, G. T., (1993) "Slicing an ear using prune-and-search," Pattern Recognition Letters, 14, (9) :719–722.
- Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry: Theory and Applications, 1: 51–64
- Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6: 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
- Skvortsov, Alexey V., Kostyuk, Yuri L. (1998), "Efficient algorithms for Delaunay triangulation" (PDF), Geoinformatics. Theory and practice, Tomsk State University, 1: 22–47
{{citation}}
: CS1 maint: multiple names: authors list (ลิงก์) (รัสเซีย) - Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376
- http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
- http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.html
- http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html