tesseract 4.1.1
Loading...
Searching...
No Matches
coutln.cpp
Go to the documentation of this file.
1/**********************************************************************
2 * File: coutln.cpp (Formerly coutline.c)
3 * Description: Code for the C_OUTLINE class.
4 * Author: Ray Smith
5 *
6 * (C) Copyright 1991, Hewlett-Packard Ltd.
7 ** Licensed under the Apache License, Version 2.0 (the "License");
8 ** you may not use this file except in compliance with the License.
9 ** You may obtain a copy of the License at
10 ** http://www.apache.org/licenses/LICENSE-2.0
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 *
17 **********************************************************************/
18
19#include "coutln.h"
20#include <algorithm> // for max, min
21#include <cmath> // for abs
22#include <cstdlib> // for abs
23#include <cstring> // for memset, memcpy, memmove
24#include "allheaders.h" // for pixSetPixel, pixGetData, pixRasterop, pixGe...
25#include "arrayaccess.h" // for GET_DATA_BYTE
26#include "blobs.h" // for TPOINT
27#include "crakedge.h" // for CRACKEDGE
28#include "environ.h" // for l_uint32
29#include "errcode.h" // for ASSERT_HOST
30#include "helpers.h" // for ClipToRange, IntCastRounded, Modulo
31#include "normalis.h" // for DENORM
32#include "pix.h" // for Pix (ptr only), PIX_DST, PIX_NOT
33
34// Include automatically generated configuration file if running autoconf.
35#ifdef HAVE_CONFIG_H
36#include "config_auto.h"
37#endif
38
40ICOORD C_OUTLINE::step_coords[4] = {
41 ICOORD (-1, 0), ICOORD (0, -1), ICOORD (1, 0), ICOORD (0, 1)
42};
43
54C_OUTLINE::C_OUTLINE(CRACKEDGE* startpt, ICOORD bot_left, ICOORD top_right,
55 int16_t length)
56 : box(bot_left, top_right), start(startpt->pos), offsets(nullptr) {
57 int16_t stepindex; //index to step
58 CRACKEDGE *edgept; //current point
59
60 stepcount = length; //no of steps
61 if (length == 0) {
62 steps = nullptr;
63 return;
64 }
65 //get memory
66 steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
67 edgept = startpt;
68
69 for (stepindex = 0; stepindex < length; stepindex++) {
70 //set compact step
71 set_step (stepindex, edgept->stepdir);
72 edgept = edgept->next;
73 }
74}
75
82//constructor
83 //steps to copy
84ICOORD startpt, DIR128 * new_steps,
85int16_t length //length of loop
86):start (startpt), offsets(nullptr) {
87 int8_t dirdiff; //direction difference
88 DIR128 prevdir; //previous direction
89 DIR128 dir; //current direction
90 DIR128 lastdir; //dir of last step
91 TBOX new_box; //easy bounding
92 int16_t stepindex; //index to step
93 int16_t srcindex; //source steps
94 ICOORD pos; //current position
95
96 pos = startpt;
97 stepcount = length; // No. of steps.
98 ASSERT_HOST(length >= 0);
99 steps = static_cast<uint8_t*>(calloc(step_mem(), 1)); // Get memory.
100
101 lastdir = new_steps[length - 1];
102 prevdir = lastdir;
103 for (stepindex = 0, srcindex = 0; srcindex < length;
104 stepindex++, srcindex++) {
105 new_box = TBOX (pos, pos);
106 box += new_box;
107 //copy steps
108 dir = new_steps[srcindex];
109 set_step(stepindex, dir);
110 dirdiff = dir - prevdir;
111 pos += step (stepindex);
112 if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
113 stepindex -= 2; //cancel there-and-back
114 prevdir = stepindex >= 0 ? step_dir (stepindex) : lastdir;
115 }
116 else
117 prevdir = dir;
118 }
119 ASSERT_HOST (pos.x () == startpt.x () && pos.y () == startpt.y ());
120 do {
121 dirdiff = step_dir (stepindex - 1) - step_dir (0);
122 if (dirdiff == 64 || dirdiff == -64) {
123 start += step (0);
124 stepindex -= 2; //cancel there-and-back
125 for (int i = 0; i < stepindex; ++i)
126 set_step(i, step_dir(i + 1));
127 }
128 }
129 while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
130 stepcount = stepindex;
131 ASSERT_HOST (stepcount >= 4);
132}
133
142C_OUTLINE::C_OUTLINE(C_OUTLINE* srcline, FCOORD rotation) : offsets(nullptr) {
143 TBOX new_box; //easy bounding
144 int16_t stepindex; //index to step
145 int16_t dirdiff; //direction change
146 ICOORD pos; //current position
147 ICOORD prevpos; //previous dest point
148
149 ICOORD destpos; //destination point
150 int16_t destindex = INT16_MAX; //index to step
151 DIR128 dir; //coded direction
152 uint8_t new_step;
153
154 stepcount = srcline->stepcount * 2;
155 if (stepcount == 0) {
156 steps = nullptr;
157 box = srcline->box;
158 box.rotate(rotation);
159 return;
160 }
161 //get memory
162 steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
163
164 for (int iteration = 0; iteration < 2; ++iteration) {
165 DIR128 round1 = iteration == 0 ? 32 : 0;
166 DIR128 round2 = iteration != 0 ? 32 : 0;
167 pos = srcline->start;
168 prevpos = pos;
169 prevpos.rotate (rotation);
170 start = prevpos;
171 box = TBOX (start, start);
172 destindex = 0;
173 for (stepindex = 0; stepindex < srcline->stepcount; stepindex++) {
174 pos += srcline->step (stepindex);
175 destpos = pos;
176 destpos.rotate (rotation);
177 // tprintf("%i %i %i %i ", destpos.x(), destpos.y(), pos.x(), pos.y());
178 while (destpos.x () != prevpos.x () || destpos.y () != prevpos.y ()) {
179 dir = DIR128 (FCOORD (destpos - prevpos));
180 dir += 64; //turn to step style
181 new_step = dir.get_dir ();
182 // tprintf(" %i\n", new_step);
183 if (new_step & 31) {
184 set_step(destindex++, dir + round1);
185 prevpos += step(destindex - 1);
186 if (destindex < 2
187 || ((dirdiff =
188 step_dir (destindex - 1) - step_dir (destindex - 2)) !=
189 -64 && dirdiff != 64)) {
190 set_step(destindex++, dir + round2);
191 prevpos += step(destindex - 1);
192 } else {
193 prevpos -= step(destindex - 1);
194 destindex--;
195 prevpos -= step(destindex - 1);
196 set_step(destindex - 1, dir + round2);
197 prevpos += step(destindex - 1);
198 }
199 }
200 else {
201 set_step(destindex++, dir);
202 prevpos += step(destindex - 1);
203 }
204 while (destindex >= 2 &&
205 ((dirdiff =
206 step_dir (destindex - 1) - step_dir (destindex - 2)) == -64 ||
207 dirdiff == 64)) {
208 prevpos -= step(destindex - 1);
209 prevpos -= step(destindex - 2);
210 destindex -= 2; // Forget u turn
211 }
212 //ASSERT_HOST(prevpos.x() == destpos.x() && prevpos.y() == destpos.y());
213 new_box = TBOX (destpos, destpos);
214 box += new_box;
215 }
216 }
217 ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
218 dirdiff = step_dir (destindex - 1) - step_dir (0);
219 while ((dirdiff == 64 || dirdiff == -64) && destindex > 1) {
220 start += step (0);
221 destindex -= 2;
222 for (int i = 0; i < destindex; ++i)
223 set_step(i, step_dir(i + 1));
224 dirdiff = step_dir (destindex - 1) - step_dir (0);
225 }
226 if (destindex >= 4)
227 break;
228 }
229 ASSERT_HOST(destindex <= stepcount);
230 stepcount = destindex;
231 destpos = start;
232 for (stepindex = 0; stepindex < stepcount; stepindex++) {
233 destpos += step (stepindex);
234 }
235 ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
236}
237
238// Build a fake outline, given just a bounding box and append to the list.
239void C_OUTLINE::FakeOutline(const TBOX& box, C_OUTLINE_LIST* outlines) {
240 C_OUTLINE_IT ol_it(outlines);
241 // Make a C_OUTLINE from the bounds. This is a bit of a hack,
242 // as there is no outline, just a bounding box, but it works nicely.
243 CRACKEDGE start;
244 start.pos = box.topleft();
245 C_OUTLINE* outline = new C_OUTLINE(&start, box.topleft(), box.botright(), 0);
246 ol_it.add_to_end(outline);
247}
248
255int32_t C_OUTLINE::area() const {
256 int stepindex; //current step
257 int32_t total_steps; //steps to do
258 int32_t total; //total area
259 ICOORD pos; //position of point
260 ICOORD next_step; //step to next pix
261 // We aren't going to modify the list, or its contents, but there is
262 // no const iterator.
263 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
264
265 pos = start_pos ();
266 total_steps = pathlength ();
267 total = 0;
268 for (stepindex = 0; stepindex < total_steps; stepindex++) {
269 //all intersected
270 next_step = step (stepindex);
271 if (next_step.x () < 0)
272 total += pos.y ();
273 else if (next_step.x () > 0)
274 total -= pos.y ();
275 pos += next_step;
276 }
277 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
278 total += it.data ()->area ();//add areas of children
279
280 return total;
281}
282
289int32_t C_OUTLINE::perimeter() const {
290 int32_t total_steps; // Return value.
291 // We aren't going to modify the list, or its contents, but there is
292 // no const iterator.
293 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
294
295 total_steps = pathlength();
296 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward())
297 total_steps += it.data()->pathlength(); // Add perimeters of children.
298
299 return total_steps;
300}
301
308int32_t C_OUTLINE::outer_area() const {
309 int stepindex; //current step
310 int32_t total_steps; //steps to do
311 int32_t total; //total area
312 ICOORD pos; //position of point
313 ICOORD next_step; //step to next pix
314
315 pos = start_pos ();
316 total_steps = pathlength ();
317 if (total_steps == 0)
318 return box.area();
319 total = 0;
320 for (stepindex = 0; stepindex < total_steps; stepindex++) {
321 //all intersected
322 next_step = step (stepindex);
323 if (next_step.x () < 0)
324 total += pos.y ();
325 else if (next_step.x () > 0)
326 total -= pos.y ();
327 pos += next_step;
328 }
329
330 return total;
331}
332
340int32_t C_OUTLINE::count_transitions(int32_t threshold) {
341 bool first_was_max_x; //what was first
342 bool first_was_max_y;
343 bool looking_for_max_x; //what is next
344 bool looking_for_min_x;
345 bool looking_for_max_y; //what is next
346 bool looking_for_min_y;
347 int stepindex; //current step
348 int32_t total_steps; //steps to do
349 //current limits
350 int32_t max_x, min_x, max_y, min_y;
351 int32_t initial_x, initial_y; //initial limits
352 int32_t total; //total changes
353 ICOORD pos; //position of point
354 ICOORD next_step; //step to next pix
355
356 pos = start_pos();
357 total_steps = pathlength();
358 total = 0;
359 max_x = min_x = pos.x();
360 max_y = min_y = pos.y();
361 looking_for_max_x = true;
362 looking_for_min_x = true;
363 looking_for_max_y = true;
364 looking_for_min_y = true;
365 first_was_max_x = false;
366 first_was_max_y = false;
367 initial_x = pos.x();
368 initial_y = pos.y(); //stop uninit warning
369 for (stepindex = 0; stepindex < total_steps; stepindex++) {
370 //all intersected
371 next_step = step(stepindex);
372 pos += next_step;
373 if (next_step.x() < 0) {
374 if (looking_for_max_x && pos.x() < min_x)
375 min_x = pos.x();
376 if (looking_for_min_x && max_x - pos.x() > threshold) {
377 if (looking_for_max_x) {
378 initial_x = max_x;
379 first_was_max_x = false;
380 }
381 total++;
382 looking_for_max_x = true;
383 looking_for_min_x = false;
384 min_x = pos.x(); //reset min
385 }
386 }
387 else if (next_step.x() > 0) {
388 if (looking_for_min_x && pos.x() > max_x)
389 max_x = pos.x();
390 if (looking_for_max_x && pos.x() - min_x > threshold) {
391 if (looking_for_min_x) {
392 initial_x = min_x; //remember first min
393 first_was_max_x = true;
394 }
395 total++;
396 looking_for_max_x = false;
397 looking_for_min_x = true;
398 max_x = pos.x();
399 }
400 }
401 else if (next_step.y() < 0) {
402 if (looking_for_max_y && pos.y() < min_y)
403 min_y = pos.y();
404 if (looking_for_min_y && max_y - pos.y() > threshold) {
405 if (looking_for_max_y) {
406 initial_y = max_y; //remember first max
407 first_was_max_y = false;
408 }
409 total++;
410 looking_for_max_y = true;
411 looking_for_min_y = false;
412 min_y = pos.y(); //reset min
413 }
414 }
415 else {
416 if (looking_for_min_y && pos.y() > max_y)
417 max_y = pos.y();
418 if (looking_for_max_y && pos.y() - min_y > threshold) {
419 if (looking_for_min_y) {
420 initial_y = min_y; //remember first min
421 first_was_max_y = true;
422 }
423 total++;
424 looking_for_max_y = false;
425 looking_for_min_y = true;
426 max_y = pos.y();
427 }
428 }
429
430 }
431 if (first_was_max_x && looking_for_min_x) {
432 if (max_x - initial_x > threshold)
433 total++;
434 else
435 total--;
436 }
437 else if (!first_was_max_x && looking_for_max_x) {
438 if (initial_x - min_x > threshold)
439 total++;
440 else
441 total--;
442 }
443 if (first_was_max_y && looking_for_min_y) {
444 if (max_y - initial_y > threshold)
445 total++;
446 else
447 total--;
448 }
449 else if (!first_was_max_y && looking_for_max_y) {
450 if (initial_y - min_y > threshold)
451 total++;
452 else
453 total--;
454 }
455
456 return total;
457}
458
466bool
467C_OUTLINE::operator<(const C_OUTLINE& other) const {
468 int16_t count = 0; //winding count
469 ICOORD pos; //position of point
470 int32_t stepindex; //index to cstep
471
472 if (!box.overlap (other.box))
473 return false; //can't be contained
474 if (stepcount == 0)
475 return other.box.contains(this->box);
476
477 pos = start;
478 for (stepindex = 0; stepindex < stepcount
479 && (count = other.winding_number (pos)) == INTERSECTING; stepindex++)
480 pos += step (stepindex); //try all points
481 if (count == INTERSECTING) {
482 //all intersected
483 pos = other.start;
484 for (stepindex = 0; stepindex < other.stepcount
485 && (count = winding_number (pos)) == INTERSECTING; stepindex++)
486 //try other way round
487 pos += other.step (stepindex);
488 return count == INTERSECTING || count == 0;
489 }
490 return count != 0;
491}
492
500int16_t C_OUTLINE::winding_number(ICOORD point) const {
501 int16_t stepindex; //index to cstep
502 int16_t count; //winding count
503 ICOORD vec; //to current point
504 ICOORD stepvec; //step vector
505 int32_t cross; //cross product
506
507 vec = start - point; //vector to it
508 count = 0;
509 for (stepindex = 0; stepindex < stepcount; stepindex++) {
510 stepvec = step (stepindex); //get the step
511 //crossing the line
512 if (vec.y () <= 0 && vec.y () + stepvec.y () > 0) {
513 cross = vec * stepvec; //cross product
514 if (cross > 0)
515 count++; //crossing right half
516 else if (cross == 0)
517 return INTERSECTING; //going through point
518 }
519 else if (vec.y () > 0 && vec.y () + stepvec.y () <= 0) {
520 cross = vec * stepvec;
521 if (cross < 0)
522 count--; //crossing back
523 else if (cross == 0)
524 return INTERSECTING; //illegal
525 }
526 vec += stepvec; //sum vectors
527 }
528 return count; //winding number
529}
530
537int16_t C_OUTLINE::turn_direction() const { //winding number
538 DIR128 prevdir; //previous direction
539 DIR128 dir; //current direction
540 int16_t stepindex; //index to cstep
541 int8_t dirdiff; //direction difference
542 int16_t count; //winding count
543
544 if (stepcount == 0)
545 return 128;
546 count = 0;
547 prevdir = step_dir (stepcount - 1);
548 for (stepindex = 0; stepindex < stepcount; stepindex++) {
549 dir = step_dir (stepindex);
550 dirdiff = dir - prevdir;
551 ASSERT_HOST (dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
552 count += dirdiff;
553 prevdir = dir;
554 }
555 ASSERT_HOST (count == 128 || count == -128);
556 return count; //winding number
557}
558
565void C_OUTLINE::reverse() { //reverse drection
566 DIR128 halfturn = MODULUS / 2; //amount to shift
567 DIR128 stepdir; //direction of step
568 int16_t stepindex; //index to cstep
569 int16_t farindex; //index to other side
570 int16_t halfsteps; //half of stepcount
571
572 halfsteps = (stepcount + 1) / 2;
573 for (stepindex = 0; stepindex < halfsteps; stepindex++) {
574 farindex = stepcount - stepindex - 1;
575 stepdir = step_dir (stepindex);
576 set_step (stepindex, step_dir (farindex) + halfturn);
577 set_step (farindex, stepdir + halfturn);
578 }
579}
580
588void C_OUTLINE::move(const ICOORD vec) {
589 C_OUTLINE_IT it(&children); // iterator
590
591 box.move (vec);
592 start += vec;
593
594 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
595 it.data ()->move (vec); // move child outlines
596}
597
605 if (stepcount == 0) return true;
606 int64_t parent_area = outer_area();
607 // We aren't going to modify the list, or its contents, but there is
608 // no const iterator.
609 C_OUTLINE_IT child_it(const_cast<C_OUTLINE_LIST*>(&children));
610 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
611 const C_OUTLINE* child = child_it.data();
612 if (child->outer_area() * parent_area > 0 || !child->IsLegallyNested())
613 return false;
614 }
615 return true;
616}
617
627void C_OUTLINE::RemoveSmallRecursive(int min_size, C_OUTLINE_IT* it) {
628 if (box.width() < min_size || box.height() < min_size) {
629 ASSERT_HOST(this == it->data());
630 delete it->extract(); // Too small so get rid of it and any children.
631 } else if (!children.empty()) {
632 // Search the children of this, deleting any that are too small.
633 C_OUTLINE_IT child_it(&children);
634 for (child_it.mark_cycle_pt(); !child_it.cycled_list();
635 child_it.forward()) {
636 C_OUTLINE* child = child_it.data();
637 child->RemoveSmallRecursive(min_size, &child_it);
638 }
639 }
640}
641
642// Factored out helpers below are used only by ComputeEdgeOffsets to operate
643// on data from an 8-bit Pix, and assume that any input x and/or y are already
644// constrained to be legal Pix coordinates.
645
651static void ComputeGradient(const l_uint32* data, int wpl,
652 int x, int y, int width, int height,
653 ICOORD* gradient) {
654 const l_uint32* line = data + y * wpl;
655 int pix_x_y = x < width && y < height ? GET_DATA_BYTE(line, x) : 255;
656 int pix_x_prevy = x < width && y > 0 ? GET_DATA_BYTE(line - wpl, x) : 255;
657 int pix_prevx_prevy = x > 0 && y > 0 ? GET_DATA_BYTE(line - wpl, x - 1) : 255;
658 int pix_prevx_y = x > 0 && y < height ? GET_DATA_BYTE(line, x - 1) : 255;
659 gradient->set_x(pix_x_y + pix_x_prevy - (pix_prevx_y + pix_prevx_prevy));
660 gradient->set_y(pix_x_prevy + pix_prevx_prevy - (pix_x_y + pix_prevx_y));
661}
662
668static bool EvaluateVerticalDiff(const l_uint32* data, int wpl, int diff_sign,
669 int x, int y, int height,
670 int* best_diff, int* best_sum, int* best_y) {
671 if (y <= 0 || y >= height)
672 return false;
673 const l_uint32* line = data + y * wpl;
674 int pixel1 = GET_DATA_BYTE(line - wpl, x);
675 int pixel2 = GET_DATA_BYTE(line, x);
676 int diff = (pixel2 - pixel1) * diff_sign;
677 if (diff > *best_diff) {
678 *best_diff = diff;
679 *best_sum = pixel1 + pixel2;
680 *best_y = y;
681 }
682 return diff > 0;
683}
684
690static bool EvaluateHorizontalDiff(const l_uint32* line, int diff_sign,
691 int x, int width,
692 int* best_diff, int* best_sum, int* best_x) {
693 if (x <= 0 || x >= width)
694 return false;
695 int pixel1 = GET_DATA_BYTE(line, x - 1);
696 int pixel2 = GET_DATA_BYTE(line, x);
697 int diff = (pixel2 - pixel1) * diff_sign;
698 if (diff > *best_diff) {
699 *best_diff = diff;
700 *best_sum = pixel1 + pixel2;
701 *best_x = x;
702 }
703 return diff > 0;
704}
705
721void C_OUTLINE::ComputeEdgeOffsets(int threshold, Pix* pix) {
722 if (pixGetDepth(pix) != 8) return;
723 const l_uint32* data = pixGetData(pix);
724 int wpl = pixGetWpl(pix);
725 int width = pixGetWidth(pix);
726 int height = pixGetHeight(pix);
727 bool negative = flag(COUT_INVERSE);
728 delete [] offsets;
729 offsets = new EdgeOffset[stepcount];
730 ICOORD pos = start;
731 ICOORD prev_gradient;
732 ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height,
733 &prev_gradient);
734 for (int s = 0; s < stepcount; ++s) {
735 ICOORD step_vec = step(s);
736 TPOINT pt1(pos);
737 pos += step_vec;
738 TPOINT pt2(pos);
739 ICOORD next_gradient;
740 ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height,
741 &next_gradient);
742 // Use the sum of the prev and next as the working gradient.
743 ICOORD gradient = prev_gradient + next_gradient;
744 // best_diff will be manipulated to be always positive.
745 int best_diff = 0;
746 // offset will be the extrapolation of the location of the greyscale
747 // threshold from the edge with the largest difference, relative to the
748 // location of the binary edge.
749 int offset = 0;
750 if (pt1.y == pt2.y && abs(gradient.y()) * 2 >= abs(gradient.x())) {
751 // Horizontal step. diff_sign == 1 indicates black above.
752 int diff_sign = (pt1.x > pt2.x) == negative ? 1 : -1;
753 int x = std::min(pt1.x, pt2.x);
754 int y = height - pt1.y;
755 int best_sum = 0;
756 int best_y = y;
757 EvaluateVerticalDiff(data, wpl, diff_sign, x, y, height,
758 &best_diff, &best_sum, &best_y);
759 // Find the strongest edge.
760 int test_y = y;
761 do {
762 ++test_y;
763 } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
764 &best_diff, &best_sum, &best_y));
765 test_y = y;
766 do {
767 --test_y;
768 } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
769 &best_diff, &best_sum, &best_y));
770 offset = diff_sign * (best_sum / 2 - threshold) +
771 (y - best_y) * best_diff;
772 } else if (pt1.x == pt2.x && abs(gradient.x()) * 2 >= abs(gradient.y())) {
773 // Vertical step. diff_sign == 1 indicates black on the left.
774 int diff_sign = (pt1.y > pt2.y) == negative ? 1 : -1;
775 int x = pt1.x;
776 int y = height - std::max(pt1.y, pt2.y);
777 const l_uint32* line = pixGetData(pix) + y * wpl;
778 int best_sum = 0;
779 int best_x = x;
780 EvaluateHorizontalDiff(line, diff_sign, x, width,
781 &best_diff, &best_sum, &best_x);
782 // Find the strongest edge.
783 int test_x = x;
784 do {
785 ++test_x;
786 } while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
787 &best_diff, &best_sum, &best_x));
788 test_x = x;
789 do {
790 --test_x;
791 } while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
792 &best_diff, &best_sum, &best_x));
793 offset = diff_sign * (threshold - best_sum / 2) +
794 (best_x - x) * best_diff;
795 }
796 offsets[s].offset_numerator =
797 ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
798 offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
799 if (negative) gradient = -gradient;
800 // Compute gradient angle quantized to 256 directions, rotated by 64 (pi/2)
801 // to convert from gradient direction to edge direction.
802 offsets[s].direction =
803 Modulo(FCOORD::binary_angle_plus_pi(gradient.angle()) + 64, 256);
804 prev_gradient = next_gradient;
805 }
806}
807
838 delete [] offsets;
839 offsets = new EdgeOffset[stepcount];
840 // Count of the number of steps in each direction in the sliding window.
841 int dir_counts[4];
842 // Sum of the positions (y for a horizontal step, x for vertical) in each
843 // direction in the sliding window.
844 int pos_totals[4];
845 memset(dir_counts, 0, sizeof(dir_counts));
846 memset(pos_totals, 0, sizeof(pos_totals));
847 ICOORD pos = start;
848 ICOORD tail_pos = pos;
849 // tail_pos is the trailing position, with the next point to be lost from
850 // the window.
851 tail_pos -= step(stepcount - 1);
852 tail_pos -= step(stepcount - 2);
853 // head_pos is the leading position, with the next point to be added to the
854 // window.
855 ICOORD head_pos = tail_pos;
856 // Set up the initial window with 4 points in [-2, 2)
857 for (int s = -2; s < 2; ++s) {
858 increment_step(s, 1, &head_pos, dir_counts, pos_totals);
859 }
860 for (int s = 0; s < stepcount; pos += step(s++)) {
861 // At step s, s in in the middle of [s-2, s+2].
862 increment_step(s + 2, 1, &head_pos, dir_counts, pos_totals);
863 int dir_index = chain_code(s);
864 ICOORD step_vec = step(s);
865 int best_diff = 0;
866 int offset = 0;
867 // Use only steps that have a count of >=2 OR the strong U-turn with a
868 // single d and 2 at d-1 and 2 at d+1 (mod 4).
869 if (dir_counts[dir_index] >= 2 || (dir_counts[dir_index] == 1 &&
870 dir_counts[Modulo(dir_index - 1, 4)] == 2 &&
871 dir_counts[Modulo(dir_index + 1, 4)] == 2)) {
872 // Valid step direction.
873 best_diff = dir_counts[dir_index];
874 int edge_pos = step_vec.x() == 0 ? pos.x() : pos.y();
875 // The offset proposes that the actual step should be positioned at
876 // the mean position of the steps in the window of the same direction.
877 // See ASCII art above.
878 offset = pos_totals[dir_index] - best_diff * edge_pos;
879 }
880 offsets[s].offset_numerator =
881 ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
882 offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
883 // The direction is just the vector from start to end of the window.
884 FCOORD direction(head_pos.x() - tail_pos.x(), head_pos.y() - tail_pos.y());
885 offsets[s].direction = direction.to_direction();
886 increment_step(s - 2, -1, &tail_pos, dir_counts, pos_totals);
887 }
888}
889
894void C_OUTLINE::render(int left, int top, Pix* pix) const {
895 ICOORD pos = start;
896 for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
897 ICOORD next_step = step(stepindex);
898 if (next_step.y() < 0) {
899 pixRasterop(pix, 0, top - pos.y(), pos.x() - left, 1,
900 PIX_NOT(PIX_DST), nullptr, 0, 0);
901 } else if (next_step.y() > 0) {
902 pixRasterop(pix, 0, top - pos.y() - 1, pos.x() - left, 1,
903 PIX_NOT(PIX_DST), nullptr, 0, 0);
904 }
905 pos += next_step;
906 }
907}
908
916void C_OUTLINE::render_outline(int left, int top, Pix* pix) const {
917 ICOORD pos = start;
918 for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
919 ICOORD next_step = step(stepindex);
920 if (next_step.y() < 0) {
921 pixSetPixel(pix, pos.x() - left, top - pos.y(), 1);
922 } else if (next_step.y() > 0) {
923 pixSetPixel(pix, pos.x() - left - 1, top - pos.y() - 1, 1);
924 } else if (next_step.x() < 0) {
925 pixSetPixel(pix, pos.x() - left - 1, top - pos.y(), 1);
926 } else if (next_step.x() > 0) {
927 pixSetPixel(pix, pos.x() - left, top - pos.y() - 1, 1);
928 }
929 pos += next_step;
930 }
931}
932
941#ifndef GRAPHICS_DISABLED
942void C_OUTLINE::plot(ScrollView* window, ScrollView::Color colour) const {
943 int16_t stepindex; // index to cstep
944 ICOORD pos; // current position
945 DIR128 stepdir; // direction of step
946
947 pos = start; // current position
948 window->Pen(colour);
949 if (stepcount == 0) {
950 window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
951 return;
952 }
953 window->SetCursor(pos.x(), pos.y());
954
955 stepindex = 0;
956 while (stepindex < stepcount) {
957 pos += step(stepindex); // step to next
958 stepdir = step_dir(stepindex);
959 stepindex++; // count steps
960 // merge straight lines
961 while (stepindex < stepcount &&
962 stepdir.get_dir() == step_dir(stepindex).get_dir()) {
963 pos += step(stepindex);
964 stepindex++;
965 }
966 window->DrawTo(pos.x(), pos.y());
967 }
968}
969
975 ScrollView* window) const {
976 window->Pen(colour);
977 if (stepcount == 0) {
978 window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
979 return;
980 }
981 const DENORM* root_denorm = denorm.RootDenorm();
982 ICOORD pos = start; // current position
983 FCOORD f_pos = sub_pixel_pos_at_index(pos, 0);
984 FCOORD pos_normed;
985 denorm.NormTransform(root_denorm, f_pos, &pos_normed);
986 window->SetCursor(IntCastRounded(pos_normed.x()),
987 IntCastRounded(pos_normed.y()));
988 for (int s = 0; s < stepcount; pos += step(s++)) {
989 int edge_weight = edge_strength_at_index(s);
990 if (edge_weight == 0) {
991 // This point has conflicting gradient and step direction, so ignore it.
992 continue;
993 }
994 FCOORD f_pos = sub_pixel_pos_at_index(pos, s);
995 FCOORD pos_normed;
996 denorm.NormTransform(root_denorm, f_pos, &pos_normed);
997 window->DrawTo(IntCastRounded(pos_normed.x()),
998 IntCastRounded(pos_normed.y()));
999 }
1000}
1001#endif
1002
1011 box = source.box;
1012 start = source.start;
1013 free(steps);
1014 stepcount = source.stepcount;
1015 steps = static_cast<uint8_t *>(malloc(step_mem()));
1016 memmove (steps, source.steps, step_mem());
1017 if (!children.empty ())
1018 children.clear ();
1019 children.deep_copy(&source.children, &deep_copy);
1020 delete [] offsets;
1021 if (source.offsets != nullptr) {
1022 offsets = new EdgeOffset[stepcount];
1023 memcpy(offsets, source.offsets, stepcount * sizeof(*offsets));
1024 } else {
1025 offsets = nullptr;
1026 }
1027 return *this;
1028}
1029
1036void C_OUTLINE::increment_step(int s, int increment, ICOORD* pos,
1037 int* dir_counts, int* pos_totals) const {
1038 int step_index = Modulo(s, stepcount);
1039 int dir_index = chain_code(step_index);
1040 dir_counts[dir_index] += increment;
1041 ICOORD step_vec = step(step_index);
1042 if (step_vec.x() == 0)
1043 pos_totals[dir_index] += pos->x() * increment;
1044 else
1045 pos_totals[dir_index] += pos->y() * increment;
1046 *pos += step_vec;
1047}
1048
1050 return step_coords[chaindir % 4];
1051}
#define INTERSECTING
Definition: coutln.h:35
@ COUT_INVERSE
Definition: coutln.h:42
#define MODULUS
Definition: mod128.h:25
#define ELISTIZE(CLASSNAME)
Definition: elst.h:931
#define ASSERT_HOST(x)
Definition: errcode.h:88
int Modulo(int a, int b)
Definition: helpers.h:158
int IntCastRounded(double x)
Definition: helpers.h:175
int count(LIST var_list)
Definition: oldlist.cpp:95
Definition: blobs.h:51
int16_t x
Definition: blobs.h:93
int16_t y
Definition: blobs.h:94
uint8_t pixel_diff
Definition: coutln.h:64
int8_t offset_numerator
Definition: coutln.h:63
uint8_t direction
Definition: coutln.h:65
bool IsLegallyNested() const
Definition: coutln.cpp:604
C_OUTLINE_LIST * child()
Definition: coutln.h:108
bool operator<(const C_OUTLINE &other) const
Definition: coutln.cpp:467
ICOORD step(int index) const
Definition: coutln.h:144
int chain_code(int index) const
Definition: coutln.h:195
void reverse()
Definition: coutln.cpp:565
void render_outline(int left, int top, Pix *pix) const
Definition: coutln.cpp:916
DIR128 step_dir(int index) const
Definition: coutln.h:139
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:261
const ICOORD & start_pos() const
Definition: coutln.h:148
int16_t winding_number(ICOORD testpt) const
Definition: coutln.cpp:500
int32_t area() const
Definition: coutln.cpp:255
int32_t perimeter() const
Definition: coutln.cpp:289
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: coutln.cpp:942
int32_t outer_area() const
Definition: coutln.cpp:308
void ComputeBinaryOffsets()
Definition: coutln.cpp:837
void ComputeEdgeOffsets(int threshold, Pix *pix)
Definition: coutln.cpp:721
int edge_strength_at_index(int index) const
Definition: coutln.h:187
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1049
void move(const ICOORD vec)
Definition: coutln.cpp:588
FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const
Definition: coutln.h:163
bool flag(C_OUTLINE_FLAGS mask) const
Definition: coutln.h:98
void RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it)
Definition: coutln.cpp:627
C_OUTLINE()
Definition: coutln.h:74
void set_step(int16_t stepindex, int8_t stepdir)
Definition: coutln.h:116
static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines)
Definition: coutln.cpp:239
int32_t pathlength() const
Definition: coutln.h:135
void render(int left, int top, Pix *pix) const
Definition: coutln.cpp:894
int32_t count_transitions(int32_t threshold)
Definition: coutln.cpp:340
int16_t turn_direction() const
Definition: coutln.cpp:537
C_OUTLINE & operator=(const C_OUTLINE &source)
Definition: coutln.cpp:1010
void plot_normed(const DENORM &denorm, ScrollView::Color colour, ScrollView *window) const
Definition: coutln.cpp:974
CRACKEDGE * next
Definition: crakedge.h:35
int8_t stepdir
Definition: crakedge.h:33
ICOORD pos
Definition: crakedge.h:30
Definition: mod128.h:30
int8_t get_dir() const
Definition: mod128.h:76
const DENORM * RootDenorm() const
Definition: normalis.h:258
void NormTransform(const DENORM *first_norm, const TPOINT &pt, TPOINT *transformed) const
Definition: normalis.cpp:335
integer coordinate
Definition: points.h:32
void set_x(int16_t xin)
rewrite function
Definition: points.h:61
int16_t y() const
access_function
Definition: points.h:56
void set_y(int16_t yin)
rewrite function
Definition: points.h:65
float angle() const
find angle
Definition: points.h:97
int16_t x() const
access function
Definition: points.h:52
void rotate(const FCOORD &vec)
Definition: points.h:536
Definition: points.h:189
uint8_t to_direction() const
Definition: points.cpp:108
static uint8_t binary_angle_plus_pi(double angle)
Definition: points.cpp:121
float y() const
Definition: points.h:210
float x() const
Definition: points.h:207
Definition: rect.h:34
void rotate(const FCOORD &vec)
Definition: rect.h:197
int16_t top() const
Definition: rect.h:58
void move(const ICOORD vec)
Definition: rect.h:157
ICOORD botright() const
Definition: rect.h:96
int16_t width() const
Definition: rect.h:115
int32_t area() const
Definition: rect.h:122
int16_t height() const
Definition: rect.h:108
bool overlap(const TBOX &box) const
Definition: rect.h:355
ICOORD topleft() const
Definition: rect.h:100
int16_t left() const
Definition: rect.h:72
int16_t bottom() const
Definition: rect.h:65
bool contains(const FCOORD pt) const
Definition: rect.h:333
int16_t right() const
Definition: rect.h:79
void DrawTo(int x, int y)
Definition: scrollview.cpp:525
void SetCursor(int x, int y)
Definition: scrollview.cpp:519
void Pen(Color color)
Definition: scrollview.cpp:719
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:600