مثلث سازی فضایی دلونی

مسئله ساخت شبکه ای از مثلث های غیر همپوشانی یکی از مسائل اساسی در هندسه محاسباتی است و به طور گسترده در گرافیک کامپیوتری و سیستم های اطلاعات جغرافیایی برای مدل سازی سطح و حل مسائل فضایی استفاده می شود.

مسئله ساخت شبکه ای از مثلث های غیر همپوشانی برای اولین بار در سال 1934 در کار ریاضیدان شوروی B.N. Delone مطرح شد که شرایط مربوطه را فرموله کرد.

در ریاضیات، وظیفه ساخت مثلث از نقاط داده شده، وظیفه اتصال آنها به صورت جفت توسط قطعات غیر متقاطع است به طوری که شبکه ای از مثلث ها تشکیل شود. عناصر اصلی آن عبارتند از (شکل 5.3): گره ها (راس مثلث ها)، لبه ها (اضلاع) و وجه ها (خود مثلث ها). مثلث ساخته شده می تواند محدب باشد (اگر یک چند ضلعی حداقلی باشد که ناحیه مدل سازی را پوشش می دهد)، غیر محدب (اگر مثلث محدب نباشد) و بهینه (اگر مجموع طول تمام یال ها حداقل باشد).

شبکه ای از این مثلث ها در صورتی که شرایط خاصی را برآورده کند، مثلث دلونی نامیده می شود:

هیچ یک از نقاط اصلی در داخل دایره محصور شده در اطراف هر مثلث قرار نمی گیرد (شکل 5.3).

مثلث محدب است و شرایط Delaunay فرموله شده در بالا را برآورده می کند.

مجموع حداقل زوایای همه مثلث ها حداکثر همه مثلث های ممکن است.

مجموع شعاع‌های دایره‌های توصیف شده در اطراف مثلث‌ها در بین تمام مثلث‌های ممکن حداقل است.

اولین معیار از معیارهای بالا برای ساخت مثلث دلونی که دایره ای نام دارد، یکی از معیارهای اصلی است و برای هر جفت مثلث با وجه مشترک بررسی می شود. تفسیر ریاضی معیار از شکل 1 به دست می آید. 5.3:

(5.2)

راه‌های زیادی برای ساخت مثلث دلونی وجود دارد که یکی از محبوب‌ترین آنهاست اخیراروش های ساخت شبکه مثلثی در بسیاری از سیستم های GIS برای ساخت مدل های امدادی استفاده می شود.

هنگامی که در فضای دو بعدی اعمال می شود، به صورت زیر فرموله می شود: اگر هیچ یک از رئوس در داخل هیچ یک از دایره های شرح داده شده در اطراف مثلث های تشکیل شده قرار نگیرد، سیستمی از مثلث های به هم پیوسته غیر همپوشانی کوچکترین محیط را دارد (شکل 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)

سپس شرط دلون برای فقط زمانی برآورده می شود که برای هر نقطه مثلثی دیگری باشد:

(x 0 - x C) 2 + (y 0 - y C) 2 ≥ r 2 . (5.7)

در حال حاضر الگوریتم های زیادی برای ساخت مثلث دلونی وجود دارد. بسیاری از الگوریتم‌های معروف از تعریف مثلث‌سازی Delaunay به عنوان یک ویژگی مثلث‌سازی ثانویه استفاده می‌کنند. بنابراین، نقاط ضعف زیر در این گونه الگوریتم ها ذکر شده است:

- الگوریتم ها از توابع مثلثاتی محاسبه شده به طور مداوم استفاده می کنند که به طور چشمگیری روند را کند می کند.

- هنگام مطالعه رابطه بین نقاط و بخش پایه، زوایای بسیار کوچکی ایجاد می شود و هنگام استفاده توابع مثلثاتیبه دلیل دقت محدود نمایش داده ها در یک کامپیوتر، خطر ناپدید شدن سفارش و تقسیم بر 0 وجود دارد.

شناخته‌شده‌ترین محصولات نرم‌افزاری مثلث‌سازی دلونی را با استفاده از قضیه توپ خالی به عنوان اصل اصلی و اولیه برای ساخت مثلث می‌سازند. الگوریتم به شکل زیر است:

- کل مجموعه نقاط به مثلث تقسیم می شود، یعنی. ترکیبی از سه نقطه ایجاد می شود.

- برای هر ترکیب، دایره محدود شده و مختصات مرکز آن پیدا می شود.

- اگر در داخل دایره ترکیب فعلی یک نقطه باقی نمانده باشد، این ترکیب یک مثلث است - بخشی از مثلث دلون.

از مزایای این الگوریتم می توان به موارد زیر اشاره کرد:

- عدم استفاده از توابع مثلثاتی، که روند ساخت و ساز را کند نمی کند.

- ساخت مستقیم مثلث دلونی، بدون هیچ گونه ساخت و ساز اولیه.

- سادگی تمامی محاسبات و تبدیل ها؛

- در نتیجه، شبکه مثلثی به جای خطوط منفرد، با مثلث های زیادی نشان داده می شود.

مثلثی که به این ترتیب ساخته شده است، مبنای هندسی ساخت خطوط ایزوله است.

الگوریتم های ساخت مثلث دلونی را می توان به چند گروه تقسیم کرد که در ساختار داده های ورودی استفاده شده، حجم عملیات محاسباتی، مقدمات اولیه و غیره متفاوت است. اجازه دهید برخی از آنها را در نظر بگیریم.

الگوریتم های ادغام شامل تقسیم مجموعه ای از نقاط منبع به زیر مجموعه ها، ساختن یک مثلث روی هر یک از آنها و سپس ترکیب آنها در یک شبکه واحد است. ماهیت یکی از این الگوریتم ها به موارد زیر خلاصه می شود.

مجموعه ای از نقاط اولیه توسط خطوط عمودی به دو یا چند قسمت تقسیم می شود و پس از آن هر یک از آنها با خطوط افقی و عمودی به قسمت های تقریباً مساوی تقسیم می شوند. در نتیجه، کل منطقه نقاط شروع به سه یا چهار نقطه اولیه تقسیم می شود (شکل 2.4) که در امتداد آنها یک یا دو مثلث ساخته شده است.

ادغام این مثلث ها در یک شبکه واحد با ساخت دو خط مبنا انجام می شود (P 0 P 1 و P 2 P 3، برنج 5.7.a)، رسم دایره‌هایی با شعاع متغیر با مرکزیت عمود بر خط پایه (شکل 5.7، b)، جستجوی گره‌ای که روی دایره می‌افتد (نقطه) الف، برنج 5.7. ج) و ساخت مثلث جدید (P 0 P 1 A).در این مورد، ممکن است لازم باشد یک مثلث موجود را حذف کنید (به عنوان مثال، P 0 AB).

الگوریتم‌های تکراری مبتنی بر ایده اضافه کردن متوالی نقاط به یک مثلث نیمه ساخته شده با بهبود و بازسازی همزمان آن مطابق با معیارهای دلون هستند. در نمای کلیآنها چندین مرحله را شامل می شوند و به ساختن یک مثلث در سه مرحله اول ختم می شوند نقاط شروعو بررسی چندین گزینه برای قرار دادن نقطه بعدی. به طور خاص، گزینه هایی برای قرار گرفتن آن در خارج از مرز منطقه مدل سازی، روی یک گره یا لبه موجود، داخل یک مثلث ساخته شده و غیره در نظر گرفته می شود. سه و غیره؛ پس از آن مثلث های حاصل از نظر انطباق با شرط دلون و بازسازی های لازم بررسی می شوند.

الگوریتم‌های دو گذر ابتدا شامل ساختن یک مثلث‌بندی با نادیده گرفتن شرایط دلون و سپس بازسازی آن مطابق با این شرایط می‌شوند. نمونه ای از کاربرد الگوریتم در شکل 1 نشان داده شده است. 5.8.

برای نزدیک‌تر کردن مدل برجسته ایجاد شده به مدل واقعی، عناصر اضافی به آن وارد می‌شوند تا اطمینان حاصل شود که عناصر ساختاری خطی و منطقه‌ای آن در نظر گرفته شده و نمایش داده می‌شوند. چنین عناصر اضافی خطوط ساختاری هستند که به طور گسترده در توپوگرافی مورد استفاده قرار می گیرند که "اسکلت برجسته" را تعریف می کنند: حوضه های آبخیز، تالوگ ها، پشته ها، صخره ها، تاقچه ها، دریاچه ها، دره ها، خطوط ساحلی، مرزهای سازه های مصنوعی و غیره که مجموع آنها نوعی ایجاد می کند. قاب برای مثلث دلونی. این خطوط ساختاری به عنوان لبه‌های مثلث وارد مثلث می‌شوند که به مدل‌سازی عناصر برجسته واقعی در پس‌زمینه ناهمواری عمومی سطح زمین دست می‌یابد. چنین لبه هایی ساختاری (ثابت، غیر قابل تنظیم) نامیده می شوند، لبه های مثلث های دیگر را قطع نمی کنند و متعاقباً تغییر نمی کنند.

در صورتی که شرایط دلونی برای هر جفت مثلث مجاور که با خطوط شکست از هم جدا نشده باشند، مشکل ایجاد یک مدل سطحی با در نظر گرفتن خطوط شکست، مثلث دلونی مقید نامیده می شود. محققان معتقدند موثرترین راه ساختن چنین مثلثی با استفاده از الگوریتم های تکراری است.

قطعه ای از مثلث دلونی با عناصر اضافی موجود در آن در شکل نشان داده شده است. 5.9، که در آن گره ها، لبه ها، لبه ها و خطوط ساختاری در سمت راست و خطوط ساختاری زمین (خطوط ساحلی، لبه های دره و غیره) و نقاط با علائم شناخته شده در سمت چپ نشان داده شده اند.

الگوریتم‌های ساخت مثلث دلونی با نمایش واقعی یا صحیح مختصات گره‌ها پیاده‌سازی می‌شوند که می‌تواند سرعت و دقت پردازش را به میزان قابل توجهی افزایش دهد، اما مشکلات جستجو و حذف گره‌های تطبیق را ایجاد می‌کند.

مدل TIN به راحتی با جابجایی گره ها، درج گره های جدید، حذف موارد موجود، تغییر موقعیت یک یا چند یال، معرفی خطوط ساختاری جدید و غیره قابل ویرایش است. چنین تغییراتی همیشه بر گروه کوچکی از مثلث های مجاور تأثیر می گذارد، نیازی به بازسازی مجدد نیست کل شبکه و با اشاره مکان نما به عنصر مربوطه به صورت آنلاین انجام می شوند.

در مورد دقت:

با قرار دادن پیکت ها بر روی عناصر برجسته برجسته (مثلاً حوضه های آبخیز و تالوگ ها)، عناصر کوچکتر را در شکاف ها نادیده می گیریم. هنگام ساخت خطوط کانتور1 در امتداد چنین لبه های مثلث، خطایی رخ می دهد که به میزان ناهمواری زمین و زاویه شیب زمین بستگی دارد. به عنوان مثال، میانگین خطا در نقشه برداری نقش برجسته نباید از 1/3 سطح مقطع در زوایای شیب سطحی از 2 تا 10 درجه بیشتر شود. می توان محاسبه کرد که با یک بخش تسکین 0.5 متر، حداکثر مقدار ناهمواری از دست رفته (یعنی انحراف سطح زمین از یک خط مستقیم که از میان پایه های مجاور عبور می کند) نباید از (0.5/3) * cos10 درجه تجاوز کند. = 0.16 متر

برای دقت در تعیین حجم خاک حمل شده، مساحت اشغال شده توسط جزئیات امدادی به حساب نیامده نیز مهم است. فرض کنید در یک مربع 20x20 متری بین دو جفت پیکت یک محدب استوانه ای با حداکثر ارتفاع 0.15 متر وجود دارد که محاسبه نکردن آن هنگام نمایش این سطح تنها با دو مثلث به آسانی منجر می شود خطای تقریباً 40 متر مکعب. نه چندان، اما برای یک قطعه 1 هکتاری، واقع در یک تپه یا قسمت بالایی (معمولاً محدب) شیب، 40 * 25 = 1000 متر مکعب خاک اضافی دریافت می کنید. اگر دوبار بیشتر (یعنی هر 10 متر) پیکت بردارید، خطا چهار برابر شده و به 250 متر مکعب در هکتار می رسد. این عامل را می توان از قبل در نظر گرفت، زیرا اشکال مثبت نقش برجسته معمولاً شکل محدب دارند، در حالی که اشکال منفی شکل مقعر دارند. اگر منطقه مورد بررسی دارای داده های تقریبی در مورد نقش برجسته باشد، شعاع انحنای سطح و تراکم مورد نیاز پیکت ها را می توان به راحتی از مقادیر خطوط کانتور یا ارتفاعات فردی محاسبه کرد.

تعاریف و ویژگی های اساسی

مثلث یک نمودار مسطح است که نواحی داخلی آن همه مثلث هستند.

خواص:

· مثلث Delaunay یک به یک با نمودار Voronoi برای همان مجموعه نقاط مطابقت دارد.

در نتیجه: اگر هیچ چهار نقطه روی یک دایره قرار نگیرد، مثلث دلونی منحصر به فرد است.

· مثلث سازی Delaunay حداقل زاویه را در بین تمام زوایای تمام مثلث های ساخته شده به حداکثر می رساند و در نتیجه از مثلث های "نازک" اجتناب می کند.

· مثلث سازی دلونی مجموع شعاع کره های محاطی را به حداکثر می رساند.

· مثلث سازی Delaunay عملکرد گسسته دیریکله را به حداقل می رساند.

· مثلث سازی Delaunay حداکثر شعاع حداقل کره محیط را به حداقل می رساند.

· مثلث Delaunay در صفحه دارای حداقل مجموع شعاع های دایره های توصیف شده در اطراف مثلث در بین تمام مثلث های ممکن است.

شکل 1. مثلث بندی.

مثلث محدب مثلثی است که حداقل چند ضلعی که همه مثلث ها را در بر می گیرد محدب است. مثلثی که محدب نباشد غیر محدب نامیده می شود.

مسئله ساخت مثلث از یک مجموعه معین از نقاط دو بعدی را مسئله اتصال می گویند امتیاز داده شدهقطعات غیر متقاطع به طوری که یک مثلث تشکیل می شود.

اگر هیچ یک از نقاط مثلث داده شده در داخل دایره محصور شده در اطراف هر مثلث ساخته شده قرار نگیرد، مثلث بندی شرط دلونی را برآورده می کند.

یک مثلث اگر محدب باشد و شرط دلونی را برآورده کند، مثلث دلونی نامیده می شود.

شکل 2. مثلث سازی دلون.

روش توپ خالی دلون. ساخت و ساز در حالت کلی

بیایید از یک توپ خالی استفاده کنیم که آن را حرکت می دهیم و اندازه آن را تغییر می دهیم تا بتواند نقاط سیستم (A) را لمس کند اما همیشه خالی بماند.

بنابراین، بیایید در سیستم نقاط (A) قرار دهیم. توپ خالیدلوني اگر توپی به اندازه کافی کوچک انتخاب کنید، همیشه این امکان وجود دارد. بیایید شروع به افزایش شعاع آن کنیم و مرکز توپ را در جای خود بگذاریم. در نقطه ای سطح توپ با نقطه ای از سیستم (A) برخورد می کند. این قطعا اتفاق خواهد افتاد، زیرا هیچ فضای خالی بی نهایت بزرگی در سیستم ما وجود ندارد. به شعاع توپ خالی ادامه می دهیم تا نقطه i روی سطح آن باقی بماند. برای انجام این کار، باید مرکز توپ را از نقطه i حرکت دهید. دیر یا زود توپ با سطح خود به نقطه دیگری در سیستم (A) خواهد رسید.

شکل 3

سیمپلکس های Delaunay فضا را بدون شکاف یا همپوشانی پر می کنند.

کره توصیف شده هر سیمپلکسی حاوی نقاط دیگری از سیستم در درون خود نیست.

بگذارید این نقطه j باشد. بیایید به افزایش شعاع توپ خود ادامه دهیم و هر دو نقطه را روی سطح آن نگه داریم. با افزایش توپ، به نقطه سوم سیستم یعنی نقطه k می رسد. در حالت دو بعدی، "دایره خالی" ما در این لحظه ثابت می شود، یعنی. افزایش بیشتر شعاع آن با خالی نگه داشتن دایره غیرممکن خواهد بود. در همان زمان، ما یک پیکربندی دو بعدی ابتدایی از سه نقطه (i، j، k) را شناسایی می کنیم، که یک مثلث خاص را تعریف می کند، که ویژگی آن این است که هیچ نقطه دیگری از سیستم (A) در داخل دایره دایره آن وجود ندارد. در فضای سه بعدی، توپ با سه نقطه تعریف نمی شود. بیایید به افزایش شعاع آن ادامه دهیم، و هر سه نقطه موجود در سطح آن را حفظ کنیم. این کار تا زمانی امکان پذیر خواهد بود که سطح توپ به نقطه چهارم l سیستم برسد. پس از این حرکت و رشد توپ خالی غیرممکن خواهد شد. چهار نقطه یافت شده (i,j,k,l) ​​رئوس چهار وجهی را مشخص می کند که با این واقعیت مشخص می شود که در داخل کره محصور آن هیچ نقطه دیگری از سیستم (A) وجود ندارد. به چنین چهار وجهی، دلاوی سیمپلکس می گویند.

در ریاضیات، یک سیمپلکس ساده ترین شکل در یک فضای یک بعد معین است: چهار وجهی - در فضای سه بعدی. مثلث - در دو بعد. یک سه (چهار) نقطه دلخواه از سیستم که در یک صفحه قرار ندارند همیشه یک سیمپلکس مشخص را تعریف می کنند. با این حال، تنها در صورتی یک سیمپلکس دلونی خواهد بود که کره توصیف شده آن خالی باشد. به عبارت دیگر، ساده سازی های دلونی با انتخاب خاصی از سه گانه (چهار برابر) نقاط در سیستم (A) تعیین می شوند.

ما یک Delaunay simplex ساخته‌ایم، اما با قرار دادن توپ خالی در مکان‌های مختلف و تکرار همان رویه، می‌توانیم موارد دیگری را تعریف کنیم. بیان شده است که مجموعه تمام ساده سازی های دلونی سیستم (A) فضا را بدون همپوشانی و شکاف پر می کند، یعنی. تقسیم فضا را اجرا می کند، اما این بار به چهار وجهی. این پارتیشن نامیده می شود کاشی کاری دلون(شکل 3).

کاربرد مثلث بندی دلونی

مثلث سازی های دلونی اغلب در فضای اقلیدسی استفاده می شود. درخت پوشا حداقل اقلیدسی تضمین شده است که بر روی مثلث دلونی قرار می گیرد، بنابراین برخی از الگوریتم ها از مثلث بندی استفاده می کنند. همچنین، از طریق مثلث سازی دلون، مسئله فروشنده دوره گرد اقلیدسی تقریباً حل می شود.

در درون یابی دوبعدی، مثلث سازی دلونه، صفحه را به ضخیم ترین مثلث های ممکن تقسیم می کند و از زوایای خیلی تیز و بیش از حد مبهم جلوگیری می کند. با استفاده از این مثلث ها می توانید به عنوان مثال درون یابی دو خطی بسازید.

