lib/pdf/bbox.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <memory.h>
   4 #include <assert.h>
   5 #include "../types.h"
   6 #include "../mem.h"
   7
   8 typedef struct _ibbox {
   9     int xmin,ymin,xmax,ymax;
  10     struct _ibbox*next;
  11 } ibbox_t;
  12
  13 ibbox_t* ibbox_new(int x1, int y1, int x2, int y2)
  14 {
  15     ibbox_t*b = (ibbox_t*)rfx_calloc(sizeof(ibbox_t));
  16     b->xmin = x1;
  17     b->ymin = y1;
  18     b->xmax = x2;
  19     b->ymax = y2;
  20     return b;
  21 }
  22
  23 void ibbox_destroy(ibbox_t*b)
  24 {
  25     while(b) {
  26         ibbox_t*next = b->next;
  27         free(b);
  28         b = next;
  29     }
  30 }
  31
  32 ibbox_t*get_bitmap_bboxes_old(unsigned char*alpha, int width, int height)
  33 {
  34     int ymin = -1;
  35     int ymax = -1;
  36     int xmin = width;
  37     int xmax = 0;
  38
  39     int x,y;
  40     for(y=0;y<height;y++) {
  41         unsigned char*a = &alpha[y*width];
  42         for(x=0;x<width;x++) {
  43             if(a[x]) break;
  44         }
  45         int left = x; //first occupied pixel from left
  46         int right = x+1; //last non-occupied pixel from right
  47         for(;x<width;x++) {
  48             if(a[x]) right=x+1;
  49         }
  50
  51         if(left!=width) {
  52             if(ymin<0)
  53                 ymin=y;
  54             ymax=y+1;
  55             if(left<xmin) xmin = left;
  56             if(right>xmax) xmax = right;
  57         }
  58     }
  59     ibbox_t* bbox = 0;
  60     if(xmin<xmax || ymin<ymax) {
  61         bbox = ibbox_new(xmin, ymin, xmax, ymax);
  62     }
  63     return bbox;
  64 }
  65
  66 typedef struct _head {
  67     ptroff_t magic;
  68     ibbox_t bbox;
  69     int nr;
  70     int pos;
  71     int rank;
  72     struct _head*next;
  73     struct _head*prev;
  74 } head_t;
  75
  76 typedef struct _context {
  77     void**group;
  78     unsigned char*alpha;
  79     int width;
  80     int height;
  81     head_t*heads;
  82     int count;
  83 } context_t;
  84
  85 #define HEAD_MAGIC ((ptroff_t)-1)
  86
  87 head_t*head_new(context_t*context, int x, int y)
  88 {
  89     int pos = context->width*y+x;
  90     head_t*h = rfx_calloc(sizeof(head_t));
  91     h->magic = HEAD_MAGIC;
  92     h->nr = context->count++;
  93     h->pos = pos;
  94     h->bbox.xmin = h->bbox.xmax = x;
  95     h->bbox.ymin = h->bbox.ymax = y;
  96     h->next = context->heads;
  97     context->heads = h;
  98     if(h->next) {
  99         h->next->prev = h;
 100     }
 101     return h;
 102 }
 103
 104 void head_delete(context_t*context, head_t*h)
 105 {
 106     if(h->prev) {
 107         h->prev->next = h->next;
 108     }
 109     if(h->next) {
 110         h->next->prev = h->prev;
 111     }
 112     if(h==context->heads) {
 113         assert(!h->prev);
 114         context->heads = h->next;
 115     }
 116 }
 117
 118 #define POINTS_TO_HEAD(ptr) (((head_t*)(ptr))->magic==HEAD_MAGIC)
 119
 120 static inline link_to(context_t*context, int from, int to)
 121 {
 122     // path compression
 123     void**data = context->group;
 124     int head = to;
 125     assert(data[head]);
 126     while(!POINTS_TO_HEAD(data[head])) {
 127         head=(void**)data[head]-(void**)data;
 128     }
 129     head_t*h = (head_t*)data[head];
 130     int x = from%context->width;
 131     int y = from/context->width;
 132     if(x < h->bbox.xmin) h->bbox.xmin = x;
 133     if(y < h->bbox.ymin) h->bbox.ymin = y;
 134     if(x > h->bbox.xmax) h->bbox.xmax = x;
 135     if(y > h->bbox.ymax) h->bbox.ymax = y;
 136
 137     data[from] = (void*)&data[head];
 138 }
 139 static char ibbox_does_overlap(ibbox_t*b1, ibbox_t*b2)
 140 {
 141     if(b1->xmax < b1->xmin) return 0;
 142     if(b2->xmax < b2->xmin) return 0;
 143     if(b1->ymax < b1->ymin) return 0;
 144     if(b2->ymax < b2->ymin) return 0;
 145     return 1;
 146 }
 147 static void ibbox_expand(ibbox_t*src, ibbox_t*add)
 148 {
 149     if(add->xmin < src->xmin)
 150         src->xmin = add->xmin;
 151     if(add->ymin < src->ymin)
 152         src->ymin = add->ymin;
 153     if(add->xmax > src->xmax)
 154         src->xmax = add->xmax;
 155     if(add->ymax > src->ymax)
 156         src->ymax = add->ymax;
 157 }
 158 static inline merge(context_t*context, int set1, int set2)
 159 {
 160     void**data = context->group;
 161     assert(data[set1]);
 162     assert(data[set2]);
 163     int head1 = set1;
 164     int head2 = set2;
 165     while(!POINTS_TO_HEAD(data[head1])) {
 166         head1=(void**)data[head1]-(void**)data;
 167     }
 168     while(!POINTS_TO_HEAD(data[head2])) {
 169         head2=(void**)data[head2]-(void**)data;
 170     }
 171     head_t*h1 = (head_t*)data[head1];
 172     head_t*h2 = (head_t*)data[head2];
 173
 174     if(h1->rank>h2->rank) {
 175         h1->rank++;
 176         ibbox_expand(&h1->bbox,&h2->bbox);
 177         data[head2] = (void*)&data[head1];
 178         head_delete(context, h2);
 179     } else {
 180         h2->rank++;
 181         ibbox_expand(&h2->bbox,&h1->bbox);
 182         data[head1] = (void*)&data[head2];
 183         head_delete(context, h1);
 184     }
 185 }
 186
 187 void** annotate(context_t*context)
 188 {
 189     unsigned char*alpha = context->alpha;
 190     int width = context->width;
 191     int height = context->height;
 192     void** group = rfx_calloc(width*height*sizeof(void*));
 193     context->group = group;
 194     int x,y;
 195
 196     for(x=1;x<width;x++) {
 197         if(alpha[x]) {
 198             if(group[x-1])
 199                 link_to(context,x,x-1);
 200             else
 201                 group[x]=head_new(context,x,0);
 202         }
 203     }
 204     int pos = 0;
 205     for(y=1;y<height;y++) {
 206         pos += width;
 207         if(alpha[pos]) {
 208             if(group[pos-width])
 209                 link_to(context,pos,pos-width);
 210             else
 211                 group[pos]=head_new(context,0,y);
 212         }
 213         for(x=1;x<width;x++) {
 214             /* once this code is stable we should copy&paste it
 215                out of the loop, change the loop end to width-1 and
 216                add the pos-width+1 case */
 217             if(alpha[pos+x]) {
 218                 if(group[pos+x-width]) {
 219                     link_to(context,pos+x,pos+x-width);
 220                     if(group[pos+x-1])
 221                         merge(context,pos+x,pos+x-1);
 222                 } else if(group[pos+x-1]) {
 223                     link_to(context,pos+x,pos+x-1);
 224                 } else if(group[pos+x-width-1]) {
 225                     link_to(context,pos+x,pos+x-width-1);
 226                 } else {
 227                     group[pos+x]=head_new(context,x,y);
 228                 }
 229             }
 230         }
 231     }
 232     return group;
 233 }
 234
 235 ibbox_t*get_bitmap_bboxes(unsigned char*alpha, int width, int height)
 236 {
 237     int size = width*height;
 238     if(width<=1 || height<=1)
 239         return get_bitmap_bboxes_old(alpha, width, height);
 240
 241     context_t context;
 242     context.alpha = alpha;
 243     context.width = width;
 244     context.height = height;
 245     context.heads = 0;
 246     context.count = 1;
 247
 248     void**group = annotate(&context);
 249     int x,y;
 250     for(y=0;y<height;y++) {
 251         for(x=0;x<width;x++) {
 252             if(!group[y*width+x]) {
 253                 printf(" -- ");
 254             } else if(POINTS_TO_HEAD(group[y*width+x])) {
 255                 printf("g%02d ", ((head_t*)group[y*width+x])->nr);
 256             } else {
 257                 printf("x%02d ", (void**)group[y*width+x]-(void**)group);
 258             }
 259         }
 260         printf("\n");
 261     }
 262
 263     head_t*h1 = context.heads;
 264     while(h1) {
 265         head_t*next = h1->next;
 266         head_t*h2 = context.heads;
 267         while(h2) {
 268             if(ibbox_does_overlap(&h1->bbox, &h2->bbox)) {
 269                 merge(&context, h1->pos, h2->pos);
 270                 break;
 271             }
 272             h2 = h2->next;
 273         }
 274         h1 = next;
 275     }
 276
 277     head_t*h = context.heads;
 278     while(h) {
 279         printf("head: %d\n", h->nr);
 280         printf(" pos: %d/%d\n", h->pos%width, h->pos/width);
 281         printf(" bbox: [%d/%d,%d/%d]\n", h->bbox.xmin, h->bbox.ymin, h->bbox.xmax, h->bbox.ymax);
 282         h = h->next;
 283     }
 284 }
 285
 286 #ifdef MAIN
 287 int main(int argn, char*argv[])
 288 {
 289     unsigned char alpha[8*8]=
 290         "\0\0\1\0\0\0\0\0"
 291         "\1\0\0\1\0\1\0\0"
 292         "\0\0\0\0\0\0\1\0"
 293         "\0\0\1\0\1\0\0\0"
 294         "\1\0\1\0\1\0\0\0"
 295         "\1\0\1\1\1\0\0\1"
 296         "\1\0\0\0\0\0\1\0"
 297         "\1\1\1\0\0\0\0\0";
 298
 299     get_bitmap_bboxes(alpha, 8,8);
 300 }
 301 #endif