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

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

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

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

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

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

شبه‌کد

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

let ${\displaystyle *(z)}$ be the transformation ${\displaystyle *(z)=(z_{x},z_{y}+d(z))}$,
  where ${\displaystyle d(z)}$ is the Euclidean distance between ${\displaystyle z}$ and the nearest site
let ${\displaystyle T}$ be the "beach line"
let ${\displaystyle R_{p}}$ be the region covered by site ${\displaystyle p}$.
let ${\displaystyle C_{pq}}$ be the boundary ray between sites ${\displaystyle p}$ and ${\displaystyle q}$.
let ${\displaystyle p_{1},p_{2},...,p_{m}}$ be the sites with minimal ${\displaystyle y}$-coordinate, ordered by ${\displaystyle x}$-coordinate
${\displaystyle Q\gets S-{p_{1},p_{2},...,p_{m}}}$
create initial vertical boundary rays ${\displaystyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...C_{p_{m-1},p_{m}}^{0}}$
${\displaystyle 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(${\displaystyle Q}$) do
    ${\displaystyle p}$ ← DeleteMin(${\displaystyle Q}$)
    case ${\displaystyle p}$ of
    ${\displaystyle p}$ is a site in ${\displaystyle *(V)}$:
        find the occurrence of a region ${\displaystyle *(R_{q})}$ in ${\displaystyle T}$ containing ${\displaystyle p}$,
          bracketed by ${\displaystyle C_{rq}}$ on the left and ${\displaystyle C_{qs}}$ on the right
        create new boundary rays ${\displaystyle C_{pq}^{-}}$ and ${\displaystyle C_{pq}^{+}}$ with bases ${\displaystyle p}$
        replace ${\displaystyle *(R_{q})}$ with ${\displaystyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$ in ${\displaystyle T}$
        delete from ${\displaystyle Q}$ any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{qs}}$
        insert into ${\displaystyle Q}$ any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{pq}^{-}}$
        insert into ${\displaystyle Q}$ any intersection between ${\displaystyle C_{pq}^{+}}$ and ${\displaystyle C_{qs}}$
    ${\displaystyle p}$ is a Voronoi vertex in ${\displaystyle *(V)}$:
        let ${\displaystyle p}$ be the intersection of ${\displaystyle C_{qr}}$ on the left and ${\displaystyle C_{rs}}$ on the right
        let ${\displaystyle C_{uq}}$ be the left neighbor of ${\displaystyle C_{qr}}$ and
          let ${\displaystyle C_{sv}}$ be the right neighbor of ${\displaystyle C_{rs}}$ in ${\displaystyle T}$
        create a new boundary ray ${\displaystyle C_{qs}^{0}}$ if ${\displaystyle q_{y}=s_{y}}$,
          or create ${\displaystyle C_{qs}^{+}}$ if ${\displaystyle p}$ is right of the higher of ${\displaystyle q}$ and ${\displaystyle s}$,
          otherwise create ${\displaystyle C_{qs}^{-}}$
        replace ${\displaystyle C_{qr},*(R_{r}),C_{rs}}$ with newly created ${\displaystyle C_{qs}}$ in ${\displaystyle T}$
        delete from ${\displaystyle Q}$ any intersection between ${\displaystyle C_{uq}}$ and ${\displaystyle C_{qr}}$
        delete from ${\displaystyle Q}$ any intersection between ${\displaystyle C_{rs}}$ and ${\displaystyle C_{sv}}$
        insert into ${\displaystyle Q}$ any intersection between ${\displaystyle C_{uq}}$ and ${\displaystyle C_{qs}}$
        insert into ${\displaystyle Q}$ any intersection between ${\displaystyle C_{qs}}$ and ${\displaystyle C_{sv}}$
        record ${\displaystyle p}$ as the summit of ${\displaystyle C_{qr}}$ and ${\displaystyle C_{rs}}$ and the base of ${\displaystyle C_{qs}}$
        output the boundary segments ${\displaystyle C_{qr}}$ and ${\displaystyle C_{rs}}$
    endcase
endwhile
output the remaining boundary rays in ${\displaystyle T}$

بخش‌ها و دیسک‌های وزن‌دار

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

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

منابع

1. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Section 7.2: Computing the Voronoi Diagram: pp.151–160.
2. Austin, David, Voronoi Diagrams and a Day at the Beach, Feature Column, American Mathematical Society.
3. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink
4. Kenny Wong, Hausi A. Müller, An Efficient Implementation of Fortune's Plane-Sweep Algorithm for Voronoi Diagrams.

پیوند به بیرون

• 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