GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-3f124c5c78
clip.c
Go to the documentation of this file.
1 #include <math.h>
2 #include <string.h>
3 
4 #include <grass/gis.h>
5 #include <grass/display.h>
6 #include <grass/glocale.h>
7 #include "path.h"
8 #include "clip.h"
9 
10 /******************************************************************************/
11 
12 static double dist_plane(double x, double y, const struct plane *p)
13 {
14  return x * p->x + y * p->y + p->k;
15 }
16 
17 static double interpolate(double a, double b, double ka, double kb)
18 {
19  return (a * kb - b * ka) / (kb - ka);
20 }
21 
22 static void clip_path_plane(struct path *dst, const struct path *src,
23  const struct plane *p)
24 {
25  struct vertex *v0 = &src->vertices[src->count - 1];
26  double x0 = v0->x;
27  double y0 = v0->y;
28  double d0 = dist_plane(x0, y0, p);
29  int i;
30 
31  path_reset(dst);
32 
33  for (i = 0; i < src->count; i++) {
34  struct vertex *v1 = &src->vertices[i];
35  double x1 = v1->x;
36  double y1 = v1->y;
37  double d1 = dist_plane(x1, y1, p);
38  int in0 = d0 <= 0;
39  int in1 = d1 <= 0;
40 
41  if (in0 && !in1) {
42  /* leaving */
43  double x = interpolate(x0, x1, d0, d1);
44  double y = interpolate(y0, y1, d0, d1);
45  path_cont(dst, x, y);
46  }
47 
48  if (!in0 && in1) {
49  /* entering */
50  double x = interpolate(x0, x1, d0, d1);
51  double y = interpolate(y0, y1, d0, d1);
52  path_move(dst, x, y);
53  }
54 
55  if (in1)
56  /* inside */
57  path_cont(dst, x1, y1);
58 
59  x0 = x1;
60  y0 = y1;
61  d0 = d1;
62  }
63 }
64 
65 /******************************************************************************/
66 
67 static void cull_path_plane(struct path *dst, const struct path *src,
68  const struct plane *p)
69 {
70  int last = -1;
71  int prev = src->count - 1;
72  struct vertex *v0 = &src->vertices[prev];
73  double x0 = v0->x;
74  double y0 = v0->y;
75  double d0 = dist_plane(x0, y0, p);
76  int i;
77 
78  path_reset(dst);
79 
80  for (i = 0; i < src->count; i++) {
81  struct vertex *v1 = &src->vertices[i];
82  double x1 = v1->x;
83  double y1 = v1->y;
84  double d1 = dist_plane(x1, y1, p);
85  int in0 = d0 <= 0;
86  int in1 = d1 <= 0;
87 
88  if (!in0 && in1 && last != prev) {
89  /* entering */
90  path_move(dst, x0, y0);
91  last = prev;
92  }
93 
94  if (in1 || in0) {
95  /* inside or leaving */
96  path_cont(dst, x1, y1);
97  last = i;
98  }
99 
100  x0 = x1;
101  y0 = y1;
102  d0 = d1;
103  prev = i;
104  }
105 }
106 
107 /******************************************************************************/
108 
109 void D__set_clip_planes(struct clip *clip, const struct rectangle *rect)
110 {
111  clip->left.x = -1;
112  clip->left.y = 0;
113  clip->left.k = rect->left;
114 
115  clip->rite.x = 1;
116  clip->rite.y = 0;
117  clip->rite.k = -rect->rite;
118 
119  clip->bot.x = 0;
120  clip->bot.y = -1;
121  clip->bot.k = rect->bot;
122 
123  clip->top.x = 0;
124  clip->top.y = 1;
125  clip->top.k = -rect->top;
126 }
127 
128 void D__cull_path(struct path *dst, const struct path *src,
129  const struct clip *clip)
130 {
131  struct path tmp1, tmp2;
132 
133  path_init(&tmp1);
134  path_init(&tmp2);
135 
136  cull_path_plane(&tmp1, src, &clip->left);
137  cull_path_plane(&tmp2, &tmp1, &clip->rite);
138  cull_path_plane(&tmp1, &tmp2, &clip->bot);
139  cull_path_plane(dst, &tmp1, &clip->top);
140 
141  path_free(&tmp1);
142  path_free(&tmp2);
143 }
144 
145 void D__clip_path(struct path *dst, const struct path *src,
146  const struct clip *clip)
147 {
148  struct path tmp1, tmp2;
149 
150  path_init(&tmp1);
151  path_init(&tmp2);
152 
153  clip_path_plane(&tmp1, src, &clip->left);
154  clip_path_plane(&tmp2, &tmp1, &clip->rite);
155  clip_path_plane(&tmp1, &tmp2, &clip->bot);
156  clip_path_plane(dst, &tmp1, &clip->top);
157 
158  path_free(&tmp1);
159  path_free(&tmp2);
160 }
161 
162 /******************************************************************************/
void D__cull_path(struct path *dst, const struct path *src, const struct clip *clip)
Definition: clip.c:128
void D__clip_path(struct path *dst, const struct path *src, const struct clip *clip)
Definition: clip.c:145
void D__set_clip_planes(struct clip *clip, const struct rectangle *rect)
Definition: clip.c:109
void path_reset(struct path *p)
Definition: driver/path.c:31
void path_free(struct path *p)
Definition: driver/path.c:12
void path_cont(struct path *p, double x, double y)
Definition: driver/path.c:78
void path_move(struct path *p, double x, double y)
Definition: driver/path.c:72
void path_init(struct path *p)
Definition: driver/path.c:4
double b
Definition: r_raster.c:39
Definition: clip.h:10
struct plane left rite bot top
Definition: clip.h:11
Definition: path.h:15
int count
Definition: path.h:17
struct vertex * vertices
Definition: path.h:16
Definition: clip.h:6
double x
Definition: clip.h:7
double k
Definition: clip.h:7
double y
Definition: clip.h:7
Definition: clip.h:14
double left
Definition: clip.h:15
double bot
Definition: clip.h:15
double rite
Definition: clip.h:15
double top
Definition: clip.h:15
Definition: path.h:10
double x
Definition: path.h:11
double y
Definition: path.h:11
#define x