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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
پویانمایی الگوریتم فورچون

الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان و حافظۀ است.[۱][۲] این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودار‌های ورونی" چاپ شد.[۳]

توضیح الگوریتم[ویرایش]

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

این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوۀ بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطۀ ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایرۀ عبور کننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور 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ها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.

منابع[ویرایش]

  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 .

پیوند به بیرون[ویرایش]