00001
00020 #include "mfcpch.h"
00021 #include <string.h>
00022 #ifdef __UNIX__
00023 #include <assert.h>
00024 #endif
00025 #include "coutln.h"
00026
00027 ELISTIZE_S (C_OUTLINE)
00028 ICOORD C_OUTLINE::step_coords[4] = {
00029 ICOORD (-1, 0), ICOORD (0, -1), ICOORD (1, 0), ICOORD (0, 1)
00030 };
00031
00035 C_OUTLINE::C_OUTLINE (
00036 CRACKEDGE * startpt,
00037 ICOORD bot_left,
00038 ICOORD top_right, INT16 length
00039 ):box (bot_left, top_right), start (startpt->pos) {
00040 INT16 stepindex;
00041 CRACKEDGE *edgept;
00042
00043 stepcount = length;
00044
00045 steps = (UINT8 *) alloc_mem (step_mem());
00046 memset(steps, 0, step_mem());
00047 edgept = startpt;
00048
00049 for (stepindex = 0; stepindex < length; stepindex++) {
00050
00051 set_step (stepindex, edgept->stepdir);
00052 edgept = edgept->next;
00053 }
00054 }
00055
00056
00064 C_OUTLINE::C_OUTLINE (
00065 ICOORD startpt, DIR128 * new_steps,
00066 INT16 length
00067 ):start (startpt) {
00068 INT8 dirdiff;
00069 DIR128 prevdir;
00070 DIR128 dir;
00071 DIR128 lastdir;
00072 BOX new_box;
00073 INT16 stepindex;
00074 INT16 srcindex;
00075 ICOORD pos;
00076
00077 pos = startpt;
00078 stepcount = length;
00079
00080 steps = (UINT8 *) alloc_mem (step_mem());
00081 memset(steps, 0, step_mem());
00082
00083 lastdir = new_steps[length - 1];
00084 prevdir = lastdir;
00085 for (stepindex = 0, srcindex = 0; srcindex < length;
00086 stepindex++, srcindex++) {
00087 new_box = BOX (pos, pos);
00088 box += new_box;
00089
00090 dir = new_steps[srcindex];
00091 set_step(stepindex, dir);
00092 dirdiff = dir - prevdir;
00093 pos += step (stepindex);
00094 if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
00095 stepindex -= 2;
00096 prevdir = stepindex >= 0 ? step_dir (stepindex) : lastdir;
00097 }
00098 else
00099 prevdir = dir;
00100 }
00101 ASSERT_HOST (pos.x () == startpt.x () && pos.y () == startpt.y ());
00102 do {
00103 dirdiff = step_dir (stepindex - 1) - step_dir (0);
00104 if (dirdiff == 64 || dirdiff == -64) {
00105 start += step (0);
00106 stepindex -= 2;
00107 for (int i = 0; i < stepindex; ++i)
00108 set_step(i, step_dir(i + 1));
00109 }
00110 }
00111 while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
00112 stepcount = stepindex;
00113 ASSERT_HOST (stepcount >= 4);
00114 }
00115
00119 C_OUTLINE::C_OUTLINE(
00120 C_OUTLINE *srcline,
00121 FCOORD rotation
00122 ) {
00123 BOX new_box;
00124 INT16 stepindex;
00125 INT16 dirdiff;
00126 ICOORD pos;
00127 ICOORD prevpos;
00128
00129 ICOORD destpos;
00130 INT16 destindex;
00131 DIR128 dir;
00132 UINT8 new_step;
00133
00134 stepcount = srcline->stepcount * 2;
00135
00136 steps = (UINT8 *) alloc_mem (step_mem());
00137 memset(steps, 0, step_mem());
00138
00139 for (int iteration = 0; iteration < 2; ++iteration) {
00140 DIR128 round1 = iteration == 0 ? 32 : 0;
00141 DIR128 round2 = iteration != 0 ? 32 : 0;
00142 pos = srcline->start;
00143 prevpos = pos;
00144 prevpos.rotate (rotation);
00145 start = prevpos;
00146 box = BOX (start, start);
00147 destindex = 0;
00148 for (stepindex = 0; stepindex < srcline->stepcount; stepindex++) {
00149 pos += srcline->step (stepindex);
00150 destpos = pos;
00151 destpos.rotate (rotation);
00152 if (destpos.x () != prevpos.x () || destpos.y () != prevpos.y ()) {
00153 dir = DIR128 (FCOORD (destpos - prevpos));
00154 dir += 64;
00155 new_step = dir.get_dir ();
00156 if (new_step & 31) {
00157 set_step(destindex++, dir + round1);
00158 if (destindex < 2
00159 || (dirdiff =
00160 step_dir (destindex - 1) - step_dir (destindex - 2)) !=
00161 -64 && dirdiff != 64)
00162 set_step(destindex++, dir + round2);
00163 else {
00164 set_step(destindex - 1, dir + round2);
00165 set_step(destindex++, dir + round1);
00166 }
00167 }
00168 else {
00169 set_step(destindex++, dir);
00170 if (destindex >= 2
00171 &&
00172 ((dirdiff =
00173 step_dir (destindex - 1) - step_dir (destindex - 2)) ==
00174 -64 || dirdiff == 64))
00175 destindex -= 2;
00176 }
00177 prevpos = destpos;
00178 new_box = BOX (destpos, destpos);
00179 box += new_box;
00180 }
00181 }
00182 ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
00183 dirdiff = step_dir (destindex - 1) - step_dir (0);
00184 while ((dirdiff == 64 || dirdiff == -64) && destindex > 1) {
00185 start += step (0);
00186 destindex -= 2;
00187 for (int i = 0; i < destindex; ++i)
00188 set_step(i, step_dir(i + 1));
00189 dirdiff = step_dir (destindex - 1) - step_dir (0);
00190 }
00191 if (destindex >= 4)
00192 break;
00193 }
00194 stepcount = destindex;
00195 destpos = start;
00196 for (stepindex = 0; stepindex < stepcount; stepindex++) {
00197 destpos += step (stepindex);
00198 }
00199 ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
00200 }
00201
00202
00208 INT32 C_OUTLINE::area() {
00209 int stepindex;
00210 INT32 total_steps;
00211 INT32 total;
00212 ICOORD pos;
00213 ICOORD next_step;
00214 C_OUTLINE_IT it = child ();
00215
00216 pos = start_pos ();
00217 total_steps = pathlength ();
00218 total = 0;
00219 for (stepindex = 0; stepindex < total_steps; stepindex++) {
00220
00221 next_step = step (stepindex);
00222 if (next_step.x () < 0)
00223 total += pos.y ();
00224 else if (next_step.x () > 0)
00225 total -= pos.y ();
00226 pos += next_step;
00227 }
00228 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
00229 total += it.data ()->area ();
00230
00231 return total;
00232 }
00233
00234
00240 INT32 C_OUTLINE::outer_area() {
00241 int stepindex;
00242 INT32 total_steps;
00243 INT32 total;
00244 ICOORD pos;
00245 ICOORD next_step;
00246
00247 pos = start_pos ();
00248 total_steps = pathlength ();
00249 total = 0;
00250 for (stepindex = 0; stepindex < total_steps; stepindex++) {
00251
00252 next_step = step (stepindex);
00253 if (next_step.x () < 0)
00254 total += pos.y ();
00255 else if (next_step.x () > 0)
00256 total -= pos.y ();
00257 pos += next_step;
00258 }
00259
00260 return total;
00261 }
00262
00263
00267 INT32 C_OUTLINE::count_transitions(
00268 INT32 threshold
00269 ) {
00270 BOOL8 first_was_max_x;
00271 BOOL8 first_was_max_y;
00272 BOOL8 looking_for_max_x;
00273 BOOL8 looking_for_min_x;
00274 BOOL8 looking_for_max_y;
00275 BOOL8 looking_for_min_y;
00276 int stepindex;
00277 INT32 total_steps;
00278
00279 INT32 max_x, min_x, max_y, min_y;
00280 INT32 initial_x, initial_y;
00281 INT32 total;
00282 ICOORD pos;
00283 ICOORD next_step;
00284
00285 pos = start_pos ();
00286 total_steps = pathlength ();
00287 total = 0;
00288 max_x = min_x = pos.x ();
00289 max_y = min_y = pos.y ();
00290 looking_for_max_x = TRUE;
00291 looking_for_min_x = TRUE;
00292 looking_for_max_y = TRUE;
00293 looking_for_min_y = TRUE;
00294 first_was_max_x = FALSE;
00295 first_was_max_y = FALSE;
00296 initial_x = pos.x ();
00297 initial_y = pos.y ();
00298 for (stepindex = 0; stepindex < total_steps; stepindex++) {
00299
00300 next_step = step (stepindex);
00301 pos += next_step;
00302 if (next_step.x () < 0) {
00303 if (looking_for_max_x && pos.x () < min_x)
00304 min_x = pos.x ();
00305 if (looking_for_min_x && max_x - pos.x () > threshold) {
00306 if (looking_for_max_x) {
00307 initial_x = max_x;
00308 first_was_max_x = FALSE;
00309 }
00310 total++;
00311 looking_for_max_x = TRUE;
00312 looking_for_min_x = FALSE;
00313 min_x = pos.x ();
00314 }
00315 }
00316 else if (next_step.x () > 0) {
00317 if (looking_for_min_x && pos.x () > max_x)
00318 max_x = pos.x ();
00319 if (looking_for_max_x && pos.x () - min_x > threshold) {
00320 if (looking_for_min_x) {
00321 initial_x = min_x;
00322 first_was_max_x = TRUE;
00323 }
00324 total++;
00325 looking_for_max_x = FALSE;
00326 looking_for_min_x = TRUE;
00327 max_x = pos.x ();
00328 }
00329 }
00330 else if (next_step.y () < 0) {
00331 if (looking_for_max_y && pos.y () < min_y)
00332 min_y = pos.y ();
00333 if (looking_for_min_y && max_y - pos.y () > threshold) {
00334 if (looking_for_max_y) {
00335 initial_y = max_y;
00336 first_was_max_y = FALSE;
00337 }
00338 total++;
00339 looking_for_max_y = TRUE;
00340 looking_for_min_y = FALSE;
00341 min_y = pos.y ();
00342 }
00343 }
00344 else {
00345 if (looking_for_min_y && pos.y () > max_y)
00346 max_y = pos.y ();
00347 if (looking_for_max_y && pos.y () - min_y > threshold) {
00348 if (looking_for_min_y) {
00349 initial_y = min_y;
00350 first_was_max_y = TRUE;
00351 }
00352 total++;
00353 looking_for_max_y = FALSE;
00354 looking_for_min_y = TRUE;
00355 max_y = pos.y ();
00356 }
00357 }
00358
00359 }
00360 if (first_was_max_x && looking_for_min_x) {
00361 if (max_x - initial_x > threshold)
00362 total++;
00363 else
00364 total--;
00365 }
00366 else if (!first_was_max_x && looking_for_max_x) {
00367 if (initial_x - min_x > threshold)
00368 total++;
00369 else
00370 total--;
00371 }
00372 if (first_was_max_y && looking_for_min_y) {
00373 if (max_y - initial_y > threshold)
00374 total++;
00375 else
00376 total--;
00377 }
00378 else if (!first_was_max_y && looking_for_max_y) {
00379 if (initial_y - min_y > threshold)
00380 total++;
00381 else
00382 total--;
00383 }
00384
00385 return total;
00386 }
00387
00388
00392 BOOL8
00393 C_OUTLINE::operator< (
00394 const C_OUTLINE & other
00395 ) const
00396 {
00397 INT16 count = 0;
00398 ICOORD pos;
00399 INT32 stepindex;
00400
00401 if (!box.overlap (other.box))
00402 return FALSE;
00403
00404 pos = start;
00405 for (stepindex = 0; stepindex < stepcount
00406 && (count = other.winding_number (pos)) == INTERSECTING; stepindex++)
00407 pos += step (stepindex);
00408 if (count == INTERSECTING) {
00409
00410 pos = other.start;
00411 for (stepindex = 0; stepindex < other.stepcount
00412 && (count = winding_number (pos)) == INTERSECTING; stepindex++)
00413
00414 pos += other.step (stepindex);
00415 return count == INTERSECTING || count == 0;
00416 }
00417 return count != 0;
00418 }
00419
00420
00424 INT16 C_OUTLINE::winding_number(
00425 ICOORD point
00426 ) const {
00427 INT16 stepindex;
00428 INT16 count;
00429 ICOORD vec;
00430 ICOORD stepvec;
00431 INT32 cross;
00432
00433 vec = start - point;
00434 count = 0;
00435 for (stepindex = 0; stepindex < stepcount; stepindex++) {
00436 stepvec = step (stepindex);
00437
00438 if (vec.y () <= 0 && vec.y () + stepvec.y () > 0) {
00439 cross = vec * stepvec;
00440 if (cross > 0)
00441 count++;
00442 else if (cross == 0)
00443 return INTERSECTING;
00444 }
00445 else if (vec.y () > 0 && vec.y () + stepvec.y () <= 0) {
00446 cross = vec * stepvec;
00447 if (cross < 0)
00448 count--;
00449 else if (cross == 0)
00450 return INTERSECTING;
00451 }
00452 vec += stepvec;
00453 }
00454 return count;
00455 }
00456
00457
00461 INT16 C_OUTLINE::turn_direction() const {
00462 DIR128 prevdir;
00463 DIR128 dir;
00464 INT16 stepindex;
00465 INT8 dirdiff;
00466 INT16 count;
00467
00468 count = 0;
00469 prevdir = step_dir (stepcount - 1);
00470 for (stepindex = 0; stepindex < stepcount; stepindex++) {
00471 dir = step_dir (stepindex);
00472 dirdiff = dir - prevdir;
00473 ASSERT_HOST (dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
00474 count += dirdiff;
00475 prevdir = dir;
00476 }
00477 ASSERT_HOST (count == 128 || count == -128);
00478 return count;
00479 }
00480
00481
00485 void C_OUTLINE::reverse() {
00486 DIR128 halfturn = MODULUS / 2;
00487 DIR128 stepdir;
00488 INT16 stepindex;
00489 INT16 farindex;
00490 INT16 halfsteps;
00491
00492 halfsteps = (stepcount + 1) / 2;
00493 for (stepindex = 0; stepindex < halfsteps; stepindex++) {
00494 farindex = stepcount - stepindex - 1;
00495 stepdir = step_dir (stepindex);
00496 set_step (stepindex, step_dir (farindex) + halfturn);
00497 set_step (farindex, stepdir + halfturn);
00498 }
00499 }
00500
00501
00505 void C_OUTLINE::move(
00506 const ICOORD vec
00507 ) {
00508 C_OUTLINE_IT it(&children);
00509
00510 box.move (vec);
00511 start += vec;
00512
00513 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
00514 it.data ()->move (vec);
00515 }
00516
00517
00521 #ifndef GRAPHICS_DISABLED
00522 void C_OUTLINE::plot(
00523 WINDOW window,
00524 COLOUR colour
00525 ) const {
00526 INT16 stepindex;
00527 ICOORD pos;
00528 DIR128 stepdir;
00529 DIR128 oldstepdir;
00530
00531 pos = start;
00532 line_color_index(window, colour);
00533 move2d (window, pos.x (), pos.y ());
00534 stepindex = 0;
00535 stepdir = step_dir (0);
00536 while (stepindex < stepcount) {
00537 do {
00538 pos += step (stepindex);
00539 stepindex++;
00540 oldstepdir = stepdir;
00541
00542 stepdir = step_dir (stepindex);
00543 }
00544 while (stepindex < stepcount
00545 && oldstepdir.get_dir () == stepdir.get_dir ());
00546
00547 draw2d (window, pos.x (), pos.y ());
00548 }
00549 }
00550 #endif
00551
00552
00556
00557 C_OUTLINE & C_OUTLINE::operator= (
00558 const C_OUTLINE & source
00559 ) {
00560 box = source.box;
00561 start = source.start;
00562 if (steps != NULL)
00563 free_mem(steps);
00564 stepcount = source.stepcount;
00565 steps = (UINT8 *) alloc_mem (step_mem());
00566 memmove (steps, source.steps, step_mem());
00567 if (!children.empty ())
00568 children.clear ();
00569 children.deep_copy (&source.children);
00570 return *this;
00571 }