1 /* $Id: plfill.c,v 1.3 2007/05/08 09:09:37 rice Exp $
2
3 Polygon pattern fill.
4
5 Copyright (C) 2004 Alan W. Irwin
6
7 This file is part of PLplot.
8
9 PLplot is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Library Public License as published
11 by the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13
14 PLplot is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU Library General Public License for more details.
18
19 You should have received a copy of the GNU Library General Public License
20 along with PLplot; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22
23 */
24
25 #include "plplotP.h"
26
27 #define DTOR 0.0174533
28 #define BINC 50
29
30 struct point {
31 PLINT x, y;
32 };
33 static PLINT bufferleng, buffersize, *buffer;
34
35 /* Static function prototypes */
36 /* INDENT OFF */
37
38 static int compar (const void *, const void *);
39 static void addcoord (PLINT, PLINT);
40 static void tran (PLINT *, PLINT *, PLFLT, PLFLT);
41 static void buildlist (PLINT, PLINT, PLINT, PLINT, PLINT, PLINT, PLINT);
42
43 /* INDENT ON */
44
45 /*----------------------------------------------------------------------*\
46 * void plfill()
47 *
48 * Pattern fills the polygon bounded by the input points.
49 * If hardware fill is used, a maximum of PL_MAXPOLY-1 vertices is allowed.
50 * The final point is explicitly added if it doesn't match up to the first,
51 * to prevent clipping problems.
52 \*----------------------------------------------------------------------*/
53
54 void
c_plfill(PLINT n,PLFLT * x,PLFLT * y)55 c_plfill(PLINT n, PLFLT *x, PLFLT *y)
56 {
57 PLINT xpoly[PL_MAXPOLY], ypoly[PL_MAXPOLY];
58 PLINT i;
59
60 if (plsc->level < 3) {
61 plabort("plfill: Please set up window first");
62 return;
63 }
64 if (n < 3) {
65 plabort("plfill: Not enough points in object");
66 return;
67 }
68 if (n > PL_MAXPOLY-1) {
69 plwarn("plfill: too many points in polygon");
70 n = PL_MAXPOLY;
71 }
72 for (i = 0; i < n; i++) {
73 xpoly[i] = plP_wcpcx(x[i]);
74 ypoly[i] = plP_wcpcy(y[i]);
75 }
76
77 if (x[0] != x[n-1] || y[0] != y[n-1]) {
78 n++;
79 xpoly[n-1] = plP_wcpcx(x[0]);
80 ypoly[n-1] = plP_wcpcy(y[0]);
81 }
82
83 plP_plfclp(xpoly, ypoly, n, plsc->clpxmi, plsc->clpxma,
84 plsc->clpymi, plsc->clpyma, plP_fill);
85 }
86
87 /*----------------------------------------------------------------------*\
88 * void plfill3()
89 *
90 * Pattern fills the polygon in 3d bounded by the input points.
91 * If hardware fill is used, a maximum of PL_MAXPOLY-1 vertices is allowed.
92 * The final point is explicitly added if it doesn't match up to the first,
93 * to prevent clipping problems.
94 \*----------------------------------------------------------------------*/
95
96 void
c_plfill3(PLINT n,PLFLT * x,PLFLT * y,PLFLT * z)97 c_plfill3(PLINT n, PLFLT *x, PLFLT *y, PLFLT *z)
98 {
99 PLFLT tx[PL_MAXPOLY], ty[PL_MAXPOLY], tz[PL_MAXPOLY];
100 PLFLT *V[3];
101 PLINT xpoly[PL_MAXPOLY], ypoly[PL_MAXPOLY];
102 PLINT i;
103 PLFLT xmin, xmax, ymin, ymax, zmin, zmax, zscale;
104
105 if (plsc->level < 3) {
106 plabort("plfill3: Please set up window first");
107 return;
108 }
109 if (n < 3) {
110 plabort("plfill3: Not enough points in object");
111 return;
112 }
113 if (n > PL_MAXPOLY-1) {
114 plwarn("plfill3: too many points in polygon");
115 n = PL_MAXPOLY;
116 }
117
118 plP_gdom(&xmin, &xmax, &ymin, &ymax);
119 plP_grange(&zscale, &zmin, &zmax);
120
121 /* copy the vertices so we can clip without corrupting the input */
122 for( i=0; i < n; i++ ) {
123 tx[i] = x[i]; ty[i] = y[i]; tz[i] = z[i];
124 }
125 if (tx[0] != tx[n-1] || ty[0] != ty[n-1] || tz[0] != tz[n-1]) {
126 tx[n] = tx[0]; ty[n] = ty[0]; tz[n] = tz[0];
127 n++;
128 }
129 V[0] = tx; V[1] = ty; V[2] = tz;
130 n = plP_clip_poly(n, V, 0, 1, -xmin);
131 n = plP_clip_poly(n, V, 0, -1, xmax);
132 n = plP_clip_poly(n, V, 1, 1, -ymin);
133 n = plP_clip_poly(n, V, 1, -1, ymax);
134 n = plP_clip_poly(n, V, 2, 1, -zmin);
135 n = plP_clip_poly(n, V, 2, -1, zmax);
136 for( i=0; i < n; i++ ) {
137 xpoly[i] = plP_wcpcx(plP_w3wcx( tx[i], ty[i], tz[i] ));
138 ypoly[i] = plP_wcpcy(plP_w3wcy( tx[i], ty[i], tz[i] ));
139 }
140
141 /* AWI: in the past we have used
142 * plP_fill(xpoly, ypoly, n);
143 * here, but our educated guess is this fill should be done via the clipping
144 * interface instead as below.
145 * No example tests this code so one of our users will end up inadvertently
146 * testing this for us.
147 *
148 * jc: I have checked, and both versions does give the same result, i.e., clipping
149 * to the window boundaries. The reason is that the above plP_clip_poly() does
150 * the clipping. To check this, is enough to diminish the x/y/z min/max arguments in
151 * plw3d() in x08c. But let's keep it, although 10% slower...
152 */
153 plP_plfclp(xpoly, ypoly, n, plsc->clpxmi, plsc->clpxma,
154 plsc->clpymi, plsc->clpyma, plP_fill);
155 }
156
157 /*----------------------------------------------------------------------*\
158 * void plfill_soft()
159 *
160 * Pattern fills in software the polygon bounded by the input points.
161 \*----------------------------------------------------------------------*/
162
163 void
plfill_soft(short * x,short * y,PLINT n)164 plfill_soft(short *x, short *y, PLINT n)
165 {
166 PLINT i, j;
167 PLINT xp1, yp1, xp2, yp2, xp3, yp3;
168 PLINT k, dinc;
169 PLFLT ci, si;
170 double temp;
171
172 buffersize = 2 * BINC;
173 buffer = (PLINT *) malloc((size_t) buffersize * sizeof(PLINT));
174 if ( ! buffer) {
175 plabort("plfill: Out of memory");
176 return;
177 }
178
179 /* Loop over sets of lines in pattern */
180
181 for (k = 0; k < plsc->nps; k++) {
182 bufferleng = 0;
183
184 temp = DTOR * plsc->inclin[k] * 0.1;
185 si = sin(temp) * plsc->ypmm;
186 ci = cos(temp) * plsc->xpmm;
187
188 /* normalize: 1 = si*si + ci*ci */
189
190 temp = sqrt((double) (si*si + ci*ci));
191 si /= temp;
192 ci /= temp;
193
194 dinc = plsc->delta[k] * SSQR(plsc->ypmm * ABS(ci),
195 plsc->xpmm * ABS(si)) / 1000.;
196
197 if (dinc < 0) dinc = -dinc;
198 if (dinc == 0) dinc = 1;
199
200 xp1 = x[n-2];
201 yp1 = y[n-2];
202 tran(&xp1, &yp1, (PLFLT) ci, (PLFLT) si);
203
204 xp2 = x[n-1];
205 yp2 = y[n-1];
206 tran(&xp2, &yp2, (PLFLT) ci, (PLFLT) si);
207
208 /* Loop over points in polygon */
209
210 for (i = 0; i < n; i++) {
211 xp3 = x[i];
212 yp3 = y[i];
213 tran(&xp3, &yp3, (PLFLT) ci, (PLFLT) si);
214 buildlist(xp1, yp1, xp2, yp2, xp3, yp3, dinc);
215 xp1 = xp2;
216 yp1 = yp2;
217 xp2 = xp3;
218 yp2 = yp3;
219 }
220
221 /* Sort list by y then x */
222
223 qsort((void *) buffer, (size_t) bufferleng / 2,
224 (size_t) sizeof(struct point), compar);
225
226 /* OK, now do the hatching */
227
228 i = 0;
229
230 while (i < bufferleng) {
231 xp1 = buffer[i];
232 yp1 = buffer[i + 1];
233 i += 2;
234 xp2 = xp1;
235 yp2 = yp1;
236 tran(&xp1, &yp1, (PLFLT) ci, (PLFLT) (-si));
237 plP_movphy(xp1, yp1);
238 xp1 = buffer[i];
239 yp1 = buffer[i + 1];
240 i += 2;
241 if (yp2 != yp1) {
242 fprintf(stderr, "plfill: oh oh we are lost\n");
243 for (j = 0; j < bufferleng; j+=2) {
244 fprintf(stderr, "plfill: %d %d\n",
245 (int) buffer[j], (int) buffer[j+1]);
246 }
247 continue; /* Uh oh we're lost */
248 }
249 tran(&xp1, &yp1, (PLFLT) ci, (PLFLT) (-si));
250 plP_draphy(xp1, yp1);
251 }
252 }
253 free((void *) buffer);
254 }
255
256 /*----------------------------------------------------------------------*\
257 * Utility functions
258 \*----------------------------------------------------------------------*/
259
260 static void
tran(PLINT * a,PLINT * b,PLFLT c,PLFLT d)261 tran(PLINT *a, PLINT *b, PLFLT c, PLFLT d)
262 {
263 PLINT ta, tb;
264
265 ta = *a;
266 tb = *b;
267
268 *a = floor((double) (ta * c + tb * d + 0.5));
269 *b = floor((double) (tb * c - ta * d + 0.5));
270 }
271
272 static void
buildlist(PLINT xp1,PLINT yp1,PLINT xp2,PLINT yp2,PLINT xp3,PLINT yp3,PLINT dinc)273 buildlist(PLINT xp1, PLINT yp1, PLINT xp2, PLINT yp2, PLINT xp3, PLINT yp3,
274 PLINT dinc)
275 {
276 PLINT min_y, max_y;
277 PLINT dx, dy, cstep, nstep, ploty, plotx;
278
279 (void) xp3; /* pmr: make it used */
280
281 dx = xp2 - xp1;
282 dy = yp2 - yp1;
283
284 if (dy == 0) {
285 if (yp2 > yp3 && ((yp2 % dinc) == 0))
286 addcoord(xp2, yp2);
287 return;
288 }
289
290 if (dy > 0) {
291 cstep = 1;
292 min_y = yp1;
293 max_y = yp2;
294 }
295 else {
296 cstep = -1;
297 min_y = yp2;
298 max_y = yp1;
299 }
300
301 nstep = (yp3 > yp2 ? 1 : -1);
302 if (yp3 == yp2) nstep = 0;
303
304 /* Build coordinate list */
305
306 ploty = (min_y / dinc) * dinc;
307 if (ploty < min_y) ploty += dinc;
308
309 for (; ploty <= max_y; ploty += dinc) {
310 if (ploty == yp1) continue;
311 if (ploty == yp2) {
312 if (cstep == -nstep) continue;
313 if (yp2 == yp3 && yp1 > yp2) continue;
314 }
315 plotx = xp1 + floor(((double) (ploty - yp1) * dx) / dy + 0.5);
316 addcoord(plotx, ploty);
317 }
318 }
319
320 static void
addcoord(PLINT xp1,PLINT yp1)321 addcoord(PLINT xp1, PLINT yp1)
322 {
323 PLINT *temp;
324
325 if (bufferleng + 2 > buffersize) {
326 buffersize += 2 * BINC;
327 temp = (PLINT *) realloc((void *) buffer,
328 (size_t) buffersize * sizeof(PLINT));
329 if (!temp) {
330 free((void *) buffer);
331 plexit("plfill: Out of memory!");
332 }
333 buffer = temp;
334 }
335
336 buffer[bufferleng++] = xp1;
337 buffer[bufferleng++] = yp1;
338 }
339
340 static int
compar(const void * pnum1,const void * pnum2)341 compar(const void *pnum1, const void *pnum2)
342 {
343 const struct point *pnt1, *pnt2;
344
345 pnt1 = (const struct point *) pnum1;
346 pnt2 = (const struct point *) pnum2;
347
348 if (pnt1->y < pnt2->y)
349 return -1;
350 else if (pnt1->y > pnt2->y)
351 return 1;
352
353 /* Only reach here if y coords are equal, so sort by x */
354
355 if (pnt1->x < pnt2->x)
356 return -1;
357 else if (pnt1->x > pnt2->x)
358 return 1;
359
360 return 0;
361 }
362