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

جالانين إم بي، شيجلوف آي.
(إم بي جالانين، آي إيه شيغلوف)

IPM لهم. إم في كيلديش راس

موسكو، 2006
تم دعم هذا العمل من قبل المؤسسة الروسية للبحوث الأساسية (المشروع رقم 06-01-00421)

حاشية. ملاحظة

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

خلاصة

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

1. مقدمة 3

2. طرق تصحيح الحدود4

2.1 بناء الشبكة الأولية4

2.2 تصحيح الشبكة الأولية6

3. الطرق المبنية على معيار ديلوناي9

3.1 بناء مثلث ديلوناي على مجموعة معينة من النقاط 12

3.2. ديلوناي التثليث مع القيود17

3.3 ميزات التنفيذ الفني للخوارزميات المبنية على
معيار ديلوناي 22

4. طرق الإرهاق23

4.1 مثال على خوارزمية الاستنفاد26

المراجع3 0

1 المقدمة

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

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

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

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

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

تم دعم العمل جزئيًا من قبل المؤسسة الروسية البحوث الأساسية(مشروع رقم 06-01-00421).

أرز. 11. تثليث المجال الذي يمثل اتحاد المجسم الاثني عشري والمجسم العشروني (تثليث ديلوناي مع القيود)

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

في أعمال B. Joe، يتم اقتراح متغيرات أخرى من الخوارزمية التي لا تستخدم نقاط إضافية وتستند بالكامل إلى التحولات المحلية المشابهة لـ "التجارة".

4) حجم رباعي الاسطح لا يزيد عن الحد الأقصى المسموح به ().

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

4. هناك نقطة داخل المنطقة التي لا تزال لا تنضب:

1) رباعي السطوح () يستوفي جميع شروط الفقرة 3؛

2) في الكرة لا توجد نقطة نائيةF(وهذا يمنع وضع العقدةص قريبة جدًا من وجوه ورؤوس رباعيات الأسطح الموجودة).

البديل من خوارزمية البحث عن العقدةصمشروح بالاسفل.

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

1) إذا كان الوجه وجهاً أمامياً، فإنه يُزال من الأمام؛

2) إذا لم يكن الوجه وجهاً أمامياً، فإنه يضاف إلى الأمام.

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

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

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

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

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

3. يتم فحص النقطة. إذا كان رباعي السطوح () يلبي جميع المتطلبات، انتقل إلى الخطوة 6، وإلا انتقل إلى الخطوة 4.

4. تم فحص النقطة. إذا كان رباعي السطوح () يفي بجميع المتطلبات، انتقل إلى الخطوة 6، وإلا انتقل إلى الخطوة 5.

5. صدق وانتقل إلى الخطوة 3.

6. تم العثور على العقدة المطلوبة.

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

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

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

فهرس

1. شايدوروف ف. طرق العناصر المحدودة متعددة الشبكات. - م.، نوكا، 1989. - 288 ثانية.

2. سكفورتسوف أ.ف. نظرة عامة على خوارزميات إنشاء تثليث ديلوناي // , 2002, №3, ج. 14-39.

3. سكفورتسوف أ.ف. خوارزميات بناء التثليث مع القيود // الطرق الحسابية والبرمجة, 2002, №3, ج. 82-92.

4. آي بابوشكا، دبليو سي. راينبولت. تقديرات الخطأ A-postteriori لطريقة العناصر المحدودة // كثافة العمليات. جي رقم. ميث. م., المجلد. 12، ص. 1597-1615، 1978.

5. تي جيه. خباز. إنشاء شبكات تلقائية للمناطق المعقدة ثلاثية الأبعاد باستخدام تثليث ديلوناي المقيد // الهندسة مع أجهزة الكمبيوتر، سبرينغر-فيرلاغ، رقم 5، ص. 161-175، 1989.

6. إم بيرن، د. إبشتاين. إنشاء الشبكات والتثليث الأمثل // الحوسبة في الهندسة الإقليدية، الشركة العالمية للنشر العلمي، ص. 23-90، 1995.

7. د.ك. بلاندفورد، ج. بليوتش، د. كاردوز، سي. كادو. تمثيلات مدمجة للشبكات المبسطة في بعدين وثلاثة أبعاد // وقائع المائدة المستديرة الدولية الثانية عشرة للربط، مختبرات سانديا الوطنية، الصفحات 135-146، سبتمبر. 2003.

8. ه. بوروشاكي، س.ه. لو. التثليث السريع لديلوناي في ثلاثة أبعاد // طرق الكمبيوتر في الميكانيكا التطبيقية والهندسة، إلسفير، المجلد. 128، ص. 153-167، 1995.

