الگوریتمی جدید جهت تولید چندضلعی ساده ازمجموعه نقاط مسطح تصادفی به روش لایه های محدب
عنوان مقاله: الگوریتمی جدید جهت تولید چندضلعی ساده ازمجموعه نقاط مسطح تصادفی به روش لایه های محدب
شناسه ملی مقاله: CECIT01_650
منتشر شده در کنگره ملی مهندسی برق، کامپیوتر و فناوری اطلاعات در سال 1392
شناسه ملی مقاله: CECIT01_650
منتشر شده در کنگره ملی مهندسی برق، کامپیوتر و فناوری اطلاعات در سال 1392
مشخصات نویسندگان مقاله:
علی نوراله - استادیاردانشگاه تربیت دبیر شهید رجایی تهران
محمد ابوئی مهریزی - دانشجوی برق و کامپیوتر
خلاصه مقاله:
علی نوراله - استادیاردانشگاه تربیت دبیر شهید رجایی تهران
محمد ابوئی مهریزی - دانشجوی برق و کامپیوتر
تولید چندضلعی ساده تصادفی ازجمله مسائل مطرح درهندسه محاسباتی می باشد این مسئله دربررسی صحت عملکرد الگوریتم و نیز درزمینه های مختلف گرافیک کامپیوتری نظیر خلق تصاویر پدیده های طبیعی تصادفی مانند پدیده ابر و سطحزمین بطور گسترده ای مورد استفاده قرارمیگیرد دراین مقاله الگوریتمی جدید جهت تولید چندضلعی ساده تصادفی ازیک مجموعه نقاط تصادفی واقع بر صفحه ارایه شده است دراین الگوریتم ابتدا خطی عمود بصورت تصادفی بین چپ ترین و راست ترین نقطه درنظر میگیریم سپس لایه های محدب را بدین گونه بدست می آوریم که اگراتصال دو نقطه ازلایه موردنظر باخط مفروض تلاقی ایجاد کند نباید رسم شود باستثنای اولین لایه محدب که باید یک تلاقی با خط مفروض داشته ب اشد درنهایت بعدازایجاد لایه های محدب تا اینکه فقط دو نقطه ازمجموعه نقاط ورودی باقی بماند دونقطه باقی مانده را بهم متصل کرده و چندضلعی بدست می اید پیچیدگی زمانی این الگوریتم ازمرتبه 0 nlogn می باشد که نشان میدهد الگوریتم ازنظر زمانی بهینه می باشد ازانجایی که زمان اجرا دربرخی ازکاربردهای بلادرنگ نظیربازیهای رایانه ای ازاهمیت بالایی برخوردار است این الگوریتم میتواند دراین موارد بسیار مفید واقع شود.
کلمات کلیدی: پوسته محدب، چندضلعی تصادفی گرافیک کامپیوتری، لایههای محدب، هندسه محاسباتی
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/211048/