123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283 |
- #include "vnc.h"
- #include "vncs.h"
- static int tot;
- static void rprint(Rlist*);
- static void
- growrlist(Rlist *rlist, int n)
- {
- int old;
- if(rlist->nrect+n <= rlist->maxrect)
- return;
- old = rlist->maxrect;
- while(rlist->nrect+n > rlist->maxrect){
- if(rlist->maxrect == 0)
- rlist->maxrect = 16;
- else
- rlist->maxrect *= 2;
- }
- tot += rlist->maxrect - old;
- if(tot > 10000)
- sysfatal("too many rectangles");
- rlist->rect = realloc(rlist->rect, rlist->maxrect*sizeof(rlist->rect[0]));
- if(rlist->rect == nil)
- sysfatal("realloc failed in growrlist");
- }
- static void
- rappend(Rlist *rl, Rectangle r)
- {
- growrlist(rl, 1);
- rl->rect[rl->nrect++] = r;
- }
- /* remove rectangle i from the list */
- static int
- rtrim(Rlist *r, int i)
- {
- if(i < 0 || i >= r->nrect)
- return 0;
- if(i == r->nrect-1){
- r->nrect--;
- return 1;
- }
- r->rect[i] = r->rect[--r->nrect];
- return 1;
- }
- static int
- rectadjacent(Rectangle r, Rectangle s)
- {
- return r.min.x<=s.max.x && s.min.x<=r.max.x &&
- r.min.y<=s.max.y && s.min.y<=r.max.y;
- }
- /*
- * If s shares three edges with r, compute the
- * rectangle r - s and return 1.
- * Else return 0.
- */
- static int
- rectubr(Rectangle *r, Rectangle s)
- {
- if(r->min.y==s.min.y && r->max.y==s.max.y){
- if(r->min.x == s.min.x){
- r->min.x = s.max.x;
- assert(r->max.x > r->min.x);
- return 1;
- }
- if(r->max.x == s.max.x){
- r->max.x = s.min.x;
- assert(r->max.x > r->min.x);
- return 1;
- }
- }
- if(r->min.x==s.min.x && r->max.x==s.max.x){
- if(r->min.y == s.min.y){
- r->min.y = s.max.y;
- assert(r->max.y > r->min.y);
- return 1;
- }
- if(r->max.y == s.max.y){
- r->max.y = s.min.y;
- assert(r->max.y > r->min.y);
- return 1;
- }
- }
- return 0;
- }
- /*
- * If s is a corner of r, remove s from r, yielding
- * two rectangles r and rr. R holds the part with
- * smaller coordinates.
- */
- static int
- rectcornersubr(Rectangle *r, Rectangle s, Rectangle *rr)
- {
- # define UPRIGHT(r) Pt((r).max.x, (r).min.y)
- # define LOWLEFT(r) Pt((r).min.x, (r).max.y)
- *rr = *r;
- if(s.min.x == r->min.x){
- if(s.min.y == r->min.y){ // upper left
- *rr = Rpt(UPRIGHT(s), r->max);
- *r = Rpt(LOWLEFT(s), LOWLEFT(*rr));
- return 1;
- }
- if(s.max.y == r->max.y){ // lower left
- *rr = Rpt(Pt(s.max.x, r->min.y), r->max);
- *r = Rpt(r->min, UPRIGHT(s));
- return 1;
- }
- }
- if(s.max.x == r->max.x){
- if(s.max.y == r->max.y){ // lower right
- *rr = Rpt(Pt(s.min.x, r->min.y), UPRIGHT(s));
- *r = Rpt(r->min, LOWLEFT(s));
- return 1;
- }
- if(s.min.y == r->min.y){ // upper right
- *rr = Rpt(LOWLEFT(s), r->max);
- *r = Rpt(r->min, LOWLEFT(*rr));
- return 1;
- }
- }
- return 0;
- }
- /*
- * If s is a band cutting r into two pieces, set r to one piece
- * and rr to the other.
- */
- static int
- recttridesubr(Rectangle *nr, Rectangle s, Rectangle *rr)
- {
- *rr = *nr;
- if((nr->min.x == s.min.x && nr->max.x == s.max.x) &&
- (nr->min.y < s.min.y && s.max.y < nr->max.y)){
- nr->max.y = s.min.y;
- rr->min.y = s.max.y;
- return 1;
- }
- if((nr->min.y == s.min.y && nr->max.y == s.max.y) &&
- (nr->min.x < s.min.x && s.max.x < nr->max.x)){
- nr->max.x = s.min.x;
- rr->min.x = s.max.x;
- return 1;
- }
- return 0;
- }
- void
- addtorlist(Rlist *rlist, Rectangle r)
- {
- int i, j;
- Rectangle ir, cr, rr;
- Rlist tmp;
- if(r.min.x >= r.max.x || r.min.y >= r.max.y)
- return;
- memset(&tmp, 0, sizeof tmp);
- rappend(&tmp, r);
-
- if(verbose > 5)
- fprint(2, "region union add %R:\n", r);
- combinerect(&rlist->bbox, r); // must do this first
- for(j = 0; j < tmp.nrect; j++){
- r = tmp.rect[j];
- for(i=0; i < rlist->nrect; i++){
- ir = rlist->rect[i];
- if(verbose > 5)
- fprint(2, "checking %R against %R\n", r, ir);
- if(!rectadjacent(ir, r))
- continue;
- /* r is covered by ir? */
- if(rectinrect(r, ir))
- break;
- /* r covers ir? */
- if(rectinrect(ir, r)){
- rtrim(rlist, i);
- i--;
- continue;
- }
- /* aligned and overlapping? */
- if((ir.min.y == r.min.y && ir.max.y == r.max.y) ||
- (ir.min.x == r.min.x && ir.max.x == r.max.x)){
- combinerect(&r, ir);
- rtrim(rlist, i);
- i--;
- continue;
- }
- /* not aligned */
- if(verbose > 5)
- fprint(2, "break up rect %R and %R\n", ir, r);
- /* 2->2 breakup */
- cr = ir;
- if (!rectclip(&cr, r)) /* share only one point */
- continue;
- if(rectubr(&r, cr))
- continue;
- if(rectubr(&rlist->rect[i], cr))
- continue;
- /* 2 -> 3 breakup */
- /* stride across */
- if(recttridesubr(&r, cr, &rr)){
- rappend(&tmp, rr);
- continue;
- }
- /* corner overlap */
- if(rectcornersubr(&r, cr, &rr)){
- rappend(&tmp, rr);
- continue;
- }
- abort();
- }
- if(i == rlist->nrect)
- rappend(rlist, r);
- }
- freerlist(&tmp);
- if(verbose > 5)
- rprint(rlist);
- }
- void
- freerlist(Rlist *r)
- {
- free(r->rect);
- tot -= r->maxrect;
- r->nrect = 0;
- r->maxrect = 0;
- r->rect = nil;
- }
- static void
- rprint(Rlist *r)
- {
- int i;
- fprint(2, "rlist %p:", r);
- for(i=0; i<r->nrect; i++)
- fprint(2, " %R", r->rect[i]);
- fprint(2, "\n");
- }
- #ifdef REGION_DEBUG
- int verbose = 10;
- void main(int argc, char * argv[])
- {
- Rectangle r1 = Rect(0, 0, 300, 200);
- Rectangle r2 = Rect(100, 100, 400, 300);
- Rectangle r3 = Rect(200, 100, 500, 300);
- Region reg;
- initdraw(0, 0, "vncviewer");
- region_init(®);
- region_union(®, r1, r1);
- region_union(®, r2, r2);
- region_union(®, r3, r3);
- }
- #endif
|