خوارزمية مجلة فورتشن

وصف الخوارزمية باستخدام الشفرة الزائفة . ^{[ 4 ]}

يترك${\displaystyle \scriptstyle *(z)}$كن أنت التحول${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$، أين${\displaystyle \scriptstyle d(z)}$هي المسافة الإقليدية بين z وأقرب موقع، ولتكن T هي "خط الشاطئ" .${\displaystyle \scriptstyle R_{p}}$لتكن المنطقة التي يغطيها الموقع p . ${\displaystyle \scriptstyle C_{pq}}$ليكن شعاع الحدود بين الموقعين p و q . ${\displaystyle \scriptstyle S}$لنفترض أن لدينا مجموعة من المواقع التي سيتم تطبيق هذه الخوارزمية عليها. ${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$لتكن المواقع المستخرجة من S ذات الإحداثي y الأدنى ، مرتبة حسب الإحداثي x . ولتكن DeleteMin( X ) عملية إزالة الموقع الأدنى والأيسر من X (يتم الترتيب حسب y إلا إذا كانا متطابقين، وفي هذه الحالة يتم الترتيب حسب x). ولتكن V خريطة فورونوي لـ S التي سيتم إنشاؤها بواسطة هذه الخوارزمية. ${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$إنشاء أشعة حدودية رأسية أولية${\displaystyle \scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,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},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$بينما لا تكون قائمة Q فارغة ، قم بتنفيذ ما يلي : p ← DeleteMin( Q ) في حالة p ، إذا كان p موقعًا في${\displaystyle \scriptstyle *(V)}$: ابحث عن وجود منطقة${\displaystyle \scriptstyle *(R_{q})}$في T التي تحتوي على p ، محصور بين${\displaystyle \scriptstyle C_{rq}}$على اليسار و${\displaystyle \scriptstyle C_{qs}}$على اليمين، أنشئ أشعة حدودية جديدة${\displaystyle \scriptstyle C_{pq}^{-}}$و${\displaystyle \scriptstyle C_{pq}^{+}}$ مع استبدال القواعد p${\displaystyle \scriptstyle *(R_{q})}$مع${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$في T، احذف من Q أي تقاطع بين${\displaystyle \scriptstyle C_{rq}}$و${\displaystyle \scriptstyle C_{qs}}$أدخل في Q أي تقاطع بين${\displaystyle \scriptstyle C_{rq}}$و${\displaystyle \scriptstyle C_{pq}^{-}}$أدخل في Q أي تقاطع بين${\displaystyle \scriptstyle C_{pq}^{+}}$و${\displaystyle \scriptstyle C_{qs}}$p هو رأس فورونوي في${\displaystyle \scriptstyle *(V)}$ليكن p هو تقاطع${\displaystyle \scriptstyle C_{qr}}$على اليسار و${\displaystyle \scriptstyle C_{rs}}$على اليمين يسار${\displaystyle \scriptstyle C_{uq}}$كن الجار الأيسر لـ${\displaystyle \scriptstyle C_{qr}}$ودع ​${\displaystyle \scriptstyle C_{sv}}$كن الجار المناسب لـ${\displaystyle \scriptstyle C_{rs}}$في T إذا${\displaystyle \scriptstyle q_{y}=s_{y}}$أنشئ شعاعًا حدوديًا جديدًا${\displaystyle \scriptstyle C_{qs}^{0}}$أما إذا كان p يقع على يمين القيمة الأعلى بين q و s ، فأنشئ${\displaystyle \scriptstyle C_{qs}^{+}}$وإلا قم بإنشاء${\displaystyle \scriptstyle C_{qs}^{-}}$endif استبدال${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$مع إنشاء جديد${\displaystyle \scriptstyle C_{qs}}$في T، احذف من Q أي تقاطع بين${\displaystyle \scriptstyle C_{uq}}$و${\displaystyle \scriptstyle C_{qr}}$احذف من Q أي تقاطع بين${\displaystyle \scriptstyle C_{rs}}$و${\displaystyle \scriptstyle C_{sv}}$أدخل في Q أي تقاطع بين${\displaystyle \scriptstyle C_{uq}}$و${\displaystyle \scriptstyle C_{qs}}$أدخل في Q أي تقاطع بين${\displaystyle \scriptstyle C_{qs}}$و${\displaystyle \scriptstyle C_{sv}}$ سجل p كأعلى قمة${\displaystyle \scriptstyle C_{qr}}$و${\displaystyle \scriptstyle C_{rs}}$وقاعدة${\displaystyle \scriptstyle C_{qs}}$ إخراج أجزاء الحدود${\displaystyle \scriptstyle C_{qr}}$و${\displaystyle \scriptstyle C_{rs}}$endcase endwhile قم بإخراج أشعة الحدود المتبقية في T

كما يوضح فورتشن في المرجع ^{[ 1 ]،} يمكن استخدام نسخة معدلة من خوارزمية خط المسح لإنشاء مخطط فورونوي مرجح جمعيًا ، حيث يتم تعويض المسافة إلى كل موقع بوزن ذلك الموقع؛ ويمكن اعتبار هذا المخطط بمثابة مخطط فورونوي لمجموعة من الأقراص، متمركزة عند المواقع بنصف قطر يساوي وزن الموقع. وقد وُجد أن الخوارزمية تتمتع بـ${\displaystyle O(n\log(n))}$التعقيد الزمني حيث n هو عدد المواقع وفقًا للمرجع ^{[ 1 ]}

يمكن استخدام المواقع الموزونة للتحكم في مساحات خلايا فورونوي عند استخدام مخططات فورونوي لإنشاء خرائط شجرية . في مخطط فورونوي الموزون جمعيًا، يكون منصف الخط بين المواقع عادةً قطعًا زائدًا، على عكس مخططات فورونوي غير الموزونة ومخططات القوى للأقراص حيث يكون خطًا مستقيمًا.