TEPLOV A.A.، بكالوريوس ، جامعة موسكو التقنية الحكومية التي تحمل اسم N.E. بومان ، قسم برامج الحاسوب وتقنيات المعلومات ، موسكو ، [بريد إلكتروني محمي]

مايكوف ك.، دكتوراه في العلوم التقنية ، أستاذ ، جامعة موسكو التقنية الحكومية التي سميت على اسم N.E. بومان ، قسم برامج الحاسوب وتقنيات المعلومات ، موسكو ، [بريد إلكتروني محمي]

الخوارزمية المعدلة
تثليث ديلوناي

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

مقدمة

يعد التثليث أحد المراحل التي تحدد كثافة الموارد لبناء كائنات ثلاثية الأبعاد ديناميكية بدرجة معينة من التفاصيل. من الناحية العملية ، يصبح من الضروري تحديد النموذج الأولي لطريقة التثليث التي تفي بمتطلبات الأداء العالي وكثافة الموارد المنخفضة مع التعديل اللاحق لفئة معينة من المشاكل.

بيان المهام المراد حلها

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

يتم حل مشكلة "درجة انتظام" المثلثات عن طريق التثليث الذي يفي بشرط Delaunay.

يمكن تقسيم خوارزميات Delaunay Triangulation المعروفة إلى أربع فئات: الخوارزميات التكرارية ، وخوارزميات الاندماج ، وخوارزميات المسارين ، والتدرج ؛ تتم مناقشة السمات الرئيسية لهذه الخوارزميات أدناه.

الخوارزميات التكرارية لبناء تثليث ديلوناي

في الخوارزميات التكرارية ، يتم تنفيذ إضافة متسلسلة للنقاط إلى تثليث Delaunay الذي تم إنشاؤه جزئيًا. يتم تعريف تعقيد خوارزميات Delaunay التكرارية على أنها O (N2) ، وفي حالة التوزيع المنتظم للنقاط - O (N). تتمثل عيوب خوارزميات Delaunay التكرارية في عدد كبير من الدورات التكرارية ، واعتماد خوارزمية الفرز على بنية بيانات المصدر ، والحاجة إلى التحقق من حالة Delaunay في كل دورة. تتمثل مزايا خوارزميات Delaunay التكرارية في سهولة التنفيذ والسرعة العالية في اختيار خوارزمية فرز فعالة بناءً على مجموعة محددة من بيانات الإدخال.

خوارزميات لتكوين تثليث Delaunay عن طريق الدمج

تقوم خوارزميات الدمج بتنفيذ تقسيم المجموعة الأولية من النقاط إلى عدد من المجموعات الفرعية ، حيث يتم إنشاء المثلثات ، متبوعًا باتحاد عدد من الحلول. يكون تعقيد خوارزميات الدمج في المتوسط ​​O (N). تعد خوارزميات الدمج زائدة عن الحاجة بطبيعتها ، ويتم تحديدها من خلال الحاجة إلى بناء مناطق محدبة لنطاقات "ضيقة" ، وبالتالي تشكيل مثلثات طويلة و "ضيقة" ، أعيد بناؤها عند الدمج. تتمتع خوارزميات الدمج بسرعة عالية ، والتي تحدد ميزتها العملية.

خوارزميات ثنائية المسار لبناء تثليث ديلوناي

الميزة المفيدة للخوارزميات ذات المسارين هي أنه في الدورة الأولى يتم إنشاء بعض التثليث دون مراعاة حالة Delaunay ، والتي يتم تعديلها في المرحلة الثانية وفقًا لشرط Delaunay. يكون تعقيد الخوارزميات ثنائية المسار في المتوسط ​​O (N) ، وفي الحالة الأقل ملاءمة - O (N 2). عيب خوارزميات Delaunay ذات المسارين هو الحاجة إلى عدد كبير من الفرز لكل نطاق. في الوقت نفسه ، تتميز هذه الخوارزمية بالأداء العالي ، لأن لا يخضع المثلث التالي الذي يقع في التثليث لاختبار تلبية شرط Delaunay ، الأمر الذي يتطلب موارد أجهزة كبيرة.

خوارزميات خطوة بخطوة لبناء تثليث Delaunay

تقوم خوارزميات البناء التدريجي بتنفيذ المثلثات التي تفي بشرط Delaunay في التثليث النهائي ، وبالتالي لا تتطلب إعادة البناء. مع التركيز العالي للنقاط ، فإن استخدام خوارزمية خلوية خطوة بخطوة غير مناسب. تعقيد هذه الخوارزمية هو O (N) في المتوسط ​​، وفي أسوأ الحالات ، O (N 2).

اختيار نموذج أولي لتعديل Delaunay Triangulation

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

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

ومع ذلك ، يجب تعديل الخوارزميات من هذا النوع من أجل زيادة الأداء المطبق على مشاكل الوقت الفعلي. تعد خوارزمية المروحة ذات التمريرين زائدة عن الحاجة في تحديد مركز كتلة النقاط. عند تحديد إحداثيات نقطة مركز الكتلة بواسطة OX أو OY ، مع وجود عدد كبير من النقاط ، من غير المناسب حساب متوسط ​​القيمة الحسابية ، وبالنسبة للقيم الكبيرة لإحداثيات النقاط ، فقد يحدث تدفق للبيانات ، والذي سيؤدي إلى حدوث خطأ أو فشل البرنامج. لذلك ، يُنصح بتقسيم جميع قيم نقاط التثليث إلى فترات زمنية على طول المحور X بواسطة Δх 1 ، Δх 2 ، Δх 3 ... Δх n وعلى طول المحور Y على Δy 1 ، Δy 2 ، y 3. .. Δy n. من الضروري أيضًا تحديد عدد النقاط التي تنتمي إلى الفترات المقابلة على طول محوري X و Y. والصيغ الناتجة للحصول على مركز إحداثيات كتل النقاط هي كما يلي:

• x ج - إحداثيات x لنقطة مركز الكتلة ؛
• Δх i - الفاصل الزمني الأول على المحور السيني ؛
• X max - القيمة القصوى على طول المحور X بين جميع نقاط التثليث ؛
• X min - القيمة الدنيا على طول المحور X بين جميع نقاط التثليث ؛

• ص ج - إحداثيات ص لنقطة مركز الكتلة ؛
• n i هو عدد النقاط في الفترة من i إلى th ؛
• Δy i - الفاصل الزمني i على المحور Y ؛
• Y max - القيمة القصوى على طول المحور Y بين جميع نقاط التثليث ؛
• Y min - القيمة الدنيا على طول المحور Y بين جميع نقاط التثليث.

يتم تنفيذ المراحل اللاحقة من التثليث وفقًا لخوارزمية المروحة الكلاسيكية. يظهر مخطط خوارزمية Delaunay المثلث المطورة على شكل مروحة في الشكل. واحد.

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

تحليل خوارزمية تعديل Fan Delaunay Triangulation

من الذي يظهر في الشكل. يوضح الشكل 1 من الرسم التخطيطي أن قيمة وقت إنشاء التثليث بواسطة خوارزمية المروحة المعدلة يتم تحديدها من خلال التعبير:

• T 1 ، T 2 هي قيم الوقت لحساب العدد الأمثل للفترات على طول محوري X و Y ، على التوالي ؛
• T 3 ، T 4 هي قيم وقت الحساب X min و X max ، على التوالي ؛
• T 5 ، T 6 - قيم وقت الحساب Y min و Y max ، على التوالي ؛
• T 7 ، T 8 هي قيم الوقت لحساب قيم الفاصل الزمني على طول محوري X و Y ، على التوالي ؛
• T 9 هي القيمة الزمنية لحساب قيم الزاوية القطبية لكل نقطة من الصفيف بالنسبة للنقطة A (X ج ، ص ج) ؛
• T 10 هي القيمة الزمنية للفرز بدمج جميع النقاط وفقًا للزاوية القطبية بالنسبة للنقطة A (X c، Y c) ؛
• T 11 هي قيمة وقت بناء الحافة من كل نقطة من الصفيف إلى النقطة A (X c ، Y c) ؛
• T 12 - قيمة الوقت اللازم لإكمال التثليث إلى المحدب ؛
• T 13 هي قيمة وقت إعادة التثليث الذي يفي بشرط Delaunay ؛
• n هي مجموعة من قيم إحداثيات النقطة.

