الگوریتم فورچون

frame|چپ|پویانمایی الگوریتم فورچون
**الگوریتم فورچون** یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان <math>O(n log n)</math> و حافظۀ <math>O(n)</math> است.
این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد.

## توضیح الگوریتم
این الگوریتم هم از خط جارویی و هم از *خط ساحلی* استفاده می‌کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می‌کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می‌توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می‌کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده‌اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه‌های سهمیها تشکیل شده است؛ این خط صفحه را به گونه‌ای تقسیم می‌کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیۀ صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعۀ این سهمی‌ها است. هر چه خط جارویی پیشروی می‌کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال‌های نمودار ورونی را رسم می‌کنند. خط ساحلی طوری پیشرفت می‌کند که رأس هر سهمی دقیقأ در وسط نقاط اولیۀ خط جارویی و جایگاه جدید خط جارویی قرار بگیرد.

این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوۀ بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطۀ ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایرۀ عبورکننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت‌بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می‌کند و بهنگام‌سازی داده ساختارها، تشکیل می‌شود. از آنجا که <math>O(n)</math> رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی‌های دیاگرام ورونی مرتبط هستند) و زمان <math>O(log n)</math> برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت‌دار هستند) زمان کلی الگوریتم <math>O(n log n)</math> است.

### شبه‌کد
شبه‌کد توضیحات الگوریتم.

 let *(z) be the transformation *(z)=(z_x,z_y+d(z)),
   where d(z) is the Euclidean distance between z and the nearest site
 let T be the "beach line"
 let R_p be the region covered by site p.
 let C_{pq} be the boundary ray between sites p and q.
 let p_1,p_2,...,p_m be the sites with minimal y-coordinate, ordered by x-coordinate
 Q \gets S - {p_1,p_2,...,p_m}
 create initial vertical boundary rays C_{p_1,p_2}^0,C_{p_2,p_3}^0,...C_{p_{m-1},p_m}^0
 T \gets *(R_{p_1}),C_{p_1,p_2}^0,*(R_{p_2}),C_{p_2,p_3}^0,...,*(R_{p_{m-1}}),C_{p_{m-1},p_m}^0,*(R_{p_m})
 **while not** IsEmpty(Q) **do**
     p ← DeleteMin(Q)
     **case** p of
     p is a site in *(V):
         find the occurrence of a region *(R_q) in T containing p,
           bracketed by C_{rq} on the left and C_{qs} on the right
         create new boundary rays C_{pq}^- and C_{pq}^+ with bases p
         replace *(R_q) with *(R_q),C_{pq}^-,*(R_p),C_{pq}^+,*(R_q) in T
         delete from Q any intersection between C_{rq} and C_{qs}
         insert into Q any intersection between C_{rq} and C_{pq}^-
         insert into Q any intersection between C_{pq}^+ and C_{qs}
     p is a Voronoi vertex in *(V):
         let p be the intersection of C_{qr} on the left and C_{rs} on the right
         let C_{uq} be the left neighbor of C_{qr} and
           let C_{sv} be the right neighbor of C_{rs} in T
         create a new boundary ray C_{qs}^0 if q_y = s_y,
           or create C_{qs}^+ if p is right of the higher of q and s,
           otherwise create C_{qs}^-
         replace C_{qr},*(R_r),C_{rs} with newly created C_{qs} in T
         delete from Q any intersection between C_{uq} and C_{qr}
         delete from Q any intersection between C_{rs} and C_{sv}
         insert into Q any intersection between C_{uq} and C_{qs}
         insert into Q any intersection between C_{qs} and C_{sv}
         record p as the summit of C_{qr} and C_{rs} and the base of C_{qs}
         output the boundary segments C_{qr} and C_{rs}
     **endcase**
 **endwhile**
 output the remaining boundary rays in T

## بخش‌ها و دیسک‌های وزن‌دار
همان‌طور که فورچون در  توضیح داده است، یک نوع الگوریتم توسعه‌یافتۀ خط جارویی می‌تواند برای ساخت نمودار ورونی وزن‌دارافزایشی استفاده شود، که در آن فاصلۀ هر بخش با وزن آن تعیین می‌شود؛ که این می‌تواند برابر با نمودار ورونی مجموعه‌ای از دیسک‌های هم‌مرکز بخش‌ها و به شعاع وزن آن‌ها باشد.

زمانی که از نمودار ورونی برای ساخت treemapها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به‌طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.

## منابع

## پیوند به بیرون
* Steven Fortune's C implementation
* Fortune's Voronoi algorithm implemented in C++
* Fortune's Voronoi algorithm implemented in C# 
* Fortune's algorithm implemented in JavaScript

رده:هندسه محاسباتی