نقاط مرزی: نقاط شبکهای روی اضلاع چندضلعی
چندضلعیها و شبکههای نقطهای: زمین بازی نقاط مرزی
برای شروع، فرض کنید یک صفحهٔ شطرنجی بینهایت بزرگ داریم. هر خانه از این صفحه یک مربع واحد است. هر نقطهای از صفحه که روی گوشههای این مربعها قرار بگیرد، یک نقطهٔ شبکهای نامیده میشود. مختصات این نقاط، همواره شامل دو عدد صحیح (x, y) است.
حالا یک چندضلعی (مثل مربع، مستطیل یا مثلث) را روی این صفحه تصور کنید. اگر این چندضلعی طوری رسم شود که رأسهای آن دقیقاً روی نقاط شبکهای قرار گیرند، به آن یک چندضلعی شبکهای میگوییم. حال سؤال اینجاست: چه تعداد از نقاط شبکهای، دقیقاً روی اضلاع این چندضلعی میافتند؟ به این نقاط، نقاط مرزی میگوییم.
چگونه نقاط مرزی را بشماریم؟ یک فرمول جادویی
شمارش نقاط مرزی برای شکلهای ساده مانند مستطیلهای هممحور با محورها3 آسان است. اما برای خطهای مورب، نیاز به یک ابزار ریاضی داریم: بزرگترین مقسومعلیه مشترک4 یا $\gcd$.
فرض کنید پارهخطی داریم که دو نقطهٔ شبکهای A(x_1, y_1) و B(x_2, y_2) را به هم وصل میکند. تعداد نقاط شبکهای روی این پارهخط (شامل دو نقطهٔ A و B) با این فرمول به دست میآید:
چرا $\gcd$؟$\gcd$ تفاوتهای طول و عرض، به ما میگوید پارهخط بین دو نقطه را چند قسمت مساوی میتوان تقسیم کرد تا هر قسمتشکننده5 مختصات صحیح داشته باشد. با اضافه کردن عدد 1، خود نقطهٔ شروع را نیز به شمارش اضافه میکنیم.
| نقطهٔ شروع (A) | نقطهٔ پایان (B) | تفاوت مختصات (Δx, Δy) | gcd(|Δx|,|Δy|) | تعداد نقاط مرزی (b) |
|---|---|---|---|---|
| (0,0) | (6,0) | (6,0) | 6 | 6+1=7 |
| (1,1) | (7,4) | (6,3) | 3 | 3+1=4 |
| (0,0) | (5,12) | (5,12) | 1 | 1+1=2فقط دو نقطه |
از محیط به مساحت: نقاط مرزی در قضیهٔ پیک
حالا که میدانیم چگونه نقاط روی هر ضلع را بشماریم، میتوانیم مجموع نقاط مرزی کل یک چندضلعی شبکهای را محاسبه کنیم. این عدد که آن را با $B$ نشان میدهیم، یکی از دو دادهٔ اصلی در یک فرمول معروف به نام قضیه پیک است. این قضیه یک راه ساده و زیبا برای محاسبهٔ مساحت $A$ یک چندضلعی شبکهای ارائه میدهد:
که در آن:
$A$ = مساحت چندضلعی.
$I$ = تعداد نقاط شبکهای داخل چندضلعی.
$B$ = تعداد نقاط شبکهای روی محیط (نقاط مرزی).
مثال: مستطیلی با رأسهای (0,0)، (4,0)، (4,3)، (0,3) را در نظر بگیرید. ابتدا نقاط مرزی $B$ را میشماریم. روی محیط این مستطیل 14 نقطهٔ شبکهای وجود دارد. همچنین 6 نقطهٔ شبکهای در داخل آن قرار دارد ($I=6$). طبق قضیه پیک: $A = 6 + \frac{14}{2} - 1 = 6 + 7 - 1 = 12$. و این با فرمول معمول مساحت مستطیل ($4 \times 3 = 12$) مطابقت دارد!
کاربرد نقاط مرزی: از بازیهای کامپیوتری تا هنر پیکسلی
شاید فکر کنید این مفاهیم فقط در کتابهای ریاضی کاربرد دارند. اما نمونههای کاربردی آن را همهروزه میبینیم:
- گرافیک کامپیوتری و بازیهای ویدئویی: زمانی که یک خط یا چندضلعی روی صفحهٔ پیکسلی (که خودش یک شبکهٔ بزرگ است) رسم میشود، الگوریتمهایی مانند الگوریتم برزنهام برای تعیین اینکه کدام پیکسلها باید روشن شوند، از مفاهیم مشابه شمارش نقاط روی یک خط استفاده میکنند.
- هنر پیکسلی و طراحی: هنرمندانی که آثار خود را با مربعهای ریز (پیکسل) خلق میکنند، ناخودآگاه در حال کار با نقاط شبکهای و مرزی هستند تا خطوط صاف یا مورب ایجاد کنند.
- نقشهبرداری و GIS: هنگام تقسیم یک منطقه به واحدهای کوچک مربعی (مثل نقشههای شطرنجی)، شمارش واحدهای مرزی برای محاسبهٔ طول مرزها یا تعیین حریم، اهمیت دارد.
یک مثال ساده: فرض کنید در یک بازی استراتژی، قلمرو شما یک چندضلعی است و میخواهید دور آن دیوار بکشید. هزینهٔ ساخت دیوار به طول مرز بستگی دارد. اگر بازی روی شبکه باشد، محاسبهٔ تعداد واحدهای مرزی (نقاطی که دیوار روی آنها ساخته میشود) دقیقاً همان محاسبهٔ $B$ است!
اشتباهات رایج و پرسشهای مهم
بله، کاملاً. در شمارش نقاط مرزی روی هر ضلع ($b = \gcd(...)+1$)، نقطهٔ شروع و پایان هر ضلع (که همان رأسها هستند) نیز شمرده میشوند. هنگام جمعبندی برای کل چندضلعی، باید مراقب باشیم که رأسها را فقط یک بار بشماریم، نه به ازای هر دو ضلع مجاور.
این به این معنی است که روی آن پارهخط، هیچ نقطهٔ شبکهای دیگری جز دو نقطهٔ ابتدا و انتها وجود ندارد. در واقع، این دو نقطه «هماول»6 هستند و خط واصل آنها از هیچ نقطهٔ شبکهای دیگری نمیگذرد. این حالت برای رسم دقیقترین خطوط مورب در گرافیک مهم است.
خیر. قضیه پیک فقط برای چندضلعیهای ساده (بدونخود عبور7) که رأسهایشان روی نقاط شبکهای قرار دارد، صادق است. اگر چندضلعی حفره8 داشته باشد، فرمول باید تعدیل شود: $A = I + \frac{B}{2} + H - 1$ که در آن $H$ تعداد حفرههاست.
پاورقی
1نقاط مرزی (Boundary Points): نقاطی که روی محیط یک شکل هندسی قرار دارند.
2قضیه پیک (Pick's Theorem): فرمولی برای محاسبه مساحت یک چندضلعی شبکهای ساده بر اساس شمارش نقاط درونی و مرزی.
3هممحور با محورها (Axis-Aligned): اضلاع شکل موازی با محورهای مختصات x و y باشند.
4بزرگترین مقسومعلیه مشترک (Greatest Common Divisor - GCD): بزرگترین عددی که هر دو عدد بر آن بخشپذیر باشند.
5قسمتشکننده (Segment): بخشی از یک خط.
6هماول (Relatively Prime/Coprime): دو عدد صحیح که بزرگترین مقسومعلیه مشترک آنها برابر با ۱ باشد.
7خود عبور (Self-Intersecting): حالتی که اضلاع یک چندضلعی یکدیگر را قطع کنند.
8حفره (Hole): ناحیهای خالی و محصور در داخل یک چندضلعی.
