تثليث ديلوناي المكاني

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

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

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

وتسمى شبكة من هذه المثلثات بتثليث ديلوناي إذا استوفت شروطًا معينة:

لا تقع أي من النقاط الأصلية داخل الدائرة المحددة حول أي مثلث (الشكل ٥-٣)؛

التثليث محدب ويفي بشرط ديلوناي المذكور أعلاه؛

مجموع الزوايا الدنيا لجميع المثلثات هو الحد الأقصى لجميع المثلثات الممكنة؛

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

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

(5.2)

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

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

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

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

تستخدم العديد من الخوارزميات لإنشاء تثليث ديلوناي النظرية التالية.

نظرية 1. يمكن الحصول على تثليث ديلوناي من أي تثليث آخر باستخدام نفس نظام النقاط عن طريق إعادة ترتيب أزواج المثلثات المتجاورة ABC و BCD التي لا تحقق شرط ديلوناي إلى أزواج من المثلثات ABD و ACD (الشكل 5.5).

أرز. 5.5.. إعادة بناء المثلثات التي لا تستوفي شرط ديلوناي

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

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

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

- التحقق من معادلة الدائرة المحيطة؛

- تحقق من خلال دائرة مقيدة محسوبة مسبقًا؛

- التحقق من مجموع الزوايا المتقابلة؛

- فحص معدل لمجموع الزوايا المتقابلة.

تقوم العديد من الأنظمة بإجراء الاختبار باستخدام دائرة محيطية محسوبة مسبقًا. الفكرة الرئيسية لخوارزمية التحقق من خلال الدوائر المحسوبة مسبقًا هي الحساب المسبق لكل مثلث مبني مركز ونصف قطر الدائرة الموصوفة حوله، وبعد ذلك سيتم تقليل التحقق من شرط ديلوناي إلى حساب المسافة إلى المركز لهذه الدائرة ومقارنة النتيجة مع نصف القطر. يمكن العثور على مركز ونصف قطر r للدائرة الموصوفة حولها كـ , , , r 2 = (b 2 + c 2 - 4аd)/4а 2، حيث تكون القيم ا ب ت ثتحددها الصيغ (5.3)

(5.3)

إدخال آخر لمعادلة هذه الدائرة هو:

(5.5.)

(5.6)

عندها لن يتم استيفاء شرط Delaunay إلا عندما يكون: بالنسبة لأي نقطة تثليث أخرى:

(س 0 – س ج) 2 + (ص 0 – ص ج) 2 ≥ ص 2 . (5.7)

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

- تستخدم الخوارزميات الدوال المثلثية المحسوبة باستمرار، مما يؤدي إلى إبطاء العملية بشكل كبير؛

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

تقوم أكثر المنتجات البرمجية شهرة ببناء تثليث ديلوناي باستخدام نظرية الكرة الفارغة كمبدأ رئيسي أساسي لبناء المثلثات. تبدو الخوارزمية كما يلي:

- مجموعة النقاط بأكملها مقسمة إلى مثلثات، أي. يتم إنشاء مجموعات من ثلاث نقاط؛

- لكل مجموعة، يتم العثور على الدائرة المحددة وإحداثيات مركزها؛

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

تشمل مزايا هذه الخوارزمية ما يلي:

- عدم استخدام الدوال المثلثية، مما لا يؤدي إلى إبطاء عملية البناء؛

- البناء المباشر لتثليث ديلوناي، دون أي إنشاءات أولية؛

- بساطة جميع الحسابات والتحويلات؛

– ونتيجة لذلك، يتم تمثيل شبكة التثليث بالعديد من المثلثات، بدلاً من الخطوط الفردية.

التثليث المبني بهذه الطريقة هو الأساس الهندسي لبناء الخطوط المتساوية.

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

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

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

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

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

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

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

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

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

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

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

حول الدقة:

من خلال وضع الأوتاد على عناصر الإغاثة المميزة (على سبيل المثال، مستجمعات المياه والمسطحات المائية)، فإننا نتجاهل العناصر الأصغر في الفجوات. عند إنشاء خطوط كفاف 1 على طول حواف المثلثات، يحدث خطأ يعتمد على مقدار مخالفات التضاريس وزاوية ميل التضاريس. على سبيل المثال، يجب ألا يتجاوز متوسط ​​الخطأ في مسح التضاريس 1/3 المقطع العرضي للتضاريس عند زوايا ميل السطح من 2 إلى 10 درجات. يمكن حساب أنه مع قسم إغاثة يبلغ 0.5 متر، يجب ألا تتجاوز القيمة القصوى للتفاوت المفقود (أي انحراف سطح الأرض عن الخط المستقيم الذي يمر عبر الأوتاد المجاورة) (0.5/3)*cos10° =0.16 م.

