الگوریتم Delaunay Triangulation برای تقسیم‌بندی مجموعه‌ای از نقاط در فضای دو بعدی به مثلث‌ها استفاده می‌شود. در این تقسیم‌بندی، مثلث‌ها به گونه‌ای ساخته می‌شوند که هیچ نقطه‌ای از مجموعه در داخل دایره محیطی که از سه راس مثلث تشکیل می‌شود، قرار نگیرد. به این ویژگی حجم Delaunay گفته می‌شود.
ویژگی ها:
- در این الگوریتم، هیچ یک از نقاط مجموعه نباید در دایره محیطی که به دور مثلث‌های ایجاد شده قرار دارد، واقع شود. این ویژگی باعث می‌شود که مثلث‌ها بهینه و متوازن باشند؛ به‌طوری که نه خیلی کشیده و نه خیلی کوچک هستند. این ویژگی به‌ویژه در مسائل هندسی و محاسباتی اهمیت دارد، زیرا دقت و صحت محاسبات را بهبود می‌بخشد.
- این الگوریتم به گونه ای نقاط را به هم متصل می کند که زاویه های مثلث ها تا حد امکان بزرگتر و متوازن باشند.
کاربردها:
- مدل سازی سطح زمین (DTM): در GIS، یکی از کاربردهای اصلی Delaunay Triangulation ایجاد مدل‌های دیجیتالی سطح زمین است. این مدل‌ها از نقاط ارتفاعی ساخته می‌شوند و برای نمایش و تحلیل دقیق‌تر سطح زمین استفاده می‌شوند.
- تحلیل جریان سیالات و آب های سطحی: در تحلیل‌های هیدرولوژیکی و مدل‌سازی جریان سیالات، Delaunay Triangulation به شبیه‌سازی جریان آب کمک می‌کند. این الگوریتم با تقسیم منطقه به مثلث‌های کوچک، امکان مدل‌سازی دقیق‌تر جریان سیالات را فراهم می‌آورد.
برای مثال، برای شناسایی بهترین مکان ساخت سد در نزدیکی رودخانه کارون، دسترسی به مدل دیجیتال ارتفاعی (DEM) منطقه در فاز اولیه تصمیم‌گیری اهمیت دارد. با وارد کردن نقاط جی‌پی‌اس برداشت‌شده و استفاده از ابزار Delaunay Triangulation، می‌توانیم DEM یا شبکه مثلثی (TIN) را برای تحلیل سطح زمین به‌دست آوریم. همچنین، می‌توانیم حریم رودخانه و ویژگی‌های طبیعی دیگر را در مدل تحلیل کنیم. در تصویر بالا، محدوده مثلث‌بندی‌شده با رنگ صورتی و نقاط ارتفاعی برداشت‌شده با نقاط قرمز نمایش داده شده است.
برای اجرای این ابزار، ابتدا مطابق با تصویر بالا از کمبوباکس layer، لایه نقطه‌ای مورد نظر که قرار است مثلث‌بندی شود را انتخاب می‌کنیم. پس از کلیک بر روی دکمه Run، مثلث‌بندی تشکیل می‌شود. این مثلث‌بندی را می‌توان به لایه‌های موجود اضافه کرد. برای این کار، مطابق با تصویر بالا، با انتخاب گزینه Save As، پنجره‌ای باز می‌شود که در آن باید Save as Layer را انتخاب کرده و لایه جدید به لایه‌های قبلی اضافه می‌شود.
نکته: عوارض ورودی در Delaunay Triangulation حتما باید نقطه ای باشند. عوارض خطی یا پلیگونی (مثل خطوط جاده، رودخانه‌ها، یا محدوده‌ها) معمولاً برای Delaunay Triangulation به‌طور مستقیم مناسب نیستند. اما می‌توان این عوارض را به نقاطی تبدیل کرد (مثلاً نقاط ابتدای هر خط یا گوشه‌های پلیگون‌ها) و سپس این نقاط را برای مثلث‌بندی استفاده کرد.