الگوریتم سادرلند-هاجمن

الگوریتم سادرلند-هاجمن (به انگلیسی: Sutherland–Hodgman algorithm) برای چند تکه کردن چند ضلعی‌ها مورد استفاده قرار می‌گیرد. این الگوریتم، با گسترش هر خط از کلیپ چند ضلعی محدب و تنها انتخاب رئوس از چند ضلعی موضوع که در سمت قابل رویت هستند کار می‌کند.

شرح

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

تمام مراحل تقسیم چندضلعی محدب w با چند ضلعی مقعر 5 طرفه

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

شبه کد

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

  List outputList = subjectPolygon;
  for (Edge clipEdge in clipPolygon) do
  List inputList = outputList;
  outputList.clear();
  Point S = inputList.last;
  for (Point E in inputList) do
  if (E inside clipEdge) then
  if (S not inside clipEdge) then
  outputList.add(ComputeIntersection(S,E,clipEdge));
  end if
  outputList.add(E);
  else if (S inside clipEdge) then
  outputList.add(ComputeIntersection(S,E,clipEdge));
  end if
  S = E;
  done
  done

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

جستارهای وابسته

• الگوریتم کلیپینگ ویلر–آترتون
• الگوریتم کلیپینگ واتی
• کلیپینگ (در رستریزیشن)

منابع

• مل اسلاتر، آنتونی استید، یورگوس کریسنتو: گرافیک کامپیوتری و محیط‌های مجازی: از واقع گرایی تا زمان واقعی.. ادیسون ویلی. شابک 0-201-62420-6
• ایوان سادرلند، Gary W. Hodgman: Reentrant Polygon Clipping. Communications of the ACM, vol. 17, pp. 32-42, 1974
• ویکی‌پدیای انگلیسی

پیوند به بیرون

• Polygon clipping and filling Describes the algorithm using images that are easy to understand.