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

ประวัติ

ในอดีตหลายปีที่ผ่านมาได้มีผู้ที่คิดค้นขั้นตอนวิธีสำหรับการสร้างแผนโวโรนอยโดยใช้เวลาในการคำนวณเป็น 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

รหัสเทียม

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