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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم ساترلند-هاگمن (به انگلیسی: 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 یک تابع بی اهمیت است، که در اینجا برای وضوح حذف شده است. این تابع تقاطع یک تکه خط و یک لبه ی نامحدود را برمیگرداند. توجه کنید که این اتفاق تنها در صورتی رخ می دهد که چنین تقاطعی وجود داشته باشد، از این رو به سادگی می توان با هر دو خط به صورت دو خط نامتناهی رفتار کرد.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

پیوند به بیرون[ویرایش]