9. إ.ك. بوراتينسكي. مولد شبكي غير منظم ثلاثي الأبعاد للحدود الداخلية التعسفية // توليد الشبكة العددية في ميكانيكا الموائع الحسابية، مطبعة بينريدج، ص. 621-631، 1988.

10. العلاقات العامة. كافالكانتي، الولايات المتحدة ميلو. تثليث ديلوناي المقيد ثلاثي الأبعاد: نهج الحد الأدنى // وقائع المائدة المستديرة الدولية الثامنة للربط، ص. 119-129، 1999.

11. داي، ك. تامال، ك. سوغيهارا، سي.إل. باجاج. مثلثات ديلوناي في ثلاثة أبعاد ذات دقة حسابية محدودة // التصميم الهندسي بمساعدة الحاسوب، شمال هولندا، رقم 9، ص. 457-470، 1992.

12. ح.ن. جيدجيف. الطرق الموجهة بالقوة لتنعيم الشبكات المثلثة ورباعية السطوح غير المنظمة // وقائع المائدة المستديرة الدولية التاسعة، مختبرات سانديا الوطنية، ص. 395-406، أكتوبر 2000.

13. إل دوربيك. التبخر: تقنية لتصور جودة الشبكة // وقائع المائدة المستديرة الدولية الثامنة، ساوث ليك تاهو، كاليفورنيا، الولايات المتحدة الأمريكية، ص. 259-265، أكتوبر 1999.

14. د.أ. مجال. تجانس لابلاس ومثلثات ديلوناي // ، المجلد. 4، ص. 709-712, 1988.

15. بي جيه. فراي، إتش. بوروشاكي، P.-L. جورج. ديلوناي رباعي السطوح باستخدام النهج الأمامي المتقدم // وقائع المائدة المستديرة الدولية الخامسة للربط، مختبرات سانديا الوطنية، ص. 31-46 أكتوبر 1996.

16. لوس أنجلوس فريتاج، سي. أوليفييه-جوتش. مقارنة بين تقنيات تحسين الشبكة رباعية السطوح // وقائع المائدة المستديرة الدولية الخامسة للربط، مختبرات سانديا الوطنية، ص. 87-106، أكتوبر 1996.

17. لوس أنجلوس فريتاج، سي.أوليفييه-جوتش، تحسين الشبكة رباعية السطوح باستخدام المبادلة والتجانس // ، المجلد. 40، ص. 3979-4002, 1995.

18. لوس أنجلوس فريتاج، سي. أوليفييه-جوتش. تأثير جودة الشبكة على كفاءة الحل // وقائع المائدة المستديرة الدولية السادسة، مختبرات سانديا الوطنية، ص 249، أكتوبر 1997.

19. ب.ل. جورج. TET MESHING: البناء والتحسين والتكيف // وقائع الثامنالمائدة المستديرة للشبكة الدولية، ص 133-141، 1999.

20. لا. جولياس، تي.دي. تسيبوكيس. نهج لتحسين الشبكات رباعية الأبعاد ثلاثية الأبعاد على أساس تحويلات ديلوناي // ، جون وايلي، رقم 37، ص 793-812، 1994.

21. ج. هازلوود. تقريب رباعيات السطوح المقيدة // التصميم الهندسي بمساعدة الحاسوب، المجلد. 10، ص. 67-87، 1993.

22. ب. جو. شبكات Delaunay المثلثة ذات المضلعات المحدبة، سيام ي العلوم. القانون الأساسي. حساب.، المجلد. 7، ص. 514-539، 1986.

23. ب. جو. بناء مثلثات ديلوناي ثلاثية الأبعاد باستخدام التحولات المحلية // التصميم الهندسي بمساعدة الحاسوب، المجلد. 8، ص. 123-142، 1991.

24. ب. جو. بناء مثلثات محسنة الجودة ثلاثية الأبعاد باستخدام التحولات المحلية // صيام جيه. حساب.، المجلد. 16، ص. 1292-1307، 1995.

25. ر.و. لويس، ياو تشنغ، د.ت. جيثين. إنشاء شبكات غير منظمة ثلاثية الأبعاد: الجزء 3. شبكات الحجم // طرق الكمبيوتر في الميكانيكا التطبيقية والهندسة، إلسفير، المجلد 134، الصفحات من 285 إلى 310، 1996.

26. أ. ليو، ب. جو. على شكل رباعي الاسطح من المنتصف // رياضيات الحساب، المجلد. 63، رقم 207، 141-154، 1994.

27. ش. لو. تقسيم الحجم إلى رباعي الاسطح-I. التحقق من الأسطح الحدودية وتوجيهها // أجهزة الكمبيوتر والهياكل، مطبعة بيرغامون، المجلد. 39، رقم 5، ص. 493-500، 1991.

28. ش. لو. تقسيم الحجم إلى رباعي الأسطح - II. التثليث ثلاثي الأبعاد من خلال تقدم النهج الأمامي // أجهزة الكمبيوتر والهياكل, بيرغامون، المجلد. 39، رقم 5، ص. 501-511، 1991.

29. ر. لونر. توليد شبكات غير منظمة ثلاثية الأبعاد بالطريقة الأمامية المتقدمة // وقائع الاجتماع السادس والعشرون لعلوم الطيران AIAA، رينو، نيفادا، 1988.

30. س.ج. أوين. مسح لتكنولوجيا توليد الشبكات غير المنظمة // وقائع المائدة المستديرة الدولية السابعة للربط، ص. 239-269، ديربورن، ميشيغان، 1998.

31. ف.ن. بارثاساراتي، سي.م. غرايشن، أ.ف. هاثاواي. مقارنة مقاييس الجودة رباعية الأسطح // العناصر المحدودة في التحليل والتصميم، إلسفير، لا. 15، ص. 255-261، 1993.

32. س. بيرزاده. إنشاء شبكة لزجة غير منظمة بطريقة الطبقات المتقدمة // AIAA-93-3453-CP، AIAA، ص. 420-434، 1993.

33. V.T. راجان. الأمثلية لتثليث ديلوناي في // بروك. 7th ACM Symp. شركات. هندسة، ص. 357-363، 1991.

34. أ. راسينو. إنشاء وتحسين شبكات رباعية السطوح من خلال تطوير التقنية الأمامية // المجلة الدولية للطرق العددية في الهندسة، وايلي، المجلد. 41، ص. 651-674، 1998.

35. إس ريباي. إنشاء شبكات فعالة غير منظمة عن طريق تثليث ديلوناي وخوارزمية بوير-واتسون // مجلة الفيزياء الحاسوبية، المجلد. 106، ص. 125-138، 1993.

36. م.-ج. ريفارا. خوارزميات التحسين/التحديد الانتقائي لتسلسلات المثلثات المتداخلة // المجلة الدولية للطرق العددية في الهندسة، رقم 28، ص. 2889-2906, 1998.

37. م.-ج. ريفارا، سي. ليفين. خوارزمية تحسين ثلاثية الأبعاد مناسبة للتقنيات التكيفية ومتعددة الشبكات // الاتصالات في الطرق العددية التطبيقية، رقم 8، ص. 281-290، 1998.

38. جي روبرت. خوارزمية تحسين Delaunay لتوليد شبكات ثنائية الأبعاد عالية الجودة // مجلة الخوارزميات، رقم 18، ص. 548-585، 1995.

39. آنسة. الراعي، م.ك. جورج. إنشاء شبكات ثلاثية الأبعاد بتقنية Finite Octree // المجلة الدولية للطرق العددية في الهندسة، المجلد. 32، ص. 709-749, 1991.

40. آنسة. شيبارد، إف. غيرينوني، جي.إي. فلاهيرتي، ر.أ. لودفيج، ب.ل. باهمان. إنشاء شبكات متناهية الثمان لتحليل التدفق التكيفي ثلاثي الأبعاد // توليد الشبكة العددية في ميكانيكا الموائع الحسابيةميامي، 1988

41. ك. شيمادا، العاصمة جوسارد. الشبكة الفقاعية: شبكة مثلثية آلية للهندسة غير المتشعبة عن طريق التعبئة الكروية // وقائع الندوة الثالثة حول النمذجة الصلبة والتطبيقات ، ص. 409-419، 1995.

42. ك. شيمادا، أ. يامادا، ت. إيتو. شبكات مثلثة متباينة الخواص للأسطح البارامترية عبر التعبئة المتقاربة للفقاعات الإهليلجية // وقائع المائدة المستديرة الدولية السادسة، ص. 375-390، 1997.

43. د.ف. واتسون. حساب التغطية بالفسيفساء Delaunay مع التطبيق على Voronoi Polytopes // مجلة الكمبيوتر، المجلد. 24(2)، ص. 167-172، 1981.

44. ماجستير يري، م.س. الراعي. إنشاء شبكات ثلاثية الأبعاد بواسطة تقنية Octree المعدلة // المجلة الدولية للطرق العددية في الهندسة، المجلد. 20، ص. 1965-1990، 1984.

45. جالانين إم بي، شيجلوف آي. تطوير وتنفيذ خوارزميات للتثليث ثلاثي الأبعاد للمناطق المكانية المعقدة: الطرق المباشرة. IPM ما قبل الطباعة ايم. م.ف. كيلديش ران، 2006، في الصحافة. النقاط، أي. عقدة شتاينر - عقدة إضافية لم يتم تضمينها في المجموعة الأصلية

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

20 أغسطس 2012 الساعة 10:41 مساءً

تحسين خوارزمية التحقق من حالة ديلوناي من خلال معادلة الدائرة المقيدة وتطبيقها

