Sutherland-Hodgman polygon clipping: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Add Swift) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 422:
250 300
test.eps written</pre>[[file:poly-clip-C.png]]
=={{header|C sharp}}==
Line 958 ⟶ 830:
[[File:PolyIntersect.png]]
=={{header|C++}}==
<lang C++>#include <iostream>
using namespace std;
struct point2D { float x, y; };
const int N = 99; // clipped (new) polygon size
// check if a point is on the LEFT side of an edge
bool inside(point2D p, point2D p1, point2D p2)
{
return (p2.y - p1.y) * p.x + (p1.x - p2.x) * p.y + (p2.x * p1.y - p1.x * p2.y) < 0;
}
// calculate intersection point
point2D intersection(point2D cp1, point2D cp2, point2D s, point2D e)
{
point2D dc = { cp1.x - cp2.x, cp1.y - cp2.y };
point2D dp = { s.x - e.x, s.y - e.y };
float n1 = cp1.x * cp2.y - cp1.y * cp2.x;
float n2 = s.x * e.y - s.y * e.x;
float n3 = 1.0 / (dc.x * dp.y - dc.y * dp.x);
return { (n1 * dp.x - n2 * dc.x) * n3, (n1 * dp.y - n2 * dc.y) * n3 };
}
// Sutherland-Hodgman clipping
void SutherlandHodgman(point2D *subjectPolygon, int &subjectPolygonSize, point2D *clipPolygon, int &clipPolygonSize, point2D (&newPolygon)[N], int &newPolygonSize)
{
point2D cp1, cp2, s, e, inputPolygon[N];
// copy subject polygon to new polygon and set its size
for(int i = 0; i < subjectPolygonSize; i++)
newPolygon[i] = subjectPolygon[i];
newPolygonSize = subjectPolygonSize;
for(int j = 0; j < clipPolygonSize; j++)
{
// copy new polygon to input polygon & set counter to 0
for(int k = 0; k < newPolygonSize; k++){ inputPolygon[k] = newPolygon[k]; }
int counter = 0;
// get clipping polygon edge
cp1 = clipPolygon[j];
cp2 = clipPolygon[(j + 1) % clipPolygonSize];
for(int i = 0; i < newPolygonSize; i++)
{
// get subject polygon edge
s = inputPolygon[i];
e = inputPolygon[(i + 1) % newPolygonSize];
// Case 1: Both vertices are inside:
// Only the second vertex is added to the output list
if(inside(s, cp1, cp2) && inside(e, cp1, cp2))
newPolygon[counter++] = e;
// Case 2: First vertex is outside while second one is inside:
// Both the point of intersection of the edge with the clip boundary
// and the second vertex are added to the output list
else if(!inside(s, cp1, cp2) && inside(e, cp1, cp2))
{
newPolygon[counter++] = intersection(cp1, cp2, s, e);
newPolygon[counter++] = e;
}
// Case 3: First vertex is inside while second one is outside:
// Only the point of intersection of the edge with the clip boundary
// is added to the output list
else if(inside(s, cp1, cp2) && !inside(e, cp1, cp2))
newPolygon[counter++] = intersection(cp1, cp2, s, e);
// Case 4: Both vertices are outside
else if(!inside(s, cp1, cp2) && !inside(e, cp1, cp2))
{
// No vertices are added to the output list
}
}
// set new polygon size
newPolygonSize = counter;
}
}
int main(int argc, char** argv)
{
// subject polygon
point2D subjectPolygon[] = {
{50,150}, {200,50}, {350,150},
{350,300},{250,300},{200,250},
{150,350},{100,250},{100,200}
};
int subjectPolygonSize = sizeof(subjectPolygon) / sizeof(subjectPolygon[0]);
// clipping polygon
point2D clipPolygon[] = { {100,100}, {300,100}, {300,300}, {100,300} };
int clipPolygonSize = sizeof(clipPolygon) / sizeof(clipPolygon[0]);
// define the new clipped polygon (empty)
int newPolygonSize = 0;
point2D newPolygon[N] = { 0 };
// apply clipping
SutherlandHodgman(subjectPolygon, subjectPolygonSize, clipPolygon, clipPolygonSize, newPolygon, newPolygonSize);
// print clipped polygon points
cout << "Clipped polygon points:" << endl;
for(int i = 0; i < newPolygonSize; i++)
cout << "(" << newPolygon[i].x << ", " << newPolygon[i].y << ")" << endl;
return 0;
}
</lang>
{{out}}
<pre>Clipped polygon points:
(300, 300)
(250, 300)
(200, 250)
(175, 300)
(125, 300)
(100, 250)
(100, 116.667)
(125, 100)
(275, 100)
(300, 116.667)</pre>
=={{header|D}}==
Line 1,428:
275.00000000000000 100.00000000000000
300.00000000000000 116.66666666666666
300.00000000000000 300.00000000000000
=={{header|Go}}==
Line 2,322:
<pre>Clipped polygon:
(100 116.666666666667) (125 100) (275 100) (300 116.666666666667) (300 300) (250 300) (200 250) (175 300) (125 300) (100 250)</pre>
=={{header|Phix}}==
Line 2,819 ⟶ 2,749:
(point 275 100)
(point 300 350/3))</lang>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.11}}
{{trans|Sidef}}
<lang perl6>sub intersection ($L11, $L12, $L21, $L22) {
my ($Δ1x, $Δ1y) = $L11 »-« $L12;
my ($Δ2x, $Δ2y) = $L21 »-« $L22;
my $n1 = $L11[0] * $L12[1] - $L11[1] * $L12[0];
my $n2 = $L21[0] * $L22[1] - $L21[1] * $L22[0];
my $n3 = 1 / ($Δ1x * $Δ2y - $Δ2x * $Δ1y);
(($n1 * $Δ2x - $n2 * $Δ1x) * $n3, ($n1 * $Δ2y - $n2 * $Δ1y) * $n3)
}
sub is-inside ($p1, $p2, $p3) {
($p2[0] - $p1[0]) * ($p3[1] - $p1[1]) > ($p2[1] - $p1[1]) * ($p3[0] - $p1[0])
}
sub sutherland-hodgman (@polygon, @clip) {
my @output = @polygon;
my $clip-point1 = @clip.tail;
for @clip -> $clip-point2 {
my @input = @output;
@output = ();
my $start = @input.tail;
for @input -> $end {
if is-inside($clip-point1, $clip-point2, $end) {
@output.push: intersection($clip-point1, $clip-point2, $start, $end)
unless is-inside($clip-point1, $clip-point2, $start);
@output.push: $end;
} elsif is-inside($clip-point1, $clip-point2, $start) {
@output.push: 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);
say "Clipped polygon: ", @clipped;
# Output an SVG as well as it is easier to visualize
use SVG;
my $outfile = 'Sutherland-Hodgman-polygon-clipping-perl6.svg'.IO.open(:w);
$outfile.say: SVG.serialize(
svg => [
:400width, :400height,
:rect[ :400width, :400height, :fill<white> ],
:text[ :10x, :20y, "Polygon (blue)" ],
:text[ :10x, :35y, "Clip port (green)" ],
:text[ :10x, :50y, "Clipped polygon (red)" ],
:polyline[ :points(@polygon.join: ','), :style<stroke:blue>, :fill<blue>, :opacity<.3> ],
:polyline[ :points( @clip.join: ','), :style<stroke:green>, :fill<green>, :opacity<.3> ],
:polyline[ :points(@clipped.join: ','), :style<stroke:red>, :fill<red>, :opacity<.5> ],
],
);</lang>
{{out}}
<pre>Clipped polygon: [(100 116.666667) (125 100) (275 100) (300 116.666667) (300 300) (250 300) (200 250) (175 300) (125 300) (100 250)]</pre>
Also see output image: [https://github.com/thundergnat/rc/blob/master/img/Sutherland-Hodgman-polygon-clipping-perl6.svg offsite SVG image]
=={{header|Ruby}}==
| |||