یکی دیگر از مشکلات رایج در ژئوانفورماتیک، ساخت نوردهی شیب است. در اینجا لازم است جهت های غالب دامنه ها را با جهت اصلی تعیین کنیم و سطح را به مناطقی که در آن جهت خاصی غالب است تقسیم کنیم. از آنجایی که تعیین نوردهی برای نواحی افقی سطح معنی ندارد، مناطقی که افقی هستند یا شیب کمی دارند به یک منطقه جداگانه اختصاص داده می شوند، به عنوان مثال.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

شکل 4.

مشکل محاسبه نوردهی شیب معمولاً برای تجزیه و تحلیل روشنایی زمین استفاده می شود. در این رابطه، اغلب نیاز به در نظر گرفتن موقعیت فعلی خورشید وجود دارد، یعنی. نوردهی به عنوان جهت بین حالت عادی به مثلث و جهت به خورشید محاسبه می شود.

بنابراین، هر مثلث مثلث را می توان بر اساس اصل تعلق به یک منطقه خاص طبقه بندی کرد. پس از این، فقط باید الگوریتم انتخاب منطقه را فراخوانی کنید.

مثلث سازی تقریب سطح یک جسم مدل شده توسط صفحات مثلثی است که از آن در فاصله ای بیش از مقدار مشخص شده 6 نیست. همه صفحات مثلثی باید به هم متصل شوند. بالای آنها روی سطح قرار دارد. کار با مجموعه ای از صفحات مثلثی راحت تر از یک سطح عمومی است. صفحات مثلثی را مثلث می نامیم. برای یک مثلث، فاصله تا یک نقطه معین یا نقطه تقاطع با یک خط معین در فضا به سرعت محاسبه می شود. مثلث بندی صورت ها برای درک بصری مدل هندسی انجام می شود، بنابراین اضلاع مثلث ها طوری انتخاب می شوند که چشم متوجه پیچ خوردگی ها نشود.

هنگام نمایش اجسام هندسی به‌وسیله مثلث بر روی سطوح پارامتریک سطوح، باید با محاسبه آرایه‌ای از نقاط در فضا و آرایه‌ای از نرمال‌ها به صورت‌های بدن در این نقاط، یک مثلث فضایی وجه‌های بدن با استفاده از آرایه‌ای ساخته شود. نقاط دو بعدی برای نمایش سریع اجسام، چهره آنها توسط صفحات مثلثی ساخته شده بر روی نقاط عادی برای تعیین رفتار پرتوهای نور در تعامل با چهره بدن مورد نیاز است. ترسیم تن در فصل های قبل و در این فصل با استفاده از مثلث انجام شده است.

در نتیجه مثلث‌سازی سطح، می‌خواهیم آرایه‌ای از نقاط دوبعدی در یک صفحه پارامتریک و آرایه‌ای از سه گانه اعداد صحیح داشته باشیم که تعداد نقاط اولین آرایه ذکر شده است. بنابراین، هر مثلث با سه عدد از رئوس خود در آرایه پارامتر نمایش داده می شود. برای هر نقطه دو بعدی حوزه پارامتریک، یک نقطه فضایی روی سطح و سطح نرمال در آن قابل محاسبه است. نقاط مکانی و نرمال ها را می توان در آرایه هایی مشابه آرایه نقطه ای دوبعدی ذخیره کرد.

بیایید به چند روش مثلث بندی نگاه کنیم. برای سطوح مسطح، روش های مثلث بندی مقرون به صرفه ای وجود دارد که در آن مثلث ها در نقاط مرزی سطح ساخته می شوند و نیازی به جستجوی نقاط داخل ناحیه پارامتری نیست.

مثلث سازی دلون.

بیایید قسمتی را در هواپیما در نظر بگیریم. اگر ناحیه ای را محدب می نامیم اگر هنگام حرکت در امتداد مرز آن فقط در یک جهت بچرخید (فقط به چپ یا فقط به راست). الگوریتم Delaunay می تواند برای مثلث بندی مناطق مسطح محدب استفاده شود. ما نمی‌توانیم مستقیماً از این الگوریتم برای مثلث‌بندی سطوح آزاد استفاده کنیم، اما از روش آن برای ساخت مثلث استفاده خواهیم کرد.

برنج. 9.7.1. منطقه محدب با نقاط داده شده در داخل

اجازه دهید یک منطقه دو بعدی محدب که توسط یک خط شکسته بسته محدود شده و مجموعه ای از نقاط در داخل این منطقه مشخص شود (شکل 9.7.1).

لازم است ناحیه مشخص شده را به مثلث هایی تقسیم کنیم که رئوس آن نقاط داده شده در داخل منطقه و رئوس خط شکسته محدود کننده آن است. مثلث ها نباید روی یکدیگر همپوشانی داشته باشند و اضلاع آنها فقط می توانند در رئوس یکدیگر را قطع کنند.

چندین مجموعه مختلف از مثلث ها را می توان برای پر کردن یک منطقه مشخص ساخت. در همه موارد، تعداد مثلث ها برابر است، که در آن K تعداد رئوس چندخط کران کننده است، I تعداد نقاط داده شده در داخل منطقه است.

برنج. 9.7.2. انتخاب نقطه سوم الگوریتم دلون

مثلث‌سازی یک منطقه، مثلث دلونی خواهد بود اگر هیچ رئوسی از مثلث‌های دیگر در داخل دایره توصیف‌شده در اطراف هر مثلث وجود نداشته باشد. مثلث سازی Delaunay مثلث هایی را تا حد امکان نزدیک به متساوی الاضلاع می سازد (اجازه ساخت مثلث های بی دلیل کشیده را نمی دهد).

می توان آن را متعادل نامید. اگر چهار راس روی یک دایره نباشد، مثلث دلونی منحصر به فرد خواهد بود.

بیایید مثلث Delaunay را در نظر بگیریم. رئوس چندخط محدود کننده ناحیه و نقاط داده شده در داخل منطقه را رئوس مثلث می نامیم. اضلاع مثلث ها را لبه می نامیم. از میان یال ها، بخش هایی از چند خط مرزی را انتخاب می کنیم که آن ها را لبه های مرزی می نامیم. بیایید تمام لبه های مرزی را طوری جهت دهیم که ناحیه محدب در سمت چپ هر یال قرار گیرد. اجازه دهید لازم باشد مثلثی بسازیم که ضلع آن لبه مرزی AB است که در شکل نشان داده شده است. 9.7.2.