• معالجة الصورة ،
• برمجة

سأخبرك بسر كيفية التحقق بسرعة من حالة Delaunay لمثلثين.
في الواقع، يتم وصف التحسين نفسه أدناه قليلا (انظر "تحسين الخوارزمية للتحقق من حالة Delaunay من خلال معادلة الدائرة المقيدة")، لكنني سأخبرك بكل شيء بالترتيب.

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

في المدخل

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

الصورة 1

ما يجب القيام به

من الضروري مسح الشكل بالمثلثات.

يبحث

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

خوارزمية

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

الشكل 2

الشكل 3

الشكل 4

شيء آخر: عند حفظ المثلث التالي، من الضروري تسجيل القمم في اتجاه عقارب الساعة (في نظام الإحداثيات الصحيح). سيكون هذا مفيدًا في المستقبل لتقليل موارد الحوسبة.

2) كرر الخطوة 1 حتى نقوم بمسح الطائرة بأكملها.

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

الشكل 5

الشكل 6
4) بعد ذلك، يجب عليك إدخال جميع التسلسلات الداخلية بدورها في التسلسلات التي تم تشكيلها بالفعل، والمنفصلة عن بعضها البعض (النقطة 3). تحتاج إلى الدمج مع الذي يحتوي على الجديد. بحكم التعريف، لا يوجد تسلسل داخلي يلامس أو يتقاطع مع الآخرين (سواء كان خارجيًا أو كل الأجزاء الداخلية الممكنة)، لذلك كل شيء سوف يسير بسلاسة.
بعد العثور على المنافذ (الشكل 6)، من السهل إنشاء تسلسلات جديدة وتجاوزها بالنقطتين 1 و2 من الخوارزمية الحالية (الشكل 7).

الشكل 7

5) بعد المرحلة الرابعة، لدينا قائمة المثلثات (الشكل 8). كما لو كنا قد تعاملنا مع المهمة بالفعل، ولكن يبقى أن نجعل الصورة جميلة: التحقق من استيفاء شرط Delaunay (الشكل 9).

الشكل 8

الشكل 9

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

المزيد عن المرحلة الخامسة

الآن، بقدر ما أعرف، هناك اثنان الطرق الممكنةتحديد ما إذا كان المثلثان يحققان شرط ديلوناي أم لا: 1) التحقق من مجموع الزوايا المتقابلة. ويجب أن يكون أقل من 180. 2) احسب مركز الدائرة المقيدة واحسب المسافة إلى النقطة الرابعة. يعلم الجميع أن شرط ديلوناي يتحقق إذا كانت النقطة خارج الدائرة المحدودة.

قوة الحوسبة رقم 1: 10 عمليات ضرب/قسمة و13 عملية جمع/طرح.
قوة الحوسبة رقم 2: 29 عملية ضرب/قسمة و24 عملية جمع/طرح.

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

الشكل 10

تحسين الخوارزمية للتحقق من حالة ديلوناي من خلال معادلة الدائرة المقيدة

ما يلي هو الرياضيات البحتة.

اذا لدينا:
يمكن التحقق من حالة النقطة M(X, Y) بمعادلة الدائرة التي تمر بالنقطتين A(x1, y1), B(x2, y2), C(x3, y3) على النحو التالي:

(أ ⋅ (X^2 + Y^ 2) − ب ⋅ X + ج ⋅ Y − د) ⋅ إشارة أ ≥ 0

التفاصيل تجدونها في الكتاب الممتاز. (لا، ​​أنا لست المؤلف)
إذن، الإشارة a هي علامة اتجاه الاجتياز، منذ البداية قمت ببناء مثلثات في اتجاه عقارب الساعة، بحيث يمكن حذفها (تساوي واحدًا).

أ(x1 - X، y1 - Y)، B(x2 - X، y2 - Y)، B(x3 - X، y3 - Y)؛

د >= 0

الشكل 11

فقط أليس كذلك؟

ووفقا للكتاب، مرة أخرى.

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (ص1*س2 - س1*ص2)<= 0

لدينا: 15 عملية ضرب/قسمة و14 عملية جمع/طرح.

شكرًا لكم على اهتمامكم. أنا في انتظار النقد.

فهرس

1. سكفورتسوف أ.ف. تثليث ديلوناي وتطبيقاته - تومسك: دار النشر المجلد. اون تا، 2002. - 128 ص. ردمك 5-7511-1501-5

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

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

مستضاف على http://www.allbest.ru/

مشروع الدورة

بناءالتثليثديلوناي

بواسطة تأديب "الهياكلوخوارزمياتيعالجبيانات"

محتوى

• مقدمة
• 2.1 الخوارزمية الجشعة
• 2.4 خوارزمية فهرسة مراكز المثلثك- د- شجرة
• 3.4 خوارزمية المروحة
• 4. جزء البرمجيات
• خاتمة

مقدمة

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

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

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

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

هدفعملومهام: دراسة إحدى الخوارزميات التكرارية لبناء مثلث ديلوناي.

1) دراسة التعريفات والنظريات الأساسية لمسألة تثليث ديلوناي.

2) النظر في الأنواع الرئيسية للخوارزميات التكرارية لبناء التثليث؛

3) تنفيذ خوارزمية "الحذف والبناء" لإنشاء تثليث ديلوناي.

1. وصف عام لتثليث ديلوناي

مهمة بناء التثليث.

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

التثليثديلونايبالنسبة لمجموعة من النقاط S في المستوى، يسمى التثليث DT (S) بحيث لا توجد نقطة A من S داخل دائرة محصورة حول أي مثلث من DT (S) بحيث لا تكون أي من رؤوسها نقطة A.

1.1 تحليل الأدبيات حول هذا الموضوع

سكفورتسوفأ.في.التثليثديلونايوهاطلب. /سكفورتسوفأ.في. -تومسك: دار نشرمقدار. أون تا,2002 . - 128 ثانية. هذا البرنامج التعليمي هو البرنامج الرئيسي لمشروع الدورة هذا. فهو يصف بالتفصيل المعلومات النظرية المتعلقة بتثليث ديلوناي، ويقدم تعريفات ونظريات مختلفة.

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

ماذا اقترضت، استعارت: المواد الأساسية والمعلومات النظرية والتعاريف والرسومات.

بوبوفمع.أ.الحوسبةطُرقوبرمجة. /بوبوفمع.أ. -موسكو: دار نشرجامعة موسكو2008, - 24 ثانية. هذا الدليل هو مصدر مساعد للأدب. يتم وصف بعض الخوارزميات من وجهة نظر رياضية، ويتم حساب صيغ البناء، ويوجد أيضًا وصف للتثليث في الفضاء الإقليدي

ماذا اقترضت، استعارت: الوصف الرياضي لتثليث ديلوناي، البناء على الفضاء الإقليدي

ميدفيديفح.ن.طريقةفورونوي - ديلونايالخامسبحثالهياكلغير بلوريةأنظمة/ رأس,نوفوسيبيرسكrsk: دار نشرلذارأس,2000, - 214 مع. كتاب مخصص لوصف طريقتي فورونوي وديلاوناي في الأنظمة غير البلورية.

ماذا اقترضت، استعارت: خواص مثلثات ديلوناي، تعريف مثلثات ديلوناي.

1.2 التعاريف والخصائص الأساسية

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

ملكيات:

· يتوافق مثلث ديلوناي واحد لواحد مع مخطط فورونوي لنفس مجموعة النقاط.

· ونتيجة لذلك: إذا لم تقع أربع نقاط على نفس الدائرة، فإن مثلث ديلوناي يكون فريدًا.

· يؤدي تثليث ديلوناي إلى تعظيم الحد الأدنى من الزاوية بين جميع زوايا المثلثات المبنية، وبالتالي تجنب المثلثات "الرفيعة".

· تثليث ديلوناي يزيد من مجموع أنصاف أقطار الكرات المنقوشة.

· يقلل تثليث ديلوناي من وظيفة ديريشليت المنفصلة.

· تثليث ديلوناي يقلل من الحد الأقصى لنصف القطر للكرة المحيطة الدنيا.

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

الشكل 1. التثليث.

محدب التثليث يسمى التثليث بحيث يكون الحد الأدنى للمضلع الذي يضم جميع المثلثات محدبًا. يسمى التثليث غير المحدب غير محدب.

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

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

التثليثمُسَمًّىالتثليث ديلوناي , إذا كانت محدبة وتحقق شرط ديلوناي.

الشكل 2. تثليث ديلوناي.

1.3 طريقة ديلوناي للكرة الفارغة. البناء في الحالة العامة

دعونا نستخدم كرة فارغة، والتي سوف نحركها، ونغير حجمها حتى تتمكن من لمس نقاط النظام (أ)، ولكنها تظل فارغة دائمًا.

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

الشكل 3 - تقسيم ديلوناي لنظام النقاط ثنائي الأبعاد

تبسط Delaunay المساحة دون فجوات أو تداخلات.

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

