1 #include "vnc.h"
2 #include "vncs.h"
3
4 static int tot;
5 static void rprint(Rlist*);
6
7 static void
growrlist(Rlist * rlist,int n)8 growrlist(Rlist *rlist, int n)
9 {
10 int old;
11
12 if(rlist->nrect+n <= rlist->maxrect)
13 return;
14
15 old = rlist->maxrect;
16 while(rlist->nrect+n > rlist->maxrect){
17 if(rlist->maxrect == 0)
18 rlist->maxrect = 16;
19 else
20 rlist->maxrect *= 2;
21 }
22
23 tot += rlist->maxrect - old;
24 if(tot > 10000)
25 sysfatal("too many rectangles");
26
27 rlist->rect = realloc(rlist->rect, rlist->maxrect*sizeof(rlist->rect[0]));
28 if(rlist->rect == nil)
29 sysfatal("realloc failed in growrlist");
30 }
31
32 static void
rappend(Rlist * rl,Rectangle r)33 rappend(Rlist *rl, Rectangle r)
34 {
35 growrlist(rl, 1);
36 rl->rect[rl->nrect++] = r;
37 }
38
39 /* remove rectangle i from the list */
40 static int
rtrim(Rlist * r,int i)41 rtrim(Rlist *r, int i)
42 {
43 if(i < 0 || i >= r->nrect)
44 return 0;
45 if(i == r->nrect-1){
46 r->nrect--;
47 return 1;
48 }
49 r->rect[i] = r->rect[--r->nrect];
50 return 1;
51 }
52
53 static int
rectadjacent(Rectangle r,Rectangle s)54 rectadjacent(Rectangle r, Rectangle s)
55 {
56 return r.min.x<=s.max.x && s.min.x<=r.max.x &&
57 r.min.y<=s.max.y && s.min.y<=r.max.y;
58 }
59
60 /*
61 * If s shares three edges with r, compute the
62 * rectangle r - s and return 1.
63 * Else return 0.
64 */
65 static int
rectubr(Rectangle * r,Rectangle s)66 rectubr(Rectangle *r, Rectangle s)
67 {
68 if(r->min.y==s.min.y && r->max.y==s.max.y){
69 if(r->min.x == s.min.x){
70 r->min.x = s.max.x;
71 assert(r->max.x > r->min.x);
72 return 1;
73 }
74 if(r->max.x == s.max.x){
75 r->max.x = s.min.x;
76 assert(r->max.x > r->min.x);
77 return 1;
78 }
79 }
80 if(r->min.x==s.min.x && r->max.x==s.max.x){
81 if(r->min.y == s.min.y){
82 r->min.y = s.max.y;
83 assert(r->max.y > r->min.y);
84 return 1;
85 }
86 if(r->max.y == s.max.y){
87 r->max.y = s.min.y;
88 assert(r->max.y > r->min.y);
89 return 1;
90 }
91 }
92 return 0;
93 }
94
95 /*
96 * If s is a corner of r, remove s from r, yielding
97 * two rectangles r and rr. R holds the part with
98 * smaller coordinates.
99 */
100 static int
rectcornersubr(Rectangle * r,Rectangle s,Rectangle * rr)101 rectcornersubr(Rectangle *r, Rectangle s, Rectangle *rr)
102 {
103 # define UPRIGHT(r) Pt((r).max.x, (r).min.y)
104 # define LOWLEFT(r) Pt((r).min.x, (r).max.y)
105
106 *rr = *r;
107
108 if(s.min.x == r->min.x){
109 if(s.min.y == r->min.y){ // upper left
110 *rr = Rpt(UPRIGHT(s), r->max);
111 *r = Rpt(LOWLEFT(s), LOWLEFT(*rr));
112 return 1;
113 }
114 if(s.max.y == r->max.y){ // lower left
115 *rr = Rpt(Pt(s.max.x, r->min.y), r->max);
116 *r = Rpt(r->min, UPRIGHT(s));
117 return 1;
118 }
119 }
120 if(s.max.x == r->max.x){
121 if(s.max.y == r->max.y){ // lower right
122 *rr = Rpt(Pt(s.min.x, r->min.y), UPRIGHT(s));
123 *r = Rpt(r->min, LOWLEFT(s));
124 return 1;
125 }
126 if(s.min.y == r->min.y){ // upper right
127 *rr = Rpt(LOWLEFT(s), r->max);
128 *r = Rpt(r->min, LOWLEFT(*rr));
129 return 1;
130 }
131 }
132 return 0;
133 }
134
135 /*
136 * If s is a band cutting r into two pieces, set r to one piece
137 * and rr to the other.
138 */
139 static int
recttridesubr(Rectangle * nr,Rectangle s,Rectangle * rr)140 recttridesubr(Rectangle *nr, Rectangle s, Rectangle *rr)
141 {
142 *rr = *nr;
143 if((nr->min.x == s.min.x && nr->max.x == s.max.x) &&
144 (nr->min.y < s.min.y && s.max.y < nr->max.y)){
145 nr->max.y = s.min.y;
146 rr->min.y = s.max.y;
147 return 1;
148 }
149
150 if((nr->min.y == s.min.y && nr->max.y == s.max.y) &&
151 (nr->min.x < s.min.x && s.max.x < nr->max.x)){
152 nr->max.x = s.min.x;
153 rr->min.x = s.max.x;
154 return 1;
155 }
156 return 0;
157 }
158
159 void
addtorlist(Rlist * rlist,Rectangle r)160 addtorlist(Rlist *rlist, Rectangle r)
161 {
162 int i, j;
163 Rectangle ir, cr, rr;
164 Rlist tmp;
165
166 if(r.min.x >= r.max.x || r.min.y >= r.max.y)
167 return;
168
169 memset(&tmp, 0, sizeof tmp);
170 rappend(&tmp, r);
171
172 if(verbose > 5)
173 fprint(2, "region union add %R:\n", r);
174
175 combinerect(&rlist->bbox, r); // must do this first
176 for(j = 0; j < tmp.nrect; j++){
177 r = tmp.rect[j];
178
179 for(i=0; i < rlist->nrect; i++){
180 ir = rlist->rect[i];
181
182 if(verbose > 5)
183 fprint(2, "checking %R against %R\n", r, ir);
184 if(!rectadjacent(ir, r))
185 continue;
186
187 /* r is covered by ir? */
188 if(rectinrect(r, ir))
189 break;
190
191 /* r covers ir? */
192 if(rectinrect(ir, r)){
193 rtrim(rlist, i);
194 i--;
195 continue;
196 }
197
198 /* aligned and overlapping? */
199 if((ir.min.y == r.min.y && ir.max.y == r.max.y) ||
200 (ir.min.x == r.min.x && ir.max.x == r.max.x)){
201 combinerect(&r, ir);
202 rtrim(rlist, i);
203 i--;
204 continue;
205 }
206
207 /* not aligned */
208 if(verbose > 5)
209 fprint(2, "break up rect %R and %R\n", ir, r);
210 /* 2->2 breakup */
211 cr = ir;
212 if (!rectclip(&cr, r)) /* share only one point */
213 continue;
214
215 if(rectubr(&r, cr))
216 continue;
217
218 if(rectubr(&rlist->rect[i], cr))
219 continue;
220
221 /* 2 -> 3 breakup */
222 /* stride across */
223 if(recttridesubr(&r, cr, &rr)){
224 rappend(&tmp, rr);
225 continue;
226 }
227
228 /* corner overlap */
229 if(rectcornersubr(&r, cr, &rr)){
230 rappend(&tmp, rr);
231 continue;
232 }
233 abort();
234 }
235 if(i == rlist->nrect)
236 rappend(rlist, r);
237 }
238 freerlist(&tmp);
239 if(verbose > 5)
240 rprint(rlist);
241 }
242
243 void
freerlist(Rlist * r)244 freerlist(Rlist *r)
245 {
246 free(r->rect);
247 tot -= r->maxrect;
248 r->nrect = 0;
249 r->maxrect = 0;
250 r->rect = nil;
251 }
252
253 static void
rprint(Rlist * r)254 rprint(Rlist *r)
255 {
256 int i;
257
258 fprint(2, "rlist %p:", r);
259 for(i=0; i<r->nrect; i++)
260 fprint(2, " %R", r->rect[i]);
261 fprint(2, "\n");
262 }
263
264
265 #ifdef REGION_DEBUG
266
267 int verbose = 10;
268
main(int argc,char * argv[])269 void main(int argc, char * argv[])
270 {
271 Rectangle r1 = Rect(0, 0, 300, 200);
272 Rectangle r2 = Rect(100, 100, 400, 300);
273 Rectangle r3 = Rect(200, 100, 500, 300);
274 Region reg;
275
276 initdraw(0, 0, "vncviewer");
277 region_init(®);
278 region_union(®, r1, r1);
279 region_union(®, r2, r2);
280 region_union(®, r3, r3);
281 }
282
283 #endif
284