8 typedef struct _ibbox {
9 int xmin,ymin,xmax,ymax;
13 ibbox_t* ibbox_new(int x1, int y1, int x2, int y2)
15 ibbox_t*b = (ibbox_t*)rfx_calloc(sizeof(ibbox_t));
23 void ibbox_destroy(ibbox_t*b)
26 ibbox_t*next = b->next;
32 ibbox_t*get_bitmap_bboxes_old(unsigned char*alpha, int width, int height)
40 for(y=0;y<height;y++) {
41 unsigned char*a = &alpha[y*width];
42 for(x=0;x<width;x++) {
45 int left = x; //first occupied pixel from left
46 int right = x+1; //last non-occupied pixel from right
55 if(left<xmin) xmin = left;
56 if(right>xmax) xmax = right;
60 if(xmin<xmax || ymin<ymax) {
61 bbox = ibbox_new(xmin, ymin, xmax, ymax);
66 typedef struct _head {
76 typedef struct _context {
85 #define HEAD_MAGIC ((ptroff_t)-1)
87 head_t*head_new(context_t*context, int x, int y)
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++;
94 h->bbox.xmin = h->bbox.xmax = x;
95 h->bbox.ymin = h->bbox.ymax = y;
96 h->next = context->heads;
104 void head_delete(context_t*context, head_t*h)
107 h->prev->next = h->next;
110 h->next->prev = h->prev;
112 if(h==context->heads) {
114 context->heads = h->next;
118 #define POINTS_TO_HEAD(ptr) (((head_t*)(ptr))->magic==HEAD_MAGIC)
120 static inline link_to(context_t*context, int from, int to)
123 void**data = context->group;
126 while(!POINTS_TO_HEAD(data[head])) {
127 head=(void**)data[head]-(void**)data;
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;
137 data[from] = (void*)&data[head];
139 static char ibbox_does_overlap(ibbox_t*b1, ibbox_t*b2)
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;
147 static void ibbox_expand(ibbox_t*src, ibbox_t*add)
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;
158 static inline merge(context_t*context, int set1, int set2)
160 void**data = context->group;
165 while(!POINTS_TO_HEAD(data[head1])) {
166 head1=(void**)data[head1]-(void**)data;
168 while(!POINTS_TO_HEAD(data[head2])) {
169 head2=(void**)data[head2]-(void**)data;
171 head_t*h1 = (head_t*)data[head1];
172 head_t*h2 = (head_t*)data[head2];
174 if(h1->rank>h2->rank) {
176 ibbox_expand(&h1->bbox,&h2->bbox);
177 data[head2] = (void*)&data[head1];
178 head_delete(context, h2);
181 ibbox_expand(&h2->bbox,&h1->bbox);
182 data[head1] = (void*)&data[head2];
183 head_delete(context, h1);
187 void** annotate(context_t*context)
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;
196 for(x=1;x<width;x++) {
199 link_to(context,x,x-1);
201 group[x]=head_new(context,x,0);
205 for(y=1;y<height;y++) {
209 link_to(context,pos,pos-width);
211 group[pos]=head_new(context,0,y);
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 */
218 if(group[pos+x-width]) {
219 link_to(context,pos+x,pos+x-width);
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);
227 group[pos+x]=head_new(context,x,y);
235 ibbox_t*get_bitmap_bboxes(unsigned char*alpha, int width, int height)
237 int size = width*height;
238 if(width<=1 || height<=1)
239 return get_bitmap_bboxes_old(alpha, width, height);
242 context.alpha = alpha;
243 context.width = width;
244 context.height = height;
248 void**group = annotate(&context);
250 for(y=0;y<height;y++) {
251 for(x=0;x<width;x++) {
252 if(!group[y*width+x]) {
254 } else if(POINTS_TO_HEAD(group[y*width+x])) {
255 printf("g%02d ", ((head_t*)group[y*width+x])->nr);
257 printf("x%02d ", (void**)group[y*width+x]-(void**)group);
263 head_t*h1 = context.heads;
265 head_t*next = h1->next;
266 head_t*h2 = context.heads;
268 if(ibbox_does_overlap(&h1->bbox, &h2->bbox)) {
269 merge(&context, h1->pos, h2->pos);
277 head_t*h = context.heads;
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);
287 int main(int argn, char*argv[])
289 unsigned char alpha[8*8]=
299 get_bitmap_bboxes(alpha, 8,8);