نقطه در چندضلعی

مسئله نقطه در چندضلعی در هندسه محاسباتی مسئلهٔ تعیین قرارگیری یک نقطهٔ مشخص نسبت به یک چندضلعی داده‌شده‌است. یک نقطه می‌تواند داخل، خارج یا روی محیط چندضلعی قرار داشته‌باشد. این مسئله حالت خاص مسئلهٔ محل‌یابی نقطه است و در زمینه‌های پردازش اطلاعات گرافیکی، مانند گرافیک رایانه‌ای، بینایی رایانه‌ای، سامانه اطلاعات جغرافیایی، برنامه‌ریزی حرکت و طراحی رایانه‌ای کاربرد دارد.

مثالی از یک چندضلعی ساده

ایوان سودرلند در سال ۱۹۷۴ دو راه‌حل (انتشار پرتو و جمع زوایا) برای این مسئله ارائه داد. تاریخچهٔ این مسئله و چند راه‌برد برای حل آن در یکی از شماره‌های مجلهٔ Ray Tracing News به چاپ رسیده‌است.

الگوریتم انتشار اشعه

نمایش تقاطع یک پرتو از خارج چندضلعی در جهتی دلخواه. اگر تعداد نقاط تقاطع فرد باشد نتیجه می‌گیریم که نقطهٔ مورد نظر خارج چندضلعی قرار داشته‌است. اگر این تعداد زوج باشد، نقطه در داخل چندضلعی قرار دارد. این آزمون در فضای سه‌بعدی نیز قابل اعمال است.

یک راه ساده برای آزمودن قرارگیری نقطه در داخل یک چندضلعی ساده، شمارش تعداد دفعات تقاطع یک پرتوی دلخواه با شروع از نقطهٔ مورد نظر با چندضلعی داده‌شده‌است. اگر نقطه داخل چندضلعی قرار داشته‌باشد، تعداد تقاطع‌ها فرد باشد نقطه داخل چندضلعی قرار دارد و اگر زوج باشد، نقطه خارج چندضلعی قرار دارد. از این الگوریتم با نام الگوریتم تعداد تقاطع یا الگوریتم قاعدهٔ زوج و فرد نیز یاد می‌شود و حداقل در سال ۱۹۶۲ کشف شده‌بوده‌است. این الگوریتم بر اساس این ایدهٔ ساده است که اگر یک نقطه از بی‌نهایت در جهت دلخواه حرکت کند و چندضلعی را چند بار قطع کند، در این‌صورت با هر بار قطع کردن چندضلعی به‌طور متناوب یک بار از بیرون چندضلعی به درون آن و یک بار از درون چندضلعی به بیرون آن جابجا می‌شود. در نتیجه با هر دو بار قطع کردن چندضلعی در همان سمت چندضلعی باقی می‌ماند. این مشاهده را می‌توان به‌طور ریاضیاتی توسط قضیهٔ خم جردن اثبات کرد.

اگر این الگوریتم در رایانه‌ای با ممیز_شناور پیاده‌سازی شود و نقطهٔ مورد نظر نزدیک مرز چندضلعی باشد، ممکن است این الگوریتم جواب نادرست دهد. البته این ایراد زیاد حائز توجه نیست، زیرا آن‌چه بیشتر مورد توجه است زمان اجرای الگوریتم است و نه صحت کامل الگوریتم. با این وجود برای اصلاح این مشکل، ثابت آنالیز_عددی رواداری_(مهندسی) با نام $\epsilon$ تعریف می‌کنیم و قبل از اجرای الگوریتم بررسی می‌کنیم که اگر فاصلهٔ نقطه تا اضلاع چندضلعی کمتر از $\epsilon$ باشد، الگوریتم را متوقف کرده و نزدیک بودن بیش از اندازهٔ نقطه به اضلاع چندضلعی را گزارش می‌دهیم.

برای پیاده‌سازی این الگوریتم معمولاً به این صورت عمل می‌شود که وجود تقاطع بین پرتو و اضلاع متوالی چندضلعی بررسی می‌شوند. در چنین پیاده‌سازی‌ای باید به این مسئله توجه کرد که اگر پرتو از رأس_(هندسه) مشترک دو ضلع چندضلعی عبور کند، آن‌گاه این تقاطع دو بار شمرده می‌شود. در مثال این بخش، این اتفاق در مورد بالاترین راس مشکلی ایجاد نمی‌کند ولی در مورد راست‌ترین راس، باعث بروز جواب نادرست خواهدشد. این مشکل را به این‌صورت برطرف می‌کنیم: اگر نقطهٔ تقاطع پرتو و یک ضلع، یکی از دو انتهای ضلع بود، در این صورت این تقاطع را تنها در صورتی شمارش می‌کنیم (و فقط یک بار شمارش می‌کنیم) که دو ضلع مجاور آن راس در دو طرف پرتو قرار گرفته‌باشند. این کار معادل این است که راس مورد نظر را اندکی به سمت بالای پرتو جابجا کرده باشیم.

مسئلهٔ عبور پرتو از رئوس در ممیز_شناور نیز مشکل‌ساز خواهدبود. در صورتی که پرتو از یک راس عبور کند، ممکن است که هنگام بررسی تقاطع دو ضلع مجاور، در هر دو مورد متوجه قرار گرفتن نقطهٔ تقاطع روی انتهای ضلع نشویم. اگر چندضلعی به‌وسیلهٔ رئوسش مشخص شده‌باشد، می‌توان قبل از محاسبهٔ محل نقطهٔ تقاطع بررسی کرد که آیا پرتو از یکی از رئوس مجاور ضلعی مورد بررسی می‌گذرد یا خیر. اگر چندضلعی به‌وسیلهٔ اطلاعاتی به‌جز رئوس آن مشخص شده‌باشد، باید از روش‌های دیگری برای اطمینان از درستی محاسبات استفاده‌کرد.

الگوریتم عدد پیچش

الگوریتم دیگر حل این مسئله الگوریتم محسابهٔ عدد پیچش نسبت به چندضلعی است. اگر این عدد ناصفر باشد نقطه در درون چندضلعی قرار دارد. برای محاسبه عدد پیچش، می‌توان زوایای داخلی متناظر با هر یک از اضلاع چندضلعی را جمع کرد. اما این روش به دفعات از معکوس توابع مثلثاتی استفاده می‌کند که باعث می‌شود در حالت کلی الگوریتم انتشار اشعه از نظر زمانی بهتر باشد. خوشبختانه لزومی به محاسبهٔ این معکوس توابع مثلثاتی نیست، چرا که نتیجه، یعنی جمع کل زوایای متناظر اضلاع، یا $0$ است یا $2\pi$ (یا هر مضربی از $2\pi$ ). پس فقط کافی است که حرکت چندضلعی را در ربع‌های مختصاتی حول نقطهٔ مورد نظر را دنبال کنیم. به این‌صورت این الگوریتم از نظر سرعت قابل مقایسه با الگوریتم انتشار پرتو خواهدبود.

مقایسه

برای چندضلعی ساده هر دو الگوریتم به ازای هر نقطهٔ ورودی جواب یکسانی را تولید خواهندکرد. اما برای چندضلعی غیرساده این دو الگوریتم ممکن است نتایج متفاوتی تولید کنند، مانند حالتی که چندضلعی خودش را قطع می‌کند یا وقتی که تعریف درون و بیرون چندضلعی دقیقاً مشخص نیست.

پرسمان‌های نقطه در چندضلعی

مسئلهٔ نقطه در چندضلعی را می‌توان نوعی نوعی از پرسمان هندسی مکرر دانست. یعنی بخواهیم با داشتن یک چندضلعی مشخض، قرار داشتن هر یک از اعضای یک دنباله از نقاط را در داخل چندضلعی بررسی کنیم. روشن است که می‌توان از هر یک از الگوریتم‌های مکان‌یابی نقطه در صفحهٔ مسطح برای حل این نوع مسائل استفاده کرد. راه‌حل‌های ساده‌تری نیز برای برخی چندضلعی‌های خاص وجود دارند.

حالت‌های خاص

الگوریتم‌های بهتری برای چند ضلعی‌های یکنوا، ستاره‌گون یا محدب وجود دارند.