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

**ขั้นตอนวิธีของฟอร์จูน** คือขั้นตอนวิธีแบบเส้นกวาด (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))
## หลักการทำงานของขั้นตอนวิธีเส้นกวาด

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

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

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

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

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

* เหตุการณ์การเกิด vertex (circle events) - เมื่อความยาวของเส้นโค้งพาราโบล่าหดจนเหลือ 0 (เส้นโค้งหายไป) จะเกิด voronoi vertex ที่จุดศูนย์กลางของวงกลมที่มีเส้นรอบวงสัมผัสไซท์ รอบตัว 3 ไซท์ และ เส้นกวาด
## การเก็บสถานะของแผนภาพโวโรนอย เส้นกวาด และ เส้นคลื่นทะเล
* สถานะของแผนภาพโวโรนอย ใช้ Doubly linked list (D) ทำให้เราสามารถสำรวจ ส่วน เซลล์ และ vertices ของแผนภาพได้

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

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

## ขั้นตอนวิธี
# กำหนดค่าเริ่มต้น
* 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
# ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
# ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
# เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
# ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์
#### การจัดการกับเหตุการณ์การเกิด vertex
# เพิ่ม vertex ใน doubly linked list
#ลบเส้นโค้งที่หายไป
#เพิ่มข้อมูลเส้นเชื่อม ใหม่ที่เกิด ลงใน doubly linked list
#ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์
## วิเคราะห์ประสิทธิภาพเชิงเวลา
#### การจัดการกับเหตุการณ์การพบ site
# ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
# ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
# เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
# ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์จะได้
# O(logn)
# O(1)
# O(1)
# O(1)

#### การจัดการกับเหตุการณ์การเกิด vertex
# เพิ่ม vertex ใน doubly linked list
# ลบเส้นโค้งที่หายไป
# เพิ่มข้อมูลเส้นเชื่อมใหม่ที่เกิด ลงใน doubly linked list
# ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์จะได้
# O(logn)
# O(1)
# O(1)
# 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
```


## อ้างอิง
# http://www.donhavey.com/blog/tutorials/tutorial-7-voronoi-diagrams 
# http://nms.csail.mit.edu/~aklmiu/6.838/L7.pdf
# http://en.wikipedia.org/wiki/Fortune%27s_algorithm
# http://en.wikipedia.org/wiki/Voronoi_diagram
# http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_1.pdf 
# http://www.diku.dk/hjemmesider/studerende/duff/Fortune/ 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:เรขาคณิตเชิงคำนวณ