الگوریتمی جدید جهت تولید چندضلعی ساده ازمجموعه نقاط مسطح تصادفی به روش لایه های محدب

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

کلیدواژه ها:

پوسته محدب ، چندضلعی تصادفی گرافیک کامپیوتری ، لایههای محدب ، هندسه محاسباتی