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

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

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 المقدمة

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

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

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

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

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

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

أرز. 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% من الحالات، تقع النقطة المطلوبة عند تكرار واحد أو تكرارين لهذه الخوارزمية.

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

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

فهرس

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 im. م.ف. كيلديش راس، 2006، في الصحافة. النقاط، أي. عقد شتاينر - العقد الإضافية غير المدرجة في المجموعة الأصلية

قد يبدو أن الشرط 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). يبدو الأمر كما لو أن المهمة قد اكتملت بالفعل، ولكن كل ما تبقى هو جعل الصورة جميلة: التحقق من استيفاء شرط ديلوناي (الشكل 9).

الشكل 8

الشكل 9

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

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

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

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

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

الشكل 10

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

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

اذا لدينا:
يمكن التحقق من حالة النقطة 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. وصف عام لتثليث ديلوناي

مشكلة بناء التثليث.

ديلوناي هو أحد الأساسيين في الهندسة الحسابية. وترتبط به العديد من المشكلات الأخرى؛ فهو يستخدم على نطاق واسع في رسومات الكمبيوتر وأنظمة المعلومات الجغرافية لنمذجة الأسطح وحل المشكلات المكانية. تم طرح مهمة إنشاء مثلث ديلوناي لأول مرة في عام 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 simplex تملأ المساحة بدون فجوات أو تداخلات.

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

فلتكن هذه النقطة j. دعونا نستمر في زيادة نصف قطر الكرة، مع إبقاء النقطتين على سطحها. ومع زيادة الكرة، ستصل إلى نقطة ثالثة من النظام، وهي النقطة k. وفي الحالة ثنائية الأبعاد، ستكون «دائرتنا الفارغة» ثابتة في هذه اللحظة، أي. سيصبح من المستحيل زيادة نصف قطرها مع إبقاء الدائرة فارغة. في الوقت نفسه، نحدد تكوينًا أوليًا ثنائي الأبعاد لثلاث نقاط (i، j، k)، يحدد مثلثًا معينًا، وتكمن خصوصيته في عدم وجود نقاط أخرى للنظام (A) داخل دائرته المحيطة. في الفضاء ثلاثي الأبعاد، لا يتم تعريف الكرة بثلاث نقاط. دعونا نستمر في زيادة نصف قطرها، مع الحفاظ على النقاط الثلاث الموجودة على سطحه. سيكون هذا ممكنًا حتى يلتقي سطح الكرة بالنقطة الرابعة l من النظام. بعد ذلك، ستصبح حركة ونمو الكرة الفارغة مستحيلة. تحدد النقاط الأربع التي تم العثور عليها (i،j،k،l) رؤوس رباعي الاسطح، والذي يتميز بحقيقة أنه لا توجد داخل مجاله المحدد نقاط أخرى للنظام (A). ويسمى هذا الرباعي السطوح 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) - وظيفة لرسم نقطة في نافذة التطبيق

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

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

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

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

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

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

خاتمة

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

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

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

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

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

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

تم النشر على موقع Allbest.ru

وثائق مماثلة

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

تمت إضافة الدورة التدريبية في 14/05/2011


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

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


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

تمت إضافة الدورة التدريبية في 27/11/2007


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

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


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

تمت إضافة الدورة التدريبية في 17/11/2011


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

تمت إضافة الدورة التدريبية في 11/03/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، لكل مثلث نتحقق من حالة Delaunay ونقوم بنقل الحواف. متوسط ​​عدد تغييرات المسار هو ثلاثة.

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

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). يبدو الأمر كما لو أن المهمة قد اكتملت بالفعل، ولكن كل ما تبقى هو جعل الصورة جميلة: التحقق من استيفاء شرط ديلوناي (الشكل 9).

الشكل 8

الشكل 9

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

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

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

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

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

الشكل 10

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

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

اذا لدينا:
يمكن التحقق من حالة النقطة 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