1 /* This file is part of the GNU plotutils package. Copyright (C) 1995,
2 1996, 1997, 1998, 1999, 2000, 2005, 2008, Free Software Foundation, Inc.
3
4 The GNU plotutils package is free software. You may redistribute it
5 and/or modify it under the terms of the GNU General Public License as
6 published by the Free Software foundation; either version 2, or (at your
7 option) any later version.
8
9 The GNU plotutils package is distributed in the hope that it will be
10 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with the GNU plotutils package; see the file COPYING. If not, write to
16 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
17 Boston, MA 02110-1301, USA. */
18
19 #include "sys-defines.h"
20 #include "extern.h"
21
22 /* bit fields for return value from Cohen-Sutherland clipper */
23 enum { ACCEPTED = 0x1, CLIPPED_FIRST = 0x2, CLIPPED_SECOND = 0x4 };
24
25 /* for internal clipper use */
26 enum { TOP = 0x1, BOTTOM = 0x2, RIGHT = 0x4, LEFT = 0x8 };
27
28 /* forward references */
29 static int compute_outcode (double x, double y, double x_min_clip, double x_max_clip, double y_min_clip, double y_max_clip);
30
31 /* _clip_line() takes two points, the endpoints of a line segment in the
32 * device frame (expressed in terms of floating-point device coordinates),
33 * and destructively passes back two points: the endpoints of the line
34 * segment clipped by Cohen-Sutherland to the rectangular clipping area.
35 * The return value contains bitfields ACCEPTED, CLIPPED_FIRST, and
36 * CLIPPED_SECOND.
37 */
38
39 int
_clip_line(double * x0_p,double * y0_p,double * x1_p,double * y1_p,double x_min_clip,double x_max_clip,double y_min_clip,double y_max_clip)40 _clip_line (double *x0_p, double *y0_p, double *x1_p, double *y1_p, double x_min_clip, double x_max_clip, double y_min_clip, double y_max_clip)
41 {
42 double x0 = *x0_p;
43 double y0 = *y0_p;
44 double x1 = *x1_p;
45 double y1 = *y1_p;
46 int outcode0, outcode1;
47 bool accepted;
48 int clipval = 0;
49
50 outcode0 = compute_outcode (x0, y0, x_min_clip, x_max_clip, y_min_clip, y_max_clip);
51 outcode1 = compute_outcode (x1, y1, x_min_clip, x_max_clip, y_min_clip, y_max_clip);
52
53 for ( ; ; )
54 {
55 if (!(outcode0 | outcode1)) /* accept */
56 {
57 accepted = true;
58 break;
59 }
60 else if (outcode0 & outcode1) /* reject */
61 {
62 accepted = false;
63 break;
64 }
65 else
66 {
67 /* at least one endpoint is outside; choose one that is */
68 int outcode_out = (outcode0 ? outcode0 : outcode1);
69 double x, y; /* intersection with clip edge */
70
71 if (outcode_out & RIGHT)
72 {
73 x = x_max_clip;
74 y = y0 + (y1 - y0) * (x_max_clip - x0) / (x1 - x0);
75 }
76 else if (outcode_out & LEFT)
77 {
78 x = x_min_clip;
79 y = y0 + (y1 - y0) * (x_min_clip - x0) / (x1 - x0);
80 }
81 else if (outcode_out & TOP)
82 {
83 x = x0 + (x1 - x0) * (y_max_clip - y0) / (y1 - y0);
84 y = y_max_clip;
85 }
86 else
87 {
88 x = x0 + (x1 - x0) * (y_min_clip - y0) / (y1 - y0);
89 y = y_min_clip;
90 }
91
92 if (outcode_out == outcode0)
93 {
94 x0 = x;
95 y0 = y;
96 outcode0 = compute_outcode (x0, y0, x_min_clip, x_max_clip, y_min_clip, y_max_clip);
97 }
98 else
99 {
100 x1 = x;
101 y1 = y;
102 outcode1 = compute_outcode (x1, y1, x_min_clip, x_max_clip, y_min_clip, y_max_clip);
103 }
104 }
105 }
106
107 if (accepted)
108 {
109 clipval |= ACCEPTED;
110 if ((x0 != *x0_p) || (y0 != *y0_p))
111 clipval |= CLIPPED_FIRST;
112 if ((x1 != *x1_p) || (y1 != *y1_p))
113 clipval |= CLIPPED_SECOND;
114 *x0_p = x0;
115 *y0_p = y0;
116 *x1_p = x1;
117 *y1_p = y1;
118 }
119
120 return clipval;
121 }
122
123 static int
compute_outcode(double x,double y,double x_min_clip,double x_max_clip,double y_min_clip,double y_max_clip)124 compute_outcode (double x, double y, double x_min_clip, double x_max_clip, double y_min_clip, double y_max_clip)
125 {
126 int code = 0;
127
128 if (x > x_max_clip)
129 code |= RIGHT;
130 else if (x < x_min_clip)
131 code |= LEFT;
132 if (y > y_max_clip)
133 code |= TOP;
134 else if (y < y_min_clip)
135 code |= BOTTOM;
136
137 return code;
138 }
139