ขั้นตอนวิธีของฟอร์จูน

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีของฟอร์จูน คือ ขั้นตอนวิธีแบบเส้นกวาด (sweep line algorithm) ที่ใช้สำหรับสร้างแผนภาพโวโรนอย จากเซตของจุดบนระนาบ โดยใช้เวลา O (n*log (n) ) ซึ่งคิดค้นขึ้นโดย Steven Fortune ในปี 1986

ประวัติ[แก้]

ในอดีตหลายปีที่ผ่านมาได้มีผู้ที่คิดค้นขั้นตอนวิธีสำหรับการสร้างแผนโวโรนอยโดยใช้เวลาในการคำนวณเป็น O (n^2) ในเวลาต่อมา ได้มีผู้คิดค้นขั้นตอนวิธีที่รวดเร็วกว่า โดยใช้เวลาในการคำนวณเป็น O (n*log (n) ) โดยขั้นตอนวิธีดังกล่าว คิดโดยพื้นฐานของขั้นตอนวิธีแบบแบ่งแยกและเอาชนะ (divide and conquer) แต่วิธีการนี้ มีความซับซ้อนมาก และยากที่จะทำความเข้าใจ ด้วยเหตุนี้ ภายหลัง Steven Fortune จึงได้คิดค้นวิธีเส้นกวาดนี้ขึ้นมาเพื่อแก้ปัญหาดังกล่าว โดยยังคงใช้เวลาในการคำนวณเท่าเดิม คือ O (n*log (n) )

หลักการทำงานของขั้นตอนวิธีเส้นกวาด[แก้]

350px

วิธีการนี้จะมีสองส่วนที่ต้องสนใจคือเส้นกวาด (sweep line) และเส้นคลื่นทะเล (beach line) แผนภาพโวโรนอยจะค่อย ๆ ถูกสร้างขึ้น ตามแนวเส้นกวาด ที่กวาดไซท์ต่าง ๆ ไป จากบนลงล่าง โดยจะค่อย ๆ พิจารณาทีละไซท์ ตามที่เส้นกวาด กวาดไปพบ นั่นคือ ทำการพิจารณาไซท์ต่าง ๆ ที่อยู่ด้านบนของเส้นกวาดก่อน ส่วนไซท์ที่อยู่หลังเส้นกวาด จะยังไม่นำมาพิจารณา

ส่วนเส้นคลื่นทะเลนั้นจะมีลักษณะเป็นเส้นโค้ง คอยไล่ตามเส้นกวาด โดยจะมีลักษณะคล้ายกับส่วนหนึ่งของเส้นโค้งพาราโบล่า แต่ละไซท์จะมีเส้นคลื่นทะเลเป็นของตนเอง โดยจากตำแหน่งใด ๆ บนเส้นคลื่นทะเลนั้น จะมีระยะห่างระหว่างจุดนั้นถึงไซท์ของมัน และ จากจุดนั้นถึงเส้นกวาด เป็นระยะทางเท่า ๆ กัน

อีกหนึ่งจุดที่สำคัญคือจุดหยุด (break point) คือ ตำแหน่งที่เกิดจากการส่วนโค้ง (arc) ของสองเส้นคลื่นทะเลมาบรรจบกัน อยู่บนเส้นเชื่อมโวโรนอย (voronoi edge) โดยมันจะเลื่อนตามเส้นเชื่อมลงมาเรื่อย ๆ ตามที่เส้นคลื่นทะเลเลื่อนลงมา ซึ่งจุดนี้เป็นจุดที่มีระยะห่าง จากจุดถึงไซท์ที่เส้นคลื่นทะเลมาบรรจบกัน และ จากจุดถึงเส้นกวาด เท่ากัน

ลักษณะการเคลื่อนตัวของทั้งสองเส้น เพื่อสร้างแผนภาพจะเป็นดังนี้

250px

250px

250px

250px

เหตุการณ์สำคัญ[แก้]

ระหว่างการเคลื่อนที่ของทั้งสามจุดนี้ จะมีเหตุการณ์สำคัญ (significant event) ที่ทำให้เกิดการเปลี่ยนแปลงของโครงสร้าง และการเปลี่ยนแปลงของลักษณะของเส้นคลื่นทะเล ที่ต้องพิจารณาด้วย คือ

  • สถานะของเส้นกวาด - ตำแหน่งปัจจุบันของเส้นกวาด (พิกัด y) ซึ่งเป็นตัวกำหนดเส้นคลื่นทะเล
  • เหตุการณ์การพบไซท์ - เส้นกวาดเคลื่อนที่จนพบไซท์ ทำให้เกิดการแทรกเส้นโค้งเข้ามาที่เส้นคลื่นทะเลเดิม ทำให้เส้นคลื่นทะเลเดิมถูกแยกเป็นสองส่วน ดังภาพ

400px

  • เหตุการณ์การเกิด vertex (circle events) - เมื่อความยาวของเส้นโค้งพาราโบล่าหดจนเหลือ 0 (เส้นโค้งหายไป) จะเกิด voronoi vertex ที่จุดศูนย์กลางของวงกลมที่มีเส้นรอบวงสัมผัสไซท์ รอบตัว 3 ไซท์ และ เส้นกวาด

400px