دعونا ننظر في كل وقت التبعية على حدة.

عند تحديد العدد الأمثل للفترات الزمنية على طول المحور X و Y ، فإننا نستخدم قاعدة Sturges ، والتي بموجبها يتم تحديد عدد الفواصل الزمنية n على النحو التالي:

• N هو العدد الإجمالي لملاحظات الكمية ؛
• [x] هو الجزء الصحيح من الرقم x.

من الواضح أن تبعيات الوقت لـ T 1 و T 2 لها تمثيلات ثابتة c 1 و c 2.

في مراحل تحديد قيم X min ، X max ، Y min ، Y max ، سيبدو الرمز الزائف كما يلي:

Xmin ← م

لـ i ← 1 إلى الطول (M) - 1

إذا كان Xmin ›M [i]

Xmin ← M [i]

Xmax ← م

لـ i ← 1 إلى الطول (M) - 1

IfXmax< M[i]

Xmax ← M [i]

يمين ← م

لـ i ← 1 إلى الطول (M) - 1

إذا كان يمين ›M [i]

Ymin ← M [i]

Ymax ← م

لـ i ← 1 إلى الطول (M) - 1

إذا كان Ymax< M[i]

Ymax ← M [i]

من الكود الكاذب أعلاه ، من الواضح أن الوقت للعثور على الحد الأقصى أو الحد الأدنى لقيمة x أو y له اعتماد خطي O (N) ، لذلك ، T 3 (n) ، T 4 (n) ، T 5 (n ) ، T 6 (n) ، لها خاصية زمنية O (N) ، على التوالي.

يظهر مخطط تحديد القيم الفاصلة على طول المحور X في الشكل. 2.

من الرسم البياني أعلاه ، فإن اعتماد الوقت الخطي O (N) مرئي أيضًا ، منذ ذلك الحين المجموعة الكاملة من إحداثيات قيم صفيف النقاط متضمنة في تحديد القيم. مخطط تحديد قيم الفواصل الزمنية على طول المحور Y له هيكل مماثل وخصائص زمنية ، وبالتالي ، فإن الاعتماد على الوقت لـ T 7 (n) و T 8 (n) هو O (N).

يظهر مخطط تحديد قيم الزاوية القطبية للمصفوفة الأولية للنقاط في الشكل. 3.

في الكود الكاذب ، سيبدو هذا المخطط كما يلي:

للحصول على نقاط إلى نقاط

# إذا كانت النقطة تقع على محور الإحداثيات بين الربعين الأول والرابع

إذا كانت point.x ≥ Xc و point.y = Yc

Point.angle ← 0

# إذا كانت النقطة تكمن بدقة في الربع الأول

عدا ذلك ، إذا كانت point.x> Xc و point.y> Yc

مؤسسة ← | point.x - Xc |

Point.angle ← arctg (عمودي / أساس)

# إذا كانت النقطة تقع على محور الإحداثيات بين الربعين الأول والثاني

عدا ذلك ، إذا كانت point.x = Xc و point.y> Yc

Point.angle ← ص / 2

# إذا كانت النقطة تكمن بدقة في الربع الثاني

آخر إذا كان point.x.< Xc and point.y >يك

مؤسسة ← | point.y - Yc |

Point.angle ← p / 2 + arctg (عمودي / أساس)

# إذا كانت النقطة تقع على محور الإحداثيات بين الربعين الثاني والثالث

إذا كانت النقطة س< Xc and point.y = Yc

Point.angle ← ص

# إذا كانت النقطة تكمن بدقة في الربع الثالث

إذا كانت النقطة س< Xc and point.y >يك

مؤسسة ← | point.x - Xc |

عمودي ← | point.y - Yc |

Point.angle ← p + arctg (عمودي / أساس)

# إذا كانت النقطة تقع على محور الإحداثيات بين الربعين الثالث والرابع

إذا كانت point.x = Xc و point.y< Yc

Point.angle ← 3p / 2

# إذا كانت النقطة تكمن بدقة في الربع الرابع

إذا كانت point.x> Xc و point.y< Yc

مؤسسة ← | point.y - Yc |

عمودي ← | point.x - Xc |

Point.angle ← 3p / 2 + arctg (عمودي / أساس)

من الواضح أن الخاصية الزمنية لتحديد قيم الزاوية القطبية للمصفوفة الأولية لإحداثيات النقاط لها الشكل O (N) ، وبالتالي ، T 9 (n) = O (N).

كما هو مبين في ، فرز الدمج له اعتماد زمني على الشكل O (N) ، وبالتالي T 10 (n) = O (NlnN).

يظهر مخطط إنشاء حافة تربط نقاط المصفوفة الأصلية في الشكل. 4.

سيبدو الرمز الكاذب للمخطط أعلاه كما يلي:

لـ i ← 0 إلى الطول (النقاط) - 1

ارسم (Xc، Yc، Points [i] .x، Points [i] .y)

الاستجابة الزمنية هي أيضًا خطية ، وبالتالي T 11 (n) = O (N).

يتم الانتهاء من التثليث الناتج إلى واحد محدب وفقًا لخوارزمية Graham. بيانات الإدخال للإجراء هي مجموعة النقاط Q ، حيث | Q | ≥3. تستدعي الوظيفة Top (S) ، والتي ترجع النقطة في أعلى المكدس S دون تغيير محتوياتها. بالإضافة إلى ذلك ، يتم أيضًا استخدام الوظيفة NextToTop (S) ، والتي تُرجع النقطة الموجودة على المكدس S ، موضع واحد أسفل النقطة العليا ؛ لا يتغير المكدس S.

جراهام (كيو)

دع p 0 تكون نقطة من المجموعة Q مع الحد الأدنى من الإحداثيات.

دع ‹p 1، p 2، ...، p N› تكون نقاط المجموعة Q مرتبة

بترتيب تصاعدي للزاوية القطبية.

دفع (ص 0 ، ق)

دفع (ص 1 ، س)

لأني = 2 إلى N تفعل

بينما تشكلت الزاوية بالنقاط NextToTop (S) و Top (S) و pi ،

شكل منعطفًا غير يسار

# عند التحرك على طول الخط المكسور الذي تشكله هذه

# نقاط ، الحركة تتم مباشرة أو على اليمين

دو بوب (صغير)

دفع (باي ، ق)

عائدات

وقت تشغيل إجراء Graham هو O (NlnN) ، حيث N = الطول (Q). ما مدى سهولة إظهار أن حلقة while ستستغرق وقتًا O (N) ، وأن فرز الزوايا القطبية سيستغرق وقت O (NlnN) ، ومن هنا جاءت المقاربات العامة لإجراء Graham ، ومن ثم T 12 (n) = O (NlnN) ).

خاصية إعادة البناء المميزة للتثليث الذي يلبي شرط Delaunay ، كما هو موضح في ، لها اعتماد خطي O (N) ، وبالتالي T 13 (n) = O (N).

إذا استبدلنا جميع خصائص الوقت الموجودة في التعبير (3) ، فسيبدو الاعتماد الزمني الناتج كما يلي:

T (n) = c 1 + c 2 + O (N) + O (N) + O (N) + O (N) + O (N) + O (N) + O (N) + O (NlnN ) + O (N) + O (NlnN) + O (N)

