00001
00020 #include "mfcpch.h"
00021 #include <stdio.h>
00022 #ifdef __UNIX__
00023 #include <assert.h>
00024 #endif
00025
00026 #define MAXEDGELENGTH 16000 //must replace
00027 #include "polyaprx.h"
00028 #include "varable.h"
00029 #include "tprintf.h"
00030
00031 #define EXTERN
00032
00035 EXTERN BOOL_VAR (poly_debug, FALSE, "Debug old poly");
00036 EXTERN BOOL_VAR (poly_wide_objects_better, TRUE,
00037 "More accurate approx on wide things");
00040 static int par1, par2;
00041
00042 #define CONVEX 1
00043 #define CONCAVE 2
00044 #define FIXED 4
00045 #define ONHULL 8
00046
00047 #define RUNLENGTH 1
00048
00049 #define DIR 2
00050
00051 #define CORRECTION 3
00052
00053 #define FLAGS 0
00054
00055 #define fixed_dist 20 //really an int_variable
00056 #define approx_dist 15 //really an int_variable
00057
00058 #define point_diff(p,p1,p2) (p).x = (p1).x - (p2).x ; (p).y = (p1).y - (p2).y
00059 #define CROSS(a,b) ((a).x * (b).y - (a).y * (b).x)
00060 #define LENGTH(a) ((a).x * (a).x + (a).y * (a).y)
00061
00062 #define DISTANCE(a,b) (((b).x-(a).x) * ((b).x-(a).x) \
00063 + ((b).y-(a).y) * ((b).y-(a).y))
00064
00070 OUTLINE *tesspoly_outline(
00071 C_OUTLINE *c_outline,
00072 float
00073 ) {
00074 EDGEPT *edgept;
00075 EDGEPT *startpt;
00076 BOX loop_box;
00077 INT32 area;
00078 FCOORD pos;
00079 FCOORD vec;
00080 POLYPT_LIST polypts;
00081 POLYPT *polypt;
00082 POLYPT_IT poly_it = &polypts;
00083 EDGEPT edgepts[MAXEDGELENGTH];
00084
00085 loop_box = c_outline->bounding_box ();
00086 area = loop_box.height ();
00087 if (!poly_wide_objects_better && loop_box.width () > area)
00088 area = loop_box.width ();
00089 area *= area;
00090 edgept = edgesteps_to_edgepts (c_outline, edgepts);
00091 fix2(edgepts, area);
00092 edgept = poly2 (edgepts, area);
00093 startpt = edgept;
00094 do {
00095 pos = FCOORD (edgept->pos.x, edgept->pos.y);
00096 vec = FCOORD (edgept->vec.x, edgept->vec.y);
00097 polypt = new POLYPT (pos, vec);
00098
00099 poly_it.add_after_then_move (polypt);
00100 edgept = edgept->next;
00101 }
00102 while (edgept != startpt);
00103 if (poly_it.length () <= 2)
00104 return NULL;
00105 else
00106
00107 return new OUTLINE (&poly_it);
00108 }
00109
00110
00114 EDGEPT *
00115 edgesteps_to_edgepts (
00116 C_OUTLINE * c_outline,
00117 EDGEPT edgepts[]
00118 ) {
00119 INT32 length;
00120 ICOORD pos;
00121 INT32 stepindex;
00122 INT32 stepinc;
00123 INT32 epindex;
00124 INT32 count;
00125 ICOORD vec;
00126 ICOORD prev_vec;
00127 INT8 epdir;
00128 DIR128 prevdir;
00129 DIR128 dir;
00130
00131 pos = c_outline->start_pos ();
00132 length = c_outline->pathlength ();
00133 stepindex = 0;
00134 epindex = 0;
00135 prevdir = -1;
00136 count = 0;
00137 do {
00138 dir = c_outline->step_dir (stepindex);
00139 vec = c_outline->step (stepindex);
00140 if (stepindex < length - 1
00141 && c_outline->step_dir (stepindex + 1) - dir == -32) {
00142 dir += 128 - 16;
00143 vec += c_outline->step (stepindex + 1);
00144 stepinc = 2;
00145 }
00146 else
00147 stepinc = 1;
00148 if (count == 0) {
00149 prevdir = dir;
00150 prev_vec = vec;
00151 }
00152 if (prevdir.get_dir () != dir.get_dir ()) {
00153 edgepts[epindex].pos.x = pos.x ();
00154 edgepts[epindex].pos.y = pos.y ();
00155 prev_vec *= count;
00156 edgepts[epindex].vec.x = prev_vec.x ();
00157 edgepts[epindex].vec.y = prev_vec.y ();
00158 pos += prev_vec;
00159 edgepts[epindex].flags[RUNLENGTH] = count;
00160 edgepts[epindex].prev = &edgepts[epindex - 1];
00161 edgepts[epindex].flags[FLAGS] = 0;
00162 edgepts[epindex].next = &edgepts[epindex + 1];
00163 prevdir += 64;
00164 epdir = (DIR128) 0 - prevdir;
00165 epdir >>= 4;
00166 epdir &= 7;
00167 edgepts[epindex].flags[DIR] = epdir;
00168 epindex++;
00169 prevdir = dir;
00170 prev_vec = vec;
00171 count = 1;
00172 }
00173 else
00174 count++;
00175 stepindex += stepinc;
00176 }
00177 while (stepindex < length);
00178 edgepts[epindex].pos.x = pos.x ();
00179 edgepts[epindex].pos.y = pos.y ();
00180 prev_vec *= count;
00181 edgepts[epindex].vec.x = prev_vec.x ();
00182 edgepts[epindex].vec.y = prev_vec.y ();
00183 pos += prev_vec;
00184 edgepts[epindex].flags[RUNLENGTH] = count;
00185 edgepts[epindex].flags[FLAGS] = 0;
00186 edgepts[epindex].prev = &edgepts[epindex - 1];
00187 edgepts[epindex].next = &edgepts[0];
00188 prevdir += 64;
00189 epdir = (DIR128) 0 - prevdir;
00190 epdir >>= 4;
00191 epdir &= 7;
00192 edgepts[epindex].flags[DIR] = epdir;
00193 edgepts[0].prev = &edgepts[epindex];
00194 ASSERT_HOST (pos.x () == c_outline->start_pos ().x ()
00195 && pos.y () == c_outline->start_pos ().y ());
00196 return &edgepts[0];
00197 }
00198
00199
00200
00201
00202
00208 void fix2(
00209 EDGEPT *start,
00210 int area) {
00211 register EDGEPT *edgept;
00212 register EDGEPT *edgept1;
00213 register EDGEPT *loopstart;
00214 register EDGEPT *linestart;
00215 register int dir1, dir2;
00216 register int sum1, sum2;
00217 int stopped;
00218 int fixed_count;
00219 int d01, d12, d23, gapmin;
00220 TPOINT d01vec, d12vec, d23vec;
00221 register EDGEPT *edgefix, *startfix;
00222 register EDGEPT *edgefix0, *edgefix1, *edgefix2, *edgefix3;
00223
00224 edgept = start;
00225 while ((edgept->flags[DIR] - edgept->prev->flags[DIR] + 1 & 7) < 3
00226 && (dir1 =
00227 edgept->prev->flags[DIR] - edgept->next->flags[DIR] & 7) != 2
00228 && dir1 != 6)
00229 edgept = edgept->next;
00230 loopstart = edgept;
00231
00232 stopped = 0;
00233 edgept->flags[FLAGS] |= FIXED;
00234 do {
00235 linestart = edgept;
00236 dir1 = edgept->flags[DIR];
00237
00238 sum1 = edgept->flags[RUNLENGTH];
00239 edgept = edgept->next;
00240 dir2 = edgept->flags[DIR];
00241
00242 sum2 = edgept->flags[RUNLENGTH];
00243 if ((dir1 - dir2 + 1 & 7) < 3) {
00244 while (edgept->prev->flags[DIR] == edgept->next->flags[DIR]) {
00245 edgept = edgept->next;
00246 if (edgept->flags[DIR] == dir1)
00247
00248 sum1 += edgept->flags[RUNLENGTH];
00249 else
00250 sum2 += edgept->flags[RUNLENGTH];
00251 }
00252
00253 if (edgept == loopstart)
00254 stopped = 1;
00255 if (sum2 + sum1 > 2
00256 && linestart->prev->flags[DIR] == dir2
00257 && (linestart->prev->flags[RUNLENGTH] >
00258 linestart->flags[RUNLENGTH] || sum2 > sum1)) {
00259
00260 linestart = linestart->prev;
00261 linestart->flags[FLAGS] |= FIXED;
00262 }
00263
00264 if ((edgept->next->flags[DIR] - edgept->flags[DIR] + 1 & 7) >= 3
00265 || edgept->flags[DIR] == dir1 && sum1 >= sum2
00266 || (edgept->prev->flags[RUNLENGTH] < edgept->flags[RUNLENGTH]
00267 || edgept->flags[DIR] == dir2 && sum2 >= sum1)
00268 && linestart->next != edgept)
00269 edgept = edgept->next;
00270 }
00271
00272 edgept->flags[FLAGS] |= FIXED;
00273 }
00274
00275 while (edgept != loopstart && !stopped);
00276
00277 edgept = start;
00278 do {
00279 if (((edgept->flags[RUNLENGTH] >= 8) &&
00280 (edgept->flags[DIR] != 2) && (edgept->flags[DIR] != 6)) ||
00281 ((edgept->flags[RUNLENGTH] >= 8) &&
00282 ((edgept->flags[DIR] == 2) || (edgept->flags[DIR] == 6)))) {
00283 edgept->flags[FLAGS] |= FIXED;
00284 edgept1 = edgept->next;
00285 edgept1->flags[FLAGS] |= FIXED;
00286 }
00287 edgept = edgept->next;
00288 }
00289 while (edgept != start);
00290
00291 edgept = start;
00292 do {
00293
00294 if (edgept->flags[FLAGS] & FIXED && edgept->flags[RUNLENGTH] == 1
00295
00296 && edgept->next->flags[FLAGS] & FIXED && (edgept->prev->flags[FLAGS] & FIXED) == 0
00297
00298 && (edgept->next->next->flags[FLAGS] & FIXED) == 0 && edgept->prev->flags[DIR] == edgept->next->flags[DIR] && edgept->prev->prev->flags[DIR] == edgept->next->next->flags[DIR]
00299 && (edgept->prev->flags[DIR] - edgept->flags[DIR] + 1 & 7) < 3) {
00300
00301 edgept->flags[FLAGS] &= ~FIXED;
00302 edgept->next->flags[FLAGS] &= ~FIXED;
00303 }
00304 edgept = edgept->next;
00305 }
00306 while (edgept != start);
00307
00308 stopped = 0;
00309 if (area < 450)
00310 area = 450;
00311
00312 gapmin = area * fixed_dist * fixed_dist / 44000;
00313
00314 edgept = start;
00315 fixed_count = 0;
00316 do {
00317 if (edgept->flags[FLAGS] & FIXED)
00318 fixed_count++;
00319 edgept = edgept->next;
00320 }
00321 while (edgept != start);
00322 while ((edgept->flags[FLAGS] & FIXED) == 0)
00323 edgept = edgept->next;
00324 edgefix0 = edgept;
00325
00326 edgept = edgept->next;
00327 while ((edgept->flags[FLAGS] & FIXED) == 0)
00328 edgept = edgept->next;
00329 edgefix1 = edgept;
00330
00331 edgept = edgept->next;
00332 while ((edgept->flags[FLAGS] & FIXED) == 0)
00333 edgept = edgept->next;
00334 edgefix2 = edgept;
00335
00336 edgept = edgept->next;
00337 while ((edgept->flags[FLAGS] & FIXED) == 0)
00338 edgept = edgept->next;
00339 edgefix3 = edgept;
00340
00341 startfix = edgefix2;
00342
00343 do {
00344 if (fixed_count <= 3)
00345 break;
00346 point_diff (d12vec, edgefix1->pos, edgefix2->pos);
00347 d12 = LENGTH (d12vec);
00348 if (d12 <= gapmin) {
00349 point_diff (d01vec, edgefix0->pos, edgefix1->pos);
00350 d01 = LENGTH (d01vec);
00351 point_diff (d23vec, edgefix2->pos, edgefix3->pos);
00352 d23 = LENGTH (d23vec);
00353 if (d01 > d23) {
00354 edgefix2->flags[FLAGS] &= ~FIXED;
00355 fixed_count--;
00356
00357
00358
00359 }
00360 else {
00361 edgefix1->flags[FLAGS] &= ~FIXED;
00362 fixed_count--;
00363
00364
00365
00366 edgefix1 = edgefix2;
00367 }
00368 }
00369 else {
00370 edgefix0 = edgefix1;
00371 edgefix1 = edgefix2;
00372 }
00373 edgefix2 = edgefix3;
00374 edgept = edgept->next;
00375 while ((edgept->flags[FLAGS] & FIXED) == 0) {
00376 if (edgept == startfix)
00377 stopped = 1;
00378 edgept = edgept->next;
00379 }
00380 edgefix3 = edgept;
00381 edgefix = edgefix2;
00382 }
00383 while ((edgefix != startfix) && (!stopped));
00384 }
00385
00386
00387
00388
00395 EDGEPT *poly2(
00396 EDGEPT *startpt,
00397 int area
00398 ) {
00399 register EDGEPT *edgept;
00400 EDGEPT *loopstart;
00401 register EDGEPT *linestart;
00402 register int edgesum;
00403
00404 if (area < 1200)
00405 area = 1200;
00406
00407
00408 par1 = 4500 / (approx_dist * approx_dist);
00409
00410 par2 = 6750 / (approx_dist * approx_dist);
00411
00412 loopstart = NULL;
00413 edgept = startpt;
00414
00415 do {
00416
00417 if (edgept->flags[FLAGS] & FIXED
00418
00419 && (edgept->next->flags[FLAGS] & FIXED) == 0) {
00420 loopstart = edgept;
00421 break;
00422 }
00423 edgept = edgept->next;
00424 }
00425 while (edgept != startpt);
00426
00427 if (loopstart == NULL && (startpt->flags[FLAGS] & FIXED) == 0) {
00428
00429 startpt->flags[FLAGS] |= FIXED;
00430 loopstart = startpt;
00431 }
00432 if (loopstart) {
00433 do {
00434 edgept = loopstart;
00435 do {
00436 linestart = edgept;
00437 edgesum = 0;
00438 do {
00439
00440 edgesum += edgept->flags[RUNLENGTH];
00441 edgept = edgept->next;
00442 }
00443 while ((edgept->flags[FLAGS] & FIXED) == 0
00444 && edgept != loopstart && edgesum < 126);
00445 if (poly_debug)
00446 tprintf
00447 ("Poly2:starting at (%d,%d)+%d=(%d,%d),%d to (%d,%d)\n",
00448 linestart->pos.x, linestart->pos.y, linestart->flags[DIR],
00449 linestart->vec.x, linestart->vec.y, edgesum, edgept->pos.x,
00450 edgept->pos.y);
00451
00452 cutline(linestart, edgept, area);
00453
00454 while ((edgept->next->flags[FLAGS] & FIXED)
00455 && edgept != loopstart)
00456 edgept = edgept->next;
00457 }
00458
00459 while (edgept != loopstart);
00460 edgesum = 0;
00461 do {
00462 if (edgept->flags[FLAGS] & FIXED)
00463 edgesum++;
00464 edgept = edgept->next;
00465 }
00466
00467 while (edgept != loopstart);
00468 if (edgesum < 3)
00469 area /= 2;
00470 }
00471 while (edgesum < 3);
00472 do {
00473 linestart = edgept;
00474 do {
00475 edgept = edgept->next;
00476 }
00477 while ((edgept->flags[FLAGS] & FIXED) == 0);
00478 linestart->next = edgept;
00479 edgept->prev = linestart;
00480 linestart->vec.x = edgept->pos.x - linestart->pos.x;
00481 linestart->vec.y = edgept->pos.y - linestart->pos.y;
00482 }
00483 while (edgept != loopstart);
00484 }
00485 else
00486 edgept = startpt;
00487
00488 loopstart = edgept;
00489 return loopstart;
00490 }
00491
00492
00496 void cutline(
00497 EDGEPT *first,
00498 EDGEPT *last,
00499 int area
00500 ) {
00501 register EDGEPT *edge;
00502 TPOINT vecsum;
00503 int vlen;
00504 TPOINT vec;
00505 EDGEPT *maxpoint;
00506 int maxperp;
00507 register int perp;
00508 int ptcount;
00509 int squaresum;
00510
00511 edge = first;
00512 if (edge->next == last)
00513 return;
00514
00515
00516 vecsum.x = last->pos.x - edge->pos.x;
00517 vecsum.y = last->pos.y - edge->pos.y;
00518 if (vecsum.x == 0 && vecsum.y == 0) {
00519
00520 vecsum.x = -edge->prev->vec.x;
00521 vecsum.y = -edge->prev->vec.y;
00522 }
00523
00524 vlen = vecsum.x > 0 ? vecsum.x : -vecsum.x;
00525 if (vecsum.y > vlen)
00526 vlen = vecsum.y;
00527 else if (-vecsum.y > vlen)
00528 vlen = -vecsum.y;
00529
00530 vec.x = edge->vec.x;
00531 vec.y = edge->vec.y;
00532 maxperp = 0;
00533 squaresum = ptcount = 0;
00534 edge = edge->next;
00535 maxpoint = edge;
00536 do {
00537 perp = CROSS (vec, vecsum);
00538 if (perp != 0) {
00539 perp *= perp;
00540 }
00541 squaresum += perp;
00542 ptcount++;
00543 if (poly_debug)
00544 tprintf ("Cutline:Final perp=%d\n", perp);
00545 if (perp > maxperp) {
00546 maxperp = perp;
00547 maxpoint = edge;
00548 }
00549 vec.x += edge->vec.x;
00550 vec.y += edge->vec.y;
00551 edge = edge->next;
00552 }
00553 while (edge != last);
00554
00555 perp = LENGTH (vecsum);
00556 ASSERT_HOST (perp != 0);
00557
00558 if (maxperp < 256 * MAX_INT16) {
00559 maxperp <<= 8;
00560 maxperp /= perp;
00561 }
00562 else {
00563 maxperp /= perp;
00564 maxperp <<= 8;
00565 }
00566 if (squaresum < 256 * MAX_INT16)
00567
00568 perp = (squaresum << 8) / (perp * ptcount);
00569 else
00570
00571 perp = (squaresum / perp << 8) / ptcount;
00572
00573 if (poly_debug)
00574 tprintf ("Cutline:A=%d, max=%.2f(%.2f%%), msd=%.2f(%.2f%%)\n",
00575 area, maxperp / 256.0, maxperp * 200.0 / area,
00576 perp / 256.0, perp * 300.0 / area);
00577 if (maxperp * par1 >= 10 * area || perp * par2 >= 10 * area || vlen >= 126) {
00578 maxpoint->flags[FLAGS] |= FIXED;
00579
00580 cutline(first, maxpoint, area);
00581 cutline(maxpoint, last, area);
00582 }
00583 }