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

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

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