صقل ديلاوناي
في توليد الشبكة ، تعد تحسينات ديلاوناي خوارزميات لتوليد الشبكة تعتمد على مبدأ إضافة نقاط شتاينر إلى هندسة المدخل المراد تقسيمه إلى شبكة، بطريقة تجعل عملية التثليث ديلاوناي أو التثليث المقيد ديلاوناي للمدخل المعزز يلبي متطلبات الجودة لتطبيق التثليث.
تحفيز
عند إجراء محاكاة حاسوبية، مثل ديناميكيات الموائع الحسابية ، يبدأ المرء بنموذج، كشكل ثنائي الأبعاد لجزء من جناح. يجب أن تكون مدخلات طريقة العناصر المحدودة ثنائية الأبعاد على شكل مثلثات تملأ الفراغ، وأن يُملأ كل مثلث بنوع واحد من المواد - في هذا المثال، إما "الهواء" أو "الجناح". لا يمكن محاكاة المثلثات الطويلة والرفيعة بدقة. يتناسب وقت المحاكاة عمومًا مع عدد المثلثات، لذا يُفضّل تقليل عدد المثلثات مع الحفاظ على عدد كافٍ منها للحصول على نتائج دقيقة نسبيًا - عادةً باستخدام شبكة غير منتظمة . يستخدم الحاسوب خوارزمية تقسيم الشبكة لتحويل النموذج المضلع إلى مثلثات مناسبة لطريقة العناصر المحدودة.
الخوارزمية الثانية لـ Chew
تأخذ خوارزمية تشو الثانية نظامًا خطيًا مجزأً (PLS) وتُعيد تثليث ديلاوناي مقيدًا من مثلثات عالية الجودة فقط، حيث تُعرَّف الجودة بأصغر زاوية في المثلث. طُوِّرت هذه الخوارزمية بواسطة ل. بول تشو لإنشاء شبكات للأسطح المضمنة في الفضاء ثلاثي الأبعاد، [ 1 ] وقد اعتُمدت كمولد شبكات ثنائية الأبعاد نظرًا لمزاياها العملية مقارنةً بخوارزمية روبرت في بعض الحالات، وهي مولد الشبكات الافتراضي عالي الجودة المُطبَّق في حزمة Triangle المجانية. [ 2 ] تضمن خوارزمية تشو الثانية إنهاء العملية وإنتاج شبكات متدرجة الحجم المحلي للميزات بزاوية دنيا تصل إلى حوالي 28.6 درجة. [ 3 ]
تبدأ الخوارزمية بتقسيم رؤوس المدخلات إلى مثلثات ديلاوناي مقيدة. في كل خطوة، يُدرج مركز الدائرة المحيطة بالمثلث ذي الجودة الرديئة في عملية التقسيم، باستثناء حالة واحدة: إذا كان مركز الدائرة المحيطة يقع على الجانب المقابل لقطعة المدخلات التي يقع عليها المثلث ذو الجودة الرديئة، يُدرج منتصف تلك القطعة. علاوة على ذلك، تُزال أي مراكز دوائر محيطة أُدرجت سابقًا داخل الكرة القطرية للقطعة الأصلية (قبل تقسيمها) من عملية التقسيم. تُكرر عملية إدراج مراكز الدوائر المحيطة حتى لا يتبقى أي مثلثات ذات جودة رديئة.
خوارزمية روبرت
تأخذ خوارزمية روبرت رسمًا بيانيًا خطيًا مستويًا (أو نظامًا خطيًا متقطعًا في الأبعاد الأعلى من اثنين ) وتُنتج تثليثًا متوافقًا من نوع ديلاوناي يتكون فقط من مثلثات عالية الجودة. يُعتبر المثلث رديء الجودة إذا كانت نسبة نصف قطر الدائرة المحيطة به إلى أقصر ضلع فيه أكبر من عتبة محددة مسبقًا. اكتشف جيم روبرت هذه الخوارزمية في أوائل التسعينيات، [ 4 ] "ربما تكون خوارزمية روبرت لتوليد شبكات ثنائية الأبعاد عالية الجودة أول خوارزمية توليد شبكات مضمونة نظريًا تُحقق نتائج مرضية عمليًا." [ 5 ]
الخوارزمية
تبدأ الخوارزمية بعملية تثليث ديلاوناي لرؤوس الإدخال، ثم تتكون من عمليتين رئيسيتين.
- يتم إدخال نقطة منتصف قطعة مستقيمة ذات دوائر قطرية غير فارغة في عملية التثليث.
- يُدرج مركز الدائرة المحيطة بمثلث رديء الجودة في عملية التثليث، إلا إذا كان هذا المركز يقع ضمن الدائرة القطرية لقطعة مستقيمة. في هذه الحالة، تُقسّم القطعة المستقيمة المتداخلة بدلاً من ذلك.
تتكرر هذه العمليات حتى لا توجد مثلثات ذات جودة رديئة ولا يتم التعدي على أي من القطاعات.
- الشفرة الزائفة
دالة Ruppert( النقاط ، القطاعات ، العتبة ) هي T := DelaunayTriangulation( النقاط ) Q := مجموعة القطاعات المتعدى عليها والمثلثات ذات الجودة الرديئة بينما Q ليست فارغة: // الحلقة الرئيسية إذا كانت Q تحتوي على مقطع s : أدخل نقطة منتصف s في T وإلا فإن Q تحتوي على مثلث رديء الجودة t : إذا كان مركز الدائرة المحيطة بـ t يتعدى على قطعة مستقيمة s : أضف s إلى Q ؛ وإلا : أدخل مركز الدائرة المحيطة بـ t في T نهاية إذا نهاية إذا حدّث Q نهاية الحلقةأعد T نهاية روبرت.
الاستخدام العملي
يضمن خوارزمية روبرت، دون تعديل، إنهاء العملية وإنشاء شبكة عالية الجودة للمدخلات غير الحادة وأي عتبة جودة منخفضة تقل عن 20.7 درجة تقريبًا. ولتخفيف هذه القيود، أُدخلت تحسينات طفيفة متعددة. بتخفيف شرط الجودة بالقرب من زوايا الإدخال الصغيرة، يمكن توسيع الخوارزمية لتشمل أي مدخلات خطية مستقيمة. [ 6 ] كما يمكن إنشاء شبكة للمدخلات المنحنية باستخدام تقنيات مماثلة. [ 7 ] يمكن توسيع خوارزمية روبرت بسهولة إلى ثلاثة أبعاد، إلا أن ضمانات مخرجاتها أضعف نوعًا ما بسبب شكل رباعي الأوجه من نوع "الشريط".
تم تطبيق امتداد لخوارزمية روبرت في بُعدين ضمن حزمة Triangle المجانية. يضمن هذا الامتداد إنهاء نسختين من خوارزمية روبرت عند عتبة جودة منخفضة تبلغ حوالي 26.5 درجة. [ 8 ] عمليًا، تنجح هذه الخوارزميات عند عتبات جودة منخفضة تتجاوز 30 درجة. مع ذلك، توجد حالات معروفة تتسبب في فشل الخوارزمية عند عتبة تتجاوز 29.06 درجة. [ 9 ]
انظر أيضاً
مراجع
- ↑ تشيو، إل. بول (1993). "توليد شبكة ذات جودة مضمونة للأسطح المنحنية". وقائع الندوة السنوية التاسعة حول الهندسة الحسابية . ص 274-280 .
- ↑ شيوشوك، جوناثان (2002). "خوارزميات تحسين ديلاوناي لتوليد الشبكات المثلثية" . الهندسة الحسابية: النظرية والتطبيقات . 22 ( 1-3 ): 21-74 . doi : 10.1016/s0925-7721(01)00047-5 .
- ↑ راند، ألكسندر (2011). "أين وكيف تعمل خوارزمية تحسين ديلاوناي الثانية لتشو" (ملف PDF) . وقائع المؤتمر الكندي الثالث والعشرين للهندسة الحسابية . الصفحات 157-162 .
- ↑ روبرت، جيم (1995). "خوارزمية تحسين ديلاوناي لتوليد شبكات ثنائية الأبعاد عالية الجودة". مجلة الخوارزميات . 18 (3): 548-585 . doi : 10.1006/jagm.1995.1021 .
- ↑ شيوشوك، جوناثان (12 أغسطس 1996). "خوارزمية تحسين ديلاوناي لروبرت" . تم الاسترجاع في 28 ديسمبر 2018 .
- ↑ ميلر، غاري؛ باف، ستيفن؛ والكنغتون، نويل (2005). "متى ولماذا تنجح خوارزميات تحسين ديلاوناي". المجلة الدولية للهندسة الحسابية وتطبيقاتها . 15 (1): 25-54 . doi : 10.1142/S0218195905001592 .
- ↑ باف، ستيفن؛ والكنجتون، نويل (2005). تحسين ديلاوناي عن طريق قطع الزوايا . وقائع المؤتمر الدولي الرابع عشر للشبكة. الصفحات 165-181 .
- ↑ شيوشوك، جوناثان (2002). "خوارزميات تحسين ديلاوناي لتوليد الشبكات المثلثية" . الهندسة الحسابية: النظرية والتطبيقات . 22 ( 1-3 ): 21-74 . doi : 10.1016/s0925-7721(01)00047-5 .
- ↑ راند، ألكسندر (2011). "أمثلة محسنة لعدم الإنهاء لخوارزمية روبرت". arXiv : 1103.3903 [ cs.CG ]..
للمزيد من القراءة
- رينو، لوران. "المثلثات والشبكات المتوافقة ثنائية الأبعاد" . تم الاطلاع عليه بتاريخ 28 ديسمبر 2018 .
- شيوتشوك، جوناثان. "المثلث: مولد شبكة ثنائية الأبعاد عالية الجودة ومُثلِّث ديلاوناي" . تم الاطلاع عليه بتاريخ 28 ديسمبر 2018 .
- سي، هانغ (2015). "TetGen: مولد شبكة رباعية الأوجه عالي الجودة ومُثلِّث ديلاوناي ثلاثي الأبعاد" . مؤرشف من الأصل في 29 ديسمبر 2018. تم الاطلاع عليه في 28 ديسمبر 2018 .
{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط )
- توليد الشبكة
- التثليث (الهندسة)