CBIR: Content Based Image Retrieval

مثلث‌ دیلانی (دلونی)

در ریاضیات و هندسه محاسباتی یک مثلث دیلانی برای یک مجموعه از نقاط به نام P در یک صفحه، یک مثلث‌بندی به نامDT(P) است به نحوی که هیچ یک از نقاط P درون هیچ‌ یک از دایره‌های محیطی مثلثهای DT(P) نباشد. این مثلث‌بندی کمینه‌ی زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری می‌کند. این مثلث‌بندی توسط بوریس دیلانی  در سال ۱۹۳۴ ابداع شده است[1]. برای چهار یا تعداد بیشتری نقطه روی یک دایره یکسان (به عنوان مثال راس های یک مستطیل) تثلیث دیلانی یکتا نیست : هر دو تثلیث ممکن که چهار ضلعی را به دو مثلث تقسیم کنند و شرط دیلانی حاصل شود به عنوان مثال فرض اینکه اگر تمام دایره های محیطی مثلث ها درون تهی باشند. با در نظر گرفتن کره های محاطی ایده ی تثلیث دیلانی به سه یا تعداد بیشتری بعد تعمیم می یابد. تعمیم به سیستم متریک نسبت به سیستم اقلیدسی ترجیح داده می‌شود ولی در این موارد (اقلیدسی) تثلیث دیلانی الزاماً وجود ندارد یا یکتا نیست.

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

            


تثلیث دیلانی درمدل سازی موقعی که مجموعه ای از نقاط داده شده اند یک مجموعه ی خوبی از مثلث ها را تولید می کند که می‌تواند به عنوان چند ضلعی در مدل استفاده شود. به طور خاص تثلیث دیلانی سعی دارد از مثلث های باریک استفاده نکند. تثلیث دیلانی می‌تواند برای مشخص کردن چگالی یا شدت نقاط در مدل سازی نقاط به معنی Delaunay tessellation field estimator استفاده شوند.

در نرم افزار متلب نیز با استفاده از دستور delaunay(x,y) می توان نسبت به محاسبه مثلث های دیلانی اقدام کرد که در آن x و y بیانگر مشخصات نقاط می باشند. (دوآرایه که مشخصات نقاط در آنها ذخیره شده است) و با دستور  voronoi(x,y,TRI) نیز گراف ورونی را نیز محاسبه نمود که TRI مشخصات مثلث های دیلانی می باشد. دیلانی چند بعدی نیز وجود دارد که توضیح آن از حوصله این نوشتار خارج است. نمونه کد مربوط به تشکیل مثلث ها و گراف نیز در قسمت برنامه نویسی آمده است


نظرات (0)
امکان ثبت نظر جدید برای این مطلب وجود ندارد.