من أجل دقة تحديد حجم التربة المنقولة، فإن المنطقة التي تشغلها تفاصيل الإغاثة غير المحسوبة مهمة أيضًا. لنفترض أنه في مربع مساحته 20 × 20 م بين زوجين من الأوتاد يوجد تحدب أسطواني يبلغ أقصى ارتفاع له 0.15 م، ومن السهل حساب أن عدم أخذ ذلك في الاعتبار عند تمثيل هذا السطح بمثلثين فقط سيؤدي إلى خطأ حوالي 40 م3. ليس كثيرًا، ولكن بالنسبة لقطعة أرض مساحتها هكتار واحد، تقع على تل أو الجزء العلوي (المحدب عادةً) من المنحدر، تحصل على 40 * 25 = 1000 متر مكعب من التربة الزائدة. إذا قمت بتركيب الأوتاد مرتين (أي كل 10 أمتار)، فإن الخطأ سينخفض ​​أربعة أضعاف ليصل إلى 250 مترًا مكعبًا لكل هكتار. يمكن أخذ هذا العامل في الاعتبار مسبقًا، نظرًا لأن الأشكال الإيجابية للإغاثة المسطحة عادة ما يكون لها شكل محدب، في حين أن الأشكال السلبية لها شكل مقعر. إذا كانت المنطقة المراد مسحها تحتوي على بيانات تقريبية عن التضاريس، فيمكن بسهولة حساب نصف قطر انحناء السطح والكثافة المطلوبة للأوتاد من قيم الخطوط الكنتورية أو الارتفاعات الفردية.

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

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

ملكيات:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تين. 3

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

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

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

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

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

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

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

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

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

الشكل 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

يتم تحديد زاوية القطعة OP مع الأفقي بالمساواة

(9.7.8)

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

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

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

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

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

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

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

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

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

أرز. 9.7.13. لا يمكنك بناء مثلثات في هذه الزاوية.

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

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

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

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

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

لنقم ببناء مثلثات عند النقطتين OCF وCEF وبين النقطتين O وC من منطقة العمل، ندرج نقاط المضلع الداخلي، بدءًا من النقطة F وتنتهي بالنقطة E. وبالتالي، سنقوم بتقسيم منطقة العمل على مقطع OS، وكسر المضلع الداخلي على الجزء EF وتوحيدهم مع قطاعات الاتحاد الأوروبي.

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

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

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

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

أرز. 9.7.16. لا يمكنك بناء مثلثات في هذه الزاوية.

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

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

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

تثليث الجسم.

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

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

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

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

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

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

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

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

أرز. 1

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

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

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

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

أرز. 2

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

أرز. 3

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

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

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

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

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

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

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

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

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

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

قائمة * (النقطة s، int n) (النقطة p؛ القائمة * المثلثات = قائمة جديدة ; قاموس frontier(edgeCmp); Edge *e = hullEdge(s, n); frontier.insert(e); بينما (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(frontier, e ->dest, p); مثلثات->insert(triangle(e->org, e->dest, p)); ) حذف e;) إرجاع المثلثات; )

أرز. 4

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

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->ORG) العودة 1؛ إذا (a->org > b->org) تُرجع 1؛ إذا (أ->ديست< b->ديست) عودة -1؛ إذا (a->dest > b->dest) يُرجع 1؛ العودة 0؛ )

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

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

أرز. 5

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

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

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

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

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

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

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

,

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

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

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

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

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

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

كيف أقرب إلى 1، يتم أخذ المزيد من النقاط ذات الأوزان الأعلى في الاعتبار.

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

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

عيب:

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

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

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

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

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

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

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

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

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

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

هيكل العرض:

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

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

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

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

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

الجزء الداخلي من الدائرة المحيطة بأي مثلث لا يشمل نقاط المثلثات الأخرى. تم بناؤه بالطريقة الوحيدة.

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

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

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

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

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

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

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

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

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

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

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