T (ن) = O (NlnN)

يؤكد التحليل النظري للخصائص الزمنية لخوارزمية Delaunay التثليث المعدلة الكفاءة والأداء العالي للخوارزمية المقترحة.

الموجودات

نتيجة لتحليل مقارن لخوارزميات Delaunay المثلثية المطلوبة عمليًا ، يتضح أن الطرق المدروسة لا تفي بمتطلبات البناء في الوقت الفعلي للكائنات الديناميكية ثلاثية الأبعاد بدرجة محددة مسبقًا من التفاصيل ، وبالتالي ، هناك حاجة عملية لتعديلها. تم اقتراح تعديل خوارزمية Delaunay لتثليث المروحة ذات المسارين ، وتتمثل الميزة الوظيفية لها في حساب قيم مركز الكتلة لمصفوفة إحداثيات نقاط التثليث عن طريق تقسيم مجموعة النقاط إلى مجموعات فرعية على طول المحوران X و Y: تم إجراء تحليل للخصائص الزمنية لخوارزمية Delaunay المعدلة للتثليث. تتيح هذه الحسابات إمكانية تحسين الأداء بشكل كبير على مجموعة كبيرة من النقاط عند تحديد إحداثيات مركز نقطة الكتلة وتجنب تدفق البيانات ، وبالتالي حدوث أخطاء في تنفيذ البرامج.

1. كنوت دي. فن البرمجة. المجلد 1. الخوارزميات الأساسية. - م: ويليامز ، 2008. - 680 ص.
2. كنوت دي. فن البرمجة. المجلد 3. الفرز والبحث. - م: ويليامز ، 2008. - 800 صفحة.
3. ماندلبروت ب. الهندسة الكسورية للطبيعة. - م: معهد بحوث الحاسب 2002. - 656 ص.
4. Skvortsov A. V. Delaunay التثليث وتطبيقه. - تومسك: دار النشر بجامعة تومسك ، 2002. - 128 ص.
5. سكفورتسوف أ. بناء تثليث ديلوناي في الزمن الخطي. - تومسك: دار النشر بجامعة تومسك ، 1999. - ص 120-126.
6. سكفورتسوف إيه في ، ميرزا ​​إن إس. خوارزميات لبناء وتحليل التثليث. - تومسك: دار النشر بجامعة تومسك ، 2006. - 168 ص.
7. توماس إتش كورمين ، تشارلز آي ليسيرون ، رونالد إل ريفيست ، كليفورد شتاين. الخوارزميات: البناء والتحليل ، الطبعة الثالثة: لكل. من الانجليزية. - م: ويليامز ، 2013. - 1328 ص.
8. Shaydurov V.V. طرق العناصر المحدودة المتعددة الشبكات. - م: نوكا ، 1989. - 288 ص.
9. ستورجس هـ. (1926). اختيار فاصل الفصل. جيه عامر. دولة. مساعد ، 21 ، 65-66.

الكلمات الدالة:الواقع الافتراضي ، التثليث على مجموعة معينة من النقاط ، تثليث ديلوناي ، بناء كائنات ديناميكية ثلاثية الأبعاد.

خوارزمية Delaunay التثليث المعدلة

Teplov A.A.، بكالوريوس ، MSTU Bauman ، قسم "البرمجيات وتكنولوجيا المعلومات" ، موسكو ، [بريد إلكتروني محمي]

مايكوف ك.، دكتور في العلوم التقنية ، أستاذ ، MSTU Bauman ، قسم "البرمجيات وتكنولوجيا المعلومات" ، موسكو ، [بريد إلكتروني محمي]

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

الكلمات الدالة:الواقع الافتراضي ، التثليث على مجموعة خلايا معينة ، تثليث Delaunay ، بناء كائنات ديناميكية ثلاثية الأبعاد.

في تواصل مع

بشكل عام ، تستند جميع الخوارزميات إلى فكرة بسيطة جدًا تتمثل في إضافة نقاط بالتسلسل إلى تثليث Delaunay الذي تم إنشاؤه جزئيًا. رسميا ، يبدو مثل هذا.

إعطاء مجموعة من النقاط N.

1. في نقاط البداية الثلاث الأولى ، نبني مثلثًا واحدًا.

2. في دورة n لجميع النقاط الأخرى ، نفذ الخطوات 3-5.

3. تضاف النقطة رقم n التالية إلى هيكل التثليث الذي تم إنشاؤه بالفعل على النحو التالي. أولاً ، النقطة مترجمة ، أي يوجد مثلث (تم إنشاؤه سابقًا) ، حيث تقع النقطة التالية. أو ، إذا لم تقع النقطة داخل المثلث ، يوجد مثلث على حدود المثلث الأقرب إلى النقطة التالية.

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

5. يتم إجراء الفحوصات المحلية للمثلثات التي تم الحصول عليها حديثًا للتأكد من مطابقتها لشرط Delaunay وإجراء عمليات إعادة الترتيب اللازمة.

نهاية الخوارزمية.

فيما يلي وصف مفصل للعديد من الخوارزميات.

خوارزمية الجشع

اقترح أحد أول الخوارزمية التالية لبناء التثليث.

طريقة الجشعهذه طريقة لا تبطل أبدًا ما تم القيام به من قبل. يتم تنفيذ الخطوات التالية بالتسلسل في الخوارزمية.

1. يتم وضع نهايات جميع الأجزاء الهيكلية في مجموعة النقاط الأولية.

2. يتم إنشاء المقاطع التي تربط جميع أزواج النقاط ، ويتم فرز الأجزاء حسب الطول.

3. يتم إدخال جميع مقاطع الكسر في التثليث.

4. يتم تحديد المقاطع بالتسلسل للتثليث من مجموعة من المقاطع مرتبة حسب الطول (من الأقصر إلى الأطول). إذا تقاطع المقطع مع أي من الأجزاء المدرجة بالفعل ، فسيتم إهماله ، وإلا يتم إدخاله في التثليث.

تتكرر الخطوة 4 حتى تنفد المقاطع.

لاحظ أنه إذا كانت جميع المقاطع الممكنة لها أطوال مختلفة ، فإن نتيجة هذه الخوارزمية لا لبس فيها ، وإلا فإنها تعتمد على ترتيب إدخال المقاطع من نفس الطول.

يسمى التثليث بالجشع إذا تم إنشاؤه بواسطة خوارزمية جشعة.

خوارزمية "الحذف والإنشاء"

لا يقوم "حذف" و "إنشاء" بأية عمليات إعادة بناء. بدلاً من ذلك ، مع كل إدخال لعقدة جديدة (أ) ، يتم حذف جميع المثلثات على الفور ، حيث تقع عقدة جديدة (ب) داخل الدوائر الموصوفة. في هذه الحالة ، تشكل جميع المثلثات البعيدة بشكل ضمني مضلعًا معينًا. بعد ذلك ، بدلاً من المثلثات المحذوفة ، يتم إنشاء مثلث ملء عن طريق توصيل عقدة جديدة بهذا المضلع (الشكل ج).

أرز. 4. خوارزمية "الحذف والإنشاء"

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

خوارزمية "البناء بالتقسيم"

تعد خوارزمية إدخال المقاطع الهيكلية "البناء بالتكسير" أبسط خوارزمية في التنفيذ ومستقرة في التشغيل.

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

أرز. 5. خوارزمية "البناء بالتقسيم"

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

تظهر ميزة أخرى لخوارزمية الإدراج هذه مقارنة بالخوارزميات اللاحقة عند محاولة إدخال مقطع هيكلي في التثليث حيث توجد حواف ثابتة بين الحواف التي تتقاطع معها. يتم تقسيم هذه الحواف ، مثل جميع الحواف الأخرى ، إلى قسمين.

