الگوریتم جدید برای مسئله تعیین وضعیت نقطه در چند ضلعی محدب
Publish place: 13th Annual Conference of Computer Society of Iran
Publish Year: 1386
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 3,595
متن کامل این Paper منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل Paper (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI13_263
تاریخ نمایه سازی: 25 آبان 1386
Abstract:
تعیین وضعیت نقطه نسبت به یک چندضلعی یکی از مسائل بنیادی هندسه محاسباتی است . در این مقاله، الگوریتمی جدید به منظور تعیین وضعیت یک نقطه نسبت به یک چندضلعی محدب ارائه میشود. الگوریتمهای قبلی ارائه شده برای تعیین وضعیت نقطه نسبت به چندضلعی محدب یک پیش پردازش بر روی راس های چندضلعی انجام میدهند و سپس وضعیت نقاط مورد بررسی را مورد ارزیابی قرار میدهند. در الگوریتم پیشنهادی نیازی به پیش پردازش نیست. در این الگوریتم با استفاده از جستجوی باینری بین راسهای چندضلعی، سه راسی پیدا میشوند که نقطه مورد جستجو در داخل مثلث ایجاد شده از این سه راس باشد. در صورتی که چنین مثلثی پیدا شد نقطه داخل چندضلعی قرار دارد و در غیر این صورت نقطه در خارج مثلث قرار دارد. این الگوریتم در شرایطی که توزیع نقاط به صورت یکنواخت باشدوضعیت نقطه را در زمان ثابت ( ( 1(O( مشخص می کند . هرچند که پیچیدگی زمان الگوریتم در بدترین حالتO( log n ) است.
Keywords:
Authors
سیدمحمد ابوالحسنی
آزمایشگاه محاسبات نرم، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر
محمدرضا رزازی
هیئت علمی، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران،
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :