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

پویانمایی الگوریتم فورچون
الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان و حافظه است.
این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقاله "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد.
توضیح الگوریتم
این الگوریتم هم از خط جارویی و هم از خط ساحلی استفاده می‌کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می‌کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می‌توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می‌کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده‌اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه‌های سهمیها تشکیل شده است؛ این خط صفحه را به گونه‌ای تقسیم می‌کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیه صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعه این سهمی‌ها است. هر چه خط جارویی پیشروی می‌کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال‌های نمودار ورونی را رسم می‌کنند. خط ساحلی طوری پیشرفت می‌کند که راس هر سهمی دقیقا در وسط نقاط اولیه خط جارویی و جایگاه جدید خط جارویی قرار بگیرد.
این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوه بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطه ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایره عبورکننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت‌بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می‌کند و بهنگام‌سازی داده ساختارها، تشکیل می‌شود. از آنجا که رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی‌های دیاگرام ورونی مرتبط هستند) و زمان برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت‌دار هستند) زمان کلی الگوریتم است.
شبه‌کد
شبه‌کد توضیحات الگوریتم.
let be the transformation ,
where is the Euclidean distance between and the nearest site
let be the "beach line"
let be the region covered by site .
let be the boundary ray between sites and .
let be the sites with minimal -coordinate, ordered by -coordinate
create initial vertical boundary rays
while not IsEmpty( ) do
← DeleteMin( )
case of
is a site in :
find the occurrence of a region in containing ,
bracketed by on the left and on the right
create new boundary rays and with bases
replace with in
delete from any intersection between and
insert into any intersection between and
insert into any intersection between and
is a Voronoi vertex in :
let be the intersection of on the left and on the right
let be the left neighbor of and
let be the right neighbor of in
create a new boundary ray if ,
or create if is right of the higher of and ,
otherwise create
replace with newly created in
delete from any intersection between and
delete from any intersection between and
insert into any intersection between and
insert into any intersection between and
record as the summit of and and the base of
output the boundary segments and
endcase
endwhile
output the remaining boundary rays in
بخش‌ها و دیسک‌های وزن‌دار
همان‌طور که فورچون در توضیح داده است، یک نوع الگوریتم توسعه‌یافته خط جارویی می‌تواند برای ساخت نمودار ورونی وزن‌دارافزایشی استفاده شود، که در آن فاصله هر بخش با وزن آن تعیین می‌شود؛ که این می‌تواند برابر با نمودار ورونی مجموعه‌ای از دیسک‌های هم‌مرکز بخش‌ها و به شعاع وزن آن‌ها باشد.
زمانی که از نمودار ورونی برای ساخت treemapها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به‌طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.