از طریق رئوس A، B و هر رأسی که روی یک خط با آنها قرار نگیرد، می توان یک دایره رسم کرد. به عنوان راس سوم مثلث، ما راس V را انتخاب می کنیم، دایره مربوطه شامل رئوس دیگری در همان ضلع نسبت به قطعه AB که نقطه V روی آن قرار دارد، برای یک یال مرزی، در حالت کلی، یکی از این رئوس وجود ندارد پیدا شود. ما آن را نزدیکترین می نامیم. مرکز دایره ای که از نقاط A، B و V می گذرد در محل تلاقی عمود بر نقاط وسط قطعات AB، BV و VA قرار دارد. موقعیت مرکز دایره با پارامتر t از بخش MN، عمود بر لبه AB، از نظر طول مساوی و عبور از وسط لبه AB مشخص می شود.

برنج. 9.7.3. فرآیند مثلث سازی دلونی

برای همه رئوس که در سمت چپ قطعه AB قرار دارند، نزدیکترین راس دارای کوچکترین پارامتر t است. دایره مربوط به نزدیکترین راس شامل رئوس دیگری در سمت چپ قطعه AB نیست. بگذارید رئوس A، B و V به ترتیب با بردارهای شعاع دو بعدی توصیف شوند. بردار شعاع نقاط میانی قطعات AB و BV برابر خواهد بود

مقدار پارامتر t خط، مربوط به موقعیت مرکز دایره ای که از نقاط A، B و V می گذرد، برابر است با

برای نزدیکترین راس به سمت چپ قطعه AB، پارامتر t دارای حداقل مقدار است.

بیایید تمام لبه های مرزی را طوری جهت دهیم که ناحیه مثلثی در سمت چپ هر یک از آنها قرار گیرد. از هر لبه مرزی شروع به ساخت مثلث می کنیم. بیایید نزدیکترین راس را برای آن پیدا کنیم که دایره مربوطه آن راسهای دیگری را شامل نمی شود. اجازه دهید نزدیکترین راس V برای لبه مرزی AB پیدا شود سپس یک مثلث ABV می سازیم و یال AB را به دسته غیرفعال منتقل می کنیم. ما لبه ها و رئوس های غیرفعال را که در الگوریتم مثلث سازی شرکت نمی کنند فراخوانی می کنیم. اگر لبه BV در بین لبه های مرزی وجود نداشته باشد، یک یال مرزی جدید روی قطعه VB می سازیم. اگر در بین یال های مرزی یک یال BV وجود داشته باشد، آن را و راس B را به دسته غیرفعال منتقل می کنیم. اگر هیچ لبه VA در بین لبه های مرزی وجود نداشته باشد، یک لبه مرزی جدید روی قطعه AV می سازیم. اگر در بین یال های مرزی یک یال VA وجود داشته باشد، آن را و راس A را به دسته غیرفعال منتقل می کنیم. فرآیند مثلث سازی در شکل نشان داده شده است. 9.7.3.

برنج. 9.7.4. مثلث سازی دلون

وقتی تمام رئوس و یال ها غیرفعال می شوند، مثلث بندی را تمام می کنیم. نتیجه مثلث بندی یک ناحیه معین در شکل نشان داده شده است. 9.7.4.

مثلث بندی به روش تصحیح.

بیایید مثلث بندی یک سطح خاص را با یک دامنه مستطیلی برای تعریف پارامترها در نظر بگیریم. اجازه دهید فواصل پارامتری بین خطوط مجاور را مطابق با فرمول (9.4.7) برابر در نظر بگیریم.

اجازه دهید فواصل پارامتریک بین خطوط مجاور را مطابق با فرمول (9.4.8) برابر در نظر بگیریم.

با ساختن مورب در تمام سلول های مستطیلی، یک مثلث سطح را به دست می آوریم (مجموعه ای از مثلث ها را به دست می آوریم که شرایط را برآورده می کند). در شکل 9.7.5 مثلث بندی سطح چرخش را با استفاده از روش توصیف شده نشان می دهد.

اجازه دهید مثلث بندی یک سطح با یک مرز دلخواه را در نظر بگیریم. ما روش مثلث‌سازی را بر روی تصحیح خطوط مرزی مثلث‌سازی سطحی که در بالا توضیح داده شد با یک ناحیه مستطیلی برای تعیین پارامترها می‌سازیم.

برنج. 9.7.5. مثلث سازی یک سطح با دامنه مستطیلی برای تعریف پارامترها

اجازه دهید مرز سطح در حوزه تعریف پارامتر با چندین خطوط دو بعدی غیر متقاطع توصیف شود (2.12.7). یکی از کانتورها خارجی است و شامل خطوط باقی مانده است. برای جهت مثبت برای هر کانتور، جهتی را در نظر می گیریم که هنگام حرکت در امتداد، ناحیه تعریف سطح همیشه در سمت چپ کانتور باشد، زمانی که به سمت سطح عادی نگاه می کنیم. بیایید چند ضلعی ها را در جهت مثبت خطوط مرزی ناحیه تعریف سطح بسازیم. برای ساخت چند ضلعی های مرزی، باید در امتداد خطوط مرزی سطح با مقداری گام متغیر قدم بزنید و آرایه ای از نقاط دو بعدی را پر کنید که مختصات آن پارامترهای سطح هستند. ما یک چند ضلعی از نقاط روی صفحه پارامتری خواهیم ساخت، اما گام در هنگام حرکت از یک نقطه به نقطه دیگر از هندسه فضایی تعیین می شود، یعنی از این شرایط که انحراف قوس منحنی بین نقاط مجاور بیش از یک داده شده نباشد. ارزش ما مراحل پارامتری ساخت یک چند ضلعی برای منحنی مرزی سطح را با استفاده از فرمول (9.4.4) محاسبه می کنیم.

هر چند ضلعی از مجموعه ای منظم از نقاط دو بعدی تشکیل شده است. ما از چنین مناطقی به عنوان لبه های مرزی استفاده خواهیم کرد و نقاط چند ضلعی که یال ها بر روی آنها قرار دارند به عنوان رئوس مثلثی استفاده می شوند. از آنجایی که ناحیه تعیین پارامترهای سطح در سمت چپ چند ضلعی های مرزی قرار دارد، هنگام ساخت مثلث برای هر یال مثلث مرزی، باید به دنبال راس سوم مثلث در سمت چپ لبه باشید.

