تبلیغات
سی تی دانلود - مثلث بندی چند ضلعی ها
 
سی تی دانلود
                                                        
درباره وبلاگ


مدیر وبلاگ : مهدی تاجیك زارع
نظرسنجی
نظرت درباره سایت چیه ؟







آمار وبلاگ
  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :
1

 

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

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

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

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

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

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

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

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


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

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

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

گوش چندضلعی

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

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





نوع مطلب : علوم تجربی، 
برچسب ها :
لینک های مرتبط :




سه شنبه 2 خرداد 1396 03:18 ب.ظ
Hello there! Quick question that's entirely off topic. Do you know how to make
your site mobile friendly? My website looks weird when viewing from my iphone4.
I'm trying to find a theme or plugin that might be able to resolve this problem.

If you have any recommendations, please share. Thank you!
دوشنبه 4 اردیبهشت 1396 09:20 ق.ظ
My developer is trying to convince me to move to .net from
PHP. I have always disliked the idea because of the costs.
But he's tryiong none the less. I've been using WordPress on numerous websites for about a
year and am worried about switching to another platform.
I have heard very good things about blogengine.net. Is there a way I
can transfer all my wordpress content into it? Any help would be really appreciated!
جمعه 25 فروردین 1396 07:24 ق.ظ
Thank you for another informative blog. Where else could I am getting that
type of information written in such an ideal means?
I have a mission that I am simply now operating on, and I have
been at the glance out for such information.
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر