GRASS Programmer's Manual  6.5.svn(2014)-r66266
draw2.c
Go to the documentation of this file.
1
2 /*******************************************************************
3  * Line drawing in the current window.
4  *
5  * Clip window:
6  * D_set_clip_window (top, bottom ,left, right)
7  * establish clipping region for subseqent line drawing.
8  * D_set_clip_window_to_map_window ()
9  * set clipping to pixels corresponding to the current map region
10  * (default)
11  * D_set_clip_window_to_screen_window ()
12  * set clipping to full extent of the window (ie disables clipping on screen)
13  *
14  * Moves.
15  * D_move_abs(x,y) move to x,y.
16  * D_move_rel(x,y) move to +x,+y.
17  * Set current position. Position is not clipped.
18  *
19  * Draw line
20  * D_cont_abs(x,y) draw to x,y.
21  * D_cont_rel(x,y) draw to +x,+y.
22  * Line draw from current position. New postion is not clipped.
23  * The lines drawn are clipped however.
24  * Return values indicate the nature of the clipping:
25  * 0 no clipping
26  * 1 part of the line is drawn
27  * -1 none of the line is drawn
28  *
29  *
30  */
31
32 #include <math.h>
33 #include <string.h>
34
35 #include <grass/gis.h>
36 #include <grass/raster.h>
37 #include <grass/display.h>
38
39 struct rectangle
40 {
41  double left;
42  double rite;
43  double bot;
44  double top;
45 };
46
47 struct vector
48 {
49  double x, y;
50 };
51
52 struct plane
53 {
54  double x, y, k;
55 };
56
57 static struct vector cur;
58
59 static struct rectangle clip;
60
61 static struct plane pl_left = { -1, 0, 0 };
62 static struct plane pl_rite = { 1, 0, 0 };
63 static struct plane pl_bot = { 0, -1, 0 };
64 static struct plane pl_top = { 0, 1, 0 };
65
66 static int window_set;
67
68 #define min(x,y) ((x) < (y) ? (x) : (y))
69 #define max(x,y) ((x) > (y) ? (x) : (y))
70
71 #define round(x) ((int) floor(0.5 + (x)))
72
73 static int *xi, *yi;
74 static int nalloc_i;
75
76 static double *xf, *yf;
77 static int nalloc_f;
78
79 static void alloc_int(int n)
80 {
81
82  if (nalloc_i >= n)
83  return;
84
85  nalloc_i = n;
86  xi = G_realloc(xi, nalloc_i * sizeof(int));
87  yi = G_realloc(yi, nalloc_i * sizeof(int));
88 }
89
90 static void alloc_float(int n)
91 {
92
93  if (nalloc_f >= n)
94  return;
95
96  nalloc_f = n + 10;
97  xf = G_realloc(xf, nalloc_f * sizeof(double));
98  yf = G_realloc(yf, nalloc_f * sizeof(double));
99 }
100
101 static void dealloc_float(const double **x, const double **y, int release)
102 {
103  if (release) {
104  G_free(*(double **)x);
105  G_free(*(double **)y);
106  }
107
108  *x = xf;
109  *y = yf;
110
111  nalloc_f = 0;
112
113  xf = NULL;
114  yf = NULL;
115 }
116
117 static int do_filter(int *x, int *y, int n)
118 {
119  int i, j;
120
121  for (i = 0, j = 1; j < n; j++) {
122  if (x[j] == x[i] && y[j] == y[i])
123  continue;
124  i++;
125  if (i == j)
126  continue;
127  x[i] = x[j];
128  y[i] = y[j];
129  }
130
131  return i + 1;
132 }
133
134 static void do_round(const double *x, const double *y, int n)
135 {
136  int i;
137
138  alloc_int(n);
139
140  for (i = 0; i < n; i++) {
141  xi[i] = round(D_u_to_d_col(x[i]));
142  yi[i] = round(D_u_to_d_row(y[i]));
143  }
144 }
145
146 static void do_floor(const double *x, const double *y, int n)
147 {
148  int i;
149
150  alloc_int(n);
151
152  for (i = 0; i < n; i++) {
153  xi[i] = floor(D_u_to_d_col(x[i]));
154  yi[i] = floor(D_u_to_d_row(y[i]));
155  }
156 }
157
158 static double dist_plane(double x, double y, const struct plane *p)
159 {
160  return x * p->x + y * p->y + p->k;
161 }
162
163 static double interpolate(double a, double b, double ka, double kb)
164 {
165  return (a * kb - b * ka) / (kb - ka);
166 }
167
168 static int clip_plane(struct vector *a, struct vector *b,
169  const struct plane *p, int *clipped)
170 {
171  double ka = dist_plane(a->x, a->y, p);
172  double kb = dist_plane(b->x, b->y, p);
173  double kab;
174
175  /* both outside */
176  if (ka > 0 && kb > 0)
177  return 1;
178
179  /* both inside */
180  if (ka <= 0 && kb <= 0)
181  return 0;
182
183  *clipped = 1;
184
185  /* a outside - swap a and b */
186  if (ka >= 0) {
187  struct vector *t;
188  double kt;
189
190  t = a;
191  a = b;
192  b = t;
193  kt = ka;
194  ka = kb;
195  kb = kt;
196  }
197
198  kab = kb - ka;
199
200  b->x = interpolate(a->x, b->x, ka, kb);
201  b->y = interpolate(a->y, b->y, ka, kb);
202
203  return 0;
204 }
205
206 static int do_clip(struct vector *a, struct vector *b)
207 {
208  int clipped = 0;
209
210  if (a->x < clip.left && b->x < clip.left)
211  return -1;
212  if (a->x > clip.rite && b->x > clip.rite)
213  return -1;
214  if (a->y < clip.bot && b->y < clip.bot)
215  return -1;
216  if (a->y > clip.top && b->y > clip.top)
217  return -1;
218
219  if (clip_plane(a, b, &pl_left, &clipped))
220  return -1;
221  if (clip_plane(a, b, &pl_rite, &clipped))
222  return -1;
223  if (clip_plane(a, b, &pl_bot, &clipped))
224  return -1;
225  if (clip_plane(a, b, &pl_top, &clipped))
226  return -1;
227
228  return clipped;
229 }
230
231 static int shift_count(double dx)
232 {
233  return (int)floor(dx / 360);
234 }
235
236 static double shift_angle(double dx)
237 {
238  return shift_count(dx) * 360;
239 }
240
241 static double coerce(double x)
242 {
243  x += 180;
244  x -= shift_angle(x);
245  x -= 180;
246  return x;
247 }
248
249 static int euclidify(double *x, const double *y, int n, int no_pole)
250 {
251  double ux0 = clip.left;
252  double ux1 = clip.rite;
253  double x0, x1;
254  int lo, hi, count;
255  int i;
256
257  x0 = x1 = x[0];
258
259  for (i = 1; i < n; i++) {
260  if (fabs(y[i]) < 89.9)
261  x[i] = x[i - 1] + coerce(x[i] - x[i - 1]);
262
263  x0 = min(x0, x[i]);
264  x1 = max(x1, x[i]);
265  }
266
267  if (no_pole && fabs(x[n - 1] - x[0]) > 180)
268  return 0;
269
270  lo = -shift_count(ux1 - x0);
271  hi = shift_count(x1 - ux0);
272  count = hi - lo + 1;
273
274  for (i = 0; i < n; i++)
275  x[i] -= lo * 360;
276
277  return count;
278 }
279
280 static void do_ll_wrap(const double *x, const double *y, int n,
281  void (*func) (const double *, const double *, int))
282 {
283  double *xx = G_malloc(n * sizeof(double));
284  int count, i;
285
286  memcpy(xx, x, n * sizeof(double));
287  count = euclidify(xx, y, n, 0);
288
289  for (i = 0; i < count; i++) {
290  int j;
291
292  (*func) (xx, y, n);
293
294  for (j = 0; j < n; j++)
295  xx[j] -= 360;
296  }
297
298  G_free(xx);
299 }
300
313 void D_set_clip(double t, double b, double l, double r)
314 {
315  clip.left = min(l, r);
316  clip.rite = max(l, r);
317  clip.bot = min(b, t);
318  clip.top = max(b, t);
319
320  pl_left.k = clip.left;
321  pl_rite.k = -clip.rite;
322  pl_bot.k = clip.bot;
323  pl_top.k = -clip.top;
324
325  window_set = 1;
326 }
327
337 void D_clip_to_map(void)
338 {
341 }
342
353 void D_move_clip(double x, double y)
354 {
355  cur.x = x;
356  cur.y = y;
357 }
358
374 static int line_clip(double x1, double y1, double x2, double y2)
375 {
376  struct vector a, b;
377  int clipped;
378
379  a.x = x1;
380  a.y = y1;
381
382  b.x = x2;
383  b.y = y2;
384
385  clipped = do_clip(&a, &b);
386
387  if (clipped >= 0) {
388  int x1 = round(D_u_to_d_col(a.x));
389  int y1 = round(D_u_to_d_row(a.y));
390  int x2 = round(D_u_to_d_col(b.x));
391  int y2 = round(D_u_to_d_row(b.y));
392
393  R_move_abs(x1, y1);
394  R_cont_abs(x2, y2);
395  }
396
397  return clipped;
398 }
399
400 static int line_clip_ll(double ax, double ay, double bx, double by)
401 {
402  double ux0 = clip.left;
403  double ux1 = clip.rite;
404  double x0, x1;
405  int lo, hi, i;
406  int ret;
407
408  bx = ax + coerce(bx - ax);
409
410  x0 = min(ax, bx);
411  x1 = max(ax, bx);
412
413  lo = -shift_count(ux1 - x0);
414  hi = shift_count(x1 - ux0);
415
416  ret = 0;
417
418  for (i = lo; i <= hi; i++)
419  ret |= line_clip(ax + i * 360, ay, bx + i * 360, by);
420
421  return ret;
422 }
423
424 int D_cont_clip(double x, double y)
425 {
426  int ret;
427
428  if (!window_set)
429  D_clip_to_map();
430
431  if (D_is_lat_lon())
432  ret = line_clip_ll(cur.x, cur.y, x, y);
433  else
434  ret = line_clip(cur.x, cur.y, x, y);
435
436  cur.x = x;
437  cur.y = y;
438
439  return ret;
440 }
441
442 void D_polydots_clip(const double *x, const double *y, int n)
443 {
444  double ux0 = clip.left;
445  int i, j;
446
447  if (!window_set)
448  D_clip_to_map();
449
450  alloc_float(n);
451
452  for (i = j = 0; i < n; i++) {
453  double xx = x[i];
454  double yy = y[i];
455
456  if (D_is_lat_lon())
457  xx -= shift_angle(x[i] - ux0);
458
459  if (xx < clip.left || xx > clip.rite)
460  continue;
461  if (yy < clip.bot || yy > clip.top)
462  continue;
463
464  xf[j] = xx;
465  yf[j] = yy;
466  j++;
467  }
468
469  do_floor(xf, yf, n);
470  n = do_filter(xi, yi, n);
471
472  R_polydots_abs(xi, yi, j);
473 }
474
475 static int cull_polyline_plane(int *pn, const double *x, const double *y,
476  const struct plane *p)
477 {
478  int n = *pn;
479  int last = -1;
480  int prev = 0;
481  double x0 = x[prev];
482  double y0 = y[prev];
483  double d0 = dist_plane(x0, y0, p);
484  int i, j;
485
486  for (i = 0, j = 0; i < n; i++) {
487  double x1 = x[i];
488  double y1 = y[i];
489  double d1 = dist_plane(x1, y1, p);
490  int in0 = d0 <= 0;
491  int in1 = d1 <= 0;
492
493  if (!in0 && in1 && last != prev) { /* entering */
494  alloc_float(j + 1);
495  xf[j] = x0;
496  yf[j] = y0;
497  j++;
498  last = prev;
499  }
500
501  if (in1 || in0) { /* inside or leaving */
502  alloc_float(j + 1);
503  xf[j] = x1;
504  yf[j] = y1;
505  j++;
506  last = i;
507  }
508
509  x0 = x1;
510  y0 = y1;
511  d0 = d1;
512  prev = i;
513  }
514
515  *pn = j;
516
517  return (j == 0);
518 }
519
520 static void polyline_cull(const double *x, const double *y, int n)
521 {
522  alloc_float(n + 10);
523
524  if (cull_polyline_plane(&n, x, y, &pl_left))
525  return;
526
527  dealloc_float(&x, &y, 0);
528
529  if (cull_polyline_plane(&n, x, y, &pl_rite))
530  return;
531
532  dealloc_float(&x, &y, 1);
533
534  if (cull_polyline_plane(&n, x, y, &pl_bot))
535  return;
536
537  dealloc_float(&x, &y, 1);
538
539  if (cull_polyline_plane(&n, x, y, &pl_top))
540  return;
541
542  dealloc_float(&x, &y, 1);
543
544  do_floor(x, y, n);
545  n = do_filter(xi, yi, n);
546
547  R_polyline_abs(xi, yi, n);
548 }
549
550 void D_polyline_cull(const double *x, const double *y, int n)
551 {
552  if (n < 2)
553  return;
554
555  if (!window_set)
556  D_clip_to_map();
557
558  if (D_is_lat_lon())
559  do_ll_wrap(x, y, n, polyline_cull);
560  else
561  polyline_cull(x, y, n);
562 }
563
564 static void polyline_clip(const double *x, const double *y, int n)
565 {
566  int i;
567
568  for (i = 1; i < n; i++)
569  line_clip(x[i - 1], y[i - 1], x[i], y[i]);
570 }
571
572 void D_polyline_clip(const double *x, const double *y, int n)
573 {
574  if (n < 2)
575  return;
576
577  if (!window_set)
578  D_clip_to_map();
579
580  if (D_is_lat_lon())
581  do_ll_wrap(x, y, n, polyline_clip);
582  else
583  polyline_clip(x, y, n);
584 }
585
586 static int cull_polygon_plane(int *pn, const double *x, const double *y,
587  const struct plane *p)
588 {
589  int n = *pn;
590  int last = -1;
591  int prev = n - 1;
592  double x0 = x[prev];
593  double y0 = y[prev];
594  double d0 = dist_plane(x0, y0, p);
595  int i, j;
596
597  for (i = j = 0; i < n; i++) {
598  double x1 = x[i];
599  double y1 = y[i];
600  double d1 = dist_plane(x1, y1, p);
601  int in0 = d0 <= 0;
602  int in1 = d1 <= 0;
603
604  if (!in0 && in1 && last != prev) { /* entering */
605  alloc_float(j + 1);
606  xf[j] = x0;
607  yf[j] = y0;
608  j++;
609  last = prev;
610  }
611
612  if (in1 || in0) { /* inside or leaving */
613  alloc_float(j + 1);
614  xf[j] = x1;
615  yf[j] = y1;
616  j++;
617  last = i;
618  }
619
620  x0 = x1;
621  y0 = y1;
622  d0 = d1;
623  prev = i;
624  }
625
626  *pn = j;
627
628  return (j == 0);
629 }
630
631 static void polygon_cull(const double *x, const double *y, int n)
632 {
633  alloc_float(n + 10);
634
635  if (cull_polygon_plane(&n, x, y, &pl_left))
636  return;
637
638  dealloc_float(&x, &y, 0);
639
640  if (cull_polygon_plane(&n, x, y, &pl_rite))
641  return;
642
643  dealloc_float(&x, &y, 1);
644
645  if (cull_polygon_plane(&n, x, y, &pl_bot))
646  return;
647
648  dealloc_float(&x, &y, 1);
649
650  if (cull_polygon_plane(&n, x, y, &pl_top))
651  return;
652
653  dealloc_float(&x, &y, 1);
654
655  do_round(x, y, n);
656  n = do_filter(xi, yi, n);
657
658  R_polygon_abs(xi, yi, n);
659 }
660
661 void D_polygon_cull(const double *x, const double *y, int n)
662 {
663  if (!window_set)
664  D_clip_to_map();
665
666  if (D_is_lat_lon())
667  do_ll_wrap(x, y, n, polygon_cull);
668  else
669  polygon_cull(x, y, n);
670 }
671
672 static int clip_polygon_plane(int *pn, const double *x, const double *y,
673  const struct plane *p)
674 {
675  int n = *pn;
676  double x0 = x[n - 1];
677  double y0 = y[n - 1];
678  double d0 = dist_plane(x0, y0, p);
679  int i, j;
680
681  for (i = j = 0; i < n; i++) {
682  double x1 = x[i];
683  double y1 = y[i];
684  double d1 = dist_plane(x1, y1, p);
685  int in0 = d0 <= 0;
686  int in1 = d1 <= 0;
687
688  if (in0 != in1) { /* edge crossing */
689  alloc_float(j + 1);
690  xf[j] = interpolate(x0, x1, d0, d1);
691  yf[j] = interpolate(y0, y1, d0, d1);
692  j++;
693  }
694
695  if (in1) { /* point inside */
696  alloc_float(j + 1);
697  xf[j] = x[i];
698  yf[j] = y[i];
699  j++;
700  }
701
702  x0 = x1;
703  y0 = y1;
704  d0 = d1;
705  }
706
707  *pn = j;
708
709  return (j == 0);
710 }
711
712 static void polygon_clip(const double *x, const double *y, int n)
713 {
714  alloc_float(n + 10);
715
716  if (clip_polygon_plane(&n, x, y, &pl_left))
717  return;
718
719  dealloc_float(&x, &y, 0);
720
721  if (clip_polygon_plane(&n, x, y, &pl_rite))
722  return;
723
724  dealloc_float(&x, &y, 1);
725
726  if (clip_polygon_plane(&n, x, y, &pl_bot))
727  return;
728
729  dealloc_float(&x, &y, 1);
730
731  if (clip_polygon_plane(&n, x, y, &pl_top))
732  return;
733
734  dealloc_float(&x, &y, 1);
735
736  do_round(x, y, n);
737  n = do_filter(xi, yi, n);
738
739  R_polygon_abs(xi, yi, n);
740 }
741
742 void D_polygon_clip(const double *x, const double *y, int n)
743 {
744  if (!window_set)
745  D_clip_to_map();
746
747  if (D_is_lat_lon())
748  do_ll_wrap(x, y, n, polygon_clip);
749  else
750  polygon_clip(x, y, n);
751 }
752
753 static void box_clip(double x1, double y1, double x2, double y2)
754 {
755  double t, b, l, r;
756  int ti, bi, li, ri;
757
758  l = max(clip.left, min(x1, x2));
759  r = min(clip.rite, max(x1, x2));
760  b = max(clip.bot, min(y1, y2));
761  t = min(clip.top, max(y1, y2));
762
763  li = round(D_u_to_d_col(l));
764  ri = round(D_u_to_d_col(r));
765  bi = round(D_u_to_d_row(b));
766  ti = round(D_u_to_d_row(t));
767
768  R_box_abs(li, ti, ri, bi);
769 }
770
771 static void box_clip_ll(double x1, double y1, double x2, double y2)
772 {
773  double ux0 = clip.left;
774  double ux1 = clip.rite;
775  int lo, hi, i;
776
777  x2 = x1 + coerce(x2 - x1);
778
779  lo = -shift_count(ux1 - x1);
780  hi = shift_count(x2 - ux0);
781
782  for (i = lo; i <= hi; i++)
783  box_clip(x1 + i * 360, y1, x2 + i * 360, y2);
784 }
785
786 void D_box_clip(double x1, double y1, double x2, double y2)
787 {
788  if (!window_set)
789  D_clip_to_map();
790
791  if (D_is_lat_lon())
792  box_clip_ll(x1, y1, x2, y2);
793  else
794  box_clip(x1, y1, x2, y2);
795 }
796
797 void D_move(double x, double y)
798 {
799  int xi = round(D_u_to_d_col(x));
800  int yi = round(D_u_to_d_row(y));
801
802  R_move_abs(xi, yi);
803 }
804
805 void D_cont(double x, double y)
806 {
807  int xi = round(D_u_to_d_col(x));
808  int yi = round(D_u_to_d_row(y));
809
810  R_cont_abs(xi, yi);
811 }
812
813 void D_polydots(const double *x, const double *y, int n)
814 {
815  do_floor(x, y, n);
816  n = do_filter(xi, yi, n);
817  R_polydots_abs(xi, yi, n);
818 }
819
820 void D_polyline(const double *x, const double *y, int n)
821 {
822  do_floor(x, y, n);
823  n = do_filter(xi, yi, n);
824  R_polyline_abs(xi, yi, n);
825 }
826
827 void D_polygon(const double *x, const double *y, int n)
828 {
829  do_round(x, y, n);
830  n = do_filter(xi, yi, n);
831  R_polygon_abs(xi, yi, n);
832 }
833
834 void D_box(double x1, double y1, double x2, double y2)
835 {
836  double l = min(x1, x2);
837  double r = max(x1, x2);
838  double b = min(y1, y2);
839  double t = max(y1, y2);
840  int li = round(D_u_to_d_col(l));
841  int ri = round(D_u_to_d_col(r));
842  int bi = round(D_u_to_d_row(b));
843  int ti = round(D_u_to_d_row(t));
844
845  R_box_abs(li, ti, ri, bi);
846 }
847
848 void D_line_width(double d)
849 {
850  int w = round(d);
851
852  if (w < 0)
853  w = 0;
854
855  R_line_width(w);
856 }
void D_set_clip(double t, double b, double l, double r)
set clipping window
Definition: draw2.c:313
void R_polygon_abs(const int *xarray, const int *yarray, int number)
draw a closed polygon
Definition: com_proto.c:311
void G_free(void *buf)
Free allocated memory.
Definition: gis/alloc.c:142
int l
float b
Definition: named_colr.c:8
void R_box_abs(int x1, int y1, int x2, int y2)
fill a box
Definition: com_proto.c:350
void D_polydots(const double *x, const double *y, int n)
Definition: draw2.c:813
void R_line_width(int width)
change the width of line
Definition: com_proto.c:123
int D_is_lat_lon(void)
Definition: cnversions.c:162
#define min(x, y)
Definition: draw2.c:68
float r
Definition: named_colr.c:8
void D_polyline_clip(const double *x, const double *y, int n)
Definition: draw2.c:572
int count
int y
Definition: plot.c:34
#define max(x, y)
Definition: draw2.c:69
void D_box_clip(double x1, double y1, double x2, double y2)
Definition: draw2.c:786
double y
Definition: draw2.c:54
double top
Definition: draw2.c:44
double D_get_u_north(void)
Definition: cnversions.c:193
void D_polygon(const double *x, const double *y, int n)
Definition: draw2.c:827
void D_line_width(double d)
Definition: draw2.c:848
void R_polyline_abs(const int *xarray, const int *yarray, int number)
draw an open polygon
Definition: com_proto.c:271
double D_get_u_east(void)
Definition: cnversions.c:189
double k
Definition: draw2.c:54
void R_cont_abs(int x, int y)
draw line
Definition: com_proto.c:190
double D_u_to_d_col(double U_col)
earth to screen (east)
Definition: cnversions.c:351
double rite
Definition: draw2.c:42
void R_move_abs(int x, int y)
move current location
Definition: com_proto.c:153
void D_polyline(const double *x, const double *y, int n)
Definition: draw2.c:820
void D_move(double x, double y)
Definition: draw2.c:797
double D_get_u_south(void)
Definition: cnversions.c:197
void D_polygon_cull(const double *x, const double *y, int n)
Definition: draw2.c:661
int D_cont_clip(double x, double y)
Definition: draw2.c:424
void R_polydots_abs(const int *xarray, const int *yarray, int number)
draw a series of dots
Definition: com_proto.c:230
double x
Definition: draw2.c:54
void D_box(double x1, double y1, double x2, double y2)
Definition: draw2.c:834
double bot
Definition: draw2.c:43
return NULL
Definition: dbfopen.c:1394
void D_move_clip(double x, double y)
move to pixel
Definition: draw2.c:353
void D_polydots_clip(const double *x, const double *y, int n)
Definition: draw2.c:442
void D_polygon_clip(const double *x, const double *y, int n)
Definition: draw2.c:742
#define round(x)
Definition: draw2.c:71
double y
Definition: cnversions.c:36
void D_polyline_cull(const double *x, const double *y, int n)
Definition: draw2.c:550
Definition: draw2.c:52
double x
Definition: cnversions.c:36
void D_cont(double x, double y)
Definition: draw2.c:805
int n