/[opencvs]/eyes/tilify_cyclone.c
ViewVC logotype

Contents of /eyes/tilify_cyclone.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.8 - (show annotations)
Thu Jan 22 00:58:47 2015 UTC (3 years, 3 months ago) by hib
Branch: MAIN
CVS Tags: HEAD
Changes since 1.7: +4 -3 lines
File MIME type: text/plain
Adding als specific things. working on cassidi
1
2
3
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <math.h>
8
9 #include "util.h"
10
11 /* This will tile an image based on finding the best contrast between the 4 areas
12 based on a range up to 30 percent from one area to another.
13
14 this is the cyclone variation. Brcause you see, we will be rotating the picture
15
16 */
17
18
19 #define SCALE
20 /* special - to scale up the picture to something really really big */
21
22 #define min(a,b) ((a)<(b)?(a):(b))
23 #define max(a,b) ((a)>(b)?(a):(b))
24
25 struct speed {
26 /* the following are for speed */
27 int xmin;
28 int ymin;
29 int xmax;
30 int ymax;
31 double one_over_vertys[4];
32 double vertx[4];
33 double verty[4];
34 };
35
36
37 struct square {
38 int x1;
39 int y1;
40 int x2;
41 int y2;
42 int x3;
43 int y3;
44 int x4;
45 int y4;
46 struct square *upper_left_sub;
47 struct square *upper_right_sub;
48 struct square *lower_left_sub;
49 struct square *lower_right_sub;
50 struct square *above;
51 struct square *below;
52 struct square *left;
53 struct square *right;
54 struct square *parent;
55 int r;
56 int g;
57 int b;
58 struct speed speed;
59 };
60
61
62 struct square squares[1048576];
63 int square_count = 0;
64
65
66 /* stoled from http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
67 But modified it to better handle the slope=0
68 */
69 inline int pnpoly(int nvert, double *vertx, double *verty, double testx, double testy)
70 {
71 int i, j, c = 0;
72 for (i = 0, j = nvert-1; i < nvert; j = i++) {
73 if ( ((verty[i]>testy) != (verty[j]>testy)) &&
74 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
75 c = !c;
76 }
77 return c;
78 }
79
80 inline int some_inside2(int x,int y,struct speed speed) {
81 double testx,testy;
82 int i, j, c = 0;
83 testx=x;
84 testy=y;
85 for (i = 0, j = 3; i < 4; j = i++) {
86 if ( ((speed.verty[i]>testy) != (speed.verty[j]>testy)) &&
87 (testx < (speed.vertx[j]-speed.vertx[i]) * (testy-speed.verty[i])
88 * (speed.one_over_vertys[i]) + speed.vertx[i]) )
89 c = !c;
90 }
91 return c;
92 }
93
94 inline int some_inside1(int x,int y,struct speed speed) {
95 double testx,testy;
96 int i, j, c = 0;
97 if ((x<speed.xmin)||(x>=speed.xmax)||(y<speed.ymin)||(y>speed.ymax)) return 0;
98 testx=x;
99 testy=y;
100 for (i = 0, j = 3; i < 4; j = i++) {
101 if ( ((speed.verty[i]>testy) != (speed.verty[j]>testy)) &&
102 (testx < (speed.vertx[j]-speed.vertx[i]) * (testy-speed.verty[i])
103 * (speed.one_over_vertys[i]) + speed.vertx[i]) )
104 c = !c;
105 }
106 return c;
107
108 }
109
110
111
112 void compute_speed(struct speed *sp,int x1,int y1,int x2,int y2,int x3,int y3, int x4, int y4)
113 {
114 sp->xmax = max(max(x1,x2),max(x3,x4));
115 sp->xmin = min(min(x1,x2),min(x3,x4));
116 sp->ymax = max(max(y1,y2),max(y3,y4));
117 sp->ymin = min(min(y1,y2),min(y3,y4));
118
119 sp->vertx[0] = x1;
120 sp->vertx[1] = x2;
121 sp->vertx[2] = x4; /* yes, this is flipped because we are doing line segments here */
122 sp->vertx[3] = x3;
123
124 sp->verty[0] = y1;
125 sp->verty[1] = y2;
126 sp->verty[2] = y4; /* yes, this is flipped because we are doing line segments here */
127 sp->verty[3] = y3;
128
129 double ydelta;
130 ydelta = sp->verty[3]-sp->verty[0];
131 if (ydelta!= 0.0) ydelta = 1.0 / ydelta;
132 sp->one_over_vertys[0] = ydelta;
133
134 ydelta = sp->verty[0]-sp->verty[1];
135 if (ydelta!= 0.0) ydelta = 1.0 / ydelta;
136 sp->one_over_vertys[1] = ydelta;
137 ydelta = sp->verty[1]-sp->verty[2];
138 if (ydelta!= 0.0) ydelta = 1.0 / ydelta;
139 sp->one_over_vertys[2] = ydelta;
140 ydelta = sp->verty[2]-sp->verty[3];
141 if (ydelta!= 0.0) ydelta = 1.0 / ydelta;
142 sp->one_over_vertys[3] = ydelta;
143
144 }
145
146
147 inline int some_inside(int x,int y,int x1,int y1,int x2,int y2,int x3,int y3, int x4, int y4)
148 {
149 /* This assumes that x1,y1 is included 100 % but x4,y4 is not included
150 This also assumes that positive y goes down and positive x goes right */
151 struct speed speed;
152 compute_speed(&speed,x1,y1,x2,y2,x3,y3,x4,y4);
153 return some_inside1(x,y,speed);
154 }
155
156
157 /* This legacy inside has the magic that makes the picture look great
158 without it it looks like crap */
159 int some_insidel(int x,int y,int x1,int y1,int x2,int y2,int x3,int y3, int x4, int y4) {
160 /* This assumes that x1,y1 is included 100 % but x4,y4 is not included
161 This also assumes that positive y goes down and positive x goes right */
162 double x1d,y1d,x2d,y2d,x3d,y3d,x4d,y4d,xd,yd;
163 /* above below slope intercept stuff - but there are weird cases at the edges
164 for now we will ignore the edge cases. It is either inside or not
165 I guess we could make a percentage inside by multiplying and doing an antialiasing and
166 getting a percentage
167 */
168
169 xd = x;yd = y;
170 x1d = x1;y1d = y1;
171 x2d = x2; y2d = y2;
172 x3d = x3; y3d = y3;
173 x4d = x4; y4d = y4;
174 if ((xd < x1d)&&(xd < x3d)) { return 0;} /* x is to the left */
175 if ((xd >= x2d)&&(xd >= x4d)) { return 0;} /* x is to the right */
176 if ((yd < y1d)&&(yd < y2d)) { return 0;} /* y is above */
177 if ((yd >= y3d)&&(yd >= y4d)) { return 0;} /* y is below */
178 double slope;
179 double y_intercept;
180 double inv_slope;
181 double x_intercept;
182 double our_y;
183 double our_x;
184
185 /* see if above the 12 line */
186 if (x1==x2) {
187 if ((yd < y1d)||(yd < y2d)) { return 0;}
188 }
189 else {
190 slope = ((double)(y2d - y1d))/((double)(x2d-x1d));
191 y_intercept = y1 - x1*slope;
192 our_y = slope * xd + y_intercept;
193 if (y <our_y) {return 0;} /* y is above our line for the given x */
194 }
195
196
197 /* see if below or on the 34 line */
198 if (x3==x4) {
199 if ((yd >= y3d)||(yd >= y4d)) { return 0;}
200 }
201 else {
202 slope = (y4d - y3d)/(x4d-x3d);
203 y_intercept = y3 - x3*slope;
204 our_y = slope * xd + y_intercept;
205 if (y >= our_y) {return 0;} /* y is below or on our line for the given x */
206 }
207
208 /* see if to the right of the 13 line */
209 if (y1==y3) {
210 if ((xd < x1d)||(xd < x3d)) { return 0;}
211 }
212 inv_slope = (x3d-x1d)/(y3d-y1d);
213 x_intercept = x3 - y3*inv_slope;
214 our_x = inv_slope * yd + x_intercept;
215 if (x < our_x) {return 0;};
216
217
218 /* see if to the left of the 24 line */
219 if (y2==y4) {
220 if ((xd >= x2d)||(xd >= x4d)) { return 0;}
221 }
222 inv_slope = (x4d-x2d)/(y4d-y2d);
223 x_intercept = x4 - y4*inv_slope;
224 our_x = inv_slope * yd + x_intercept;
225 if (x >= our_x) {return 0;};
226
227 return 1;
228 }
229
230
231
232 int compute_average(unsigned char *raster,int xsize,int ysize,
233 int x1,int y1, int x2, int y2, int x3, int y3, int x4, int y4,double *pr, double *pg, double *pb)
234 {
235 double count;
236 double r,g,b;
237 count = 0.;
238 r=0.;
239 g=0.;
240 b=0.;
241
242 int ix,iy;
243 int minx,miny,maxx,maxy;
244 minx=min(min(x1,x2),min(x3,x4));
245 miny=min(min(y1,y2),min(y3,y4));
246 maxx=max(max(x1,x2),max(x3,x4));
247 maxy=max(max(y1,y2),max(y3,y4));
248 for (iy=miny;iy<maxy;iy++) {
249 for (ix=minx;ix<maxx;ix++) {
250 if (some_insidel(ix,iy,x1,y1,x2,y2,x3,y3,x4,y4)) {
251 int loc= (iy*xsize+ix);
252 loc = loc+loc+loc;
253 r += raster[loc++];
254 g += raster[loc++];
255 b += raster[loc++];
256 count += 1.;
257 }
258 }
259 }
260 if (count==0) {
261 r=128.;
262 g=128.;
263 b=128.;
264 }
265 else {
266 r = r / count;
267 g = g / count;
268 b = b / count;
269 }
270 *pr = r;
271 *pg = g;
272 *pb = b;
273 return count;
274 }
275
276
277
278
279 int compute_average1(unsigned char *raster,int xsize,int ysize,
280 int x1,int y1, int x2, int y2, int x3, int y3, int x4, int y4,double *pr, double *pg, double *pb)
281 {
282 double count;
283 double r,g,b;
284 count = 0.;
285 r=0.;
286 g=0.;
287 b=0.;
288
289 int ix,iy;
290 struct speed speed;
291 compute_speed(&speed,x1,y1,x2,y2,x3,y3,x4,y4);
292 int loc;
293 for (iy=speed.ymin;iy<speed.ymax;iy++) {
294 loc=(speed.ymin*xsize+speed.xmin)*3;
295 for (ix=speed.xmin;ix<speed.xmax;ix++) {
296 if (some_inside2(ix,iy,speed)) {
297 r += raster[loc++];
298 g += raster[loc++];
299 b += raster[loc++];
300 count++;
301 }
302 else {
303 loc += 3;
304 }
305 }
306 }
307 if (count==0) {
308 r=128.;
309 g=128.;
310 b=128.;
311 }
312 else {
313 r = r / count;
314 g = g / count;
315 b = b / count;
316 }
317 *pr = r;
318 *pg = g;
319 *pb = b;
320 return count;
321 }
322
323
324
325
326
327
328
329
330 int find_best_intersection_main(unsigned char *raster,int xsize,int ysize,int percentage,
331 int x1,int y1, int x2, int y2,int x3, int y3, int x4, int y4,
332 int cx, int cy, int *pbestx, int *pbesty)
333 {
334 int ix,iy;
335 int rx1,rx2,rx3,rx4,ry1,ry2,ry3,ry4; /* range to look for the new center point */
336 /* figure out the range to look at */
337 rx1 = cx + ((x1-cx) * percentage) / 100;
338 ry1 = cy + ((y1-cy)*percentage) / 100;
339 rx2 = cx + ((x2-cx) * percentage) / 100;
340 ry2 = cy + ((y2-cy)*percentage) / 100;
341 rx3 = cx + ((x3-cx) * percentage) / 100;
342 ry3 = cy + ((y3-cy)*percentage) / 100;
343 rx4 = cx + ((x4-cx) * percentage) / 100;
344 ry4 = cy + ((y4-cy)*percentage) / 100;
345
346 int x12 = (x1+x2)>>1;
347 int x13 = (x1+x3)>>1;
348 int x24 = (x2+x4)>>1;
349 int x34 = (x3+x4)>>1;
350 int y12 = (y1+y2)>>1;
351 int y13 = (y1+y3)>>1;
352 int y24 = (y2+y4)>>1;
353 int y34 = (y3+y4)>>1;
354
355 /* convert the quad range into a square range bigger than the quad */
356 struct speed speed;
357 compute_speed(&speed,rx1,ry1,rx2,ry2,rx3,ry3,rx4,ry4);
358 int minx,miny,maxx,maxy;
359 minx=speed.xmin;
360 maxx=speed.xmax;
361 miny=speed.ymin;
362 maxy=speed.ymax;
363
364 int tries;
365
366 double best_variance=-1.;
367 int best_x = -1;
368 int best_y = -1;
369 /* loop through all possible points and find the one combination with the highest variance between the blobs - thats where
370 we want to make a sub-point */
371 {
372 for (tries = 0;tries<500;tries++) {
373 if (maxy==miny) iy=maxy;
374 else iy = ((random()>>2)%(maxy-miny))+miny;
375 if (maxx==minx) ix=maxx;
376 else ix = ((random()>>2)%(maxx-minx))+minx;
377
378
379 /*for (iy=miny;iy<maxy;iy++) {
380 fprintf(stderr," \r");
381 fprintf(stderr,"%lf %d,%d %d\r",best_variance,best_x,best_y,iy);
382 for (ix=minx;ix<maxx;ix++) {
383 */
384 if (some_inside2(ix,iy,speed)) {
385 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
386 double meanr,meang,meanb;
387 double varr,varg,varb;
388 double combined_var;
389 compute_average(raster,xsize,ysize,x1,y1,x12,y12,x13,y13,ix,iy,&r1,&g1,&b1); /* upper left */
390 compute_average(raster,xsize,ysize,x12,y12,x2,y2,ix,iy,x24,y24,&r2,&g2,&b2); /* upper right */
391 compute_average(raster,xsize,ysize,x13,y13,ix,iy,x3,y3,x34,y34,&r3,&g3,&b3); /* lower left */
392 compute_average(raster,xsize,ysize,ix,iy,x24,y24,x34,y34,x4,y4,&r4,&g4,&b4); /* lower right */
393 meanr=(r1+r2+r3+r4)/4.0;
394 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
395 meang = (g1+g2+g3+g4)/4.0;
396 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
397 meanb = (b1+b2+b3+b4)/4.0;
398 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
399 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
400 if (combined_var > best_variance) {
401 best_variance = combined_var;
402 best_x = ix;
403 best_y = iy;
404 }
405 } /* if we fit */
406 } /* for each possible x */
407 } /* for each possible y */
408
409
410 if (best_x == -1) { /* cannot split further */
411 *pbestx = cx;
412 *pbesty = cy;
413 return 0;
414 }
415 *pbestx = best_x;
416 *pbesty = best_y;
417 return 1;
418 }
419
420
421
422
423
424
425
426
427
428 #ifdef NOTUSEDfgdsgdsg
429
430
431
432 int find_best_intersection_points(unsigned char *raster,int xsize,int ysize,int percentage,
433 struct square *s)
434 {
435 int minx,miny,maxx,maxy;
436 /* figure out the range to look at */
437 double r;
438 double slope;
439 double y_intercept;
440 double inv_slope;
441 double x_intercept;
442 double our_y;
443 double our_x;
444 struct square *s1,*s2,*s3,*s4;
445 s1 = s->upper_left_sub;
446 s2 = s->upper_right_sub;
447 s3 = s->lower_left_sub;
448 s4 = s->lower_right_sub;
449
450 int x1, y1,x2,y2,x3,y3,x4,y4;
451 int cx,cy;
452 x1=s->x1;y1=s->y1;
453 x2=s->x2;y2=s->y2;
454 x3=s->x3;y3=s->y3;
455 x4=s->x4;y4=s->y4;
456 cx = s1->x4;
457 cy = s1->y4;
458
459
460 int r2;
461
462 int x12 = (x1+x2)>>1;
463 int x13 = (x1+x3)>>1;
464 int x24 = (x2+x4)>>1;
465 int x34 = (x3+x4)>>1;
466 int y12 = (y1+y2)>>1;
467 int y13 = (y1+y3)>>1;
468 int y24 = (y2+y4)>>1;
469 int y34 = (y3+y4)>>1;
470
471
472 double factor;
473
474 int flag=1;
475 if ((x1==50717)&&(x2==50981)&&(x2==50541)&&(x4==50776)) {
476 flag=1;
477 fprintf(stderr,"got it\n");
478 }
479
480
481
482 /* handle 1-2 edge */
483 double best_variance=-1.;
484 int best_x = -1;
485 int best_y = -1;
486
487
488
489 if (x2==x1) { // no slope
490 int rf,rt;
491 int miny,maxy;
492 miny = min(y1,y2);
493 maxy = max(y1,y2);
494 rf = (maxy+miny)>>1 - ((maxy-miny)>>1 * percentage / 100) ;
495 rt = (maxy+miny)>>1 + ((maxy-miny)>>1 * percentage / 100) ;
496
497 int i;
498 for (i=rf;i<rt;i++) {
499 int ix,iy;
500 ix = x1;
501 iy = i;
502 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
503 double meanr,meang,meanb;
504 double varr,varg,varb;
505 double combined_var;
506 compute_average(raster,xsize,ysize,x1,y1,ix,iy,x13,y13,cx,cy,&r1,&g1,&b1); /* upper left */
507 compute_average(raster,xsize,ysize,ix,iy,x2,y2,cx,cy,x24,y24,&r2,&g2,&b2); /* upper right */
508
509 if (s1->above) {
510 struct square *k;
511 k=s1->above;
512 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,k->x3,k->y3,ix,iy,&r3,&g3,&b3); /* upper neighbor */
513 } else {
514 r3=r1;g3=g1;b3=b1;
515 }
516
517 if (s2->above) {
518 struct square *k;
519 k=s2->above;
520 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,ix,iy,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
521 } else {
522 r4=r2;g4=g2;b4=b2;
523 }
524
525
526 meanr=(r1+r2+r3+r4)/4.0;
527 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
528 meang = (g1+g2+g3+g4)/4.0;
529 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
530 meanb = (b1+b2+b3+b4)/4.0;
531 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
532 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
533 if (combined_var > best_variance) {
534 best_variance = combined_var;
535 best_x = ix;
536 best_y = iy;
537 }
538 } /* for each possible position */
539 } /* if we have no slope */
540 else {
541 int rf,rt;
542 r = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
543 r = sqrt(r);
544 r2 = r*1.5; /*fudge */
545 slope = ((double)(y2-y1))/((double)(x2-x1));
546 y_intercept = (double)(y1) - ((double)(x1))*slope;
547 factor = ((double)(x2-x1))/r2;
548 rf = r2>>1 - ((r2>>1) * percentage) / 100;
549 rt = r2>>1 + ((r2>>1) * percentage) / 100;
550
551 int i;
552 for (i=rf;i<rt;i++) {
553 int pos;
554 double x,y;
555 int ix,iy;
556 x = x1 + factor * ((double)(i));
557 y = x * slope + y_intercept;
558 ix=x;
559 iy=y;
560 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
561 double meanr,meang,meanb;
562 double varr,varg,varb;
563 double combined_var;
564 compute_average(raster,xsize,ysize,x1,y1,ix,iy,x13,y13,cx,cy,&r1,&g1,&b1); /* upper left */
565 compute_average(raster,xsize,ysize,ix,iy,x2,y2,cx,cy,x24,y24,&r2,&g2,&b2); /* upper right */
566
567 if (s1->above) {
568 struct square *k;
569 k=s1->above;
570 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,k->x3,k->y3,ix,iy,&r3,&g3,&b3); /* upper neighbor */
571 } else {
572 r3=r1;g3=g1;b3=b1;
573 }
574
575 if (s2->above) {
576 struct square *k;
577 k=s2->above;
578 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,ix,iy,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
579 } else {
580 r4=r2;g4=g2;b4=b2;
581 }
582
583
584 meanr=(r1+r2+r3+r4)/4.0;
585 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
586 meang = (g1+g2+g3+g4)/4.0;
587 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
588 meanb = (b1+b2+b3+b4)/4.0;
589 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
590
591 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
592 if (combined_var > best_variance) {
593 best_variance = combined_var;
594 best_x = ix;
595 best_y = iy;
596 }
597 } /* for each possible position */
598 }
599 if (best_x == -1) { /* cannot split further */
600 best_x = x12;
601 best_y = y12;
602 }
603 else {
604 x12 = best_x;
605 y12 = best_y;
606 }
607
608 s1->x2 = best_x;
609 s1->y2 = best_y;
610 s2->x1 = best_x;
611 s2->y1 = best_y;
612 if (s1->above) {
613 s1->above->x4 = best_x;
614 s1->above->y4 = best_y;
615 }
616 if (s2->above) {
617 s2->above->x3 = best_x;
618 s2->above->y3 = best_y;
619 }
620
621
622
623 /* now find the point on the 3/4 line */
624 /* handle 3-4 edge */
625 best_variance=-1.;
626 best_x = -1;
627 best_y = -1;
628
629 if (x3==x4) { // no slope
630 int rf,rt;
631 int miny,maxy;
632 miny = min(y3,y4);
633 maxy = max(y3,y4);
634 rf = (maxy+miny)>>1 - ((maxy-miny)>>1 * percentage / 100) ;
635 rt = (maxy+miny)>>1 + ((maxy-miny)>>1 * percentage / 100) ;
636
637 int i;
638 for (i=rf;i<rt;i++) {
639 int ix,iy;
640 ix = x1;
641 iy = i;
642 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
643 double meanr,meang,meanb;
644 double varr,varg,varb;
645 double combined_var;
646 compute_average(raster,xsize,ysize,x13,y13,cx,cy,x3,y3,ix,iy,&r1,&g1,&b1); /* lower left */
647 compute_average(raster,xsize,ysize,cx,cy,x24,y24,ix,iy,x4,y4,&r2,&g2,&b2); /* lower right */
648
649 if (s3->below) {
650 struct square *k;
651 k=s3->below;
652 compute_average(raster,xsize,ysize,k->x1,k->y1,ix,iy,k->x3,k->y3,k->x4,k->y4,&r3,&g3,&b3); /* upper neighbor */
653 } else {
654 r3=r1;g3=g1;b3=b1;
655 }
656
657 if (s4->below) {
658 struct square *k;
659 k=s4->below;
660 compute_average(raster,xsize,ysize,ix,iy,k->x2,k->y2,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
661 } else {
662 r4=r2;g4=g2;b4=b2;
663 }
664
665
666 meanr=(r1+r2+r3+r4)/4.0;
667 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
668 meang = (g1+g2+g3+g4)/4.0;
669 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
670 meanb = (b1+b2+b3+b4)/4.0;
671 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
672 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
673 if (combined_var > best_variance) {
674 best_variance = combined_var;
675 best_x = ix;
676 best_y = iy;
677 }
678 } /* for each possible position */
679 } /* if we have no slope */
680 else {
681 int rf,rt;
682 r = (x4-x3)*(x4-x3) + (y4-y3)*(y4-y3);
683 r = sqrt(r);
684 r2 = r*1.5; /*fudge */
685 slope = ((double)(y4-y3))/((double)(x4-x3));
686 y_intercept = ((double)y3) - ((double)(x3))*slope;
687 factor = ((double)(x4-x3))/r2;
688 rf = r2>>1 - ((r2>>1) * percentage) / 100;
689 rt = r2>>1 + ((r2>>1) * percentage) / 100;
690
691 int i;
692 for (i=rf;i<rt;i++) {
693 int pos;
694 double x,y;
695 int ix,iy;
696 x = x3 + factor * ((double)(i));
697 y = x * slope + y_intercept;
698 ix=x;
699 iy=y;
700 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
701 double meanr,meang,meanb;
702 double varr,varg,varb;
703 double combined_var;
704 compute_average(raster,xsize,ysize,x13,y13,cx,cy,x3,y3,ix,iy,&r1,&g1,&b1); /* lower left */
705 compute_average(raster,xsize,ysize,cx,cy,x24,y24,ix,iy,x4,y4,&r2,&g2,&b2); /* lower right */
706
707 if (s3->below) {
708 struct square *k;
709 k=s3->below;
710 compute_average(raster,xsize,ysize,k->x1,k->y1,ix,iy,k->x3,k->y3,k->x4,k->y4,&r3,&g3,&b3); /* upper neighbor */
711 } else {
712 r3=r1;g3=g1;b3=b1;
713 }
714
715 if (s4->below) {
716 struct square *k;
717 k=s4->below;
718 compute_average(raster,xsize,ysize,ix,iy,k->x2,k->y2,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
719 } else {
720 r4=r2;g4=g2;b4=b2;
721 }
722
723
724 meanr=(r1+r2+r3+r4)/4.0;
725 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
726 meang = (g1+g2+g3+g4)/4.0;
727 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
728 meanb = (b1+b2+b3+b4)/4.0;
729 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
730 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
731
732 if (combined_var > best_variance) {
733 best_variance = combined_var;
734 best_x = ix;
735 best_y = iy;
736 }
737 } /* for each possible position */
738 }
739 if (best_x == -1) { /* cannot split further */
740 best_x = x34;
741 best_y = y34;
742 }
743 else {
744 x34 = best_x;
745 y34 = best_y;
746 }
747
748 s3->x4 = best_x;
749 s3->y4 = best_y;
750 s4->x3 = best_x;
751 s4->y3 = best_y;
752 if (s3->below) {
753 s3->below->x2 = best_x;
754 s3->below->y2 = best_y;
755 }
756 if (s4->below) {
757 s4->below->x1 = best_x;
758 s4->below->y1 = best_y;
759 }
760
761
762
763
764
765
766
767
768 /* handle 1-3 edge */
769 best_variance=-1.;
770 best_x = -1;
771 best_y = -1;
772
773 if (x3==x1) { // no slope
774 int rf,rt;
775 int miny,maxy;
776 miny = min(y1,y3);
777 maxy = max(y1,y3);
778 rf = (maxy+miny)>>1 - ((maxy-miny)>>1 * percentage / 100) ;
779 rt = (maxy+miny)>>1 + ((maxy-miny)>>1 * percentage / 100) ;
780
781 int i;
782 for (i=rf;i<rt;i++) {
783 int ix,iy;
784 ix = x1;
785 iy = i;
786 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
787 double meanr,meang,meanb;
788 double varr,varg,varb;
789 double combined_var;
790 compute_average(raster,xsize,ysize,x1,y1,x12,y12,ix,iy,cx,cy,&r1,&g1,&b1); /* upper left */
791 compute_average(raster,xsize,ysize,ix,iy,cx,cy,x3,y3,x34,y34,&r2,&g2,&b2); /* lower left */
792 if (s1->left) {
793 struct square *k;
794 k=s1->left;
795 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,k->x3,k->y3,ix,iy,&r3,&g3,&b3); /* left */
796 } else {
797 r3=r1;g3=g1;b3=b1;
798 }
799
800 if (s3->left) {
801 struct square *k;
802 k=s3->left;
803 compute_average(raster,xsize,ysize,k->x1,k->y1,ix,iy,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
804 } else {
805 r4=r2;g4=g2;b4=b2;
806 }
807
808
809 meanr=(r1+r2+r3+r4)/4.0;
810 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
811 meang = (g1+g2+g3+g4)/4.0;
812 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
813 meanb = (b1+b2+b3+b4)/4.0;
814 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
815 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
816 if (combined_var > best_variance) {
817 best_variance = combined_var;
818 best_x = ix;
819 best_y = iy;
820 }
821 } /* for each possible position */
822 } /* if we have no slope */
823 else {
824 int rf,rt;
825 r = (x3-x1)*(x3-x1) + (y3-y1)*(y3-y1);
826 r = sqrt(r);
827 r2 = r*1.5; /*fudge */
828 slope = ((double)(y3-y1))/((double)(x3-x1));
829 y_intercept = (double)(y1) - ((double)(x1))*slope;
830 factor = ((double)(x3-x1))/r2;
831 rf = r2>>1 - ((r2>>1) * percentage) / 100;
832 rt = r2>>1 + ((r2>>1) * percentage) / 100;
833
834 int i;
835 for (i=rf;i<rt;i++) {
836 int pos;
837 double x,y;
838 int ix,iy;
839 x = x1 + factor * ((double)(i));
840 y = x * slope + y_intercept;
841 ix=x;
842 iy=y;
843 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
844 double meanr,meang,meanb;
845 double varr,varg,varb;
846 double combined_var;
847 compute_average(raster,xsize,ysize,x1,y1,x12,y12,ix,iy,cx,cy,&r1,&g1,&b1); /* upper left */
848 compute_average(raster,xsize,ysize,ix,iy,cx,cy,x3,y3,x34,y34,&r2,&g2,&b2); /* lower left */
849 if (s1->left) {
850 struct square *k;
851 k=s1->left;
852 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,k->x3,k->y3,ix,iy,&r3,&g3,&b3); /* left */
853 } else {
854 r3=r1;g3=g1;b3=b1;
855 }
856
857 if (s3->left) {
858 struct square *k;
859 k=s3->left;
860 compute_average(raster,xsize,ysize,k->x1,k->y1,ix,iy,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
861 } else {
862 r4=r2;g4=g2;b4=b2;
863 }
864
865
866 meanr=(r1+r2+r3+r4)/4.0;
867 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
868 meang = (g1+g2+g3+g4)/4.0;
869 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
870 meanb = (b1+b2+b3+b4)/4.0;
871 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
872 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
873 if (combined_var > best_variance) {
874 best_variance = combined_var;
875 best_x = ix;
876 best_y = iy;
877 }
878 } /* for each possible position */
879 }
880 if (best_x == -1) { /* cannot split further */
881 best_x = x13;
882 best_y = y13;
883 }
884 else {
885 x13 = best_x;
886 y13 = best_y;
887 }
888
889 s1->x3 = best_x;
890 s1->y3 = best_y;
891 s3->x1 = best_x;
892 s3->y1 = best_y;
893 if (s1->left) {
894 s1->left->x4 = best_x;
895 s1->left->y4 = best_y;
896 }
897 if (s3->left) {
898 s3->left->x2 = best_x;
899 s3->left->y2 = best_y;
900 }
901
902
903
904
905
906
907
908 /* handle 2-4 edge */
909 best_variance=-1.;
910 best_x = -1;
911 best_y = -1;
912
913 if (x4==x2) { // no slope
914 int rf,rt;
915 int miny,maxy;
916 miny = min(y2,y4);
917 maxy = max(y2,y4);
918 rf = (maxy+miny)>>1 - ((maxy-miny)>>1 * percentage / 100) ;
919 rt = (maxy+miny)>>1 + ((maxy-miny)>>1 * percentage / 100) ;
920
921 int i;
922 for (i=rf;i<rt;i++) {
923 int ix,iy;
924 ix = x2;
925 iy = i;
926 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
927 double meanr,meang,meanb;
928 double varr,varg,varb;
929 double combined_var;
930 compute_average(raster,xsize,ysize,x12,y12,x2,y2,cx,cy,ix,iy,&r1,&g1,&b1); /* upper right */
931 compute_average(raster,xsize,ysize,cx,cy,ix,iy,x34,y34,x4,y4,&r2,&g2,&b2); /* lower right */
932 if (s2->right) {
933 struct square *k;
934 k=s2->right;
935 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,ix,iy,k->x4,k->y4,&r3,&g3,&b3); /* left */
936 } else {
937 r3=r1;g3=g1;b3=b1;
938 }
939
940 if (s4->right) {
941 struct square *k;
942 k=s4->right;
943 compute_average(raster,xsize,ysize,ix,iy,k->x2,k->y2,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
944 } else {
945 r4=r2;g4=g2;b4=b2;
946 }
947
948
949 meanr=(r1+r2+r3+r4)/4.0;
950 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
951 meang = (g1+g2+g3+g4)/4.0;
952 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
953 meanb = (b1+b2+b3+b4)/4.0;
954 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
955 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
956
957
958 if (combined_var > best_variance) {
959 best_variance = combined_var;
960 best_x = ix;
961 best_y = iy;
962 }
963 } /* for each possible position */
964 } /* if we have no slope */
965 else {
966 int rf,rt;
967 r = (x4-x2)*(x4-x2) + (y4-y2)*(y4-y2);
968 r = sqrt(r);
969 r2 = r*1.5; /*fudge */
970 slope = ((double)(y4-y2))/((double)(x4-x2));
971 y_intercept = (double)(y2) - ((double)(x2))*slope;
972 factor = ((double)(x4-x2))/r2;
973 rf = r2>>1 - ((r2>>1) * percentage) / 100;
974 rt = r2>>1 + ((r2>>1) * percentage) / 100;
975
976
977 if (flag) {
978 fprintf(stderr,"from [%d to %d)\n",rf,rt);
979 }
980 int i;
981 for (i=rf;i<rt;i++) {
982 int pos;
983 double x,y;
984 int ix,iy;
985 x = x2 + factor * ((double)(i));
986 y = x * slope + y_intercept;
987 ix=x;
988 iy=y;
989 if (flag) {
990 fprintf(stderr,"i %d x %d y %d\n",i,ix,iy);
991 }
992
993 double r1,g1,b1,r2,g2,b2,r3,g3,b3,r4,g4,b4;
994 double meanr,meang,meanb;
995 double varr,varg,varb;
996 double combined_var;
997 compute_average(raster,xsize,ysize,x12,y12,x2,y2,cx,cy,ix,iy,&r1,&g1,&b1); /* upper right */
998 compute_average(raster,xsize,ysize,cx,cy,ix,iy,x34,y34,x4,y4,&r2,&g2,&b2); /* lower right */
999
1000
1001 if (s2->right) {
1002 struct square *k;
1003 k=s2->right;
1004 compute_average(raster,xsize,ysize,k->x1,k->y1,k->x2,k->y2,ix,iy,k->x4,k->y4,&r3,&g3,&b3); /* left */
1005 } else {
1006 r3=r1;g3=g1;b3=b1;
1007 }
1008
1009 if (s4->right) {
1010 struct square *k;
1011 k=s4->right;
1012 compute_average(raster,xsize,ysize,ix,iy,k->x2,k->y2,k->x3,k->y3,k->x4,k->y4,&r4,&g4,&b4); /* upper neighbor */
1013 } else {
1014 r4=r2;g4=g2;b4=b2;
1015 }
1016
1017
1018 meanr=(r1+r2+r3+r4)/4.0;
1019 varr = fabs(r1-meanr) + fabs(r2-meanr) + fabs(r3-meanr) + fabs(r4-meanr);
1020 meang = (g1+g2+g3+g4)/4.0;
1021 varg = fabs(g1-meang) + fabs(g2-meang) + fabs(g3-meang) + fabs(g4-meang);
1022 meanb = (b1+b2+b3+b4)/4.0;
1023 varb = fabs(b1-meanb) + fabs(b2-meanb) + fabs(b3-meanb) + fabs(b4-meanb);
1024 combined_var = varr*varr + varg*varg + varb*varb; /* could square root, but there is no point */
1025
1026 if (combined_var > best_variance) {
1027 best_variance = combined_var;
1028 best_x = ix;
1029 best_y = iy;
1030 }
1031 } /* for each possible position */
1032 }
1033 if (best_x == -1) { /* cannot split further */
1034 best_x = x24;
1035 best_y = y24;
1036 }
1037 else {
1038 if (flag) {
1039 fprintf(stderr,"changing 24 from %d,%d to %d,%d\n",x24,y24,best_x,best_y);
1040 }
1041 x24 = best_x;
1042 y24 = best_y;
1043 }
1044
1045 s2->x4 = best_x;
1046 s2->y4 = best_y;
1047 s4->x2 = best_x;
1048 s4->y2 = best_y;
1049 if (s2->right) {
1050 s2->right->x3 = best_x;
1051 s2->right->y3 = best_y;
1052 }
1053 if (s4->right) {
1054 s4->right->x1 = best_x;
1055 s4->right->y1 = best_y;
1056 }
1057
1058
1059
1060 return 1;
1061 }
1062
1063 #endif
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075 int find_sub_squares(unsigned char *raster,
1076 int xsize,int ysize,
1077 int percentage,
1078 int level,
1079 int top_level,
1080 struct square *s) {
1081
1082 if (level<0) level=0; /* hack */
1083 if (!level) {
1084
1085 int x1,y1,x2,y2,x3,y3,x4,y4;
1086 int cx,cy; /* the center of the 4 points */
1087 int rx1,rx2,rx3,rx4,ry1,ry2,ry3,ry4; /* range to look for the new center point */
1088 int minx,miny,maxx,maxy; /* change the quad to a square for checking */
1089 int ix,iy; /* loop control variables */
1090
1091 x1=s->x1;
1092 y1=s->y1;
1093 x2=s->x2;
1094 y2=s->y2;
1095 x3=s->x3;
1096 y3=s->y3;
1097 x4=s->x4;
1098 y4=s->y4;
1099
1100 {
1101 double r,g,b;
1102 int c=compute_average(raster,xsize,ysize,x1,y1,x2,y2,x3,y3,x4,y4,&r,&g,&b);
1103 if (c) {
1104 s->r = (int)r;
1105 s->g = (int)g;
1106 s->b = (int)b;
1107 }
1108 else {
1109 s->r = s->parent->r;
1110 s->g = s->parent->g;
1111 s->b = s->parent->b;
1112 }
1113 }
1114
1115
1116 /*
1117 printf("-stroke green -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x2,y2);
1118 printf("-stroke red -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x3,y3);
1119 printf("-stroke blue -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x3,y3,x4,y4);
1120 printf("-stroke white -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x2,y2,x4,y4);
1121 */
1122 return (squares-s);
1123 }
1124 /* OK we have 4 points in a quad. And we need to find 5 more points. We will start with the center,
1125 the center takes the longest to find. And in this case, we are going to do it linear.
1126 Could do random and get an estimate. Oh well */
1127 int x1,y1,x2,y2,x3,y3,x4,y4;
1128 int cx,cy; /* the center of the 4 points */
1129 int rx1,rx2,rx3,rx4,ry1,ry2,ry3,ry4; /* range to look for the new center point */
1130 int minx,miny,maxx,maxy; /* change the quad to a square for checking */
1131 int ix,iy; /* loop control variables */
1132
1133 x1=s->x1;
1134 y1=s->y1;
1135 x2=s->x2;
1136 y2=s->y2;
1137 x3=s->x3;
1138 y3=s->y3;
1139 x4=s->x4;
1140 y4=s->y4;
1141
1142 {
1143 double r,g,b;
1144 int c=compute_average(raster,xsize,ysize,x1,y1,x2,y2,x3,y3,x4,y4,&r,&g,&b);
1145 if (c) {
1146 s->r = (int)r;
1147 s->g = (int)g;
1148 s->b = (int)b;
1149 }
1150 else {
1151 s->r = s->parent->r;
1152 s->g = s->parent->g;
1153 s->b = s->parent->b;
1154 }
1155 }
1156
1157
1158 /* 1 2
1159 3 4
1160 */
1161 /* need to find all points that are in a percentage% average */
1162 cx = (x1+x2+x3+x4)>>2;
1163 cy = (y1+y2+y3+y4)>>2;
1164
1165 /* figure out the range to look at */
1166 rx1 = cx + ((x1-cx) * percentage) / 100;
1167 ry1 = cy + ((y1-cy)*percentage) / 100;
1168 rx2 = cx + ((x2-cx) * percentage) / 100;
1169 ry2 = cy + ((y2-cy)*percentage) / 100;
1170 rx3 = cx + ((x3-cx) * percentage) / 100;
1171 ry3 = cy + ((y3-cy)*percentage) / 100;
1172 rx4 = cx + ((x4-cx) * percentage) / 100;
1173 ry4 = cy + ((y4-cy)*percentage) / 100;
1174
1175 /* convert the quad range into a square range bigger than the quad */
1176 minx=min(min(rx1,rx2),min(rx3,rx4));
1177 miny=min(min(ry1,ry2),min(ry3,ry4));
1178
1179 maxx=max(max(rx1,rx2),max(rx3,rx4));
1180 maxy=max(max(ry1,ry2),max(ry3,ry4));
1181
1182 int x12 = (x1+x2)>>1;
1183 int x13 = (x1+x3)>>1;
1184 int x24 = (x2+x4)>>1;
1185 int x34 = (x3+x4)>>1;
1186 int y12 = (y1+y2)>>1;
1187 int y13 = (y1+y3)>>1;
1188 int y24 = (y2+y4)>>1;
1189 int y34 = (y3+y4)>>1;
1190
1191
1192
1193 find_best_intersection_main(raster,xsize,ysize,percentage,
1194 x1,y1,x2,y2,x3,y3,x4,y4,
1195 cx,cy,&cx,&cy);
1196
1197
1198
1199
1200 /* make 4 quads */
1201 struct square *s1,*s2,*s3,*s4;
1202 s1 = squares+square_count++;
1203 s2 = squares+square_count++;
1204 s3 = squares+square_count++;
1205 s4 = squares+square_count++;
1206
1207
1208 s1->parent = s;
1209 s2->parent = s;
1210 s3->parent = s;
1211 s4->parent = s;
1212
1213 s1->upper_left_sub = NULL;
1214 s1->lower_left_sub = NULL;
1215 s1->upper_right_sub = NULL;
1216 s1->lower_right_sub = NULL;
1217
1218 if ((s->above)&&(s->above->lower_left_sub)) {
1219 s1->above = s->above->lower_left_sub;
1220 s1->above->below = s1;
1221 }
1222 else
1223 s1->above = NULL;
1224 s1->below = s3;
1225 if ((s->left) && (s->left->upper_right_sub)) {
1226 s1->left = s->left->upper_right_sub;
1227 s1->left->right = s1;
1228 }
1229 else
1230 s1->left = NULL;
1231 s1->right = s2; /* figure this out later */
1232
1233
1234
1235
1236 s2->upper_left_sub = NULL;
1237 s2->lower_left_sub = NULL;
1238 s2->upper_right_sub = NULL;
1239 s2->lower_right_sub = NULL;
1240
1241 if ((s->above)&&(s->above->lower_right_sub)) {
1242 s2->above = s->above->lower_right_sub;
1243 s2->above->below = s2;
1244 }
1245 else
1246 s2->above = NULL;
1247 s2->below = s4;
1248 s2->left = s1;
1249 if ((s->right) && (s->right->upper_left_sub)) {
1250 s2->right = s->right->upper_left_sub;
1251 s2->right->left = s2;
1252 }
1253 else
1254 s2->right = NULL; /* figure this out later */
1255
1256
1257 s3->upper_left_sub = NULL;
1258 s3->lower_left_sub = NULL;
1259 s3->upper_right_sub = NULL;
1260 s3->lower_right_sub = NULL;
1261
1262 s3->above = s1;
1263 if ((s->below)&&(s->below->upper_left_sub)) {
1264 s3->below = s->below->upper_left_sub;
1265 s3->below->above = s3;
1266 }
1267 else
1268 s3->below = NULL;
1269 if ((s->left) && (s->left->lower_right_sub)) {
1270 s3->left = s->left->lower_right_sub;
1271 s3->left->right = s3;
1272 }
1273 else
1274 s3->left = NULL;
1275 s3->right = s4; /* figure this out later */
1276
1277
1278
1279 s4->upper_left_sub = NULL;
1280 s4->lower_left_sub = NULL;
1281 s4->upper_right_sub = NULL;
1282 s4->lower_right_sub = NULL;
1283 s4->above = s2;
1284 if ((s->below)&&(s->below->upper_right_sub)) {
1285 s4->below = s->below->upper_right_sub;
1286 s4->below->above = s4;
1287 }
1288 else
1289 s4->below = NULL;
1290 s4->left = s3;
1291 if ((s->right) && (s->right->lower_left_sub)) {
1292 s4->right = s->right->lower_left_sub;
1293 s4->right->left = s4;
1294 }
1295 else s4->right = NULL; /* figure this out later */
1296
1297
1298 s->upper_left_sub = s1;
1299 s->lower_left_sub = s3;
1300 s->upper_right_sub = s2;
1301 s->lower_right_sub = s4;
1302
1303 s1->x1 = x1;
1304 s1->y1 = y1;
1305 s1->x2 = x12;
1306 s1->y2 = y12;
1307 s1->x3 = x13;
1308 s1->y3 = y13;
1309 s1->x4 = cx;
1310 s1->y4 = cy;
1311
1312 s2->x1 = x12;
1313 s2->y1 = y12;
1314 s2->x2 = x2;
1315 s2->y2 = y2;
1316 s2->x3 = cx;
1317 s2->y3 = cy;
1318 s2->x4 = x24;
1319 s2->y4 = y24;
1320
1321 s3->x1 = x13;
1322 s3->y1 = y13;
1323 s3->x2 = cx;
1324 s3->y2 = cy;
1325 s3->x3 = x3;
1326 s3->y3 = y3;
1327 s3->x4 = x34;
1328 s3->y4 = y34;
1329
1330 s4->x1 = cx;
1331 s4->y1 = cy;
1332 s4->x2 = x24;
1333 s4->y2 = y24;
1334 s4->x3 = x34;
1335 s4->y3 = y34;
1336 s4->x4 = x4;
1337 s4->y4 = y4;
1338
1339
1340 /*
1341 This ha a bug between level 2 and level 3, and itl looks yucky with long streams when linemode is drawn
1342 Maybee someday we will fix the bug and then have ti look cool. But not today.
1343 find_best_intersection_points(raster,xsize,ysize,percentage,s);
1344 */
1345
1346
1347 /* OK - this level is done. Now go down a level */
1348 int ss;
1349 ss = find_sub_squares(raster,xsize,ysize,percentage,level-1,top_level,s1);
1350 find_sub_squares(raster,xsize,ysize,percentage,level-1,top_level,s2);
1351 find_sub_squares(raster,xsize,ysize,percentage,level-1,top_level,s3);
1352 find_sub_squares(raster,xsize,ysize,percentage,level-1,top_level,s4);
1353 return ss;
1354
1355 }
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371 void scale_it(struct square *s,int oldxsize,int oldysize, int newxsize, int newysize)
1372 {
1373 if (s) {
1374 scale_it(s->upper_left_sub,oldxsize,oldysize,newxsize,newysize);
1375 scale_it(s->lower_left_sub,oldxsize,oldysize,newxsize,newysize);
1376 scale_it(s->upper_right_sub,oldxsize,oldysize,newxsize,newysize);
1377 scale_it(s->lower_right_sub,oldxsize,oldysize,newxsize,newysize);
1378
1379 s->x1=s->x1 * newxsize / oldxsize;
1380 s->x2=s->x2 * newxsize / oldxsize;
1381 s->x3=s->x3 * newxsize / oldxsize;
1382 s->x4=s->x4 * newxsize / oldxsize;
1383 s->y1 = s->y1 * newysize / oldysize;
1384 s->y2 = s->y2 * newysize / oldysize;
1385 s->y3 = s->y3 * newysize / oldysize;
1386 s->y4 = s->y4 * newysize / oldysize;
1387 }
1388 }
1389
1390
1391 /* This makes the scale more accurate - because
1392 the integer math can make some points off of their centers.
1393 */
1394 void clean_scale(struct square *s)
1395 {
1396 if (s->upper_left_sub) {
1397 int x1=s->x1;
1398 int x2=s->x2;
1399 int x3=s->x3;
1400 int x4=s->x4;
1401 int y1=s->y1;
1402 int y2=s->y2;
1403 int y3=s->y3;
1404 int y4=s->y4;
1405 int x12 = (x1+x2)>>1;
1406 int x13 = (x1+x3)>>1;
1407 int x24 = (x2+x4)>>1;
1408 int x34 = (x3+x4)>>1;
1409 int y12 = (y1+y2)>>1;
1410 int y13 = (y1+y3)>>1;
1411 int y24 = (y2+y4)>>1;
1412 int y34 = (y3+y4)>>1;
1413
1414 /* redo all points except the center point, and fix the lower ones as well */
1415 s->upper_left_sub->x1 = x1;
1416 s->upper_left_sub->y1 = y1;
1417 s->upper_left_sub->x2 = x12;
1418 s->upper_left_sub->y2 = y12;
1419 s->upper_left_sub->x3 = x13;
1420 s->upper_left_sub->y3 = y13;
1421 clean_scale(s->upper_left_sub);
1422
1423 s->upper_right_sub->x1 = x12;
1424 s->upper_right_sub->y1 = y12;
1425 s->upper_right_sub->x2 = x2;
1426 s->upper_right_sub->y2 = y2;
1427 s->upper_right_sub->x4 = x24;
1428 s->upper_right_sub->y4 = y24;
1429 clean_scale(s->upper_right_sub);
1430
1431 s->lower_left_sub->x1 = x13;
1432 s->lower_left_sub->y1 = y13;
1433 s->lower_left_sub->x3 = x3;
1434 s->lower_left_sub->y3 = y3;
1435 s->lower_left_sub->x4 = x34;
1436 s->lower_left_sub->y4 = y34;
1437 clean_scale(s->lower_left_sub);
1438
1439 s->lower_right_sub->x2 = x24;
1440 s->lower_right_sub->y2 = y24;
1441 s->lower_right_sub->x3 = x34;
1442 s->lower_right_sub->y3 = y34;
1443 s->lower_right_sub->x4 = x4;
1444 s->lower_right_sub->y4 = y4;
1445 clean_scale(s->lower_right_sub);
1446 }
1447 }
1448
1449
1450
1451
1452
1453 /* This makes the scale more accurate - because
1454 the integer math can make some points off of their centers.
1455 */
1456 void set_speed(struct square *s)
1457 {
1458 compute_speed(&(s->speed),s->x1,s->y1,s->x2,s->y2,s->x3,s->y3,s->x4,s->y4);
1459 if (s->upper_left_sub) {
1460 set_speed(s->upper_left_sub);
1461 set_speed(s->upper_right_sub);
1462 set_speed(s->lower_left_sub);
1463 set_speed(s->lower_right_sub);
1464 }
1465 }
1466
1467
1468
1469
1470
1471 int draw_squares(struct square *s) {
1472 if (!s) return;
1473 int x1,y1,x2,y2,x3,y3,x4,y4;
1474 x1=s->x1;
1475 y1=s->y1;
1476 x2=s->x2;
1477 y2=s->y2;
1478 x3=s->x3;
1479 y3=s->y3;
1480 x4=s->x4;
1481 y4=s->y4;
1482
1483 if (s->upper_left_sub) {
1484 int ss;
1485
1486 printf("-stroke white -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x2,y2);
1487 printf("-stroke pink -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x3,y3);
1488 printf("-stroke orange -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x3,y3,x4,y4);
1489 printf("-stroke yellow -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x2,y2,x4,y4);
1490 ss=draw_squares(s->upper_left_sub);
1491 draw_squares(s->upper_right_sub);
1492 draw_squares(s->lower_left_sub);
1493 draw_squares(s->lower_right_sub);
1494 return ss;
1495 }
1496 else {
1497
1498 printf("-stroke green -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x2,y2);
1499 printf("-stroke red -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x1,y1,x3,y3);
1500 printf("-stroke blue -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x3,y3,x4,y4);
1501 printf("-stroke white -strokewidth 1 -draw \"line %d,%d,%d,%d\" \\\n",x2,y2,x4,y4);
1502 return (squares-s);
1503 }
1504
1505 }
1506
1507
1508 struct square *find_square(struct square *s,int x,int y) {
1509 while (s->upper_left_sub) s=s->upper_left_sub;
1510 while (x) {
1511 s=s->right;
1512 x--;
1513 }
1514 while (y) {
1515 s=s->below;
1516 y--;
1517 }
1518 return s;
1519 }
1520
1521
1522
1523 int print_square(struct square *s,int x,int y) {
1524 int minx,maxx;
1525 int miny,maxy;
1526 if (!s) {
1527 fprintf(stderr,"no square at %d,%d\n",x,y);
1528 return;
1529 }
1530 minx=s->x1;
1531 maxx=s->x1;
1532 miny=s->y1;
1533 maxy=s->y1;
1534 if (s->x2<minx) minx=s->x2;
1535 if (s->x2>maxx) maxx=s->x2;
1536 if (s->y2<miny) miny=s->y2;
1537 if (s->y2>maxy) maxy=s->y2;
1538 if (s->x3<minx) minx=s->x3;
1539 if (s->x3>maxx) maxx=s->x3;
1540 if (s->y3<miny) miny=s->y3;
1541 if (s->y3>maxy) maxy=s->y3;
1542 if (s->x4<minx) minx=s->x4;
1543 if (s->x4>maxx) maxx=s->x4;
1544 if (s->y4<miny) miny=s->y4;
1545 if (s->y4>maxy) maxy=s->y4;
1546
1547 int x1,y1,x2,y2,x3,y3,x4,y4;
1548 int width,height;
1549 width=maxx-minx;
1550 height=maxy-miny;
1551 x1=s->x1-minx;
1552 x2=s->x2-minx;
1553 x3=s->x3-minx;
1554 x4=s->x4-minx;
1555 y1=s->y1-miny;
1556 y2=s->y2-miny;
1557 y3=s->y3-miny;
1558 y4=s->y4-miny;
1559 printf("%3.3d|%3.3d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d|%d\n",
1560 x,y,s->x1,s->y1,s->x3,s->y3,s->x2,s->y2,s->x4,s->y4,s->r,s->g,s->b,
1561 x1,y1,x3,y3,x2,y2,x4,y4,minx,miny,width,height);
1562 /*
1563 0 1 X
1564 1 2 Y
1565 2 3 top left x - in real coordinates
1566 3 4 top left y - in real coordinates
1567 4 5 Top right x - in real coordinates
1568 5 6 top right y - in real coodrindates
1569 6 7 bottom left x - in real coordinates
1570 7 8 bottom left y - in real coordinates
1571 8 9 bottom right x - in real coordinates
1572 9 10 bottom right y - in real coordinates
1573 10 11 R color - 0-255
1574 11 12 g color - 0-255
1575 12 13 b color - 0-255
1576 13 14 top left x - in local coordinates
1577 14 15 top left y - in local coordinates
1578 15 16 top right x - in local coordiantes
1579 16 17 top right y - in local coordinates
1580 17 18 bottom left x - in local coordinates
1581 18 19 bottom left y - in local coordinates
1582 19 20 bottom right x - in local coordinates
1583 20 21 bottom right y - in local coodinates
1584 21 22 x offset to place the local to global
1585 22 23 y offset ...
1586 23 24 wisth
1587 24 25 height
1588 */
1589 }
1590
1591
1592 /* usage tilify xsize ysize seed basefile */
1593 int main (int argc,char *argv[]) {
1594 char *basefile; /* base.txt by convention */
1595 int xsize;
1596 int ysize;
1597 int degree;
1598 int levels;
1599 if (argc==6) {
1600 xsize=atoi(argv[1]);
1601 ysize=atoi(argv[2]);
1602 degree=atoi(argv[3]);
1603 levels=atoi(argv[4]);
1604 basefile=argv[5];
1605 }
1606 else {
1607 fprintf(stderr,"usage tilify xsize ysize degree levels basefile\n"
1608 "Where file has x|y|r|g|b text format\n"
1609 "oh and degree is hard coded to be percentage and levels is hard coded to 5 at the moment\n");
1610 exit(-1);
1611 }
1612 if (levels<1) levels=1;
1613 if (degree<1) degree=30;
1614 FILE *base;
1615 base = fopen(basefile,"r");
1616 char basebuf[10001];
1617 char otherbuf[10001];
1618 char alphabuf[10001];
1619 char hologrambuf[10001];
1620 unsigned char *a = (unsigned char *)malloc(sizeof(unsigned char)*3*xsize*ysize);
1621
1622
1623 fprintf(stderr,"reading\n");
1624 fprintf(stderr,"some inside %d",
1625 some_inside(5568,1,5568,0,5692,0,5456,58,5647,58)
1626 );
1627
1628
1629 while (fgets(basebuf,10000,base)) {
1630 char *q;
1631 int xb,yb,rb,gb,bb;
1632 int xo,yo,ro,go,bo;
1633 int xa,ya,ra,ga,ba;
1634 int hb;
1635 xb = fieldi(basebuf,0);
1636 yb = fieldi(basebuf,1);
1637 rb = fieldi(basebuf,2);
1638 gb = fieldi(basebuf,3);
1639 bb = fieldi(basebuf,4);
1640 int loc= (yb*xsize+xb);
1641 loc = loc+loc+loc;
1642 a[loc++] = rb;
1643 a[loc++] = gb;
1644 a[loc++] = bb;
1645 }
1646
1647
1648 /* for each level, we know 4 points, and need to find 5 points more. */
1649 square_count++;
1650 struct square *top_square = squares;
1651 top_square->x1 = 0;
1652 top_square->y1 = 0;
1653 top_square->x2 = xsize;
1654 top_square->y2 = 0;
1655 top_square->x3 = 0;
1656 top_square->y3 = ysize;
1657 top_square->x4 = xsize;
1658 top_square->y4 = ysize;
1659 top_square->upper_left_sub = NULL;
1660 top_square->lower_left_sub = NULL;
1661 top_square->upper_right_sub = NULL;
1662 top_square->lower_right_sub = NULL;
1663 top_square->above = NULL;
1664 top_square->below = NULL;
1665 top_square->left = NULL;
1666 top_square->right = NULL;
1667
1668 fprintf(stderr,"find sub squares\n");
1669 int start_square;
1670 //printf("convert source.png -size 550x780 \\\n");
1671 start_square = find_sub_squares(a,xsize,ysize,degree,levels,levels,top_square);
1672
1673 fprintf(stderr,"scaling\n");
1674
1675 #ifdef SCALE
1676 scale_it(top_square,xsize,ysize,30000,30000);
1677 //scale_it(top_square,xsize,ysize,24016,17920);
1678 //scale_it(top_square,xsize,ysize,20880,27840);
1679 //scale_it(top_square,xsize,ysize,20880,27840);
1680 //scale_it(top_square,xsize,ysize,6600,8800);
1681 //scale_it(top_square,xsize,ysize,63360,84480);
1682 //scale_it(top_square,xsize,ysize,63360,84480); /* for kristie*/
1683 /* OK things are scaled, but because of the inaccuracy of ints, the mid points are
1684 kinda screwed up. So we will clean them up
1685 This is only useful if the midpoints don't float, and currently they don't
1686 */
1687 clean_scale(top_square);
1688 /* scale */
1689 xsize = 30000;
1690 ysize = 30000;
1691 #endif
1692 set_speed(top_square);
1693
1694 {
1695 int x,y;
1696 for (y=0;y<16;y++) {
1697 for (x=0;x<16;x++) {
1698 print_square(find_square(top_square,x,y),x,y);
1699 }
1700 }
1701 }
1702
1703 /*printf("# ImageMagick pixel enumeration: %d,%d,255,rgb\n",xsize,ysize);*/
1704
1705 exit(0);
1706 }
1707
1708
1709
1710
1711

  ViewVC Help
Powered by ViewVC 1.1.5