نقطه در چندضلعی
From Wikipedia, the free encyclopedia
مسئله نقطه در چندضلعی در هندسه محاسباتی مسئلهٔ تعیین قرارگیری یک نقطهٔ مشخص نسبت به یک چندضلعی دادهشدهاست. یک نقطه میتواند داخل، خارج یا روی محیط چندضلعی قرار داشتهباشد. این مسئله حالت خاص مسئلهٔ محلیابی نقطه است و در زمینههای پردازش اطلاعات گرافیکی، مانند گرافیک رایانهای، بینایی رایانهای، سامانه اطلاعات جغرافیایی، برنامهریزی حرکت و طراحی رایانهای کاربرد دارد.
ایوان سودرلند[1] در سال ۱۹۷۴ دو راهحل (انتشار پرتو و جمع زوایا) برای این مسئله ارائه داد. تاریخچهٔ این مسئله و چند راهبرد برای حل آن در یکی از شمارههای مجلهٔ Ray Tracing News[2] به چاپ رسیدهاست.