خوارزمية مع فهرسة مراكز المثلث ك د - شجرة

في خوارزمية التثليث مع فهرسة شجرة k-D لمراكز المثلث ، يتم وضع مراكز المثلث فقط في شجرة k-D (لـ k = 2). عند حذف المثلثات القديمة ، من الضروري إزالة مراكزها من شجرة k-D ، وعند إنشاء مثلثات جديدة ، يجب إدخالها.

للبحث عن مثلث يحتوي على النقطة الحالية المدرجة في التثليث ، من الضروري تنفيذ استعلام نقطة غير قياسي إلى شجرة k-D. يجب أن يبدأ البحث في الشجرة من الجذر وينزل إلى الأوراق. إذا كانت أحفاد العقدة الحالية لشجرة k-D (المستطيل الذي يحيط المتحدرين) لا تغطي النقطة الحالية ، فمن الضروري اختيار السليل الأقرب إلى نقطة البحث لمزيد من الانحدار على طول الشجرة.

نتيجة لذلك ، سيتم العثور على بعض المثلث ، سيكون مركزه قريبًا من النقطة المحددة. إذا لم تقع النقطة المحددة في المثلث الذي تم العثور عليه ، فمن الضروري استخدام خوارزمية بحث المثلث المعتادة من خوارزمية تكرارية بسيطة لإنشاء مثلث Delaunay.

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

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

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

دعونا نتناول بعض طرق التثليث. بالنسبة للأسطح المستوية ، توجد طرق اقتصادية للتثليث يتم من خلالها بناء المثلثات عند النقاط الحدودية للسطح وليس من الضروري البحث عن نقاط داخل المنطقة البارامترية.

تثليث ديلوناي.

ضع في اعتبارك بعض المساحة على الطائرة. ستسمى المنطقة محدبة إذا كان على المرء ، عند التحرك على طول حدودها ، أن يدور في اتجاه واحد فقط (فقط إلى اليسار أو إلى اليمين فقط). يمكنك استخدام خوارزمية Delaunay لتثليث المناطق المحدبة المستوية. لن نتمكن من تطبيق هذه الخوارزمية مباشرة لتثليث الأسطح ذات الشكل الحر ، لكننا سنستخدم طريقتها في إنشاء مثلثات.

أرز. 9.7.1. منطقة محدبة بنقاط معينة بالداخل

دع بعض المنطقة المحدبة ثنائية الأبعاد محدودة بخط مكسور مغلق ومجموعة من النقاط داخل هذه المنطقة (الشكل 9.7.1).

مطلوب تقسيم المنطقة المحددة إلى مثلثات ، تكون رؤوسها هي النقاط المعطاة داخل المنطقة ورؤوس الخطوط المتعددة التي تحيط بها. يجب ألا تتداخل المثلثات ، ولا يمكن أن تتقاطع جوانبها إلا عند الرؤوس.

يمكنك بناء عدة مجموعات مختلفة من المثلثات التي تملأ المنطقة المحددة. في جميع الحالات ، يكون عدد المثلثات ، حيث K هو عدد رؤوس الخط المتعدد المحيط ، وأنا هو عدد النقاط المعطاة داخل المنطقة.

أرز. 9.7.2. اختيار النقطة الثالثة لخوارزمية Delaunay

سيكون مثلث المجال مثلث Delaunay إذا لم تكن هناك رؤوس مثلثات أخرى داخل الدائرة المُحددة حول كل مثلث. يبني تثليث ديلوناي مثلثات أقرب ما يكون إلى متساوي الزوايا (لا يسمح ببناء مثلثات مطولة بشكل غير معقول).

يمكنك تسميتها متوازنة. سيكون تثليث Delaunay فريدًا إذا لم تكن هناك أربعة رؤوس على نفس الدائرة.

تأمل في تثليث ديلوناي. رؤوس الخطوط المتعددة التي تحيط بالمنطقة والنقاط المعطاة داخل المنطقة ستسمى رؤوس التثليث. تسمى جوانب المثلثات بالحواف. من بين الحواف ، نختار مقاطع الخط المتعدد المحيط ، والذي سنسميه حواف الحدود. دعونا نوجه كل حواف الحدود بحيث تقع المنطقة المحدبة على يسار كل حافة. دع الأمر يتطلب إنشاء مثلث يكون جانبه هو الحافة الحدودية AB الموضحة في الشكل. 9.7.2.

يمكن رسم دائرة من خلال الرؤوس A و B وأي رأس لا يقع على نفس الخط معهم. بصفتنا الرأس الثالث للمثلث ، نختار الرأس V ، المقابل الذي لا تحتوي الدائرة له على رؤوس أخرى على نفس الجانب بالنسبة للمقطع AB ، حيث تقع النقطة V. في الحالة العامة ، رأس واحد من هذا القبيل يمكن العثور عليها لحافة الحدود. دعنا نسميها أقرب واحد. يقع مركز الدائرة التي تمر عبر النقاط A و B و V عند تقاطع الخطوط العمودية لنقاط المنتصف للمقاطع AB و BV و VA. سيتم تمييز موضع مركز الدائرة بواسطة المعلمة t للمقطع MN المتعامد مع الحافة AB ، مساويًا له في الطول ويمر عبر منتصف الحافة AB.

أرز. 9.7.3. عملية تثليث ديلوناي

لكل الرؤوس الموجودة على يسار المقطع AB ، فإن أقرب رأس له المعلمة t هي الأصغر. لا تحتوي الدائرة المقابلة لأقرب رأس على رءوس أخرى على يسار المقطع AB. دع الرؤوس A و B و V توصف بواسطة متجهات نصف قطر ثنائية الأبعاد ، على التوالي. ستكون متجهات نصف القطر لنقاط المنتصف للقطاعات AB و BV متساوية

قيمة المعلمة t للخط المستقيم ، المقابلة لموضع عليها مركز الدائرة التي تمر عبر النقاط A و B و V ، تساوي

بالنسبة للرأس الأقرب إلى يسار المقطع AB ، يكون للمعلمة t قيمة دنيا.

قم بتوجيه كل حواف الحدود بحيث تكون المنطقة المراد مثلثها على يسار كل منها. نبدأ في بناء مثلثات من أي حافة حدية. ابحث عنه أقرب رأس لا تحتوي دائرته المقابلة على رءوس أخرى. دعنا نوجد أقرب رأس V لحافة الحدود AB ، ثم نبني المثلث ABV ونحول الحافة AB إلى فئة غير نشطة. سوف نسمي الحواف والرؤوس غير النشطة التي لا تشارك في خوارزمية التثليث. إذا لم يكن هناك حافة BV بين حواف الحدود ، فإننا نبني حافة حدية جديدة على المقطع VB. إذا كان هناك حافة BV بين حواف الحدود ، فإننا ننقلها والرأس B إلى فئة غير نشطة. إذا لم تكن هناك حافة VA بين حواف الحدود ، فإننا نبني حافة حدية جديدة على المقطع AV. إذا كانت هناك حافة VA بين حواف الحدود ، فسننقلها والرأس A إلى فئة الحواف غير النشطة. تظهر عملية التثليث في الشكل. 9.7.3.

أرز. 9.7.4. تثليث ديلوناي

ينتهي التثليث عندما تصبح جميع الرؤوس والحواف غير نشطة. تظهر نتيجة تثليث المنطقة المعينة في الشكل. 9.7.4.

التثليث بطريقة التصحيح.

لنفكر في تثليث بعض الأسطح بنطاق مستطيل لتعريف المعلمة ، دعونا نقسم مجال تعريف معلمات السطح إلى خلايا مستطيلة بخطوط ثنائية الأبعاد ، هذه الخطوط تشكل شبكة مستطيلة. نأخذ المسافات البارامترية بين الخطوط المتجاورة وفقًا للصيغة (9.4.7) التي تساوي