بیایید تعیین کنیم که کدام گره ها در داخل چند ضلعی های مرزی قرار دارند و کدام گره ها در مرز یا خارج از ناحیه تعریف سطح قرار دارند. با استفاده از این اطلاعات، سلول های شبکه مستطیلی را به دو گروه دسته بندی می کنیم. گروه اول شامل سلول هایی است که به طور کامل در منطقه ای قرار دارند که پارامترهای سطح تعیین می شوند (سلول ها نباید چند ضلعی های مرزی را لمس کنند). گروه دوم شامل سلول‌های باقی‌مانده (که خارج از ناحیه تعریف سطح قرار دارند یا با چندضلعی‌های مرزی قطع شده‌اند) است.

برنج. 9.7.6. مثلث سازی سطحی ناتمام

در داخل هر خانه از گروه اول با استفاده از یک مورب دو مثلث می سازیم. بنابراین ما یک مثلث ناتمام دریافت می کنیم. نمونه ای از ساخت مثلث در سلول های گروه اول برای سطح چرخشی محدود شده توسط خطوط در شکل 1 نشان داده شده است. 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 ختم می شود. چند ضلعی داخلی در قطعه EF و آنها را با بخش های OF و EU یکی کنید.

برنج. 9.7.14. ساخت دو مثلث

برنج. 9.7.15. ادغام چند ضلعی های خارجی و داخلی

نتیجه ادغام در شکل نشان داده شده است. 9.7.15. البته قبل از ادغام چند ضلعی بیرونی و داخلی باید بررسی هایی انجام شود تا از صحت این عملیات اطمینان حاصل شود.

در مرحله بعد، به محدود کردن ناحیه کار به روشی که توضیح داده شد ادامه می دهیم تا زمانی که خود را در مجاورت یک منطقه داخلی دیگر قرار دهیم و آن را در منطقه کار قرار دهیم. در نتیجه، همه چند ضلعی های داخلی در چند ضلعی کار گنجانده می شوند که باید به سه نقطه آخر باریک شوند. در نتیجه، کل دامنه ضربی متصل برای تعیین پارامترهای سطح با مثلث پوشیده می شود.

برنج. 9.7.16. در این گوشه نمی توانید مثلث بسازید.

ممکن است شرایطی وجود داشته باشد که ساختن یک مثلث منفرد روی چند ضلعی های داده شده غیرممکن باشد. در شکل شکل 9.7.16 یک ناحیه محدود شده توسط دو چند ضلعی را نشان می دهد که هر کدام از چهار بخش تشکیل شده است. برای چند ضلعی بیرونی، نمی‌توانیم مثلث‌سازی را ادامه دهیم، زیرا چندضلعی داخلی در مسیر قرار دارد. در این حالت دو نقطه همسایه B و C از چند ضلعی را خواهیم یافت که می توانیم برای آنها یک مثلث HRV بسازیم. نقطه P به وسط ضلع BC کشیده شده و در فاصله ای از آن قرار دارد که مثلث جدید چند ضلعی ها را قطع نمی کند.

روش های دیگر مثلث بندی

راه های دیگری برای مثلث بندی وجود دارد. به عنوان مثال، پس از ساخت چند ضلعی های خطوط خارجی و داخلی ناحیه تعریف سطح، می توان استراتژی متفاوتی برای ساخت مثلث ها انتخاب کرد. گزینه دیگر ترکیب چند ضلعی های بیرونی و داخلی در یک چند ضلعی قبل از شروع مثلث سازی است. می‌توانید با استفاده از الگوریتم خاصی، نقاط داخل ناحیه تعریف پارامتر را ترسیم کنید و با استفاده از آنها و نقاط چندضلعی‌های مرزی، مثلث‌سازی دلونی را انجام دهید. الگوریتم هایی وجود دارند که ابتدا مثلث های بزرگ می سازند و سپس آنها را به اندازه های قابل مدیریت تقسیم می کنند.

مثلث بندی بدن.

