مثلث‌بندی چندضلعی‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

مثلث بندی حالت خاصی از گراف مسطح با خطوط مستقیم است.

چند ضلعی‌های محدب بسادگی با پیچیدگی زمانی (O(n مثلث بندی می‌شوند. به این شکل که یک راس را به همه رئوس دیگر وصل می‌کنیم.

چند ضلعی‌های یکنوا نیز بسادگی همانطورکه توسط A. Fournier و D.Y. Montuno توضیح داده شده‌اند، با پیچیدگی زمانی (O(n مثلث بندی می‌شوند.

مثلث بندی یک چند ضلعی ساده با پیچیدگی زمانی (O(n برای یک مدت طولانی مسئله‌ای حل نشده بود. سرانجام Bernad Chazelle در سال ۱۹۹۱ نشان داد که هر چند ضلعی ساده‌ای را می‌شود با پیچیدگی زمانی (O(n مثلث بندی کرد. با این وجود الگوریتم ارائه شده بسیار پیچیده‌است. به همین دلیل Chazelle و دیگران هنوز به دنبال پیدا کردن الگوریتم ساده تری هستند.

پیچیدگی زمانی مثلث بندی یک چند ضلعی حفره دار دارای حد پایین (Ω(nlogn است.

الگوریتم‌ها[ویرایش]

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

روش کم کردن گوش ها

گوش چندضلعی

با فرض اینکه هر چند ضلعی سادهٔ بی حفره‌ای حداقل دو گوش دارد می‌توان آن را مثلث بندی کرد. گوش یک چند ضلعی به مثلثی می‌گویند که دو ضلع آن روی دو ضلع چند ضلعی باشد و ضلع دیگر آن به طور کامل درون چند ضلعی قرار بگیرد. الگوریتم به این صورت است که در هر مرحله یک گوش چند ضلعی را پیدا کرده و آن را حذف می‌کند. در پایان هر مرحله شکل حاصل همچنان شرایط اولیه را دارد. این کار تا جایی ادامه پیدا می‌کند که فقط یک مثلث باقی بماند. پیاده سازی این الگوریتم آسان می‌باشد، ولی کارایی این الگوریتم محدود است و فقط بروی چند ضلعی‌های بدون حفره کار می‌کند. پیچیدگی زمانی این الگوریتم O(n۲) می‌باشد. به این الگوریتم ear clipping یا ear trimming نیز می‌گویند.

همچنین ببینید[ویرایش]

منابع[ویرایش]