#include "tessclas.h"
#include "poutline.h"
#include "coutln.h"
Go to the source code of this file.
#define CROSS | ( | a, | |||
b | ) | ((a).x * (b).y - (a).y * (b).x) |
Definition at line 50 of file polyaprx.h.
#define fixed_dist 20 |
#define LENGTH | ( | a | ) | ((a).x * (a).x + (a).y * (a).y) |
Definition at line 51 of file polyaprx.h.
#define point_diff | ( | p, | |||
p1, | |||||
p2 | ) | (p).x = (p1).x - (p2).x ; (p).y = (p1).y - (p2).y |
Definition at line 49 of file polyaprx.h.
Straightens out a line by partitioning and joining the ends by a straight line
Definition at line 496 of file polyaprx.cpp.
References ASSERT_HOST, CROSS, cutline(), first, FIXED, FLAGS, edgeptstruct::flags, last(), LENGTH, MAX_INT16, edgeptstruct::next, par1, par2, edgeptstruct::pos, edgeptstruct::prev, tprintf(), edgeptstruct::vec, TPOINT::x, and TPOINT::y.
Referenced by cutline(), and poly2().
00500 { 00501 register EDGEPT *edge; /*current edge */ 00502 TPOINT vecsum; /*vector sum */ 00503 int vlen; /*approx length of vecsum */ 00504 TPOINT vec; /*accumulated vector */ 00505 EDGEPT *maxpoint; /*worst point */ 00506 int maxperp; /*max deviation */ 00507 register int perp; /*perp distance */ 00508 int ptcount; /*no of points */ 00509 int squaresum; /*sum of perps */ 00510 00511 edge = first; /*start of line */ 00512 if (edge->next == last) 00513 return; /*simple line */ 00514 00515 /*vector sum */ 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 /*special case */ 00520 vecsum.x = -edge->prev->vec.x; 00521 vecsum.y = -edge->prev->vec.y; 00522 } 00523 /*absolute value */ 00524 vlen = vecsum.x > 0 ? vecsum.x : -vecsum.x; 00525 if (vecsum.y > vlen) 00526 vlen = vecsum.y; /*maximum */ 00527 else if (-vecsum.y > vlen) 00528 vlen = -vecsum.y; /*absolute value */ 00529 00530 vec.x = edge->vec.x; /*accumulated vector */ 00531 vec.y = edge->vec.y; 00532 maxperp = 0; /*none yet */ 00533 squaresum = ptcount = 0; 00534 edge = edge->next; /*move to actual point */ 00535 maxpoint = edge; /*in case there isn't one */ 00536 do { 00537 perp = CROSS (vec, vecsum); /*get perp distance */ 00538 if (perp != 0) { 00539 perp *= perp; /*squared deviation */ 00540 } 00541 squaresum += perp; /*sum squares */ 00542 ptcount++; /*count points */ 00543 if (poly_debug) 00544 tprintf ("Cutline:Final perp=%d\n", perp); 00545 if (perp > maxperp) { 00546 maxperp = perp; 00547 maxpoint = edge; /*find greatest deviation */ 00548 } 00549 vec.x += edge->vec.x; /*accumulate vectors */ 00550 vec.y += edge->vec.y; 00551 edge = edge->next; 00552 } 00553 while (edge != last); /*test all line */ 00554 00555 perp = LENGTH (vecsum); 00556 ASSERT_HOST (perp != 0); 00557 00558 if (maxperp < 256 * MAX_INT16) { 00559 maxperp <<= 8; 00560 maxperp /= perp; /*true max perp */ 00561 } 00562 else { 00563 maxperp /= perp; 00564 maxperp <<= 8; /*avoid overflow */ 00565 } 00566 if (squaresum < 256 * MAX_INT16) 00567 /*mean squared perp */ 00568 perp = (squaresum << 8) / (perp * ptcount); 00569 else 00570 /*avoid overflow */ 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 /*partitions */ 00580 cutline(first, maxpoint, area); 00581 cutline(maxpoint, last, area); 00582 } 00583 }
Convert a C_OUTLINE to EDGEPTs.
Definition at line 115 of file polyaprx.cpp.
References ASSERT_HOST, count(), DIR, FLAGS, edgeptstruct::flags, DIR128::get_dir(), edgeptstruct::next, edgeptstruct::pos, edgeptstruct::prev, RUNLENGTH, edgeptstruct::vec, TPOINT::x, ICOORD::y(), and TPOINT::y.
Referenced by tesspoly_outline().
00118 { 00119 INT32 length; //steps in path 00120 ICOORD pos; //current coords 00121 INT32 stepindex; //current step 00122 INT32 stepinc; //increment 00123 INT32 epindex; //current EDGEPT 00124 INT32 count; //repeated steps 00125 ICOORD vec; //for this 8 step 00126 ICOORD prev_vec; 00127 INT8 epdir; //of this step 00128 DIR128 prevdir; //prvious dir 00129 DIR128 dir; //of this step 00130 00131 pos = c_outline->start_pos (); //start of loop 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 }
void fix2 | ( | EDGEPT * | start, | |
int | area | |||
) |
Polygonal approximation
Fixes points on the outline according to a trial method
Definition at line 208 of file polyaprx.cpp.
References DIR, FIXED, fixed_dist, FLAGS, edgeptstruct::flags, LENGTH, edgeptstruct::next, point_diff, edgeptstruct::pos, edgeptstruct::prev, and RUNLENGTH.
Referenced by tesspoly_outline().
00210 { 00211 register EDGEPT *edgept; /*current point */ 00212 register EDGEPT *edgept1; 00213 register EDGEPT *loopstart; /*modified start of loop */ 00214 register EDGEPT *linestart; /*start of line segment */ 00215 register int dir1, dir2; /*directions of line */ 00216 register int sum1, sum2; /*lengths in dir1,dir2 */ 00217 int stopped; /*completed flag */ 00218 int fixed_count; //no of fixed points 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; /*start of loop */ 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; /*find suitable start */ 00230 loopstart = edgept; /*remember start */ 00231 00232 stopped = 0; /*not finished yet */ 00233 edgept->flags[FLAGS] |= FIXED; /*fix it */ 00234 do { 00235 linestart = edgept; /*possible start of line */ 00236 dir1 = edgept->flags[DIR]; /*first direction */ 00237 /*length of dir1 */ 00238 sum1 = edgept->flags[RUNLENGTH]; 00239 edgept = edgept->next; 00240 dir2 = edgept->flags[DIR]; /*2nd direction */ 00241 /*length in dir2 */ 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; /*look at next */ 00246 if (edgept->flags[DIR] == dir1) 00247 /*sum lengths */ 00248 sum1 += edgept->flags[RUNLENGTH]; 00249 else 00250 sum2 += edgept->flags[RUNLENGTH]; 00251 } 00252 00253 if (edgept == loopstart) 00254 stopped = 1; /*finished */ 00255 if (sum2 + sum1 > 2 00256 && linestart->prev->flags[DIR] == dir2 00257 && (linestart->prev->flags[RUNLENGTH] > 00258 linestart->flags[RUNLENGTH] || sum2 > sum1)) { 00259 /*start is back one */ 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 /*sharp bend */ 00272 edgept->flags[FLAGS] |= FIXED; 00273 } 00274 /*do whole loop */ 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 /*single fixed step */ 00294 if (edgept->flags[FLAGS] & FIXED && edgept->flags[RUNLENGTH] == 1 00295 /*and neighours free */ 00296 && edgept->next->flags[FLAGS] & FIXED && (edgept->prev->flags[FLAGS] & FIXED) == 0 00297 /*same pair of dirs */ 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 /*unfix it */ 00301 edgept->flags[FLAGS] &= ~FIXED; 00302 edgept->next->flags[FLAGS] &= ~FIXED; 00303 } 00304 edgept = edgept->next; /*do all points */ 00305 } 00306 while (edgept != start); /*until finished */ 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; //already too few 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 /* if ( plots[EDGE] & PATHS ) 00357 mark(edgefd,edgefix2->pos.x,edgefix2->pos.y,PLUS); 00358 */ 00359 } 00360 else { 00361 edgefix1->flags[FLAGS] &= ~FIXED; 00362 fixed_count--; 00363 /* if ( plots[EDGE] & PATHS ) 00364 mark(edgefd,edgefix1->pos.x,edgefix1->pos.y,PLUS); 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 }
Second poly
Applies a second approximation to the outline using the points which have been fixed by the first approximation
Definition at line 395 of file polyaprx.cpp.
References approx_dist, cutline(), DIR, FIXED, FLAGS, edgeptstruct::flags, edgeptstruct::next, NULL, par1, par2, edgeptstruct::pos, edgeptstruct::prev, RUNLENGTH, tprintf(), edgeptstruct::vec, TPOINT::x, and TPOINT::y.
Referenced by tesspoly_outline().
00398 { 00399 register EDGEPT *edgept; /*current outline point */ 00400 EDGEPT *loopstart; /*starting point */ 00401 register EDGEPT *linestart; /*start of line */ 00402 register int edgesum; /*correction count */ 00403 00404 if (area < 1200) 00405 area = 1200; /*minimum value */ 00406 00407 /*1200(4) */ 00408 par1 = 4500 / (approx_dist * approx_dist); 00409 /*1200(6) */ 00410 par2 = 6750 / (approx_dist * approx_dist); 00411 00412 loopstart = NULL; /*not found it yet */ 00413 edgept = startpt; /*start of loop */ 00414 00415 do { 00416 /*current point fixed */ 00417 if (edgept->flags[FLAGS] & FIXED 00418 /*and next not */ 00419 && (edgept->next->flags[FLAGS] & FIXED) == 0) { 00420 loopstart = edgept; /*start of repoly */ 00421 break; 00422 } 00423 edgept = edgept->next; /*next point */ 00424 } 00425 while (edgept != startpt); /*until found or finished */ 00426 00427 if (loopstart == NULL && (startpt->flags[FLAGS] & FIXED) == 0) { 00428 /*fixed start of loop */ 00429 startpt->flags[FLAGS] |= FIXED; 00430 loopstart = startpt; /*or start of loop */ 00431 } 00432 if (loopstart) { 00433 do { 00434 edgept = loopstart; /*first to do */ 00435 do { 00436 linestart = edgept; 00437 edgesum = 0; /*sum of lengths */ 00438 do { 00439 /*sum lengths */ 00440 edgesum += edgept->flags[RUNLENGTH]; 00441 edgept = edgept->next; /*move on */ 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 /*reapproximate */ 00452 cutline(linestart, edgept, area); 00453 00454 while ((edgept->next->flags[FLAGS] & FIXED) 00455 && edgept != loopstart) 00456 edgept = edgept->next; /*look for next non-fixed */ 00457 } 00458 /*do all the loop */ 00459 while (edgept != loopstart); 00460 edgesum = 0; 00461 do { 00462 if (edgept->flags[FLAGS] & FIXED) 00463 edgesum++; 00464 edgept = edgept->next; 00465 } 00466 //count fixed pts 00467 while (edgept != loopstart); 00468 if (edgesum < 3) 00469 area /= 2; //must have 3 pts 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; /*start of loop */ 00487 00488 loopstart = edgept; /*new start */ 00489 return loopstart; /*correct exit */ 00490 }
Old approximation
Approximate an outline from c form using the old tess algorithm.
Definition at line 70 of file polyaprx.cpp.
References edgesteps_to_edgepts(), fix2(), BOX::height(), MAXEDGELENGTH, edgeptstruct::next, NULL, poly2(), edgeptstruct::pos, edgeptstruct::vec, BOX::width(), TPOINT::x, and TPOINT::y.
00073 { 00074 EDGEPT *edgept; //converted steps 00075 EDGEPT *startpt; //start of outline 00076 BOX loop_box; //bounding box 00077 INT32 area; //loop area 00078 FCOORD pos; //vertex 00079 FCOORD vec; //vector 00080 POLYPT_LIST polypts; //output polygon 00081 POLYPT *polypt; //converted point 00082 POLYPT_IT poly_it = &polypts; //iterator 00083 EDGEPT edgepts[MAXEDGELENGTH]; //converted path 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);/*2nd approximation */ 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 //add to list 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 //turn to outline 00107 return new OUTLINE (&poly_it); 00108 }