21# include "config_auto.h"
26#include "arrayaccess.h"
35#include <allheaders.h>
45ICOORD C_OUTLINE::step_coords[4] = {ICOORD(-1, 0), ICOORD(0, -1), ICOORD(1, 0), ICOORD(0, 1)};
58 : box(bot_left, top_right), start(startpt->pos), offsets(nullptr) {
67 steps.resize(step_mem());
70 for (stepindex = 0; stepindex < length; stepindex++) {
73 edgept = edgept->
next;
88 : start(startpt), offsets(nullptr) {
101 steps.resize(step_mem());
103 lastdir = new_steps[length - 1];
105 for (stepindex = 0, srcindex = 0; srcindex < length; stepindex++, srcindex++) {
106 new_box =
TBOX(pos, pos);
109 dir = new_steps[srcindex];
111 dirdiff = dir - prevdir;
112 pos +=
step(stepindex);
113 if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
115 prevdir = stepindex >= 0 ?
step_dir(stepindex) : lastdir;
123 if (dirdiff == 64 || dirdiff == -64) {
126 for (
int i = 0;
i < stepindex; ++
i) {
130 }
while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
131 stepcount = stepindex;
151 int16_t destindex = INT16_MAX;
155 stepcount = srcline->stepcount * 2;
156 if (stepcount == 0) {
162 steps.resize(step_mem());
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;
171 box =
TBOX(start, start);
173 for (stepindex = 0; stepindex < srcline->stepcount; stepindex++) {
174 pos += srcline->
step(stepindex);
178 while (destpos.
x() != prevpos.
x() || destpos.
y() != prevpos.
y()) {
184 set_step(destindex++, dir + round1);
185 prevpos +=
step(destindex - 1);
189 set_step(destindex++, dir + round2);
190 prevpos +=
step(destindex - 1);
192 prevpos -=
step(destindex - 1);
194 prevpos -=
step(destindex - 1);
195 set_step(destindex - 1, dir + round2);
196 prevpos +=
step(destindex - 1);
200 prevpos +=
step(destindex - 1);
202 while (destindex >= 2 &&
205 prevpos -=
step(destindex - 1);
206 prevpos -=
step(destindex - 2);
211 new_box =
TBOX(destpos, destpos);
216 while (destindex > 1) {
218 if (dirdiff != 64 && dirdiff != -64) {
223 for (
int i = 0;
i < destindex; ++
i) {
227 if (destindex >= 4) {
232 stepcount = destindex;
234 for (stepindex = 0; stepindex < stepcount; stepindex++) {
235 destpos +=
step(stepindex);
242 C_OUTLINE_IT ol_it(outlines);
248 ol_it.add_to_end(outline);
265 C_OUTLINE_IT it(
const_cast<C_OUTLINE_LIST *
>(&children));
270 for (stepindex = 0; stepindex < total_steps; stepindex++) {
272 next_step =
step(stepindex);
273 if (next_step.
x() < 0) {
275 }
else if (next_step.
x() > 0) {
280 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
281 total += it.data()->area();
297 C_OUTLINE_IT it(
const_cast<C_OUTLINE_LIST *
>(&children));
300 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
301 total_steps += it.data()->pathlength();
322 if (total_steps == 0) {
326 for (stepindex = 0; stepindex < total_steps; stepindex++) {
328 next_step =
step(stepindex);
329 if (next_step.
x() < 0) {
331 }
else if (next_step.
x() > 0) {
348 bool first_was_max_x;
349 bool first_was_max_y;
350 bool looking_for_max_x;
351 bool looking_for_min_x;
352 bool looking_for_max_y;
353 bool looking_for_min_y;
357 int32_t max_x, min_x, max_y, min_y;
358 int32_t initial_x, initial_y;
366 max_x = min_x = pos.
x();
367 max_y = min_y = pos.
y();
368 looking_for_max_x =
true;
369 looking_for_min_x =
true;
370 looking_for_max_y =
true;
371 looking_for_min_y =
true;
372 first_was_max_x =
false;
373 first_was_max_y =
false;
376 for (stepindex = 0; stepindex < total_steps; stepindex++) {
378 next_step =
step(stepindex);
380 if (next_step.
x() < 0) {
381 if (looking_for_max_x && pos.
x() < min_x) {
384 if (looking_for_min_x && max_x - pos.
x() > threshold) {
385 if (looking_for_max_x) {
387 first_was_max_x =
false;
390 looking_for_max_x =
true;
391 looking_for_min_x =
false;
394 }
else if (next_step.
x() > 0) {
395 if (looking_for_min_x && pos.
x() > max_x) {
398 if (looking_for_max_x && pos.
x() - min_x > threshold) {
399 if (looking_for_min_x) {
401 first_was_max_x =
true;
404 looking_for_max_x =
false;
405 looking_for_min_x =
true;
408 }
else if (next_step.
y() < 0) {
409 if (looking_for_max_y && pos.
y() < min_y) {
412 if (looking_for_min_y && max_y - pos.
y() > threshold) {
413 if (looking_for_max_y) {
415 first_was_max_y =
false;
418 looking_for_max_y =
true;
419 looking_for_min_y =
false;
423 if (looking_for_min_y && pos.
y() > max_y) {
426 if (looking_for_max_y && pos.
y() - min_y > threshold) {
427 if (looking_for_min_y) {
429 first_was_max_y =
true;
432 looking_for_max_y =
false;
433 looking_for_min_y =
true;
438 if (first_was_max_x && looking_for_min_x) {
439 if (max_x - initial_x > threshold) {
444 }
else if (!first_was_max_x && looking_for_max_x) {
445 if (initial_x - min_x > threshold) {
451 if (first_was_max_y && looking_for_min_y) {
452 if (max_y - initial_y > threshold) {
457 }
else if (!first_was_max_y && looking_for_max_y) {
458 if (initial_y - min_y > threshold) {
483 if (stepcount == 0) {
484 return other.box.
contains(this->box);
490 pos +=
step(stepindex);
499 pos += other.
step(stepindex);
522 for (stepindex = 0; stepindex < stepcount; stepindex++) {
523 stepvec =
step(stepindex);
525 if (vec.
y() <= 0 && vec.
y() + stepvec.
y() > 0) {
526 cross = vec * stepvec;
529 }
else if (cross == 0) {
532 }
else if (vec.
y() > 0 && vec.
y() + stepvec.
y() <= 0) {
533 cross = vec * stepvec;
536 }
else if (cross == 0) {
558 if (stepcount == 0) {
563 for (stepindex = 0; stepindex < stepcount; stepindex++) {
565 dirdiff = dir - prevdir;
566 ASSERT_HOST(dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
587 halfsteps = (stepcount + 1) / 2;
588 for (stepindex = 0; stepindex < halfsteps; stepindex++) {
589 farindex = stepcount - stepindex - 1;
592 set_step(farindex, stepdir + halfturn);
604 C_OUTLINE_IT it(&children);
609 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
610 it.data()->move(vec);
621 if (stepcount == 0) {
627 C_OUTLINE_IT child_it(
const_cast<C_OUTLINE_LIST *
>(&children));
628 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
630 if (
child->outer_area() * parent_area > 0 || !
child->IsLegallyNested()) {
647 if (box.
width() < min_size || box.
height() < min_size) {
649 delete it->extract();
650 }
else if (!children.empty()) {
652 C_OUTLINE_IT child_it(&children);
653 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
655 child->RemoveSmallRecursive(min_size, &child_it);
669static void ComputeGradient(
const l_uint32 *data,
int wpl,
int x,
int y,
int width,
int height,
671 const l_uint32 *line = data +
y * wpl;
672 int pix_x_y =
x < width &&
y < height ? GET_DATA_BYTE(line,
x) : 255;
673 int pix_x_prevy = x < width && y > 0 ? GET_DATA_BYTE(line - wpl,
x) : 255;
674 int pix_prevx_prevy =
x > 0 &&
y > 0 ? GET_DATA_BYTE(line - wpl,
x - 1) : 255;
675 int pix_prevx_y =
x > 0 &&
y < height ? GET_DATA_BYTE(line,
x - 1) : 255;
676 gradient->
set_x(pix_x_y + pix_x_prevy - (pix_prevx_y + pix_prevx_prevy));
677 gradient->
set_y(pix_x_prevy + pix_prevx_prevy - (pix_x_y + pix_prevx_y));
685static bool EvaluateVerticalDiff(
const l_uint32 *data,
int wpl,
int diff_sign,
int x,
int y,
686 int height,
int *best_diff,
int *best_sum,
int *best_y) {
687 if (y <= 0 || y >= height) {
690 const l_uint32 *line = data +
y * wpl;
691 int pixel1 = GET_DATA_BYTE(line - wpl,
x);
692 int pixel2 = GET_DATA_BYTE(line,
x);
693 int diff = (pixel2 - pixel1) * diff_sign;
694 if (diff > *best_diff) {
696 *best_sum = pixel1 + pixel2;
707static bool EvaluateHorizontalDiff(
const l_uint32 *line,
int diff_sign,
int x,
int width,
708 int *best_diff,
int *best_sum,
int *best_x) {
709 if (x <= 0 || x >= width) {
712 int pixel1 = GET_DATA_BYTE(line,
x - 1);
713 int pixel2 = GET_DATA_BYTE(line,
x);
714 int diff = (pixel2 - pixel1) * diff_sign;
715 if (diff > *best_diff) {
717 *best_sum = pixel1 + pixel2;
739 if (pixGetDepth(pix) != 8) {
742 const l_uint32 *data = pixGetData(pix);
743 int wpl = pixGetWpl(pix);
744 int width = pixGetWidth(pix);
745 int height = pixGetHeight(pix);
751 ComputeGradient(data, wpl, pos.
x(), height - pos.
y(), width, height, &prev_gradient);
752 for (
int s = 0; s < stepcount; ++s) {
758 ComputeGradient(data, wpl, pos.
x(), height - pos.
y(), width, height, &next_gradient);
760 ICOORD gradient = prev_gradient + next_gradient;
767 if (pt1.
y == pt2.
y && abs(gradient.
y()) * 2 >= abs(gradient.
x())) {
769 int diff_sign = (pt1.
x > pt2.
x) == negative ? 1 : -1;
770 int x = std::min(pt1.
x, pt2.
x);
771 int y = height - pt1.
y;
774 EvaluateVerticalDiff(data, wpl, diff_sign,
x,
y, height, &best_diff, &best_sum, &best_y);
779 }
while (EvaluateVerticalDiff(data, wpl, diff_sign,
x, test_y, height, &best_diff, &best_sum,
784 }
while (EvaluateVerticalDiff(data, wpl, diff_sign,
x, test_y, height, &best_diff, &best_sum,
786 offset = diff_sign * (best_sum / 2 - threshold) + (
y - best_y) * best_diff;
787 }
else if (pt1.
x == pt2.
x && abs(gradient.
x()) * 2 >= abs(gradient.
y())) {
789 int diff_sign = (pt1.
y > pt2.
y) == negative ? 1 : -1;
791 int y = height - std::max(pt1.
y, pt2.
y);
792 const l_uint32 *line = pixGetData(pix) +
y * wpl;
795 EvaluateHorizontalDiff(line, diff_sign,
x, width, &best_diff, &best_sum, &best_x);
801 EvaluateHorizontalDiff(line, diff_sign, test_x, width, &best_diff, &best_sum, &best_x));
806 EvaluateHorizontalDiff(line, diff_sign, test_x, width, &best_diff, &best_sum, &best_x));
807 offset = diff_sign * (threshold - best_sum / 2) + (best_x -
x) * best_diff;
809 offsets[s].
offset_numerator = ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
810 offsets[s].
pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
812 gradient = -gradient;
817 prev_gradient = next_gradient;
858 memset(dir_counts, 0,
sizeof(dir_counts));
859 memset(pos_totals, 0,
sizeof(pos_totals));
864 tail_pos -=
step(stepcount - 1);
865 tail_pos -=
step(stepcount - 2);
868 ICOORD head_pos = tail_pos;
870 for (
int s = -2; s < 2; ++s) {
871 increment_step(s, 1, &head_pos, dir_counts, pos_totals);
873 for (
int s = 0; s < stepcount; pos +=
step(s++)) {
875 increment_step(s + 2, 1, &head_pos, dir_counts, pos_totals);
882 if (dir_counts[dir_index] >= 2 ||
883 (dir_counts[dir_index] == 1 && dir_counts[
Modulo(dir_index - 1, 4)] == 2 &&
884 dir_counts[
Modulo(dir_index + 1, 4)] == 2)) {
886 best_diff = dir_counts[dir_index];
887 int edge_pos = step_vec.
x() == 0 ? pos.
x() : pos.
y();
891 offset = pos_totals[dir_index] - best_diff * edge_pos;
893 offsets[s].
offset_numerator = ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
894 offsets[s].
pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
896 FCOORD direction(head_pos.
x() - tail_pos.
x(), head_pos.
y() - tail_pos.
y());
898 increment_step(s - 2, -1, &tail_pos, dir_counts, pos_totals);
908 for (
int stepindex = 0; stepindex < stepcount; ++stepindex) {
910 if (next_step.
y() < 0) {
911 pixRasterop(pix, 0, top - pos.
y(), pos.
x() - left, 1, PIX_NOT(PIX_DST),
nullptr, 0, 0);
912 }
else if (next_step.
y() > 0) {
913 pixRasterop(pix, 0, top - pos.
y() - 1, pos.
x() - left, 1, PIX_NOT(PIX_DST),
nullptr, 0, 0);
928 for (
int stepindex = 0; stepindex < stepcount; ++stepindex) {
930 if (next_step.
y() < 0) {
931 pixSetPixel(pix, pos.
x() - left, top - pos.
y(), 1);
932 }
else if (next_step.
y() > 0) {
933 pixSetPixel(pix, pos.
x() - left - 1, top - pos.
y() - 1, 1);
934 }
else if (next_step.
x() < 0) {
935 pixSetPixel(pix, pos.
x() - left - 1, top - pos.
y(), 1);
936 }
else if (next_step.
x() > 0) {
937 pixSetPixel(pix, pos.
x() - left, top - pos.
y() - 1, 1);
951#ifndef GRAPHICS_DISABLED
959 if (stepcount == 0) {
966 while (stepindex < stepcount) {
967 pos +=
step(stepindex);
971 while (stepindex < stepcount && stepdir.
get_dir() ==
step_dir(stepindex).get_dir()) {
972 pos +=
step(stepindex);
986 if (stepcount == 0) {
996 for (
int s = 0; s < stepcount; pos +=
step(s++)) {
998 if (edge_weight == 0) {
1019 start = source.start;
1020 if (!children.empty()) {
1023 children.deep_copy(&source.children, &
deep_copy);
1026 stepcount = source.stepcount;
1027 if (stepcount > 0) {
1028 steps.resize(step_mem());
1029 memmove(&steps[0], &source.steps[0], step_mem());
1030 if (source.offsets !=
nullptr) {
1032 memcpy(offsets, source.offsets, stepcount *
sizeof(*offsets));
1044void C_OUTLINE::increment_step(
int s,
int increment,
ICOORD *pos,
int *dir_counts,
1045 int *pos_totals)
const {
1046 int step_index =
Modulo(s, stepcount);
1048 dir_counts[dir_index] += increment;
1050 if (step_vec.
x() == 0) {
1051 pos_totals[dir_index] += pos->
x() * increment;
1053 pos_totals[dir_index] += pos->
y() * increment;
1059 return step_coords[chaindir % 4];
int IntCastRounded(double x)
static ICOORD chain_step(int chaindir)
int32_t pathlength() const
void set_step(int16_t stepindex, int8_t stepdir)
C_OUTLINE & operator=(const C_OUTLINE &source)
bool IsLegallyNested() const
ICOORD step(int index) const
void plot(ScrollView *window, ScrollView::Color colour) const
int32_t perimeter() const
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
void move(const ICOORD vec)
int16_t turn_direction() const
int16_t winding_number(ICOORD testpt) const
DIR128 step_dir(int index) const
int32_t outer_area() const
void ComputeBinaryOffsets()
int chain_code(int index) const
void plot_normed(const DENORM &denorm, ScrollView::Color colour, ScrollView *window) const
void render_outline(int left, int top, Image pix) const
bool operator<(const C_OUTLINE &other) const
FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const
int32_t count_transitions(int32_t threshold)
void RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it)
int edge_strength_at_index(int index) const
static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines)
const ICOORD & start_pos() const
void ComputeEdgeOffsets(int threshold, Image pix)
bool flag(C_OUTLINE_FLAGS mask) const
void render(int left, int top, Image pix) const
void NormTransform(const DENORM *first_norm, const TPOINT &pt, TPOINT *transformed) const
const DENORM * RootDenorm() const
void rotate(const FCOORD &vec)
void set_x(TDimension xin)
rewrite function
TDimension y() const
access_function
void set_y(TDimension yin)
rewrite function
TDimension x() const
access function
float angle() const
find angle
uint8_t to_direction() const
static uint8_t binary_angle_plus_pi(double angle)
TDimension height() const
void move(const ICOORD vec)
void rotate(const FCOORD &vec)
bool overlap(const TBOX &box) const
TDimension bottom() const
bool contains(const FCOORD pt) const
void Rectangle(int x1, int y1, int x2, int y2)
void SetCursor(int x, int y)
void DrawTo(int x, int y)