خوارزمية بوير-واتسون

في الهندسة الحسابية ، تُعد خوارزمية بوير-واتسون طريقةً لحساب تثليث ديلاوناي لمجموعة محدودة من النقاط في أي عدد من الأبعاد . ويمكن استخدام هذه الخوارزمية أيضًا للحصول على مخطط فورونوي للنقاط، وهو الرسم البياني الثنائي لتثليث ديلاوناي.

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

• 
  الخطوة الأولى: أدخل عقدة في مثلث "فائق" محيط
• 
  أدخل العقدة الثانية
• 
  أدخل العقدة الثالثة
• 
  أدخل العقدة الرابعة
• 
  أدخل العقدة الخامسة (والأخيرة)
• 
  قم بإزالة الحواف ذات الأطراف المتطرفة في المثلث الفائق

تُعرف هذه الخوارزمية أحيانًا باسم خوارزمية بوير أو خوارزمية واتسون . وقد ابتكرها أدريان بوير وديفيد واتسون بشكل مستقل عن بعضهما البعض في نفس الوقت، ونشر كل منهما ورقة بحثية عنها في نفس العدد من مجلة الكمبيوتر (انظر أدناه).

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

دالة BowyerWatson ( قائمة النقاط ) // قائمة النقاط هي مجموعة من الإحداثيات التي تحدد النقاط المراد تقسيمها إلى مثلثات. المثلث := بنية بيانات شبكة مثلثات فارغة. أضف مثلثًا رئيسيًا إلى المثلث // يجب أن تكون كبيرة بما يكفي لاحتواء جميع النقاط في قائمة النقاط بالكامل. لكل نقطة في قائمة النقاط، قم بما يلي: // أضف جميع النقاط واحدة تلو الأخرى إلى المثلث. المثلثات السيئة := مجموعة فارغة. لكل مثلث في المثلث ، قم بما يلي : // ابحث أولاً عن جميع المثلثات التي لم تعد صالحة بسبب الإضافة . إذا كانت النقطة داخل الدائرة المحيطة بالمثلث ، فأضف المثلث إلى المثلثات السيئة. المضلع := مجموعة فارغة. لكل مثلث في المثلثات السيئة، قم بما يلي: // ابحث عن حدود الفتحة المضلعة. لكل حافة في المثلث ، قم بما يلي : إذا لم تكن الحافة مشتركة مع أي مثلثات أخرى في المثلثات السيئة، فأضف الحافة إلى المضلع. لكل مثلث في المثلثات السيئة ، قم بما يلي: // قم بإزالتها من بنية البيانات. قم بإزالة المثلث من المثلث. لكل حافة في المضلع ، قم بما يلي: // أعد تقسيم الفتحة المضلعة إلى مثلثات. مثلث جديد : = شكل مثلثًا من الحافة إلى النقطة . أضف إنشاء مثلث جديد لكل مثلث في المثلث الحالي // تم إدخال النقاط، الآن قم بتنظيف المثلث إذا كان يحتوي على رأس من المثلث الأصلي - قم بإزالة المثلث من المثلث الحالي، ثم أعد المثلث الحالي

• بوير، أدريان (1981). "حساب تبليطات ديريشليه" . مجلة الحوسبة 24 (2): 162-166 . doi : 10.1093/comjnl/24.2.162 .
• واتسون، ديفيد ف. (1981). "حساب تجزئة ديلاوناي ذات الأبعاد n مع تطبيق على متعددات وجوه فورونوي". مجلة الحوسبة 24 (2): 167-172 . doi : 10.1093/comjnl/24.2.167 .
• خوارزمية التثليث الفعالة المناسبة لنمذجة التضاريس، مع شروحات عامة وأمثلة على شفرة المصدر بلغات متعددة.

• pyDelaunay2D : خوارزمية بوير-واتسون مُطبقة بلغة بايثون التعليمية
• Bl4ckb0ne/delaunay-triangulation : خوارزمية Bowyer–Watson مُنفذة بلغة C++