The   Sutherland-Hodgman clipping algorithm   finds the polygon that is the intersection between an arbitrary polygon (the “subject polygon”) and a convex polygon (the “clip polygon”).

It is used in computer graphics (especially 2D graphics) to reduce the complexity of a scene being displayed by eliminating parts of a polygon that do not need to be displayed.



Task

Take the closed polygon defined by the points:

 



[
(
50
,
150
)
,
(
200
,
50
)
,
(
350
,
150
)
,
(
350
,
300
)
,
(
250
,
300
)
,
(
200
,
250
)
,
(
150
,
350
)
,
(
100
,
250
)
,
(
100
,
200
)
]


{\displaystyle [(50,150),(200,50),(350,150),(350,300),(250,300),(200,250),(150,350),(100,250),(100,200)]}


and clip it by the rectangle defined by the points:

 



[
(
100
,
100
)
,
(
300
,
100
)
,
(
300
,
300
)
,
(
100
,
300
)
]


{\displaystyle [(100,100),(300,100),(300,300),(100,300)]}


Print the sequence of points that define the resulting clipped polygon.



Extra credit

Display all three polygons on a graphical surface, using a different color for each polygon and filling the resulting polygon.

(When displaying you may use either a north-west or a south-west origin, whichever is more convenient for your display mechanism.)




use strict;
use warnings;
 
sub intersection {
    my($L11, $L12, $L21, $L22) = @_;
    my ($d1x, $d1y) = ($$L11[0] - $$L12[0], $$L11[1] - $$L12[1]);
    my ($d2x, $d2y) = ($$L21[0] - $$L22[0], $$L21[1] - $$L22[1]);
    my $n1 = $$L11[0] * $$L12[1] - $$L11[1] * $$L12[0];
    my $n2 = $$L21[0] * $$L22[1] - $$L21[1] * $$L22[0];
    my $n3 = 1 / ($d1x * $d2y - $d2x * $d1y);
    [($n1 * $d2x - $n2 * $d1x) * $n3, ($n1 * $d2y - $n2 * $d1y) * $n3]
}
 
sub is_inside {
    my($p1, $p2, $p3) = @_;
    ($$p2[0] - $$p1[0]) * ($$p3[1] - $$p1[1]) > ($$p2[1] - $$p1[1]) * ($$p3[0] - $$p1[0])
}
 
sub sutherland_hodgman {
    my($polygon, $clip) = @_;
    my @output = @$polygon;
    my $clip_point1 = $$clip[-1];
    for my $clip_point2 (@$clip) {
        my @input = @output;
        @output = ();
        my $start = $input[-1];
        for my $end (@input) {
            if (is_inside($clip_point1, $clip_point2, $end)) {
                push @output, intersection($clip_point1, $clip_point2, $start, $end)
                  unless is_inside($clip_point1, $clip_point2, $start);
                push @output, $end;
            } elsif (is_inside($clip_point1, $clip_point2, $start)) {
                push @output, intersection($clip_point1, $clip_point2, $start, $end);
            }
            $start = $end;
        }
        $clip_point1 = $clip_point2;
    }
    @output
}
 
my @polygon = ([50,  150], [200, 50],  [350, 150], [350, 300], [250, 300],
              [200, 250], [150, 350], [100, 250], [100, 200]);
 
my @clip    = ([100, 100], [300, 100], [300, 300], [100, 300]);
 
my @clipped = sutherland_hodgman(\@polygon, \@clip);
 
print "Clipped polygon:\n";
print '(' . join(' ', @$_) . ') ' for @clipped;