مثلث یک جسم مجموعه ای از مثلث هاست که از مثلث سازی سطوح صورت های آن به دست می آیند. مثلث‌سازی سطوح منفرد با مثلث‌سازی چهره‌های بدن متفاوت است، زیرا در حالت دوم، چندضلعی‌های مرزی برای وجوه مجاور باید سازگار باشند (شکل 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 را در بر می گیرد. قطعات خط مستقیم مثلث ها را نزدیک می کنند، ما آنها را دنده در نظر می گیریم. در شکل شکل 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 را در نظر می گیریم. از آنجایی که همه آنها رئوس یک چند ضلعی محدب هستند، چنین مثلثی به 2 - n (n - i) منجر می شود. (تأیید این امر دشوار نیست و علاوه بر این، می توان نشان داد که هر مثلثی دلخواهیک چند ضلعی ضلع m - محدب یا غیر محدب - حاوی m - 2 مثلث است. حالا بیایید بررسی کنیم که با اضافه کردن نقاط داخلی i باقیمانده، هر بار یکی، چه اتفاقی برای مثلث می افتد. ما ادعا می کنیم که با جمع هر یک از این نقاط، تعداد مثلث ها دو تا افزایش می یابد. هنگام اضافه کردن یک نقطه داخلی، ممکن است دو وضعیت ایجاد شود که در شکل 1 نشان داده شده است. 2. ابتدا ممکن است نقطه در داخل یک مثلث باشد و سپس سه مثلث جدید جایگزین چنین مثلثی شود. ثانیاً، اگر نقطه ای با یکی از یال های مثلثی منطبق باشد، هر یک از دو مثلث مجاور این یال با دو مثلث جدید جایگزین می شود. نتیجه این است که پس از جمع کردن تمام نقاط i، تعداد کل مثلث ها (n - i - 2) + (2i) یا به سادگی n + i - 2 خواهد بود.

برنج. 2

در این بخش، الگوریتمی برای تولید نوع خاصی از مثلث‌سازی به نام مثلث‌سازی Delaunay ارائه می‌کنیم. این مثلث به خوبی متعادل است به این معنا که مثلث های تشکیل شده تمایل به متساوی الاضلاع دارند. به عنوان مثال، مثلث نشان داده شده در شکل. 1a را می توان به نوع مثلث سازی دلون نسبت داد و در شکل 1. مثلث 1b شامل چندین مثلث بسیار کشیده است و نمی توان آن را به نوع Delaunay نسبت داد. در شکل شکل 3 نمونه ای از مثلث سازی دلونی را برای مجموعه ای از تعداد زیادی نقطه نشان می دهد.

برنج. 3

برای تشکیل مثلث دلونی، به چندین تعریف جدید نیاز داریم. اگر دایره ای وجود داشته باشد که تمام نقاط مجموعه روی آن قرار گیرند، مجموعه ای از نقاط دایره ای در نظر گرفته می شود. چنین دایره ای برای مجموعه ای از نقاط مشخص خواهد شد. دایره محصور مثلث از هر سه رأس (غیر خطی) آن می گذرد. گفته می شود که یک دایره نسبت به یک مجموعه معین از نقاط S بدون نقطه خواهد بود اگر هیچ نقطه ای از مجموعه S در داخل دایره وجود نداشته باشد، اما، نقاطی از مجموعه S را می توان روی دایره ای قرار داد بی امتیاز ترین

اگر دایره دایره هر مثلث خالی از نقطه باشد، مثلث بندی مجموعه ای از نقاط S، مثلث دلونی خواهد بود. در نمودار مثلثی شکل. شکل 1a دو دایره را نشان می دهد که به وضوح حاوی نقاط دیگری در داخل آنها نیستند (می توانید دایره هایی برای مثلث های دیگر بکشید تا مطمئن شوید که آنها نیز از نقاط مجموعه آزاد نیستند). این قانون در نمودار شکل 1 رعایت نشده است. 16 - یک نقطه از مثلث دیگر در داخل دایره ترسیم شده قرار می گیرد، بنابراین، این رگه بندی از نوع دلونه نیست.

دو فرض را می توان در مورد نقاط مجموعه S برای ساده سازی الگوریتم مثلث بندی در نظر گرفت. اولاً، برای اینکه مثلث‌سازی اصلاً وجود داشته باشد، باید فرض کنیم که مجموعه S حداقل شامل سه نقطه است و آنها هم خط نیستند. ثانیا، برای اینکه یک مثلث دلونی منحصر به فرد باشد، لازم است که هیچ چهار نقطه از مجموعه S روی یک دایره دور یکسان قرار نگیرد. به راحتی می توان فهمید که بدون چنین فرضی مثلث دلونی منحصر به فرد نخواهد بود، زیرا 4 نقطه در یک دایره محدود به ما امکان می دهد دو مثلث دلونی متفاوت را درک کنیم.

الگوریتم ما با رشد مداوم مثلث فعلی یک مثلث در یک زمان کار می کند. در ابتدا، مثلث فعلی از یک لبه پوسته در انتهای الگوریتم تشکیل شده است، مثلث فعلی تبدیل به یک مثلث دلونی می شود. در هر تکرار، الگوریتم به دنبال مثلث جدیدی می گردد که به آن متصل می شود مرزمثلث بندی فعلی

تعریف مرز بستگی به این دارد نمودار زیرطبقه بندی لبه های مثلث دلونی نسبت به مثلث فعلی. هر لبه می تواند باشد خوابیدن, زندهیا مرده:

• دنده های خواب: یک یال از مثلث سازی دلونی در صورتی که هنوز توسط الگوریتم شناسایی نشده باشد، غیر فعال است.
• دنده های زنده: دنده در صورت یافتن زنده است ولی فقط یک ناحیه مجاور آن مشخص است.
• دنده های مرده: لبه ای مرده محسوب می شود که پیدا شود و هر دو ناحیه مجاور آن مشخص باشد.

در ابتدا، تنها لبه متعلق به لوب محدب i زنده است - یک صفحه نامحدود در مجاورت آن قرار دارد و تمام لبه های دیگر خاموش هستند. همانطور که الگوریتم کار می کند، لبه ها از حالت خواب به زنده به مرده تبدیل می شوند. مرز در هر مرحله از مجموعه ای از لبه های زنده تشکیل شده است.

در هر تکرار، هر یک از یال‌های مرز انتخاب می‌شود و تحت پردازش قرار می‌گیرد که شامل جستجوی ناحیه ناشناخته‌ای است که یال e به آن تعلق دارد نقاط انتهایی لبه e و برخی از راس سوم v، سپس لبه e مرده می شود، زیرا هر دو ناحیه مجاور آن اکنون شناخته شده اند. هر یک از دو یال دیگر مثلث t به حالت زیر منتقل می شود: از خواب به زنده یا از زنده به مرده. در اینجا راس v فراخوانی خواهد شد مزدوج کردنبا لبه e در غیر این صورت، اگر منطقه ناشناخته یک صفحه بی نهایت باشد، یال e به سادگی می میرد. در این حالت لبه e دارای راس مزدوج نیست.

در شکل شکل 4 عملکرد الگوریتم را نشان می دهد، جایی که عمل از بالا به پایین و شکوه به سمت راست انجام می شود. حاشیه در هر مرحله با یک خط ضخیم برجسته می شود.

این الگوریتم در برنامه delaunayTriangulate پیاده سازی شده است. به برنامه آرایه‌ای از n نقطه داده می‌شود و فهرستی از مثلث‌هایی را که نشان‌دهنده مثلث دلونی هستند، برمی‌گرداند. پیاده سازی از کلاس و کلاس های لیست دایره ای از بخش ساختار داده های هندسی استفاده می کند. کلاس Dictionary می تواند هر دیکشنری باشد که از عملیات مورد نیاز پشتیبانی می کند. برای مثال، می‌توانید #define Dictionary RandomizedSearchTree را لغو کنید.

فهرست کنید * (نقطه s، int n) (نقطه p؛ فهرست *مثلث = لیست جدید ; فرهنگ لغت

مرز (edgeCmp)؛

لبه *e = hullEdge(s, n);

Int edgeCmp (Edge *a، Edge *b) (اگر (a->org< b->org) بازگشت 1;< b->if (a->org > b->org) return 1;

اگر (a->dest

dest) بازگشت -1;

if (a->dest > b->dest) return 1;

بازگشت 0; ) چگونه حاشیه از یک مرحله به مرحله دیگر تغییر می کند، و چگونه تابع updateFrontier فرهنگ لغت لبه حاشیه را تغییر می دهد تا این تغییرات را منعکس کند؟ هنگامی که یک مثلث جدید t به مرز متصل می شود، حالات سه یال مثلث تغییر می کند. لبه مثلث t مجاور مرز از زنده به مرده تغییر می کند. تابع updateFrontier می‌تواند این لبه را نادیده بگیرد زیرا با فراخوانی تابع removeMin باید از فرهنگ لغت حذف شود. هر یک از دو یال باقیمانده مثلث t وضعیت خود را از حالت خواب به زنده تغییر می دهد، اگر قبلاً در فرهنگ لغت ثبت نشده باشد، یا از زنده به مرده، اگر لبه قبلاً در فرهنگ لغت وجود دارد. در شکل 5 هر دو مورد را نشان می دهد. مطابق شکل، لبه زنده af را پردازش می کنیم و پس از اینکه متوجه شدیم نقطه b مزدوج آن است، مثلث afb را به مثلث فعلی اضافه می کنیم. سپس در دیکشنری به دنبال edge fb می گردیم و چون هنوز وجود ندارد و برای اولین بار کشف می شود، حالت آن از حالت Sleep به زنده تغییر می کند. برای ویرایش فرهنگ لغت، لبه fb را می چرخانیم تا ناحیه مجاور آن ناشناخته در سمت راست آن قرار گیرد و این لبه را در فرهنگ لغت بنویسیم. سپس لبه ba را در فرهنگ لغت پیدا خواهیم کرد - از آنجایی که در آن است، از قبل زنده است (ناحیه شناخته شده مجاور آن مثلث abc است). از آنجایی که منطقه ناشناخته برای آن، مثلث afb، به تازگی کشف شده است، این لبه از فرهنگ لغت حذف شده است.

تابع updateFrontier فرهنگ لغت مرزی را ویرایش می کند که در آن وضعیت لبه از نقطه a به نقطه b تغییر می کند:

برنج. 5< 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]); }

