Sutherland-Hodgman polygon clipping: Difference between revisions
Sutherland-Hodgman polygon clipping (view source)
Revision as of 11:16, 11 February 2024
, 3 months ago→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (5 intermediate revisions by 2 users not shown) | |||
Line 2,203:
%{x: 100.0, y: 250.0}
</pre>
=={{header|Evaldraw}}==
{{trans|C}}
This is losely based on the C version. Since Evaldraw doesnt have dynamic memory, all sizes must be declared up front. We limit ourselves to polygons of up to 32 vertices. This is fine, as the input polygon with its 9 vertices, when clipped against the clipper rectangle only produces a 11 vertex polygon. If we run out of vertices at runtime, the errno function is called and displays an error number.
[[File:Evaldraw sutherland hodgman.png|thumb|alt=An 9 vertex polygon clipped against a rectangle|Shows input subject polygon vert count and output vert count]]
<syntaxhighlight lang="c">
struct vec{ x, y; };
enum{MAX_POLY_VERTS=32};
enum{NUM_RECT_VERTS=4, NUM_SUBJECT_VERTS=9}
struct poly_t{
len; // number of vertices
vec v[MAX_POLY_VERTS]; // wrap array of vertices inside struct
};
()
{
vec subject_verts[NUM_SUBJECT_VERTS] = { 50,150, 200,50, 350,150, 350,300,250,300,200,250, 150,350,100,250,100,200 };
vec rectangle_vertices[NUM_RECT_VERTS] = {100,100, 300,100, 300,300, 100,300};
poly_t clipper; // This polygon will define the valid area
clipper.len = 0;
for(i=0; i<NUM_RECT_VERTS; i++) {
poly_append( clipper, rectangle_vertices[i] );
}
poly_t subject; // This polygon will be clipped so its contained within the valid area.
subject.len = 0;
for(i=0; i<NUM_SUBJECT_VERTS; i++) {
poly_append( subject, subject_verts[i] );
}
poly_t clipped_result; poly_clip(subject, clipper, clipped_result);
cls(0);
setcol(255,255,255); drawpoly(clipper, 0);
setcol(255,0,255); drawpoly(subject, 0);
setcol(255,255,0); drawpoly(clipped_result, 1);
moveto(0,0); printf("%g in\n%2.0f out", subject.len, clipped_result.len);
}
poly_clip(poly_t subject, poly_t clip, poly_t pout) {
dir = poly_winding(clip);
// Clip all subject edges against first edge in clipper
poly_t p0; // current set of clipped edges
poly_t p1; // next set of clipped edges
p1.len = 0; // Clear p1
poly_edge_clip(subject, clip.v[clip.len - 1], clip.v[0], dir, p1);
for (i = 0; i < clip.len - 1; i++) { // Visit each edge in the clip polygon
poly_copy(p1,p0); // Copy p1 into p0. We could also have done p0=p1.
p1.len = 0; // Clear p1
poly_edge_clip(p0, clip.v[i], clip.v[i+1], dir, p1);
if(p1.len == 0) break; // no vertices in output, finished.
}
pout = p1;
}
poly_winding(poly_t p) {
return left_of(p.v[0], p.v[1], p.v[2]);
}
poly_edge_clip(poly_t subject, vec clip0, vec clip1, left, poly_t res) {
vec v0; v0 = subject.v[subject.len - 1];
if (res.len != 0) errno(200); // Expect empty result so far
side0 = left_of(clip0, clip1, v0);
if (side0 != -left) { poly_append(res, v0); }
// Intersect subject edge v0-v1 against clipper edge clip0-clip1
for (i = 0; i < subject.len; i++) {
vec v1; v1 = subject.v[i];
side1 = left_of(clip0, clip1, v1);
// side0+side1==0 means v0 and v1 cross the edge. v0 is inside.
if ( (side0 + side1 == 0) && side0) {
vec isect; if (line_sect(clip0, clip1, v0, v1, isect)) poly_append(res, isect);
}
if (i == subject.len - 1) break; // Back to last, finished
if (side1 != -left) { poly_append(res, v1); } // add v1 to poly
v0 = v1;
side0 = side1;
}
}
poly_append(poly_t p, vec v) {
p.v[p.len++] = v;
if(p.len>MAX_POLY_VERTS) errno(100);
}
poly_copy(poly_t src, poly_t dst) { // This improves on assigning dst to src as
for(i=0; i<src.len; i++) { // only necessary amount of vertices are copied.
dst.v[i] = src.v[i];
}
dst.len = src.len;
}
left_of(vec a, vec b, vec c) {
vec ab; vsub(ab, b, a);
vec bc; vsub(bc, c, b);
return sgn( cross2D(ab, bc) ); // return 1 if ab is left side of c. -1 if right. 0 if colinear.
}
line_sect(vec a0, vec a1, vec b0, vec b1, vec isect) {
vec da; vsub(da,a1,a0);
vec db; vsub(db,b1,b0);
vec d; vsub(d,a0, b0);
/* a0+t da = b0+s db -> a0 X da = b0 X da + s db X da -> s = (a0 - b0) X da / (db X da) */
double dbXda = cross2D(db, da);
if (!dbXda) return 0;
s = cross2D(&d, &da) / dbXda;
if (s <= 0 || s >= 1) return 0;
isect.x = b0.x + s * db.x;
isect.y = b0.y + s * db.y;
return 1;
}
errno(code) { // Since we dont have asserts, halt and print an error code
while(1) {
cls(32,32,32); setcol(200,0,0); moveto(0,0);
printf("errno(%g)", code); refresh(); sleep(1);
}
}
drawpoly(poly_t p, show_verts) {
for(i=0; i<p.len+1; i++) {
vec v = p.v[i%p.len];
if (show_verts) for(j=0; j<32; j++) { setpix( v.x+nrnd, v.y+nrnd); }
if(i==0) moveto(v.x,v.y); else lineto(v.x,v.y);
}
}
// 2D cross product - also known as directed area product.
cross2D(vec a, vec b) { return a.x * b.y - a.y * b.x; }
vsub(vec c, vec a, vec b) { c.x = a.x - b.x; c.y = a.y - b.y; }
</syntaxhighlight>
=={{header|Fortran}}==
Line 3,296 ⟶ 3,419:
>> axis square</syntaxhighlight>
[[File:Sutherland-Hodgman_MATLAB.png]]
=={{header|Mercury}}==
{{trans|ATS}}
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">
:- module sutherland_hodgman_task.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module exception.
:- import_module float.
:- import_module list.
:- import_module pair.
:- import_module string.
:- type plane_point == pair(float).
:- func xcoord(plane_point) = float.
:- func ycoord(plane_point) = float.
:- func plane_point(float, float) = plane_point.
:- pred write_plane_point(plane_point::in, io::di, io::uo) is det.
:- pred write_plane_point_list(list(plane_point)::in, string::in,
io::di, io::uo) is det.
xcoord(Pt) = fst(Pt).
ycoord(Pt) = snd(Pt).
plane_point(X, Y) = pair(X, Y).
write_plane_point(Pt, !IO) :-
write_string("(", !IO),
write_float(xcoord(Pt), !IO),
write_string(", ", !IO),
write_float(ycoord(Pt), !IO),
write_string(")", !IO).
write_plane_point_list(Pts, Separator, !IO) :-
write_list(Pts, Separator, write_plane_point, !IO).
:- type plane_edge == pair(plane_point).
:- func point0(plane_edge) = plane_point.
:- func point1(plane_edge) = plane_point.
:- func plane_edge(plane_point, plane_point) = plane_edge.
point0(Edge) = fst(Edge).
point1(Edge) = snd(Edge).
plane_edge(Pt0, Pt1) = pair(Pt0, Pt1).
:- func evaluate_line(float, float, float, float, float) = float.
evaluate_line(X1, Y1, X2, Y2, X) = Y :-
%% Given the line (X1,Y1)--(X2,Y2), evaluate it at X.
Dy = Y2 - Y1,
Dx = X2 - X1,
Slope = Dy / Dx,
Intercept = ((Dx * Y1) - (Dy * X1)) / Dx,
Y = (Slope * X) + Intercept.
:- func intersection_of_lines(float, float, float, float,
float, float, float, float)
= plane_point.
intersection_of_lines(X1, Y1, X2, Y2, X3, Y3, X4, Y4) = Pt :-
%% Given the lines (X1,Y1)--(X2,Y2) and (X3,Y3)--(X3,Y4), find their
%% point of intersection.
(if (X1 = X2)
then (Pt = plane_point(X1, evaluate_line(X3, Y3, X4, Y4, X1)))
else if (X3 = X4)
then (Pt = plane_point(X3, evaluate_line(X1, Y1, X2, Y2, X3)))
else (Pt = plane_point(X, Y),
X = Xnumerator / Denominator,
Y = Ynumerator / Denominator,
Denominator =
((X1 - X2) * (Y3 - Y4)) - ((Y1 - Y2) * (X3 - X4)),
Xnumerator =
(X1Y2_Y1X2 * (X3 - X4)) - ((X1 - X2) * X3Y4_Y3X4),
Ynumerator =
(X1Y2_Y1X2 * (Y3 - Y4)) - ((Y1 - Y2) * X3Y4_Y3X4),
X1Y2_Y1X2 = (X1 * Y2) - (Y1 * X2),
X3Y4_Y3X4 = (X3 * Y4) - (Y3 * X4))).
:- func intersection_of_edges(plane_edge, plane_edge) = plane_point.
intersection_of_edges(E1, E2) = Pt :-
%% Given two edges, find their point of intersection (on the
%% assumption that there is such an intersection).
Pt = intersection_of_lines(X1, Y1, X2, Y2, X3, Y3, X4, Y4),
Pt1 = point0(E1), Pt2 = point1(E1),
Pt3 = point0(E2), Pt4 = point1(E2),
X1 = xcoord(Pt1), Y1 = ycoord(Pt1),
X2 = xcoord(Pt2), Y2 = ycoord(Pt2),
X3 = xcoord(Pt3), Y3 = ycoord(Pt3),
X4 = xcoord(Pt4), Y4 = ycoord(Pt4).
:- pred point_is_left_of_edge(plane_point::in, plane_edge::in)
is semidet.
point_is_left_of_edge(Pt, Edge) :-
%% Is Pt left of Edge?
(OP < 0.0),
%% OP = outer product of the vectors (x1,y1)-->(x,y) and
%% (x1,y1)-->(x2,y2). *)
OP = ((X - X1) * (Y2 - Y1)) - ((X2 - X1) * (Y - Y1)),
Pt1 = point0(Edge), Pt2 = point1(Edge),
X1 = xcoord(Pt1), Y1 = ycoord(Pt1),
X2 = xcoord(Pt2), Y2 = ycoord(Pt2),
X = xcoord(Pt), Y = ycoord(Pt).
:- func clip_subject_edge(plane_edge, plane_edge,
list(plane_point)) = list(plane_point).
clip_subject_edge(Subject_edge, Clip_edge, Accum0) = Accum :-
S1 = point0(Subject_edge), S2 = point1(Subject_edge),
(if (point_is_left_of_edge(S2, Clip_edge))
then (if (point_is_left_of_edge(S1, Clip_edge))
then (Accum = [S2 | Accum0])
else (Accum = [S2, Intersection | Accum0],
Intersection =
intersection_of_edges(Subject_edge, Clip_edge)))
else (if (point_is_left_of_edge(S1, Clip_edge))
then (Accum = [Intersection | Accum0],
Intersection =
intersection_of_edges(Subject_edge, Clip_edge))
else (Accum = Accum0))).
:- func plane_points_to_plane_edges(list(plane_point))
= list(plane_edge).
plane_points_to_plane_edges(Pts) = Edges :-
plane_points_to_plane_edges_(Pt_first, Pts, [], Edges),
Pt_first = det_head(Pts).
:- pred plane_points_to_plane_edges_(plane_point::in,
list(plane_point)::in,
list(plane_edge)::in,
list(plane_edge)::out) is det.
%% Convert a list of points to a list of edges.
plane_points_to_plane_edges_(Pt_first, [Pt0, Pt1 | Rest],
Edges0, Edges) :-
plane_points_to_plane_edges_(Pt_first, [Pt1 | Rest],
[plane_edge(Pt0, Pt1) | Edges0],
Edges).
plane_points_to_plane_edges_(Pt_first, [Pt_last], Edges0, Edges) :-
Edges = [plane_edge(Pt_last, Pt_first) | reverse(Edges0)].
plane_points_to_plane_edges_(_, [], _, _) :-
throw("list(plane_point) was expected to have length >= 2").
:- pred for_each_subject_edge(list(plane_edge)::in, plane_edge::in,
list(plane_point)::in,
list(plane_point)::out) is det.
for_each_subject_edge([], _, Accum0, Accum) :-
(Accum = reverse(Accum0)).
for_each_subject_edge([Subject_edge | Rest], Clip_edge,
Accum0, Accum) :-
Accum1 = clip_subject_edge(Subject_edge, Clip_edge, Accum0),
for_each_subject_edge(Rest, Clip_edge, Accum1, Accum).
:- func clip_subject_with_clip_edge(list(plane_point), plane_edge)
= list(plane_point).
clip_subject_with_clip_edge(Subject_pts, Clip_edge) = Pts :-
for_each_subject_edge(Subject_edges, Clip_edge, [], Pts),
Subject_edges = plane_points_to_plane_edges(Subject_pts).
:- pred for_each_clip_edge(list(plane_point)::in,
list(plane_point)::out,
list(plane_edge)::in) is det.
for_each_clip_edge(Subject_pts0, Subject_pts, []) :-
(Subject_pts = Subject_pts0).
for_each_clip_edge(Subject_pts0, Subject_pts,
[Clip_edge | Rest]) :-
Subject_pts1 = clip_subject_with_clip_edge(Subject_pts0, Clip_edge),
for_each_clip_edge(Subject_pts1, Subject_pts, Rest).
:- func clip(list(plane_point), list(plane_point))
= list(plane_point).
clip(Subject_pts, Clip_pts) = Result_pts :-
for_each_clip_edge(Subject_pts, Result_pts, Clip_edges),
Clip_edges = plane_points_to_plane_edges(Clip_pts).
:- pred moveto(text_output_stream::in, plane_point::in,
io::di, io::uo) is det.
moveto(Stream, Pt, !IO) :-
write_float(Stream, xcoord(Pt), !IO),
write_string(Stream, " ", !IO),
write_float(Stream, ycoord(Pt), !IO),
write_string(Stream, " moveto\n", !IO).
:- pred lineto(plane_point::in, io::di, io::uo) is det.
lineto(Pt, !IO) :-
write_float(xcoord(Pt), !IO),
write_string(" ", !IO),
write_float(ycoord(Pt), !IO),
write_string(" lineto\n", !IO).
:- pred setrgbcolor(text_output_stream::in,
string::in, io::di, io::uo) is det.
setrgbcolor(Stream, Color, !IO) :-
write_string(Stream, Color, !IO),
write_string(Stream, " setrgbcolor\n", !IO).
:- pred write_polygon(text_output_stream::in,
list(plane_point)::in,
string::in, string::in,
io::di, io::uo) is det.
write_polygon(Stream, Pts, Line_color, Fill_color, !IO) :-
if ([First_pt | Rest] = Pts)
then (moveto(Stream, First_pt, !IO),
write_list(Stream, Rest, "", lineto, !IO),
write_string(Stream, "closepath\n", !IO),
setrgbcolor(Stream, Line_color, !IO),
write_string(Stream, "gsave\n", !IO),
setrgbcolor(Stream, Fill_color, !IO),
write_string(Stream, "fill\n", !IO),
write_string(Stream, "grestore\n", !IO),
write_string(Stream, "stroke\n", !IO))
else true.
:- pred write_eps(text_output_stream::in,
list(plane_point)::in,
list(plane_point)::in,
list(plane_point)::in,
io::di, io::uo) is det.
write_eps(Stream, Subject_pts, Clip_pts, Result_pts, !IO) :-
write_string(Stream, "%!PS-Adobe-3.0 EPSF-3.0\n", !IO),
write_string(Stream, "%%BoundingBox: 40 40 360 360\n", !IO),
write_string(Stream, "0 setlinewidth\n", !IO),
write_polygon(Stream, Clip_pts, ".5 0 0", "1 .7 .7", !IO),
write_polygon(Stream, Subject_pts, "0 .2 .5", ".4 .7 1", !IO),
write_string(Stream, "2 setlinewidth\n", !IO),
write_string(Stream, "[10 8] 0 setdash\n", !IO),
write_polygon(Stream, Result_pts, ".5 0 .5", ".7 .3 .8", !IO),
write_string(Stream, "%%EOF\n", !IO).
:- pred write_eps_to_file(string::in,
list(plane_point)::in,
list(plane_point)::in,
list(plane_point)::in,
io::di, io::uo) is det.
write_eps_to_file(Filename, Subject_pts, Clip_pts, Result_pts, !IO) :-
open_output(Filename, Open_result, !IO),
(if (Open_result = ok(Outp))
then write_eps(Outp, Subject_pts, Clip_pts, Result_pts, !IO)
else throw("Failed to open " ++ Filename ++ " for output.")).
main(!IO) :-
Subject_pts = [plane_point(50.0, 150.0),
plane_point(200.0, 50.0),
plane_point(350.0, 150.0),
plane_point(350.0, 300.0),
plane_point(250.0, 300.0),
plane_point(200.0, 250.0),
plane_point(150.0, 350.0),
plane_point(100.0, 250.0),
plane_point(100.0, 200.0)],
Clip_pts = [plane_point(100.0, 100.0),
plane_point(300.0, 100.0),
plane_point(300.0, 300.0),
plane_point(100.0, 300.0)],
Result_pts = clip(Subject_pts, Clip_pts),
write_plane_point_list(Result_pts, "\n", !IO), nl(!IO),
EPSF = "sutherland-hodgman.eps",
write_eps_to_file(EPSF, Subject_pts, Clip_pts, Result_pts, !IO),
write_string("Wrote " ++ EPSF, !IO), nl(!IO).
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
</syntaxhighlight>
{{out}}
<pre>$ mmc sutherland_hodgman_task.m && ./sutherland_hodgman_task
(100.0, 116.66666666666669)
(124.99999999999999, 100.0)
(275.0, 100.0)
(300.0, 116.66666666666667)
(300.0, 300.0)
(250.0, 300.0)
(200.0, 250.0)
(175.0, 300.0)
(125.0, 300.0)
(100.0, 250.0)
Wrote sutherland-hodgman.eps</pre>
[[File:Sutherland-hodgman-from-mercury.png|alt=The polygons as generated by a Mercury program.]]
=={{header|Modula-2}}==
Line 5,686 ⟶ 6,083:
{{libheader|DOME}}
{{libheader|Wren-polygon}}
<syntaxhighlight lang="
import "dome" for Window
import "./polygon" for Polygon
| |||