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

ไปยังการนำทาง ไปยังการค้นหา
Robot: Automated text replacement (-อัลกอริทึม +ขั้นตอนวิธี)
(r2.7.3) (โรบอต เพิ่ม: ca:Triangulació d'un polígon)
(Robot: Automated text replacement (-อัลกอริทึม +ขั้นตอนวิธี))
{{ลิงก์ไปภาษาอื่น}}
'''โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม''' ([[อังกฤษ]]:Polygon Triangulation) คือการแบ่ง[[รูปหลายเหลี่ยม]]เป็นเซ็ทของ[[สามเหลี่ยม]]ที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมขั้นตอนวิธีที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
== โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม ==
=== '''วิธีการตัดหู''' (Ear Clipping Method) ===
[[ไฟล์:Polygon-to-monotone.png|thumb|การแบ่งรูปหลายเหลี่ยมเป็นรูปหลายเหลี่ยมทางเดียว]]
เราสามารถแบ่งรูปหลายเหลี่ยมให้กลายเป็น[[รูปหลายเหลี่ยมทางเดียว]]ได้
==== อัลกอริทึมขั้นตอนวิธี ====
===== 1. แยกรูปหลายเหลี่ยมให้กลายเป็นสี่เหลี่ยมคางหมู =====
กำหนดให้ S คือเซ็ทของเส้นขอบของรูปหลายเหลี่ยมที่ไม่ใช่เส้นแนวนอนและไม่ตัดกัน อัลกอริทึมขั้นตอนวิธีแบบสุ่ม ({{lang-en|Randomised Algorithm}}) จะถูกใช้เพื่อสร้างสี่เหลี่ยมคางหมูจากเส้นตรงใน S ซึ่งจะทำโดยจะดึงเส้นตรงใน S ออกมาทีละเส้นแบบสุ่มเพื่อสร้างเป็นสี่เหลี่ยมคางหมู วิธีนี้จะแบ่งรูปหลายเหลี่ยมเป็นสี่เหลี่ยมคางหมูจำนวนหนึ่งตัวสี่เหลี่ยมคางหมูนี้สามารถลดรุปเป็นสามเหลี่ยมได้ถ้ามีขอบด้านใดด้านหนึ่งมีความยาวด้านนอนเป็นศูนย์ สำหรับเงื่อนไขที่ว่าเส้นในเซ็ทจะต้องไม่เป็นเส้นนอนนั้นมีขึ้นเพื่อจำกัดจำนวนที่ต้องทำให้ลดน้อยลง แต่ก็ไม่ได้ส่งผลอะไรต่อผลลัพธ์ที่จะได้ ซึ่งจากที่ [[:en:Siedal|Siedal]] ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น <math>O (nlog n)</math>
 
===== 2. แยกสี่เหลี่ยมคางหมูออกเป็นรูปหลายเหลี่ยมทางเดียว =====
 
===== 3. แยกรูปหลายเหลี่ยมทางเดียวเป็นสามเหลี่ยม =====
รูปหลายเหลี่ยมทางเดียวสามารถแยกเป็นสามเหลี่ยมได้โดยใช้อัลกอริทึมขั้นตอนวิธีเชิงละโมบ โดยให้ตัดมุมเว้าไปเรื่อยๆ ซึ่งในส่วนนี้จะใช้เวลาเป็น <math>O(n)</math>
 
==== รหัสเทียม ====
 
=== ความซับซ้อนในการคำนวณ ===
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า <math>O(n log n)</math> ได้หรือไม่ ในปี 1990 นั้น [[:en:David G. Kirkpatrick|David G. Kirkpatrick]],[[:en:David G. Kirkpatrick|David G. Kirkpatrick]], [[:en:Robert E. Tarjan|Robert E. Tarjan]] ได้ค้นพบอัลกอริทึมขั้นตอนวิธีที่ใช้เวลาเพียง <math>O(n log log n)</math> สำหรับวิธีใช้อัลกอริทึมขั้นตอนวิธีแบบสุ่มนั้นเช่นอัลกอริทึมขั้นตอนวิธีของ [[:en:Seidel's|Seidel's]] or [[:en:Clarkson et al.'s|Clarkson et al.'s]], ใช้เวลาเป็น <math>O(n log* n)</math> ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ <math>O(n)</math> เลย
 
นอกจากวิธีการข้างต้นแล้ว [[:en:Bernard Chazelle|Bernard Chazelle]] ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมขั้นตอนวิธีนั้นมีความซับซ้อนมาก
ต่อมาในปี 1998 อัลกอริทึมขั้นตอนวิธีที่ใช้เวลาเฉลี่ยเป็น <math>O(n)</math> ก็ได้ถูกค้นพบและตีพิมพ์โดย [[:en:Alexey V. Skvortsov|Alexey V. Skvortsov]] และ [[:en:Yuri L. Kostyuk|Yuri L. Kostyuk]] โดยอัลกอริทึมขั้นตอนวิธีนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม
 
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมขั้นตอนวิธีในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น <math>\Omega(n log n)</math>
 
==เนื้อหาอื่นๆที่เกี่ยวข้องหรือใกล้เคียง==
138,643

การแก้ไข

รายการนำทางไซต์