فلتكن هذه النقطة j. دعونا نستمر في زيادة نصف قطر الكرة، مع إبقاء النقطتين على سطحها. زيادة، ستصل الكرة إلى نقطة ثالثة من النظام، النقطة ك. وفي الحالة ثنائية الأبعاد، ستكون "الدائرة الفارغة" لدينا ثابتة في هذه اللحظة، أي. يصبح من المستحيل زيادة نصف قطرها مع إبقاء الدائرة فارغة. في الوقت نفسه، نكشف عن تكوين أولي ثنائي الأبعاد لثلاث نقاط (i، j، k)، والذي يحدد مثلثًا معينًا، وتكمن خصوصيته في عدم وجود نقاط أخرى للنظام (A) داخل محيطه دائرة. في الأبعاد الثلاثة، لا يتم تعريف الكرة بثلاث نقاط. دعونا نستمر في زيادة نصف قطرها، مع الحفاظ على النقاط الثلاث الموجودة على سطحه. سيكون هذا ممكنًا حتى يلتقي سطح الكرة بالنقطة الرابعة l من النظام. بعد ذلك، ستصبح حركة ونمو الكرة الفارغة مستحيلة. تحدد النقاط الأربع التي تم العثور عليها (i، j، k، l) رؤوس رباعي السطوح، والذي يتميز بحقيقة عدم وجود نقاط أخرى للنظام (A) داخل مجاله المحدد. ويسمى هذا الرباعي السطوح Delaunay simplex.

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

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

1.4 تطبيق تثليث ديلوناي

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

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

هناك مشكلة أخرى تنشأ غالبًا في المعلوماتية الجغرافية وهي إنشاء تعريضات للمنحدرات. مطلوب هنا تحديد الاتجاهات السائدة للمنحدرات من خلال النقاط الأساسية وتقسيم السطح إلى مناطق يهيمن عليها اتجاه معين. وبما أن تعريف التعريض غير منطقي بالنسبة للأجزاء الأفقية من السطح، فإن المناطق الأفقية أو ذات المنحدر الطفيف، على سبيل المثال، يتم تخصيصها لمنطقة منفصلة.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

الشكل 4. مثال على حساب تعرضات المنحدر باستخدام نموذج الإغاثة

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

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

2. وصف خوارزميات البناء

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

منح مجموعة من منن نقاط.

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

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

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

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

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

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

أقل معطى مفصلة وصف عديد خوارزميات.

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

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

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

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

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

3. يتم إدراج جميع شرائح الخط الفاصل في التثليث.

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

يتم تكرار الخطوة 4 حتى نفاد الأجزاء.

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

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

2.2 خوارزمية "الحذف والبناء"

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

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

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

2.3 خوارزمية "البناء بالكسر"

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

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

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

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

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

2.4 خوارزمية مع فهرسة شجرة k-D لمراكز المثلثات

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

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

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

3. تقييم كفاءة الخوارزميات

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

3.1 خوارزمية تكرارية بسيطة

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

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

3.2 خوارزمية تكرارية مع فهرسة المثلث

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

3.3 الخوارزمية التكرارية مع فهرسة شجرة K-D لمراكز المثلث

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

من هذا نحصل على أن تعقيد خوارزمية التثليث مع فهرسة مراكز المثلثات في أسوأ الحالات هو، وفي المتوسط، O (N log N).

3.4 خوارزمية المروحة

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

يكون تعقيد مثل هذه الخوارزمية في المتوسط ​​O N (). تعمل الخوارزمية بنفس سرعة الخوارزمية السابقة تقريبًا.

4. جزء البرمجيات

تم تطوير البرنامج في بيئة تطوير Microsoft Visual Studio 2012. التطبيق عبارة عن نافذة يمكن للمستخدم من خلالها إضافة نقاط مرتبطة بشكل مباشر بتثليث Delaunay بشكل عشوائي. يتم عرض قائمة إحداثيات جميع النقاط المضافة على اليمين.

رئيسي. CPP - وظائف النافذة، وظائف واجهة المستخدم

com.delone. CPP - الخوارزمية والوظائف الضرورية للعمل معها

وصف وظائف البرنامج:

void DrawPoint (int x, int y) - وظيفة لرسم نقطة في نافذة التطبيق

التثليث الفارغ () - وظيفة لإجراء التثليث

باطلة TriangulationIn () - وظيفة لتنفيذ الإجراءات مع النقاط الموجودة داخل المثلث

void TriangulationOut () - وظيفة لتنفيذ إجراءات بنقاط خارج المثلث.

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

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

أرز. 6. واجهة البرنامج

خاتمة

في هذا العمل، تم تطوير برنامج يتم على أساسه بناء مثلث ديلوناي.

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

قائمة الأدب المستخدم

1. سكفورتسوف أ.ف. تثليث ديلوناي وتطبيقاته / سكفورتسوف أ.ف. - تومسك: دار النشر المجلد. الجامعة، 2012. - 128 ثانية.

2. بوبوف إس. الطرق الحسابية والبرمجة. / بوبوف إس. - موسكو: دار النشر التابعة لجامعة موسكو الحكومية، 2008، - 24 ص.