การเก็บสถานะของแผนภาพโวโรนอย เส้นกวาด และ เส้นคลื่นทะเล[แก้]

  • สถานะของแผนภาพโวโรนอย ใช้ Doubly linked list (D) ทำให้เราสามารถสำรวจ ส่วน เซลล์ และ vertices ของแผนภาพได้
  • สถานะของเส้นคลื่นทะเล

ใช้ Balanced Binary Tree (T) • โนดภายในต้นไม้ แสดงถึงจุดหยุดระหว่างสองเส้นโค้งคลื่นทะเล • ใบของต้นไม้แสดงถึงเส้นโค้ง โดยเส้นโค้งถูกแสดงจากไซท์ของตนเอง

  • สถานะของเส้นกวาด ใช้ Priority event queue (Q)

ขั้นตอนวิธี[แก้]

  1. กำหนดค่าเริ่มต้น
  • Event queue Q ß เหตุการณ์การพบ site ทุกเหตุการณ์
  • Binary search tree T ß Æ
  • Doubly linked list D ß Æ

2. While Q not Æ,

  • Remove event (e) from Q with largest y-coordinate
  • ลบเหตุการณ์ที่มีค่าพิกัด y สูงสุด ออกจากคิว
  • HandleEvent (e, T, D)

การจัดการกับเหตุการณ์ต่าง ๆ[แก้]

การจัดการกับเหตุการณ์การพบ site[แก้]

  1. ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
  2. ลบเส้นโค้งโดยแทนที่ใบ (เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
  3. เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
  4. ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์

การจัดการกับเหตุการณ์การเกิด vertex[แก้]

  1. เพิ่ม vertex ใน doubly linked list

450px

  1. ลบเส้นโค้งที่หายไป

450px 450px

  1. เพิ่มข้อมูลเส้นเชื่อม ใหม่ที่เกิด ลงใน doubly linked list

450px

  1. ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์

450px

วิเคราะห์ประสิทธิภาพเชิงเวลา[แก้]

การจัดการกับเหตุการณ์การพบ site[แก้]

  1. ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
  2. ลบเส้นโค้งโดยแทนที่ใบ (เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
  3. เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
  4. ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์จะได้
  5. O (logn)
  6. O (1)
  7. O (1)
  8. O (1)

การจัดการกับเหตุการณ์การเกิด vertex[แก้]

  1. เพิ่ม vertex ใน doubly linked list
  2. ลบเส้นโค้งที่หายไป
  3. เพิ่มข้อมูลเส้นเชื่อมใหม่ที่เกิด ลงใน doubly linked list
  4. ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์จะได้
  5. O (logn)
  6. O (1)
  7. O (1)
  8. O (1)

สรุป[แก้]

แต่ละ site ใหม่ จะทำให้เกิดเส้นโค้งใหม่ได้มากสุด สองเส้น

  • เส้นคลื่นทะเลสามารถมีเส้นโค้งได้มากสุด 2n-1 เส้น
  • มากสุด O (n) สำหรับ site และ เหตุการณ์การเกิด vertex ในคิว
  • การจัดการทำเหตุการณืทั้งสองแบบใช้เวลา O (log (n) )

ดังนั้น เวลาทั้งหมดที่ใช้ คือ O (n*log (n) )

รหัสเทียม[แก้]

let * (z) be the transformation * (z) = (zx, zy + d (z) ), where d (z) is a parabola with minimum at z
let T be the "beach line"
let Rp be the region covered by site p.
let Cpq be the boundary ray between sites p and q.
let p1, p2, ..., pm be the sites with minimal y-coordinate, ordered by x-coordinate

create initial vertical boundary rays

while not IsEmpty (Q) do
p ← DeleteMin (Q)
case p of
p is a site in * (V) :
find the occurrence of a region * (Rq) in T containing p,
bracketed by Crq on the left and Cqs on the right
create new boundary rays and with bases p
replace * (Rq) with in T
delete from Q any intersection between Crq and Cqs
insert into Q any intersection between Crq and
insert into Q any intersection between and Cqs
p is a Voronoi vertex in * (V) :
let p be the intersection of Cqr on the left and Crs on the right
let Cuq be the left neighbor of Cqr and
let Csv be the right neighbor of Crs in T
create a new boundary ray if qy = sy,
or create if p is right of the higher of q and s,
otherwise create
replace Cqr, * (Rr), Crs with newly created Cqs in T
delete from Q any intersection between Cuq and Cqr
delete from Q any intersection between Crs and Csv
insert into Q any intersection between Cuq and Cqs
insert into Q any intersection between Cqs and Csv
record p as the summit of Cqr and Crs and the base of Cqs
output the boundary segments Cqr and Crs
endcase
endwhile
output the remaining boundary rays in T

อ้างอิง[แก้]

  1. http://www.donhavey.com/blog/tutorials/tutorial-7-voronoi-diagrams
  2. http://nms.csail.mit.edu/~aklmiu/6.838/L7.pdf
  3. http://en.wikipedia.org/wiki/Fortune's_algorithm
  4. http://en.wikipedia.org/wiki/Voronoi_diagram
  5. http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_1.pdf
  6. http://www.diku.dk/hjemmesider/studerende/duff/Fortune/