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

ไม่มีคำอธิบายอย่างย่อ
'''โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม''' ([[อังกฤษ]]:Polygon Triangulation) คือการแบ่ง[[รูปหลายเหลี่ยม]]เป็นเซ็ทของ[[สามเหลี่ยม]]ที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
== โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม ==
คือการแบ่ง[[รูปหลายเหลี่ยม]]เป็นเซ็ทของ[[สามเหลี่ยม]]ที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
=== '''วิธีการตัดหู''' ([[อังกฤษ]]: Ear Clipping Method) ===
==โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม==
[[Imageไฟล์:Polygon-ear.png|thumb|หูของรูปหลายเหลี่ยม]]
==='''วิธีการตัดหู''' ([[อังกฤษ]]: Ear Clipping Method)===
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น O (n<sup>2</sup>) วิธีในการหาหูนั้นถูกค้นพบโดย [[Hossam ElGindy]], [[Hazel Everett]] และ [[Godfried Toussaint]] โดยในการหาหูจะใช้เวลาเป็น O (n)
[[Image: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) ===
[[Imageไฟล์:Polygon-to-monotone.png|thumb|การแบ่งรูปหลายเหลี่ยมเป็นรูปหลายเหลี่ยมทางเดียว]]
เราสามารถแบ่งรูปหลายเหลี่ยมให้กลายเป็น[[รูปหลายเหลี่ยมทางเดียว]]ได้
==== อัลกอริทึม ====
===== 1. แยกรูปหลายเหลี่ยมให้กลายเป็นสี่เหลี่ยมคางหมู =====
กำหนดให้ S คือเซ็ทของเส้นขอบของรูปหลายเหลี่ยมที่ไม่ใช่เส้นแนวนอนและไม่ตัดกัน อัลกอริทึมแบบสุ่ม ([[อังกฤษ]]: Randomised Algorithm) จะถูกใช้เพื่อสร้างสี่เหลี่ยมคางหมูจากเส้นตรงใน S ซึ่งจะทำโดยจะดึงเส้นตรงใน S ออกมาทีละเส้นแบบสุ่มเพื่อสร้างเป็นสี่เหลี่ยมคางหมู วิธีนี้จะแบ่งรูปหลายเหลี่ยมเป็นสี่เหลี่ยมคางหมูจำนวนหนึ่งตัวสี่เหลี่ยมคางหมูนี้สามารถลดรุปเป็นสามเหลี่ยมได้ถ้ามีขอบด้านใดด้านหนึ่งมีความยาวด้านนอนเป็นศูนย์ สำหรับเงื่อนไขที่ว่าเส้นในเซ็ทจะต้องไม่เป็นเส้นนอนนั้นมีขึ้นเพื่อจำกัดจำนวนที่ต้องทำให้ลดน้อยลง แต่ก็ไม่ได้ส่งผลอะไรต่อผลลัพธ์ที่จะได้ ซึ่งจากที่ [[Siedal]] ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น O (n log n)
 
===== 2. แยกสี่เหลี่ยมคางหมูออกเป็นรูปหลายเหลี่ยมทางเดียว =====
รูปหลายเหลี่ยมทางเดียวคือรูปหลายเหลี่ยมที่มีสายโซ่ทางเดียวในแกน y 2 สาย รูปหลายเหลี่ยมเหล่านี้จะถูกคำนวณจากการแบ่งรูปเป็นสี่เหลี่ยมคางหมูโดยการตรวจสอบว่ามุม 2 มุมหนึ่งๆของรูปหลายเหลี่ยมเดิมนั้นอยู่บนฝั่งเดียวกันหรือไม่ ขั้นตอนนี้ใช้เวลาเป็นเชิงเส้น O (n)
 
===== 3. แยกรูปหลายเหลี่ยมทางเดียวเป็นสามเหลี่ยม =====
รูปหลายเหลี่ยมทางเดียวสามารถแยกเป็นสามเหลี่ยมได้โดยใช้อัลกอริทึมเชิงละโมบ โดยให้ตัดมุมเว้าไปเรื่อยๆ ซึ่งในส่วนนี้จะใช้เวลาเป็น O (n)
 
==== รหัสเทียม ====
<br />
Input: Monotone polygon P<br />
:WHILE V is not empty DO<br />
::/* Extract the next vertex from V */<br />
::p = MIN (V) <br />
::IF (p is opposite to points in L) THEN<br />
:::WHILE |L| > 1 DO<br />
::::Output Triangle {First (L), Second (L),p}<br />
::::REMOVE (FIRST (L)) <br />
:::Add p to L<br />
::ELSE<br />
::: WHILE (Angle{Last (L), Previous (Last (L)), p}is convex .AND. |L| > 1) DO<br />
::::Output Triangle {last (L), Previous (last), p}<br />
::::REMOVE last (L) <br />
:::/* The angle is reflex or cardinality of L is 1 */<br />
:::Add p to L<br />
=== ความซับซ้อนในการคำนวณ ===
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า 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) เลย <br /> <br />
นอกจากวิธีการข้างต้นแล้ว [[Bernard Chazelle]] ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมนั้นมีความซับซ้อนมาก<br /> <br />
ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น O (n) ก็ได้ถูกค้นพบและตีพิมพ์โดย [[Alexey V. Skvortsov]] และ [[Yuri L. Kostyuk]] โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม <br/> <br />
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω (n log n)
 