نأخذ المسافات البارامترية بين الخطوط المتجاورة وفقًا للصيغة (9.4.8) التي تساوي

من خلال إنشاء أقطار في جميع الخلايا المستطيلة ، نحصل على مثلث للسطح (نحصل على مجموعة من المثلثات التي تفي بالمتطلبات). على التين. يوضح 9.7.5 تثليث سطح الثورة بالطريقة الموصوفة.

ضع في اعتبارك تثليث السطح بحد تعسفي. نحن نبني طريقة التثليث على التصحيح من خلال خطوط الحدود لتثليث السطح الموصوف أعلاه بمجال مستطيل لتعريف المعلمة.

أرز. 9.7.5. تثليث السطح مع مجال معلمة مستطيل

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

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

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

أرز. 9.7.6. تثليث السطح غير المكتمل

داخل كل خلية من المجموعة الأولى ، باستخدام القطر ، سنقوم ببناء مثلثين. وهكذا ، نحصل على تثليث غير مكتمل. يظهر في الشكل مثال على بناء مثلثات في خلايا المجموعة الأولى لسطح ثورة تحده ملامح. 9.7.6.

على الجوانب غير المتقاطعة لخلايا المجموعة الثانية ، نقوم ببناء حواف حدية وتوجيهها بحيث تكون الخلية المقابلة على يسار الحافة. نقوم ببناء خط متعدد مغلق حول خلايا المجموعة الأولى (من الممكن وجود عدة خطوط مغلقة) بحيث عند التحرك على طولها ، يقع الجزء غير المقسم إلى مثلثات على اليسار ، إذا نظرت نحو السطح الطبيعي. سيتم أيضًا استخدام المقاطع المستقيمة من هذا متعدد الخطوط كحواف حدية. سوف نعتبر جميع الأطراف متساوية في الحقوق. لإكمال عملية التثليث ، نحتاج إلى إنشاء مثلثات بين حواف الحدود. لكل حافة ، سنبحث عن رأس يقع على يساره ويمكن استخدامه لبناء مثلث. سنبحث عن رأس فقط بين تلك القمم التي تقع في نفس الخلية ذات الحافة. لتحديد قمة الرأس ، نستخدم طريقة Delaunay الموضحة أعلاه والموضحة في الشكل. 9.7.2. إذا تم العثور على مثل هذا الرأس ، فيجب على المرء أن يتحقق مما إذا كانت حافتان جديدتان للمثلث تتقاطعان مع أي حافة حدية. دع أقرب رأس V يمكن العثور عليه للحافة الحدودية AB ويجب التحقق من أن المقطعين BV و VA لا يتقاطعان مع حواف الحدود الأخرى. ثم نبني مثلث ABV وننقل الحافة AB إلى فئة غير النشطة. إذا لم يكن هناك حافة BV بين حواف الحدود ، فسننشئ حافة حدية جديدة على المقطع VВ ، ولكن إذا كان هناك حافة حدودية BV بين حواف الحدود ، فسننقلها والرأس B إلى فئة غير نشطة . إذا لم تكن هناك حافة VA بين حواف الحدود ، فعندئذٍ على المقطع AV نقوم ببناء حافة حدية جديدة ، ولكن إذا كانت هناك حافة VA بين حواف الحدود ، فإننا ننقلها والرأس A إلى فئة غير نشطة.

إذا تقاطع المقطع أو VA مع حواف حدية أخرى ، فإننا ننتقل إلى إيجاد أقرب رأس لحافة حد أخرى. سيتم الانتهاء من التثليث بعد نقل جميع الحواف والرؤوس إلى فئة غير نشطة.

أرز. 9.7.7. التثليث بطريقة التصحيح

على التين. يوضح 9.7.7 تثليث السطح من خلال طريقة تصحيح المثلثات في الخلايا التي تتقاطع مع خطوط الحدود. على التين. 9.7.8 بمساعدة التثليث الناتج ، يتم عرض السطح نفسه.

إذا كان لمضلعات الحدود والسطح بعض التناظر ، فسيكون لتثليث التصحيح تماثل مماثل.

التثليث بطريقة الامتصاص.

فكر في طريقة أخرى للتثليث. من حيث السرعة ، فهي أدنى من تثليث Delaunay وتعديلاته. لبدء إجراء التثليث ، من الضروري تمثيل حدود السطح في شكل مضلعات مغلقة. في عملية التثليث ، سنحتاج إلى تحديد الخطوات على معلمات السطح. مع وجود اتجاه معروف للحركة ، يتم تحديد هذه الخطوات من خلال الصيغ (9.4.6). يمكن العثور على خطوات تقريبية على معلمات السطح على النحو التالي. دعونا نحدد منطقة على مستوى المعلمة حول نقطة معينة بحيث لا يكون أي جزء مكاني من نقطة إلى نقطة في هذه المنطقة أبعد من قيمة معينة S من السطح.

للقيام بذلك ، نحسب الزيادات المسموح بها للمعلمات على طول خطوط الإحداثيات

أين هي معاملات الأشكال التربيعية الأولى والثانية للسطح عند النقطة. نأخذ شكلًا بيضاويًا متمركزًا عند نقطة وشبه محاور لحد المنطقة المرغوبة. هذا القطع الناقص له المعادلة

إذا كان مطلوبًا العثور على نقطة على المستوى بالقرب من النقطة في الاتجاه المحدد بالزاوية مع المحور ، ثم تكون معلماتها

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

أوجد الرأس في مضلع العمل الذي يدور عنده داخل المنطقة. مثل هذه النقطة موجودة دائمًا وزاوية الدوران فيها أقل من. دعونا نحدد هذه النقطة من خلال O ، ومعلماتها - من خلال هذه النقطة ، سنقوم ببناء واحد أو اثنين من المثلثات ، اعتمادًا على زاوية الدوران. إذا كانت الزاوية أقل ، فسنقوم ببناء مثلث واحد على هذه النقاط الثلاث (الشكل 9.7.9). بخلاف ذلك ، نقوم ببناء مثلثين على النقطة المعطاة ، نقطتان متجاورتان وواحدة جديدة (الشكل 9.7.11). يتم الإشارة إلى النقطة الجديدة بالرمز P. سنبحث عن النقطة P على قطر متوازي الأضلاع B OS P. إذا كان رأس متوازي الأضلاع يقع داخل القطع الناقص (الشكل 9.7.10) ، فسنأخذها على أنها النقطة P. وإلا ، فسنأخذ تقاطع القطع الناقص وقطر متوازي الأضلاع على أنه النقطة P. في الحالة الأخيرة ، ليس من الضروري على الإطلاق البحث عن تقاطع القطع الناقص.

يتم تحديد إحداثيات النقطة P من خلال إحداثيات النقاط O VS

يتم تحديد زاوية المقطع OR مع الأفقي من خلال المساواة

(9.7.8)

تتيح هذه البيانات تحديد موضع النقطة P بالنسبة إلى القطع الناقص (9.7.5).

في الحالة الموضحة في الشكل. 9.7.9 أنشئ مثلثًا (تذكر أرقام رؤوسه) واحذف النقطة O في مضلع العمل ، في الحالة الموضحة في الشكل. 9.7.11 ، قم ببناء مثلثين واستبدال النقطة O في مضلع العمل بالنقطة P ووضع الأخير في مجموعة النقاط الناتجة. على التين. يوضح الشكل 9.7.12 المضلع الذي تم الحصول عليه بعد إنشاء مثلثين وإزالة النقطة O. في كلتا الحالتين ، ستتم إزالة النقطة O من مضلع العمل وسيضيق مضلع العمل. لاحظ أنه لا يمكن بناء المثلثات إلا عندما لا يتقاطع المضلع العامل مع نفسه بعد التضييق.

