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

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

کلیدواژه ها:

هندسه مح اسباتی ، دربرداری چندضلعی محدب ، روشهای بر اساس مثلث