== อ้างอิง ==
* {{Citation|author = [[Mark de Berg]], [[Marc van Kreveld]], [[Mark Overmars]], and [[Otfried Schwarzkopf]] | year = 2000 | title = Computational Geometry | publisher = [[Springer-Verlag]] | edition = 2nd revised | isbn = 3-540-65620-0}} Chapter 3: Polygon Triangulation: pp.45–61.
* {{Citation |last1=Fournier |first1=A. |author1-link=Alain Fournier |last2=Montuno |first2=D. Y. |author2-link= |title=Triangulating simple polygons and equivalent problems |journal=[[ACM Transactions on Graphics]] |volume=3 |issue=2 | year=1984 <!--|month=April--> |pages=153–174 |issn=0730-0301 |doi=10.1145/357337.357341}}
* 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.
* {{Citation |last=Seidel|first=Raimund |author-link= Raimund Seidel| title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=Computational Geometry: Theory and Applications |volume=1 |year=1991 |pages=51–64}}
* {{Citation |last=Chazelle |first=Bernard |author-link=Bernard Chazelle | title=Triangulating a Simple Polygon in Linear Time |journal=Discrete &amp; Computational Geometry |volume=6 |year=1991|pages=485–524 |issn=0179-5376 |doi=10.1007/BF02574703}}
* {{Citation | author = Skvortsov, Alexey V., Kostyuk, Yuri L. | title = Efficient algorithms for Delaunay triangulation | publisher = Tomsk State University | journal = Geoinformatics. Theory and practice | volume = 1 | year = 1998 | pages = 22–47 | url = http://www.inf.tsu.ru/Library/Publications/1999/Skvortsov_1999_1.pdf}} {{ru icon}}
* {{Citation |last1=Amato |first1=Nancy M. |last2=Goodrich |first2=Michael T. |author2-link=Michael T. Goodrich|last3=Ramos |first3=Edgar A. |title=A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time |journal=Discrete &amp; Computational Geometry |volume=26 |year=2001 <!--|month=May--> |pages=245–265 |issn=0179-5376 |doi=10.1007/s00454-001-0027-x |url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 |issue=2}}
* 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
 
[[หมวดหมู่:ขั้นตอนวิธี]]
 
[[ar:تثليث مضلع]]
[[en:Polygon triangulation]]
[[fa:مثلث‌بندی چندضلعی‌ها]]
[[fr:Triangulation d'un polygone]]
7,289

การแก้ไข