أرز. 9.7.9. بناء مثلث

أرز. 9.7.10. المضلع الناتج

أرز. 9.7.11 بناء مثلثين

أرز. 9.7.12. المضلع الناتج

تظهر مثل هذه المواقف في الشكل. 9.7.13. يمكن أن تحدث عندما تتقاطع جوانب المثلثات المنشأة مع جوانب المضلع العامل غير المجاور لها. قبل إنشاء مثلث جديد كما في الحالة الموضحة في الشكل. 9.7.9 ، وفي الحالة الموضحة في الشكل. 9.7.11 ، يجب إجراء فحص لغياب التقاطع الذاتي للمضلع الناتج.

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

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

أرز. 9.7.13. المثلثات غير مسموح بها في هذه الزاوية.

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

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

نقوم ببناء المثلثات بنفس الطريقة كما في حالة المنطقة المتصلة ببساطة. لنجد النقطة O في المضلع العامل ، ونتحقق من إمكانية تضييق المضلع العامل فيه ، وتضييق المضلع. إذا كانت هناك حدود داخلية ، يصبح من الصعب التحقق من إمكانية تضييق مضلع العمل عند النقطة المحددة. بالإضافة إلى عمليات التحقق الموصوفة لتقاطع جوانب المثلثات مع جوانب مضلع العمل ، تحتاج إلى التحقق من تقاطع جوانب المثلثات مع جوانب جميع المضلعات الداخلية.

دعونا نتحقق من إمكانية تكوين مثلثين عند النقطة O (الشكل 9.7.11) ، ونجد أن النقطة الجديدة P ، التي يتم بناؤها ، ستقع داخل أحد المضلعات الداخلية أو ستكون قريبة بشكل غير مقبول من أجزائها . في هذه الحالة ، لن نبني النقطة P ، ولكن بدلاً من ذلك نقوم بتضمين هذا المضلع الداخلي في المضلع العامل من خلال بناء مثلثين ، كما هو موضح في الشكل. 9.7.14.

لتضمين نقاط أحد المضلعات الداخلية في مضلع العمل ، نجد من بين نقاط المضلع الداخلي أقرب نقطة إلى النقطة C (المجاورة للنقطة O) في المضلع العامل.

دعونا نبني مثلثات على النقطتين OCF و CEF وبين النقطتين O و C لمضلع العمل ، سنقوم بإدخال نقاط المضلع الداخلي ، بدءًا من النقطة F وتنتهي بالنقطة E. وبالتالي ، سنكسر مضلع العمل على نظام تشغيل المقطع ، قم بكسر المضلع الداخلي على المقطع EF وقم بتوحيدهم مع مقاطع OF و EU.

أرز. 9.7.14. بناء مثلثين

أرز. 9.7.15. دمج المضلعين الخارجي والداخلي

تظهر نتيجة الاندماج في الشكل. 9.7.15. بالطبع ، قبل دمج المضلعين الخارجي والداخلي ، يجب إجراء فحوصات للتأكد من صحة هذه العملية.

علاوة على ذلك ، سنستمر في تضييق مضلع العمل بالطريقة الموصوفة حتى نجد أنفسنا على مقربة شديدة من مضلع داخلي آخر وندرجه في مضلع العمل. نتيجة لذلك ، سيتم تضمين جميع المضلعات الداخلية في مضلع العمل ، والذي يجب تضييقه حتى آخر ثلاث نقاط. نتيجة لذلك ، سيتم تغطية المجال المتصل المتضاعف بأكمله لمعلمات السطح بمثلثات.

أرز. 9.7.16. المثلثات غير مسموح بها في هذه الزاوية.

هناك حالات يكون فيها من المستحيل بناء مثلث واحد على المضلعات المحددة. على التين. يوضح الشكل 9.7.16 مساحة يحدها مضلعان ، يتكون كل منهما من أربعة أجزاء. بالنسبة للمضلع الخارجي ، لا يمكننا الاستمرار في التثليث لأن المضلع الداخلي يتدخل. في هذه الحالة ، نجد النقطتين المتجاورتين B و C للمضلع ، ويمكننا بناء مثلث VSR لهما. يتم إسقاط النقطة P على منتصف الضلع BC وتقع على مسافة منه بحيث لا يتقاطع المثلث الجديد مع المضلعات.

طرق التثليث الأخرى.

هناك طرق أخرى للتثليث. على سبيل المثال ، بعد إنشاء المضلعات للخطوط الخارجية والداخلية لمنطقة تحديد السطح ، يمكن اختيار إستراتيجية مختلفة لإنشاء مثلثات. بدلاً من ذلك ، يمكنك دمج المضلعين الخارجي والداخلي في مضلع واحد قبل بدء عملية التثليث. من الممكن "رسم" نقاط داخل منطقة تعريف المعلمة وفقًا لخوارزمية معينة وإجراء تثليث Delaunay باستخدامها ونقاط مضلعات كفاف الحدود. هناك خوارزميات تقوم ببناء مثلثات كبيرة أولاً ، ثم تقسمها إلى أحجام مقبولة.

تثليث الجسم.

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

أرز. 9.7.17. تناسق المضلعات الحدودية لوجوه الجسم

ستكون أقسام المضلعات للوجوه المجاورة التي تمر على طول الحواف المشتركة متسقة إذا كانت نقاطها تتطابق في الفضاء.

تطبيق التثليث.

يتم استخدام المثلثات التي تم إنشاؤها نتيجة للتثليث للحصول على صور نغمة. على التين. يوضح الشكلان 9.7.18 و 9.7.19 مثلثات لوجه جسم ورقة ، تظهر صورة النغمة في الشكل. 6.5.1.

أرز. 9.7.18. تثليث وجه الجسم بطريقة التصحيح

يمكن استخدام تقسيم مجال تعريف معلمات السطح إلى مثلثات في التكاملات (8.6.2) ، (8.6.3) ، (8.6.12) ، (8.7.17) - (8.7.22) عند حساب الخصائص الهندسية لـ جثث. للتكامل العددي ، يجب حساب الخطوة البارامترية للمنحنيات باستخدام الصيغة (8.11.5) ، وبالنسبة للأسطح ، يجب حساب الخطوة البارامترية باستخدام الصيغ (8.11.1) و (8.11.2).

التثليث لمجموعة محدودة من النقاط S هي مشكلة تثليث الهيكل المحدب CH (S) الذي يحيط بجميع نقاط المجموعة S. لا يمكن أن تتقاطع مقاطع الخط أثناء التثليث - يمكن أن تلتقي فقط عند النقاط المشتركة التي تنتمي إلى المجموعة S. منذ الخط المقاطع تغلق المثلثات ، سنعتبرها حوافًا. على التين. يوضح الشكل 1 نوعين مختلفين من التثليث لنفس مجموعة النقاط (سنتجاهل مؤقتًا الدوائر المرسومة في هذه الأشكال).

أرز. واحد

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

أي مجموعة من النقاط ، باستثناء بعض الحالات التافهة ، تسمح بأكثر من طريقة للتثليث. لكن في الوقت نفسه ، هناك خاصية رائعة: أي طريقة للتثليث لمجموعة معينة تحدد نفس عدد المثلثات ، الذي يتبع النظرية:

