1 /*****************************************************************************
2 *
3 * Elmer, A Finite Element Software for Multiphysical Problems
4 *
5 * Copyright 1st April 1995 - , CSC - IT Center for Science Ltd., Finland
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library (in file ../LGPL-2.1); if not, write
19 * to the Free Software Foundation, Inc., 51 Franklin Street,
20 * Fifth Floor, Boston, MA 02110-1301 USA
21 *
22 *****************************************************************************/
23
24 /*******************************************************************************
25 *
26 * Clipping routines for MATC graphics.
27 *
28 *******************************************************************************
29 *
30 * Author: Juha Ruokolainen
31 *
32 * Address: CSC - IT Center for Science Ltd.
33 * Keilaranta 14, P.O. BOX 405
34 * 02101 Espoo, Finland
35 * Tel. +358 0 457 2723
36 * Telefax: +358 0 457 2302
37 * EMail: Juha.Ruokolainen@csc.fi
38 *
39 * Date: 30 May 1996
40 *
41 * Modified by:
42 *
43 * Date of modification:
44 *
45 ******************************************************************************/
46 /**************************************************************************
47 *
48 * by Otto Pesonen
49 *
50 * Started 08-SEP-88 / OP
51 * Last edited 16-FEB-89 / OP
52 *
53 * Version: 0.0
54 * File : clip.c
55 *
56 * Clip a polygon against any bounding box
57 * An example program.
58 *
59 ************************************o*************************************/
60
61
62 /*
63 * $Id: clip.c,v 1.2 2005/05/27 12:26:19 vierinen Exp $
64 *
65 * $Log: clip.c,v $
66 * Revision 1.2 2005/05/27 12:26:19 vierinen
67 * changed header install location
68 *
69 * Revision 1.1.1.1 2005/04/14 13:29:14 vierinen
70 * initial matc automake package
71 *
72 * Revision 1.2 1998/08/01 12:34:31 jpr
73 *
74 * Added Id, started Log.
75 *
76 *
77 */
78
79 #include "elmer/matc.h"
80
81 /**************************************************************************
82 Clip a 2D-polygon against clipping box
83 If all points are inside the clipping box the polygon is trivially
84 accepted.
85 Otherwise it is clipped in turn against single clipping edge.
86
87 RETURN: Number of points in the polygon inside the box
88
89 NOTICE! The new number of points may be GRATER than the in origin!
90 The theoretical number of points newer execeeds twice
91 the number in origin.
92 ************************************o*************************************/
clip_poly(n,x,y)93 int clip_poly(n,x,y)
94 int *n; /* Number of points in polygon */
95 double *x,*y; /* Coordinate arrays of the polygon */
96 {
97 int last, /* Last point code (in/out?) */
98 this; /* Current point code (in/out?) */
99 int i,j,k; /* Arrays index (orig, new & temp) */
100 int nn; /* Internal counter of points */
101 int eg; /* Current edge for clipping */
102 int icode; /* Sum of points inside bounding box */
103 double xx,yy; /* Current point coordinates, i:th */
104 double cx,cy; /* Coordinates of the clipped point */
105 double lx,ly; /* Coordinates of the previous point */
106 double dx,dy; /* Length of the line segment */
107
108 nn = *n;
109 icode = 0;
110 last = FALSE;
111
112 for(i=0; i<nn ; i++)
113 if (x[i]<=CL_XMAX && x[i]>=CL_XMIN &&
114 y[i]<=CL_YMAX && y[i]>=CL_YMIN) icode++;
115 if(icode == nn) return(nn); /* All points inside the box! */
116
117 for( eg=0 ; eg<4 ; eg++) /* Loop over all the edges */
118 {
119 x[nn] = x[0]; /* Handle the first point */
120 y[nn] = y[0]; /* this eases the program a lot! */
121 nn++;
122
123 for(i=j=0 ; i<nn ; i++) /* Loop over the points! */
124 {
125 xx=x[i];
126 yy=y[i];
127
128 this = FALSE;
129 switch(eg) /* Code the current point */
130 {
131 case 0: if (yy <= CL_YMAX) this = TRUE; break;
132 case 1: if (yy >= CL_YMIN) this = TRUE; break;
133 case 2: if (xx <= CL_XMAX) this = TRUE; break;
134 case 3: if (xx >= CL_XMIN) this = TRUE; break;
135 }
136
137 if(i>0)
138 {
139 if((this && !last) || (last && !this))
140 {
141 dx = xx-lx;
142 dy = yy-ly;
143 switch(eg) /* Cut against edge */
144 {
145 case 0:
146 cx = lx + ((CL_YMAX-ly)*dx)/dy;
147 cy = CL_YMAX;
148 break;
149 case 1:
150 cx = lx + ((CL_YMIN-ly)*dx)/dy;
151 cy = CL_YMIN;
152 break;
153 case 2:
154 cy = ly + ((CL_XMAX-lx)*dy)/dx;
155 cx = CL_XMAX;
156 break;
157 case 3:
158 cy = ly + ((CL_XMIN-lx)*dy)/dx;
159 cx = CL_XMIN;
160 break;
161 }
162 }
163
164 if(last) /* Decide to store the point(s) */
165 if(this)
166 { x[j]=xx; y[j]=yy; j++; }
167 else
168 { x[j]=cx; y[j]=cy; j++; }
169 else
170 if(this)
171 {
172 if(j+2 > i) /* Too many points whitout shift */
173 {
174 for(k=nn; k>i ; k--) { x[k]=x[k-1]; y[k]=y[k-1]; }
175 nn++;
176 i++; /* Update pointer AND the limit */
177 }
178 x[j]=cx; y[j]=cy; j++; /* Store two points */
179 x[j]=xx; y[j]=yy; j++;
180 }
181 }
182 else
183 if(this) /* Store the first point */
184 { x[j]=xx; y[j]=yy; j++; }
185
186 lx = xx;
187 ly = yy;
188 last = this; /* Save the last point */
189
190 }
191 *n = j;
192 if(!j) return(j); /* No need to proceed */
193 nn = j;
194 }
195 *n = j;
196 return(j);
197 }
198
199 #define NULL_EDGE 0
200 #define LEFT_EDGE 1
201 #define RIGHT_EDGE 2
202 #define BOTTOM_EDGE 4
203 #define TOP_EDGE 8
204
clip_code(x,y,c)205 void clip_code(x,y,c) double x,y; int *c;
206 {
207 *c = NULL_EDGE;
208
209 if (x < CL_XMIN)
210 *c = LEFT_EDGE;
211 else if (x > CL_XMAX)
212 *c = RIGHT_EDGE;
213
214 if (y < CL_YMIN)
215 *c |= BOTTOM_EDGE;
216 else if (y > CL_YMAX)
217 *c |= TOP_EDGE;
218 }
219
220 /*
221 * Polyline clipping routine. Return value is number of points inside
222 * clipping limits when first linesegment not totally inside
223 * the limits is found (the last one is included in the count if it is
224 * part of a visible line segment). One should call this routine repeatedly
225 * until all the linesegments in the polyline are handled. Edge crossing
226 * points of the last linesegment are stored in place of originals.
227 */
clip_line(n,x,y)228 int clip_line(n,x,y)
229 int *n;
230 double *x, *y;
231 {
232 double xx, yy,
233 px, py;
234
235 int i,c,c1,c2;
236
237 px = x[0];
238 py = y[0];
239 clip_code(px,py,&c1);
240 for(i = 1; i < *n; i++)
241 {
242 clip_code(x[i],y[i],&c2);
243 if (c1 || c2)
244 {
245 while(c1 || c2)
246 {
247 if (c1 & c2)
248 {
249 *n = i;
250 return *n;
251 }
252
253 c = c1 ? c1 : c2;
254
255 if (c & LEFT_EDGE)
256 {
257 yy = py+(y[i]-py)*(CL_XMIN-px)/(x[i]-px);
258 xx = CL_XMIN;
259 }
260 else if (c & RIGHT_EDGE)
261 {
262 yy = py+(y[i]-py)*(CL_XMAX-px)/(x[i]-px);
263 xx = CL_XMAX;
264 }
265 else if (c & BOTTOM_EDGE)
266 {
267 xx = px+(x[i]-px)*(CL_YMIN-py)/(y[i]-py);
268 yy = CL_YMIN;
269 }
270 else if (c & TOP_EDGE)
271 {
272 xx = px+(x[i]-px)*(CL_YMAX-py)/(y[i]-py);
273 yy = CL_YMAX;
274 }
275
276 if (c == c1)
277 {
278 x[i-1] = px = xx;
279 y[i-1] = py = yy;
280 clip_code(xx,yy,&c1);
281 }
282 else
283 {
284 x[i] = xx;
285 y[i] = yy;
286 clip_code(xx,yy,&c2);
287 }
288 }
289 *n = i + 1;
290 return *n;
291 }
292 px = x[i];
293 py = y[i];
294 c1 = c2;
295 }
296 return *n;
297 }
298