UpdateFrontier باطل (Dictionary

&frontier، Point &a، Point &b) (Edge *e = New Edge (a, b)؛ if (frontier.find (e)) frontier.remove(e); else (e->flip(); frontier.insert( ه))

تابع hullEdge یک لبه بدنه را در بین n نقطه در آرایه s پیدا می کند. این تابع در واقع از مرحله اولیه سازی و اولین تکرار روش بسته بندی هدیه استفاده می کند:

لبه *hullEdge (نقطه s، int n) (int m = 0; برای (int i = 1; i
تابع مثلث به سادگی یک چند ضلعی را برای سه نقطه ای که به عنوان پارامتر به آن ارسال می شود تولید می کند و برمی گرداند: تابع مثلث به سادگی یک چند ضلعی را برای سه نقطه ای که به عنوان پارامتر به آن ارسال می شود تولید می کند و برمی گرداند:
چند ضلعی *مثلث (نقطه &a، نقطه &b، نقطه و ج) (چند ضلعی *t = چند ضلعی جدید؛ t->درج (a)؛ t->درج (b)؛ t->درج (c؛ بازگشت t؛)
مدل های GRID مدل هایی از سلول های معمولی هستند.
.

,

اجازه دهید سیستم مختصات معرفی شود

و
تابع مثلث به سادگی یک چند ضلعی را برای سه نقطه ای که به عنوان پارامتر به آن ارسال می شود تولید می کند و برمی گرداند:
,
- شبکه بیت.

- مقادیر کوانتیزه شده واقعی:

- پارامتر الگوریتم - تعداد نقاط، - وزن هر چه نقطه نزدیکتر باشد وزن آن بیشتر می شود.

- درجه فاصله (1 یا 2).

ضریب عادی سازی:

چگونه نزدیک به 1 امتیاز بیشتری با وزن بالاتر در نظر گرفته می شود.

این روش IDW است - طولانی است، برای هر t لازم است همسایگان پیدا شوند. مجموعه همسایگان را می توان به طور موثر پیدا کرد - نزدیکترین. هر نقطه یک "میخ" با ارتفاع مشخص تولید می کند. خیلی به بی نظمی در تعیین نقطه برای این کار بستگی دارد
یا
آن ها به بخش ها تقسیم شده و نقاطی در مجاورت ایجاد کنید.

مزیت- سادگی

نقص:

------بلیت 14. مدل حلبی. الگوریتم های مثلث سازی دلونی ------

1) مثلث سازی (قلع).

مثلث سازی- ساخت یک تابع در قالب مجموعه ای از توابع خطی تکه ای

مثلث سازی- درون یابی در یک منطقه محدب.

مثلث سازی- یک نمودار مسطح که تمام لبه های داخلی آن مثلث هستند. روشی برای نمایش فضا به شکل مثلث های مجاور یکدیگر بدون همپوشانی. مثلث سازی بر روی مجموعه ای از نقاط به روش های مختلفی ساخته می شود.

یک الگوریتم برای ساخت مثلث بهینه مورد نیاز است.

هواپیمایی که از 3 نقطه عبور می کند.

1) مثلثی را پیدا کنید که
;

2)
- معادله ای از هواپیما بسازید.

برای بررسی اینکه آیا نقاط داخل مثلث هستند یا نه، باید مقدار را در معادله خطوط - لبه های مثلث جایگزین کنید. اگر هر 3 معادله > 0 باشد، داخل.

ساختار ارائه:

هر مثلث شامل همان تعداد مثلث است.

، کجا - تعداد امتیازات داخلی
- تعداد امتیاز

مثلثی حریص.

تمام نقاط را با لبه ها به هم وصل می کنیم، حداقل را انتخاب می کنیم و آنها را به مثلث اضافه می کنیم. بعد، حداقل بعدی را که با موارد قبلی تلاقی نمی کند و غیره می گیریم. نتیجه مثلث بندی حریصانه است.

مثلث سازی دلون.

داخل دایره ای که دور هر مثلثی محصور شده است، نقاط مثلث های دیگر را شامل نمی شود. به تنها راه ساخته شده است.

تلنگر انتقال لبه ها است. این به شما امکان می دهد از مثلث سازی معمولی به مثلث سازی Delaunay بروید. برای بررسی اینکه آیا یک نقطه به یک دایره تعلق دارد: اگر را جایگزین کنید< R, то внутри.

شرایط دلون.

معادله دایره ای که از سه نقطه عبور می کند:

اگر کمتر از صفر باشد، خارجی، در غیر این صورت - داخلی.

- شرایط دلون.

الگوریتم ساخت مثلث دلونی:

1) اضافه کردن نقاط تحت بررسی- یک الگوریتم تکراری ساده:

یک مجموعه وجود دارد
به مثلث اضافه کنید، ساخت و ساز انجام می شود
تقسیم مثلث
بازسازی در مرحله صفر، ما 3-4 نقطه ساختگی را اضافه می کنیم، که بدیهی است که پاکت ما را پوشش می دهد، تمام نقاط داخل. سپس نقطه را پرتاب می کنیم، نگاه می کنیم که به کدام مثلث برخورد می کند، آن را به 3 تقسیم می کنیم، برای هر مثلث شرط Delaunay را بررسی می کنیم و یک انتقال لبه ها را انجام می دهیم. میانگین تعداد تغییر خطوط سه است.

پیچیدگی نظری

2) روش های شتاب.بر اساس نقاط وابسته آماری. مثلث بذر مثلثی است که نقطه قبلی در آن افتاد. سپس دو نقطه - قبلی و جدید را به هم وصل می کنیم.

از نقطه اول به نقطه دیگر می رویم.