نظرية حول التثليث لمجموعة من النقاط.افترض أن مجموعة النقاط S تحتوي على ن> 3 نقاط وليست كلها على خط واحد. بالإضافة إلى ذلك ، فإن نقاط i منها داخلية (أي الكذب داخل الهيكل المحدب CH (S). وبعد ذلك ، مع أي طريقة لتثليث المجموعة S ، سيتم الحصول على مثلثات n + i - 2 بالضبط.

لإثبات النظرية ، نأخذ في الاعتبار أولاً تثليث نقاط الحدود n-i. نظرًا لأنهم جميعًا رؤوس لمضلع محدب ، فإن مثل هذا التثليث سينتج عنه (n - i) - 2 مثلثات. (هذا ليس من الصعب التحقق منه ، وعلاوة على ذلك ، يمكن إثبات أن أي تثليث اعتباطيامضلع م - محدب أو غير محدب - يحتوي على م - 2 مثلثات). الآن دعنا نتحقق مما سيحدث للتثليث عند إضافة النقاط الداخلية المتبقية ، نقطة في كل مرة. ندعي أن إضافة كل نقطة تؤدي إلى زيادة عدد المثلثات بمقدار اثنين. عند إضافة نقطة داخلية ، يمكن أن تنشأ حالتان ، كما هو موضح في الشكل. 2. أولاً ، قد تكون النقطة داخل مثلث ما ، ثم يتم استبدال هذا المثلث بثلاثة مثلثات جديدة. ثانيًا ، إذا تزامنت النقطة مع أحد حواف المثلث ، فسيتم استبدال كل من المثلثين المجاورين لهذه الحافة بمثلثين جديدين. ويترتب على ذلك أنه بعد إضافة جميع نقاط r ، سيكون إجمالي عدد المثلثات (n - i - 2) + (2i) ، أو n + i - 2 فقط.

أرز. 2

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

أرز. 3

لتشكيل مثلث Delaunay ، نحتاج إلى عدة تعريفات جديدة. تعتبر مجموعة النقاط دائرية إذا كانت هناك دائرة تقع عليها جميع نقاط المجموعة. سيتم تحديد هذه الدائرة لمجموعة معينة من النقاط. الدائرة المقيدة للمثلث تمر عبر الرؤوس الثلاثة (غير الخطية). يُقال أن الدائرة خالية من النقاط فيما يتعلق بمجموعة معينة من النقاط S إذا لم تكن هناك نقاط من المجموعة S داخل الدائرة. ومع ذلك ، يمكن وضع نقاط من المجموعة S على الدائرة الأكثر خلوًا من النقاط.

سيكون التثليث لمجموعة من النقاط S بمثابة مثلث Delaunay إذا كانت الدائرة المحصورة لكل مثلث خالية من النقاط. في مخطط التثليث في الشكل. يوضح الشكل 1 أ دائرتين لا تحتويان بوضوح على نقاط أخرى بداخلهما (يمكنك رسم دوائر لمثلثات أخرى للتأكد من خلوها أيضًا من النقاط في المجموعة). لم يتم ملاحظة هذه القاعدة في الرسم البياني للتين. 16 - نقطة واحدة من مثلث آخر دخلت داخل الدائرة المرسومة ، لذلك ، هذا التحريض لا ينتمي إلى نوع Delaunay.

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

تعمل الخوارزمية الخاصة بنا من خلال بناء المثلث الحالي باستمرار بمثلث واحد في كل مرة. في البداية ، يتكون التثليث الحالي من حافة واحدة من الغلاف ، بعد الانتهاء من الخوارزمية ، يصبح التثليث الحالي مثلثًا Delaunay. في كل تكرار ، تبحث الخوارزمية عن مثلث جديد يتصل به حدودالتثليث الحالي.

يعتمد تعريف الحدود على مخطط Delaunay لتصنيف حافة المثلث التالي بالنسبة للتثليث الحالي. يمكن أن تكون كل حافة نائم, على قيد الحياةأو في ذمة الله تعالى:

• ضلوع كامنة: حافة Delaunay المثلثية نائمة إذا لم يتم اكتشافها بواسطة الخوارزمية ؛
• الضلوع الحية: تكون الحافة على قيد الحياة إذا وجدت ، ولكن لا يُعرف سوى منطقة واحدة مجاورة لها ؛
• ضلوع ميتة: تعتبر الحافة ميتة إذا وجدت ومعروفة كلتا المنطقتين المتجاورتين.

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

في كل تكرار ، يتم تحديد أي حافة من الحدود وتخضع للمعالجة ، والتي تتمثل في العثور على منطقة غير معروفة تنتمي إليها الحافة e. إذا تبين أن هذه المنطقة عبارة عن مثلث f محدد بنقاط نهاية الحافة e وبعض الرأس الثالث v ، ثم تصبح الحافة e ميتة ، لأن كلا المنطقتين المتجاورتين معروفتان الآن. يتم نقل كل من حافتي المثلث الأخريين إلى الحالة التالية: من النوم إلى الحياة أو من الحي إلى الميت. هنا سيتم استدعاء الرأس v المترافقةمع الحافة هـ. وإلا ، إذا تبين أن المنطقة غير المعروفة مستوية لانهائية ، فإن الحافة e تموت ببساطة. في هذه الحالة ، لا تحتوي الحافة e على رأس مقترن.

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

يتم تنفيذ الخوارزمية في برنامج delaunayTriangulate. يُعطى البرنامج مصفوفة من n من النقاط ويعيد قائمة بالمثلثات التي تمثل مثلث Delaunay. يستخدم التطبيق فئة قائمة الحلقة والفئات من قسم هياكل البيانات الهندسية. يمكن استخدام أي قاموس يدعم العمليات المطلوبة كفئة القاموس. على سبيل المثال ، يمكنك تجاوز #define Dictionary RandomizedSearchTree.

قائمة * (Point s، int n) (Point p؛ List.) * مثلثات = قائمة جديدة ؛ قاموس الحدود (edgeCmp) ؛ Edge * e = hullEdge (s ، n) ؛ إدراج حدودي (هـ) ؛ while (! frontier.isEmpty ()) (e = frontier.removeMin () ؛ if (mate (* e، s، n، p)) (updateFrontier (Frontier، p، e-> org) ؛ updateFrontier (فرونتير ، e -> dest ، p) ؛ مثلثات-> إدراج (مثلث (e-> org ، e-> dest ، p)) ؛) حذف e ؛) عودة مثلثات ؛ )

أرز. 4

تتم كتابة المثلثات التي تشكل المثلث في قائمة المثلثات. يتم تمثيل الحدود من خلال قاموس الحواف الحية الحدودية. يتم توجيه كل حافة بحيث تقع منطقتها غير المعروفة (يتم تحديدها) على يمين الحافة. تستخدم وظيفة المقارنة edgeCmp للبحث عن قاموس. يقارن نقطتي البداية للحافتين ، إذا كانتا متساويتين ، تتم مقارنة نقاط النهاية الخاصة بهما:

Int edgeCmp (Edge * a، Edge * b) (if (a-> org< b->org) إرجاع 1 ؛ إذا (a-> org> b-> org) تُرجع 1 ؛ إذا (a-> dest< b->dest) عودة -1 ؛ إذا (a-> dest> b-> dest) قم بإرجاع 1 ؛ العودة 0 ؛ )

إذن كيف تتغير الحدود من خطوة إلى أخرى ، وكيف تغير وظيفة updateFrontier قاموس حافة الحدود لتعكس هذه التغييرات؟ عندما يتم ربط مثلث جديد t بالحد ، تتغير حالات الأضلاع الثلاثة للمثلث. تصبح حافة المثلث t ، المجاورة للحدود ، ميتة لكونها على قيد الحياة. يمكن أن تتجاهل وظيفة updateFrontier هذه الحافة ، حيث يجب إزالتها بالفعل من القاموس عند استدعاء وظيفة removeMin. كل جانب من حافتي المثلث المتبقيين يغيران حالتهما من النوم إلى الحياة إذا لم يتم كتابتهما بالفعل في القاموس ، أو من حي إلى ميت إذا كانت الحافة موجودة بالفعل في القاموس. على التين. 5 يظهر كلتا الحالتين. وفقًا للشكل ، نعالج الحافة الحية af ، وبعد أن وجدنا أن النقطة b مترافقة معها ، نضيف المثلث afb إلى المثلث الحالي. ثم نبحث عن الحافة fb في القاموس ، وبما أنها ليست موجودة بعد ويتم اكتشافها لأول مرة ، تتغير حالتها من حالة النوم إلى الحياة. لتحرير القاموس ، سنقوم بتدوير الحافة fb بحيث تقع المنطقة المجهولة المجاورة لها على يمينها ونكتب هذه الحافة إلى القاموس. ثم سنجد حافة ba في القاموس - نظرًا لوجودها فيه ، فهي على قيد الحياة بالفعل (المنطقة المعروفة المجاورة لها هي المثلث abc). نظرًا لأن المنطقة غير المعروفة لها ، المثلث afb ، قد تم اكتشافها للتو ، تمت إزالة هذه الحافة من القاموس.

