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

Publish Year: 1386
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 3,515

متن کامل این Paper منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل Paper (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

ACCSI13_263

تاریخ نمایه سازی: 25 آبان 1386

Abstract:

تعیین وضعیت نقطه نسبت به یک چندضلعی یکی از مسائل بنیادی هندسه محاسباتی است . در این مقاله، الگوریتمی جدید به منظور تعیین وضعیت یک نقطه نسبت به یک چندضلعی محدب ارائه میشود. الگوریتمهای قبلی ارائه شده برای تعیین وضعیت نقطه نسبت به چندضلعی محدب یک پیش پردازش بر روی راس های چندضلعی انجام میدهند و سپس وضعیت نقاط مورد بررسی را مورد ارزیابی قرار میدهند. در الگوریتم پیشنهادی نیازی به پیش پردازش نیست. در این الگوریتم با استفاده از جستجوی باینری بین راسهای چندضلعی، سه راسی پیدا میشوند که نقطه مورد جستجو در داخل مثلث ایجاد شده از این سه راس باشد. در صورتی که چنین مثلثی پیدا شد نقطه داخل چندضلعی قرار دارد و در غیر این صورت نقطه در خارج مثلث قرار دارد. این الگوریتم در شرایطی که توزیع نقاط به صورت یکنواخت باشدوضعیت نقطه را در زمان ثابت ( ( 1(O( مشخص می کند . هرچند که پیچیدگی زمان الگوریتم در بدترین حالتO( log n ) است.

Keywords:

Authors

سیدمحمد ابوالحسنی

آزمایشگاه محاسبات نرم، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر

محمدرضا رزازی

هیئت علمی، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران،

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • Wang, W., Li, J., and Wu, E. 2D point- in-polygon ...
  • Manber, U. Introduction to algo rithms-a creative approach. Reading, MA: ...
  • Foley, J. D., Dam, A. V., Feiner, S. K., and ...
  • Feito, F. R., Torres, J. C., and Urena, A. Orientation, ...
  • Feito, F. R., and Torres, J. C. Inclusion test for ...
  • Preparata, F. P., and Shamos, M. I. Comp utational geometry: ...
  • Taylor, G. Point in polygon test. Survey Review. 1994;32: 4, ...
  • Berg, M. D., Kreveld, M. V., Overmars, M., and Schwarzkpf, ...
  • Zalik, B., and Clapworthy, G. J. A universal trapezoidation algorithm ...
  • Teillaud, M. Union and split operations on dynamic trapezoidal maps. ...
  • Etzion, M., and Rappoport, A. On compatible start decompos itions ...
  • Huang, C. W., and Shih, T. Y. On the complexity ...
  • Zalik, B., and Kolingerova, I. cell-based po int-in-polygon algorithm suitable ...
  • Li, J., Wang, W., and Wu, E. Point- in-polygon tests ...
  • نمایش کامل مراجع