موضوع مقاله: نقطه در چندضلعی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نقطه در چندضلعی | مقدمه: این مسئله حالت خاص مسئلهٔ محل‌یابی نقطه است و در زمینه‌های پردازش اطلاعات گرافیکی، مانند گرافیک رایانه‌ای، بینایی رایانه‌ای، سامانه اطلاعات جغرافیایی، برنامه‌ریزی حرکت و طراحی رایانه‌ای کاربرد دارد. | ## بخش 1: نقطه در چندضلعی | اگر تعداد نقاط تقاطع فرد باشد نتیجه می‌گیریم که نقطهٔ مورد نظر خارج چندضلعی قرار داشته‌است. یک راه ساده برای آزمودن قرارگیری نقطه در داخل یک چندضلعی ساده، شمارش تعداد دفعات تقاطع یک پرتوی دلخواه با شروع از نقطهٔ مورد نظر با چندضلعی داده‌شده‌است. اگر نقطه داخل چندضلعی قرار داشته‌باشد، تعداد تقاطع‌ها فرد باشد نقطه داخل چندضلعی قرار دارد و اگر زوج باشد، نقطه خارج چندضلعی قرار دارد. از این الگوریتم با نام الگوریتم تعداد تقاطع یا الگوریتم قاعدهٔ زوج و فرد نیز یاد می‌شود و حداقل در سال ۱۹۶۲ کشف شده‌بوده‌است.Shimrat, M. 1962 این الگوریتم بر اساس این ایدهٔ ساده است که اگر یک نقطه از بی‌نهایت در جهت دلخواه حرکت کند و چندضلعی را چند بار قطع کند، در این‌صورت با هر بار قطع کردن چندضلعی به‌طور متناوب یک بار از بیرون چندضلعی به درون آن و یک بار از درون چندضلعی به بیرون آن جابجا می‌شود. اگر این الگوریتم در رایانه‌ای با ممیز_شناور پیاده‌سازی شود و نقطهٔ مورد نظر نزدیک مرز چندضلعی باشد، ممکن است این الگوریتم جواب نادرست دهد. البته این ایراد زیاد حائز توجه نیست، زیرا آن‌چه بیشتر مورد توجه است زمان اجرای الگوریتم است و نه صحت کامل الگوریتم. با این وجود برای اصلاح این مشکل، ثابت آنالیز_عددی رواداری_(مهندسی) با نام تعریف می‌کنیم و قبل از اجرای الگوریتم بررسی می‌کنیم که اگر فاصلهٔ نقطه تا اضلاع چندضلعی کمتر از باشد، الگوریتم را متوقف کرده و نزدیک بودن بیش از اندازهٔ نقطه به اضلاع چندضلعی را گزارش می‌دهیم. برای پیاده‌سازی این الگوریتم معمولاً به این صورت عمل می‌شود که وجود تقاطع بین پرتو و اضلاع متوالی چندضلعی بررسی می‌شوند. | ## بخش 2: نقطه در چندضلعی | در چنین پیاده‌سازی‌ای باید به این مسئله توجه کرد که اگر پرتو از رأس_(هندسه) مشترک دو ضلع چندضلعی عبور کند، آن‌گاه این تقاطع دو بار شمرده می‌شود. در مثال این بخش، این اتفاق در مورد بالاترین راس مشکلی ایجاد نمی‌کند ولی در مورد راست‌ترین راس، باعث بروز جواب نادرست خواهدشد. این مشکل را به این‌صورت برطرف می‌کنیم: اگر نقطهٔ تقاطع پرتو و یک ضلع، یکی از دو انتهای ضلع بود، در این صورت این تقاطع را تنها در صورتی شمارش می‌کنیم (و فقط یک بار شمارش می‌کنیم) که دو ضلع مجاور آن راس در دو طرف پرتو قرار گرفته‌باشند. این کار معادل این است که راس مورد نظر را اندکی به سمت بالای پرتو جابجا کرده باشیم. در صورتی که پرتو از یک راس عبور کند، ممکن است که هنگام بررسی تقاطع دو ضلع مجاور، در هر دو مورد متوجه قرار گرفتن نقطهٔ تقاطع روی انتهای ضلع نشویم. اگر چندضلعی به‌وسیلهٔ رئوسش مشخص شده‌باشد، می‌توان قبل از محاسبهٔ محل نقطهٔ تقاطع بررسی کرد که آیا پرتو از یکی از رئوس مجاور ضلعی مورد بررسی می‌گذرد یا خیر. اگر چندضلعی به‌وسیلهٔ اطلاعاتی به‌جز رئوس آن مشخص شده‌باشد، باید از روش‌های دیگری برای اطمینان از درستی محاسبات استفاده‌کرد. الگوریتم عدد پیچش الگوریتم دیگر حل این مسئله الگوریتم محسابهٔ عدد پیچش نسبت به چندضلعی است. برای محاسبه عدد پیچش، می‌توان زوایای داخلی متناظر با هر یک از اضلاع چندضلعی را جمع کرد. | ## بخش 3: نقطه در چندضلعی | اما این روش به دفعات از معکوس توابع مثلثاتی استفاده می‌کند که باعث می‌شود در حالت کلی الگوریتم انتشار اشعه از نظر زمانی بهتر باشد. خوشبختانه لزومی به محاسبهٔ این معکوس توابع مثلثاتی نیست، چرا که نتیجه، یعنی جمع کل زوایای متناظر اضلاع، یا است یا (یا هر مضربی از ). پس فقط کافی است که حرکت چندضلعی را در ربع‌های مختصاتی حول نقطهٔ مورد نظر را دنبال کنیم. به این‌صورت این الگوریتم از نظر سرعت قابل مقایسه با الگوریتم انتشار پرتو خواهدبود. مقایسه برای چندضلعی ساده هر دو الگوریتم به ازای هر نقطهٔ ورودی جواب یکسانی را تولید خواهندکرد. اما برای چندضلعی غیرساده این دو الگوریتم ممکن است نتایج متفاوتی تولید کنند، مانند حالتی که چندضلعی خودش را قطع می‌کند یا وقتی که تعریف درون و بیرون چندضلعی دقیقاً مشخص نیست. پرسمان‌های نقطه در چندضلعی مسئلهٔ نقطه در چندضلعی را می‌توان نوعی نوعی از پرسمان هندسی مکرر دانست. یعنی بخواهیم با داشتن یک چندضلعی مشخض، قرار داشتن هر یک از اعضای یک دنباله از نقاط را در داخل چندضلعی بررسی کنیم. روشن است که می‌توان از هر یک از الگوریتم‌های مکان‌یابی نقطه در صفحهٔ مسطح برای حل این نوع مسائل استفاده کرد. | ## جمع‌بندی | حالت‌های خاص الگوریتم‌های بهتری برای چند ضلعی‌های یکنوا، ستاره‌گون یا محدب وجود دارند.