ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
| บรรทัด 5: | บรรทัด 5: | ||
[[Image:Polygon-ear.png|thumb|หูของรูปหลายเหลี่ยม]] |
[[Image:Polygon-ear.png|thumb|หูของรูปหลายเหลี่ยม]] |
||
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น O(n<sup>2</sup>) วิธีในการหาหูนั้นถูกค้นพบโดย [[Hossam ElGindy]], [[Hazel Everett]] และ [[Godfried Toussaint]] โดยในการหาหูจะใช้เวลาเป็น O(n) |
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 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) |
|||
รุ่นแก้ไขเมื่อ 21:34, 17 กันยายน 2554
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม (อังกฤษ:Polygon Triangulation) คือการแบ่งรูปหลายเหลี่ยมเป็นเซ็ทของสามเหลี่ยมที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน
โครงร่างสามเหลี่ยมของรูปหลายเหลี่ยมแบบไม่มีจุดยอดเพิ่มเติม
วิธีการตัดหู (อังกฤษ: Ear Clipping Method)
วิธีที่ได้รับความนิยมและง่ายในการเขียนวิธีหนึ่งคือการตัดสามเหลี่ยมที่เป็น “หู” สามเหลี่ยมที่เป็นหูคือสามเหลี่ยมที่มีด้าน 2 ด้านอยู่ที่ขอบของรูปหลายเหลี่ยมและด้านที่เหลืออยู่ในด้านในทั้งหมด ซึ่งวิธีนี้จะใช้ได้กับรูปหลายเหลี่ยมที่ไม่มีรูภายในเท่านั้น โดยรูปหลายเหลี่ยมเหล่านั้นที่มีมุมมากกว่า 4 มุมขึ้นไป จะมี 2 หูเป็นอย่างน้อย หลังจากตัดทิ้งไปแล้วก็จะได้รูปหลายเหลี่ยมใหม่ที่มีจุดยอดมากกว่าเท่ากับ 3 ให้ทำต่อไปเรื่อยๆจนหมดก็จะได้เซ็ทของสามเหลี่ยมทั้งหมด ซึ่งเวลาที่ใช้จะเป็น O(n2) วิธีในการหาหูนั้นถูกค้นพบโดย Hossam ElGindy, Hazel Everett และ Godfried Toussaint โดยในการหาหูจะใช้เวลาเป็น O(n)
รหัสเทียม
กำหนดให้ 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 ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น O(n log n)