تعمل وظيفة updateFrontier على تحرير القاموس الحدودي ، حيث تتغير حالة الحافة من النقطة أ إلى النقطة ب:

أرز. 5

تحديث باطل فرونتير (قاموس & Frontier، Point & a، Point & b) (Edge * e = new Edge (a، b)؛ if (frontier.find (e)) frontier.remove (e)؛ else (e-> flip ()؛ frontier.insert ( ه) ؛))

تعثر الدالة hullEdge على حافة بدن بين النقاط n من المصفوفة s. تستخدم هذه الوظيفة في الواقع خطوة التهيئة والتكرار الأول لطريقة تغليف الهدايا:

Edge * hullEdge (Point s، int n) (int m = 0؛ for (int i = 1؛ i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

تقوم وظيفة المثلث ببساطة بتشكيل وإرجاع مضلع للنقاط الثلاث التي تم تمريرها كمعلمات إليها:

مضلع * مثلث (النقطة & أ ، النقطة & ب ، النقطة & ج) (مضلع * t = مضلع جديد ؛ t-> insert (a) ؛ t-> insert (b) ؛ t-> insert (c) ؛ إرجاع t ؛)

لتحديد جودة التثليث المبني ، نحدد نوعين من المعايير ، الطوبولوجي والهندسي.

يعتمد المعيار الطوبولوجي على أقرب جيران لنقطة من مجموعة. من الناحية المثالية ، تحتوي النقطة على 6 جيران لمنطقة ثنائية الأبعاد و 12 جيرانًا لمنطقة ثلاثية الأبعاد. نحصل على تقدير طوبولوجي باستخدام الصيغة (1) ، حيث يكون العدد الإجمالي للنقاط في المنطقة ، هو درجة أو عدد النقاط المجاورة المتصلة بنقطة داخلية.

يعتمد المعيار الهندسي على الفرق بين الدوائر المنقوشة والمحدودة حول العنصر المثلث المحسوب. نحصل على تقدير هندسي باستخدام الصيغة (2) ، حيث عدد المثلثات ، هو نصف قطر الدائرة المنقوشة ، هو نصف قطر الدائرة المحاصرة.

خوارزميات لبناء التثليث

هناك عدد كبير من الخوارزميات لبناء التثليث. وهي تختلف عن بعضها البعض من حيث الشاقة ، وتعقيد التنفيذ على الكمبيوتر ، وأساليب البناء. يمكنك معرفة المزيد عن الخوارزميات في كتاب A.V. سكفورتسوفا. لنفكر في بعض الخوارزميات.

واحد من أول من اقترح خوارزمية الجشعبناء التثليث. يسمى تثليث Delaunay بالجشع إذا تم إنشاؤه باستخدام خوارزمية الجشع. تعقيد الخوارزمية الجشعة مع بعض التحسينات فيها. بسبب هذا التعقيد الكبير في الممارسة ، لا يتم استخدامه أبدًا. ضع في اعتبارك الخوارزمية خطوة بخطوة:

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

الخطوة 2بدءًا من الأقصر ، يتم إدخال المقاطع بالتسلسل في التثليث. إذا لم يتقاطع المقطع مع المقاطع الأخرى المدرجة مسبقًا ، فسيتم إدخاله ، وإلا فسيتم التخلص منه.

لاحظ أنه إذا كانت جميع المقاطع الممكنة لها أطوال مختلفة ، فإن نتيجة هذه الخوارزمية لا لبس فيها ، وإلا فإنها تعتمد على ترتيب إدخال المقاطع من نفس الطول.

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

الخطوة 1.في نقاط البداية الثلاث الأولى ، نبني مثلثًا واحدًا.

الخطوة 2في الحلقة لجميع النقاط الأخرى ، نفذ الخطوات من 3-5.

الخطوه 3تضاف النقطة التالية إلى هيكل التثليث الذي تم إنشاؤه بالفعل على النحو التالي. أولاً ، النقطة مترجمة ، أي يوجد مثلث (تم إنشاؤه سابقًا) ، حيث تقع النقطة التالية. أو ، إذا لم تقع النقطة داخل المثلث ، يوجد مثلث على حدود المثلث الأقرب إلى النقطة التالية.

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

الخطوة الخامسةيتم إجراء فحوصات محلية للمثلثات التي تم الحصول عليها حديثًا للامتثال لشرط Delaunay ويتم إجراء الترتيبات اللازمة.

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

خوارزمية السلسلةتعتمد واحدة من أولى خوارزميات بناء التثليث الفعالة على إجراء تنظيم الرسم البياني المستوي والتثليث الأحادي الشكل. تعقيد هذه الخوارزمية ، أين عدد المقاطع الأولية. ضع في اعتبارك الخوارزمية خطوة بخطوة:

الخطوة 1.من مجموعة الأجزاء الهيكلية الأولية ، نقوم بتشكيل رسم بياني مستو متصل (الشكل 4 ، أ).

الخطوة 2الرسم البياني منظم ، أي تتم إضافة حواف جديدة لا تتقاطع مع الآخرين ، بحيث يصبح كل رأس من الرسم البياني مجاورًا لرأس واحد على الأقل فوقه وآخر تحته. يتم التنظيم في تمريرين باستخدام المسح الرأسي المسطح. في التمرير الأول من أسفل إلى أعلى ، نجد بالتسلسل جميع الرؤوس التي لا توجد منها حواف تؤدي إلى الأعلى. على سبيل المثال ، في (الشكل 4 ، ب) هذا هو الرأس ب. برسم خط أفقي ، نجد أقرب حواف من الرسوم البيانية AD و EF تقاطعها على اليسار واليمين. ثم نجد أدنى قمة في الشكل الرباعي DEHG ونرسم حافة من B بداخلها ، وبالمثل ، يتم تنفيذ التمريرة الثانية من أعلى إلى أسفل (الشكل 4 ، ج). نتيجة لهذه الخطوة ، تصبح كل منطقة من الرسم البياني المستوي مضلعًا رتيبًا.

الخطوه 3يجب تقسيم كل منطقة من الرسم البياني إلى مثلثات. للقيام بذلك ، يمكنك استخدام خوارزمية الدمج غير المحدب لمثلثين (الشكل 4 ، د).

الشكل 4. مخطط تشغيل خوارزمية سلسلة التثليث: أ) - المقاطع الأولية ؛ ب - المرور من أسفل إلى أعلى تسوية الرسم البياني ؛ ج) - المرور من الأعلى إلى الأسفل ؛ د) - تثليث المضلعات الرتيبة

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

عيب خوارزمية السلسلة هو أنه لا يمكن قول أي شيء مسبقًا عن شكل التثليث الناتج. هذا ليس تثليثًا مثاليًا ، وليس جشعًا ، وليس تثليثًا مقيدًا لـ Delaunay. يمكن أن تنتج خوارزمية السلسلة مثلثات طويلة جدًا.

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