3. ميدفيديف ن.ن. طريقة فورونوي-ديلوناي في دراسة بنية الأنظمة غير البلورية / RAS، نوفوسيبيرسك: دار نشر الفرع السيبيري للأكاديمية الروسية للعلوم، 2009، - 214 صفحة.

مستضاف على Allbest.ru

وثائق مماثلة

طريقة ديلوناي للكرة الفارغة. التقسيم البسيط (التثليث). خصوصيات الترتيب المتبادل لـ Delaunay simplices. خوارزمية لبناء دائرة ديلوناي. قدرات البرمجة باستخدام تقنية Microsoft Windows Presentation Foundation.

ورقة مصطلح، أضيفت في 14/05/2011


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

ملخص، أضيفت في 02/11/2010


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

ورقة مصطلح، أضيفت في 27/11/2007


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

تمت إضافة العرض بتاريخ 19/08/2013


وصف الحل التصميمي للنظام الاستراتيجي ومراحل التحليل والتصميم الموجه للكائنات. وصف الروابط بين الكائنات. تنفيذ البرمجيات، وبناء نموذج لحالات الكائن. دليل المستخدم ووصف البرنامج.

ورقة مصطلح، أضيفت في 17/11/2011


الملامح الرئيسية للخوارزميات التطورية. وصف خوارزميات الاختيار والطفرة والعبور المستخدمة في تنفيذ الخوارزميات الجينية. حساب وظيفة اللياقة البدنية. تنفيذ البرامج. الاختبار ودليل المستخدم.

ورقة مصطلح، أضيفت في 03/11/2014


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

ورقة مصطلح، أضيفت في 06/11/2012


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

أطروحة، أضيفت في 17/12/2011


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

ورقة مصطلح، أضيفت في 13/06/2011


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

نماذج GRID هي نماذج للخلايا العادية.

دع نظام الإحداثيات
و و
. مجموعات المستخدم
وخطوات أخذ العينات
.

,

- الإحداثيات المادية للنقطة.

احسب
و
,
- شبكة بت.

- القيم الكمية. حقيقي:

- معلمة الخوارزمية - عدد النقاط، - وزن. كلما اقتربت النقطة كلما زاد الوزن.

- درجة المسافة (1 أو 2).

عامل التطبيع:

كيف أقرب إلى 1، يتم أخذ النقاط الأكثر ترجيحًا في الاعتبار.

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

ميزة- البساطة

عيب:

------التذكرة 14. نموذج القصدير. خوارزميات التثليث ديلوناي ------

1) التثليث (القصدير).

التثليث- بناء دالة على شكل مجموعة من الدوال الخطية المتعددة التعريف

التثليث- الاستيفاء داخل المنطقة المحدبة.

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

نحن بحاجة إلى خوارزمية لبناء التثليث الأمثل.

طائرة تمر عبر 3 نقاط.

1) العثور على مثلث ذلك
;

2)
- نبني معادلة المستوى .

للتحقق مما إذا كانت النقاط داخل المثلث أم لا، تحتاج إلى استبدال القيمة في معادلة الخطوط - حواف المثلث. إذا كانت جميع المعادلات الثلاث > 0، ثم بالداخل.

عرض الهيكل:

يحتوي كل مثلث على نفس عدد المثلثات.

، أين هو عدد النقاط الداخلية
- كمية النقاط.

التثليث الجشع.

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

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

نقاط المثلثات الأخرى لا تقع داخل دائرة محيطة بأي مثلث. بنيت بطريقة واحدة.

الوجه هو قلب الحواف. يسمح لك بالتبديل من التثليث التقليدي إلى تثليث ديلوناي. للتحقق مما إذا كانت النقطة تنتمي إلى دائرة: استبدل إذا< R, то внутри.

حالة ديلوناي.

معادلة الدائرة التي تمر بثلاث نقاط:

إذا كان أقل من الصفر، ثم خارجي، وإلا - داخلي.

هي حالة ديلوناي.

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

1) قيد التحقيق إضافة نقاطهي خوارزمية تكرارية بسيطة:

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

التعقيد النظري

2) طرق التسريع.بناء على النقاط المعتمدة إحصائيا. المثلث البذري هو المثلث الذي سقطت فيه النقطة السابقة. ثم نقوم بتوصيل نقطتين - النقطة السابقة والجديدة.

ننتقل من النقطة الأولى إلى أخرى.

20 أغسطس 2012 الساعة 10:41 مساءً

تحسين خوارزمية التحقق من حالة ديلوناي من خلال معادلة الدائرة المقيدة وتطبيقها

سأخبرك بسر كيفية التحقق بسرعة من حالة Delaunay لمثلثين.
في الواقع، يتم وصف التحسين نفسه أدناه قليلا (انظر "تحسين الخوارزمية للتحقق من حالة Delaunay من خلال معادلة الدائرة المقيدة")، لكنني سأخبرك بكل شيء بالترتيب.

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

