اصول هندسه محاسباتی: جهت، تقاطع پاره‌خط، و پوسته محدب

چرا مسائل هندسی به تکنیک‌های خاص خودشان نیاز دارند

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

ضرب خارجی و آزمون جهت

با داشتن سه نقطه p1، p2، و p3، یک پرسش بنیادین این است که آیا مسیر از p1 به p2 به p3 به چپ می‌پیچد (پادساعتگرد)، به راست می‌پیچد (ساعتگرد)، یا سه نقطه هم‌خط هستند. این با استفاده از Cross Product (ضرب خارجی) دو بردار تشکیل‌شده توسط این نقاط تعیین می‌شود.

تعریف بردارها:
v1 = p2 - p1 = (p2.x - p1.x, p2.y - p1.y)
v2 = p3 - p1 = (p3.x - p1.x, p3.y - p1.y)

ضرب خارجی (یک اسکالر در ۲بعدی):
cross(v1, v2) = v1.x · v2.y - v1.y · v2.x

اگر cross > 0: پیچش از p1→p2→p3 پادساعتگرد است (پیچش چپ)
اگر cross < 0: پیچش از p1→p2→p3 ساعتگرد است (پیچش راست)
اگر cross == 0: سه نقطه هم‌خط هستند

این یک آزمون واحد، محاسبه‌پذیر در زمان O(1) با استفاده فقط از ضرب و تفریق (بدون نیاز به توابع مثلثاتی گران یا جذر)، بلوک سازنده بنیادین برای تقریباً هر الگوریتمی است که در این مقاله پوشش داده می‌شود.

تعیین اینکه آیا دو پاره‌خط تقاطع دارند

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

SEGMENTS-INTERSECT(p1, p2, p3, p4):
  d1 = ORIENTATION(p3, p4, p1)
  d2 = ORIENTATION(p3, p4, p2)
  d3 = ORIENTATION(p1, p2, p3)
  d4 = ORIENTATION(p1, p2, p4)
  
  اگر ((d1 > 0 و d2 < 0) یا (d1 < 0 و d2 > 0)) و
     ((d3 > 0 و d4 < 0) یا (d3 < 0 و d4 > 0)):
      TRUE را برگردان       // پاره‌خط‌ها به‌درستی تقاطع دارند
  
  // موارد خاص هم‌خط (تماس مرزی) را جداگانه مدیریت کن
  اگر d1 == 0 و ON-SEGMENT(p3, p4, p1): TRUE را برگردان
  اگر d2 == 0 و ON-SEGMENT(p3, p4, p2): TRUE را برگردان
  اگر d3 == 0 و ON-SEGMENT(p1, p2, p3): TRUE را برگردان
  اگر d4 == 0 و ON-SEGMENT(p1, p2, p4): TRUE را برگردان
  
  FALSE را برگردان

بینش اصلی شهودی است: دو پاره‌خط تقاطع دارند اگر و فقط اگر دو نقطه‌انتهایی هر پاره‌خط در دو سمت مخالف خط شامل پاره‌خط دیگر قرار داشته باشند. آزمون جهت محاسبه‌شده دو بار برای هر پاره‌خط (بررسی هر دو نقطه‌انتهایی پاره‌خط دیگر در برابر آن) دقیقاً این شرط را تعیین می‌کند، با نیاز به مدیریت مورد خاص فقط برای حالت مرزی نقاط هم‌خط، جایی که آزمون علامت-محور ساده به‌تنهایی کافی نیست.

مسئله پوسته محدب

Convex Hull (پوسته محدب) یک مجموعه از نقاط، کوچک‌ترین چندضلعی محدبی است که شامل همه آن‌هاست — از نظر شهودی، شکلی تشکیل‌شده با کشیدن یک کش دور همه نقاط و گذاشتن آن محکم بسته شود. این کاربردهای عملی در تشخیص برخورد، تشخیص الگو، و محاسبه مرز جغرافیایی دارد.

اسکن گراهام: محاسبه پوسته محدب

Graham's Scan (اسکن گراهام) پوسته محدب را به‌طور کارآمد با استفاده از یک گام مرتب‌سازی به‌دنبال یک اسکن واحد که کاملاً به آزمون جهت معرفی‌شده در بالا متکی است، محاسبه می‌کند.

GRAHAM-SCAN(Q):
  فرض کن p0 نقطه در Q با کمترین مختصات y باشد
  (شکستن تساوی با کمترین مختصات x)

  نقاط باقی‌مانده را بر اساس زاویه قطبی نسبت به p0،
  پادساعتگرد، مرتب کن (با استفاده از آزمون جهت برای مقایسه زوایا
  بدون نیاز به محاسبه مقادیر زاویه واقعی)

  فرض کن ⟨p1, p2, ..., pn⟩ نقاط مرتب‌شده باشند
  p0، سپس p1 را روی یک پشته S فشار بده
  برای i = 2 تا n:
      تا زمانی که سه نقطه آخر روی S (با pi) یک
            پیچش غیرچپ بسازند (جهت ≤ 0):
          بالای S را پاپ کن
      pi را روی S فشار بده
  S را برگردان    // پشته اکنون دقیقاً رأس‌های پوسته را شامل می‌شود،
              // به ترتیب پادساعتگرد

چرا این الگوریتم کار می‌کند

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

شهود مثال:
اگر نقاط A، B، C به ترتیب در نظر گرفته شوند،
و پیچش از A به B به C ساعتگرد باشد (یک "پیچش راست")،
آنگاه B نسبت به A و C درون پوسته قرار دارد،
و باید از بررسی حذف شود

تحلیل زمان اجرا

مرتب‌سازی نقاط بر اساس زاویه قطبی زمان O(n log n) می‌گیرد، با استفاده از الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه که پیش‌تر در این مجموعه بحث شد. مرحله اسکن، با وجود شامل‌بودن یک حلقه while تودرتو، در زمان کل O(n) اجرا می‌شود: هر نقطه دقیقاً یک‌بار روی پشته فشار داده می‌شود و حداکثر یک‌بار پاپ می‌شود، که O(n) عملیات کل پشته در سراسر کل اسکن می‌دهد، با استفاده از استدلال تحلیل مستهلک که پیش‌تر در این مجموعه بحث شد. زمان اجرای کلی بنابراین O(n log n) است، که توسط مرتب‌سازی اولیه غالب است.

چرا هندسه محاسباتی این‌قدر به یک آزمون ساده متکی است

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

چرا این الگوریتم‌ها در عمل اهمیت دارند

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