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

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

با پردازش مرز چند ضلعی در مکان هایی لبه یا هر گوشه ی پنجره این الگوریتم کار می کند.

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

این مقاله ی کوتاه را با ما بخوانید.

پیشنهاد نویسنده : ساخت تصویر برفکی با متلب

برش ساترلند هاگمن

الگوریتم سادرلند-هاجمن که در زبان انگلیسی به Sutherland–Hodgman algorithm معروف است هدف چند تکه کردن چند ضلعی‌های را دارد.

این الگوریتم، با گسترش هر خط از چند ضلعی محدب و تنها انتخاب رئوس از چند ضلعی مورد نظر ما که در هر سمت قابل رویت هستند کار می‌کند.

چهار حالت ممکن هنگام پردازش این الگوریتم:

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

مشکلات و ضعف الگوریتم:

این روش به مقدار قابل توجهی از حافظه احتیاج دارد.

اول از همه چند ضلعی ها به صورت اصلی ذخیره می شوند. سپس در کلیپبورد در برابر لبه سمت چپ قرار گرفته و عملیات انجام می شود و بعد خروجی ذخیره می شود.

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

شبه کد الگوریتم :

List outputList = subjectPolygon;  

for (Edge clipEdge in clipPolygon) do
    List inputList = outputList;
    outputList.clear();

    for (int i = 0; i < inputList.count; i += 1) do
        Point current_point = inputList[i];
        Point prev_point = inputList[(i + inputList.count − 1) % inputList.count];

        Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)

        if (current_point inside clipEdge) then
            if (prev_point not inside clipEdge) then
                outputList.add(Intersecting_point);
            end if
            outputList.add(current_point);

        else if (prev_point inside clipEdge) then
            outputList.add(Intersecting_point);
        end if

    done
done

منابع :

https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

https://www.javatpoint.com/sutherland-hodgeman-polygon-clipping

این الگوریتم معمولا در سر فصل دروس گرافیک کامپیوتری در دوره های دانشگاهی قرار می گیرد.

موفق باشید.