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

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

الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان $O(nlogn)$ و حافظۀ $O(n)$ است. این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد.

توضیح الگوریتم

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

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

شبه‌کد

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

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# بایگانی‌شده در ۱۰ ژانویه ۲۰۱۲ توسط Wayback Machine
• Fortune's algorithm implemented in JavaScript