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