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

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

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

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

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

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

الگوریتم سادرلند-هاجمن که در زبان انگلیسی به 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

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