في المدخل

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

الصورة 1

ما يجب القيام به

من الضروري مسح الشكل بالمثلثات.

يبحث

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

خوارزمية

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

الشكل 2

الشكل 3

الشكل 4

شيء آخر: عند حفظ المثلث التالي، من الضروري تسجيل القمم في اتجاه عقارب الساعة (في نظام الإحداثيات الصحيح). سيكون هذا مفيدًا في المستقبل لتقليل موارد الحوسبة.

2) كرر الخطوة 1 حتى نقوم بمسح الطائرة بأكملها.

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

الشكل 5

الشكل 6
4) بعد ذلك، يجب عليك إدخال جميع التسلسلات الداخلية بدورها في التسلسلات التي تم تشكيلها بالفعل، والمنفصلة عن بعضها البعض (النقطة 3). تحتاج إلى الدمج مع الذي يحتوي على الجديد. بحكم التعريف، لا يوجد تسلسل داخلي يلامس أو يتقاطع مع الآخرين (سواء كان خارجيًا أو كل الأجزاء الداخلية الممكنة)، لذلك كل شيء سوف يسير بسلاسة.
بعد العثور على المنافذ (الشكل 6)، من السهل إنشاء تسلسلات جديدة وتجاوزها بالنقطتين 1 و2 من الخوارزمية الحالية (الشكل 7).

الشكل 7

5) بعد المرحلة الرابعة، لدينا قائمة المثلثات (الشكل 8). كما لو كنا قد تعاملنا مع المهمة بالفعل، ولكن يبقى أن نجعل الصورة جميلة: التحقق من استيفاء شرط Delaunay (الشكل 9).

الشكل 8

الشكل 9

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

المزيد عن المرحلة الخامسة

الآن، على حد علمي، هناك طريقتان ممكنتان لتحديد ما إذا كانت المثلثات تحقق شرط ديلوناي أم لا: 1) التحقق من مجموع الزوايا المتقابلة. ويجب أن يكون أقل من 180. 2) احسب مركز الدائرة المقيدة واحسب المسافة إلى النقطة الرابعة. يعلم الجميع أن شرط ديلوناي يتحقق إذا كانت النقطة خارج الدائرة المحدودة.

قوة الحوسبة رقم 1: 10 عمليات ضرب/قسمة و13 عملية جمع/طرح.
قوة الحوسبة رقم 2: 29 عملية ضرب/قسمة و24 عملية جمع/طرح.

من وجهة نظر قوة الحوسبة، والتي يتم حسابها، على سبيل المثال، في الكتاب، الخيار رقم 1 هو أكثر ربحية. وقد أدرك ذلك لولا... (شكل 10). وكما تبين، بعد وضع هذه الطريقة على "الناقل"، كان هناك عدم يقين. هذا خيار عندما تكون الزاوية A نفسها أكبر من 180 درجة. ويعالجها الكتاب على أنها إحدى الطرق الخاصة المنفصلة. وبهذا تختفي أناقتها وشفافيتها وأدائها. كما تبين لاحقًا أن الطريقة رقم 2 يمكن تحسينها بشكل كبير جدًا.

الشكل 10

تحسين الخوارزمية للتحقق من حالة ديلوناي من خلال معادلة الدائرة المقيدة

ما يلي هو الرياضيات البحتة.

اذا لدينا:
يمكن التحقق من حالة النقطة M(X, Y) بمعادلة الدائرة التي تمر بالنقطتين A(x1, y1), B(x2, y2), C(x3, y3) على النحو التالي:

(أ ⋅ (X^2 + Y^ 2) − ب ⋅ X + ج ⋅ Y − د) ⋅ إشارة أ ≥ 0

التفاصيل تجدونها في الكتاب الممتاز. (لا، ​​أنا لست المؤلف)
إذن، الإشارة a هي علامة اتجاه الاجتياز، منذ البداية قمت ببناء مثلثات في اتجاه عقارب الساعة، بحيث يمكن حذفها (تساوي واحدًا).

أ(x1 - X، y1 - Y)، B(x2 - X، y2 - Y)، B(x3 - X، y3 - Y)؛

د >= 0

الشكل 11

فقط أليس كذلك؟

ووفقا للكتاب، مرة أخرى.

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (ص1*س2 - س1*ص2)<= 0

لدينا: 15 عملية ضرب/قسمة و14 عملية جمع/طرح.

شكرًا لكم على اهتمامكم. أنا في انتظار النقد.

فهرس

1. سكفورتسوف أ.ف. تثليث ديلوناي وتطبيقاته - تومسك: دار النشر المجلد. اون تا، 2002. - 128 ص. ردمك 5-7511-1501-5