tesseract  5.0.0-alpha-619-ge9db
polyaprx.cpp File Reference
#include "polyaprx.h"
#include <cstdint>
#include "blobs.h"
#include "coutln.h"
#include "errcode.h"
#include "mod128.h"
#include "params.h"
#include "points.h"
#include "rect.h"
#include "tprintf.h"

Go to the source code of this file.

Macros

#define FASTEDGELENGTH   256
 
#define FIXED   4 /*OUTLINE point is fixed */
 
#define RUNLENGTH   1 /*length of run */
 
#define DIR   2 /*direction of run */
 
#define FLAGS   0
 
#define fixed_dist   20
 
#define approx_dist   15
 

Functions

TESSLINEApproximateOutline (bool allow_detailed_fx, C_OUTLINE *c_outline)
 
EDGEPTedgesteps_to_edgepts (C_OUTLINE *c_outline, EDGEPT edgepts[])
 
void fix2 (EDGEPT *start, int area)
 
EDGEPTpoly2 (EDGEPT *startpt, int area)
 
void cutline (EDGEPT *first, EDGEPT *last, int area)
 

Variables

const int par1 = 4500 / (approx_dist * approx_dist)
 
const int par2 = 6750 / (approx_dist * approx_dist)
 

Macro Definition Documentation

◆ approx_dist

#define approx_dist   15

Definition at line 44 of file polyaprx.cpp.

◆ DIR

#define DIR   2 /*direction of run */

Definition at line 39 of file polyaprx.cpp.

◆ FASTEDGELENGTH

#define FASTEDGELENGTH   256

Definition at line 29 of file polyaprx.cpp.

◆ FIXED

#define FIXED   4 /*OUTLINE point is fixed */

Definition at line 35 of file polyaprx.cpp.

◆ fixed_dist

#define fixed_dist   20

Definition at line 43 of file polyaprx.cpp.

◆ FLAGS

#define FLAGS   0

Definition at line 41 of file polyaprx.cpp.

◆ RUNLENGTH

#define RUNLENGTH   1 /*length of run */

Definition at line 37 of file polyaprx.cpp.

Function Documentation

◆ ApproximateOutline()

TESSLINE* ApproximateOutline ( bool  allow_detailed_fx,
C_OUTLINE c_outline 
)

Definition at line 59 of file polyaprx.cpp.

61  {
62  TBOX loop_box; // bounding box
63  int32_t area; // loop area
64  EDGEPT stack_edgepts[FASTEDGELENGTH]; // converted path
65  EDGEPT* edgepts = stack_edgepts;
66 
67  // Use heap memory if the stack buffer is not big enough.
68  if (c_outline->pathlength() > FASTEDGELENGTH)
69  edgepts = new EDGEPT[c_outline->pathlength()];
70 
71  loop_box = c_outline->bounding_box();
72  area = loop_box.height();
73  if (!poly_wide_objects_better && loop_box.width() > area)
74  area = loop_box.width();
75  area *= area;
76  edgesteps_to_edgepts(c_outline, edgepts);
77  fix2(edgepts, area);
78  EDGEPT* edgept = poly2(edgepts, area); // 2nd approximation.
79  EDGEPT* startpt = edgept;
80  EDGEPT* result = nullptr;
81  EDGEPT* prev_result = nullptr;
82  do {
83  auto* new_pt = new EDGEPT;
84  new_pt->pos = edgept->pos;
85  new_pt->prev = prev_result;
86  if (prev_result == nullptr) {
87  result = new_pt;
88  } else {
89  prev_result->next = new_pt;
90  new_pt->prev = prev_result;
91  }
92  if (allow_detailed_fx) {
93  new_pt->src_outline = edgept->src_outline;
94  new_pt->start_step = edgept->start_step;
95  new_pt->step_count = edgept->step_count;
96  }
97  prev_result = new_pt;
98  edgept = edgept->next;
99  }
100  while (edgept != startpt);
101  prev_result->next = result;
102  result->prev = prev_result;
103  if (edgepts != stack_edgepts)
104  delete [] edgepts;

◆ cutline()

void cutline ( EDGEPT first,
EDGEPT last,
int  area 
)

Definition at line 492 of file polyaprx.cpp.

502  {
503  EDGEPT *edge; /*current edge */
504  TPOINT vecsum; /*vector sum */
505  int vlen; /*approx length of vecsum */
506  TPOINT vec; /*accumulated vector */
507  EDGEPT *maxpoint; /*worst point */
508  int maxperp; /*max deviation */
509  int perp; /*perp distance */
510  int ptcount; /*no of points */
511  int squaresum; /*sum of perps */
512 
513  edge = first; /*start of line */
514  if (edge->next == last)
515  return; /*simple line */
516 
517  /*vector sum */
518  vecsum.x = last->pos.x - edge->pos.x;
519  vecsum.y = last->pos.y - edge->pos.y;
520  if (vecsum.x == 0 && vecsum.y == 0) {
521  /*special case */
522  vecsum.x = -edge->prev->vec.x;
523  vecsum.y = -edge->prev->vec.y;
524  }
525  /*absolute value */
526  vlen = vecsum.x > 0 ? vecsum.x : -vecsum.x;
527  if (vecsum.y > vlen)
528  vlen = vecsum.y; /*maximum */
529  else if (-vecsum.y > vlen)
530  vlen = -vecsum.y; /*absolute value */
531 
532  vec.x = edge->vec.x; /*accumulated vector */
533  vec.y = edge->vec.y;
534  maxperp = 0; /*none yet */
535  squaresum = ptcount = 0;
536  edge = edge->next; /*move to actual point */
537  maxpoint = edge; /*in case there isn't one */
538  do {
539  perp = vec.cross(vecsum); // get perp distance
540  if (perp != 0) {
541  perp *= perp; /*squared deviation */
542  }
543  squaresum += perp; /*sum squares */
544  ptcount++; /*count points */
545  if (poly_debug)
546  tprintf ("Cutline:Final perp=%d\n", perp);
547  if (perp > maxperp) {
548  maxperp = perp;
549  maxpoint = edge; /*find greatest deviation */
550  }
551  vec.x += edge->vec.x; /*accumulate vectors */
552  vec.y += edge->vec.y;
553  edge = edge->next;
554  }
555  while (edge != last); /*test all line */
556 
557  perp = vecsum.length();
558  ASSERT_HOST (perp != 0);
559 
560  if (maxperp < 256 * INT16_MAX) {
561  maxperp <<= 8;
562  maxperp /= perp; /*true max perp */
563  }
564  else {
565  maxperp /= perp;
566  maxperp <<= 8; /*avoid overflow */
567  }
568  if (squaresum < 256 * INT16_MAX)
569  /*mean squared perp */
570  perp = (squaresum << 8) / (perp * ptcount);
571  else
572  /*avoid overflow */
573  perp = (squaresum / perp << 8) / ptcount;
574 
575  if (poly_debug)
576  tprintf ("Cutline:A=%d, max=%.2f(%.2f%%), msd=%.2f(%.2f%%)\n",
577  area, maxperp / 256.0, maxperp * 200.0 / area,
578  perp / 256.0, perp * 300.0 / area);
579  if (maxperp * par1 >= 10 * area || perp * par2 >= 10 * area || vlen >= 126) {

◆ edgesteps_to_edgepts()

EDGEPT* edgesteps_to_edgepts ( C_OUTLINE c_outline,
EDGEPT  edgepts[] 
)

Definition at line 113 of file polyaprx.cpp.

119  {
120  int32_t length; //steps in path
121  ICOORD pos; //current coords
122  int32_t stepindex; //current step
123  int32_t stepinc; //increment
124  int32_t epindex; //current EDGEPT
125  int32_t count; //repeated steps
126  ICOORD vec; //for this 8 step
127  ICOORD prev_vec;
128  int8_t epdir; //of this step
129  DIR128 prevdir; //prvious dir
130  DIR128 dir; //of this step
131 
132  pos = c_outline->start_pos (); //start of loop
133  length = c_outline->pathlength ();
134  stepindex = 0;
135  epindex = 0;
136  prevdir = -1;
137  count = 0;
138  int prev_stepindex = 0;
139  do {
140  dir = c_outline->step_dir (stepindex);
141  vec = c_outline->step (stepindex);
142  if (stepindex < length - 1
143  && c_outline->step_dir (stepindex + 1) - dir == -32) {
144  dir += 128 - 16;
145  vec += c_outline->step (stepindex + 1);
146  stepinc = 2;
147  }
148  else
149  stepinc = 1;
150  if (count == 0) {
151  prevdir = dir;
152  prev_vec = vec;
153  }
154  if (prevdir.get_dir () != dir.get_dir ()) {
155  edgepts[epindex].pos.x = pos.x ();
156  edgepts[epindex].pos.y = pos.y ();
157  prev_vec *= count;
158  edgepts[epindex].vec.x = prev_vec.x ();
159  edgepts[epindex].vec.y = prev_vec.y ();
160  pos += prev_vec;
161  edgepts[epindex].flags[RUNLENGTH] = count;
162  edgepts[epindex].prev = &edgepts[epindex - 1];
163  edgepts[epindex].flags[FLAGS] = 0;
164  edgepts[epindex].next = &edgepts[epindex + 1];
165  prevdir += 64;
166  epdir = DIR128(0) - prevdir;
167  epdir >>= 4;
168  epdir &= 7;
169  edgepts[epindex].flags[DIR] = epdir;
170  edgepts[epindex].src_outline = c_outline;
171  edgepts[epindex].start_step = prev_stepindex;
172  edgepts[epindex].step_count = stepindex - prev_stepindex;
173  epindex++;
174  prevdir = dir;
175  prev_vec = vec;
176  count = 1;
177  prev_stepindex = stepindex;
178  }
179  else
180  count++;
181  stepindex += stepinc;
182  }
183  while (stepindex < length);
184  edgepts[epindex].pos.x = pos.x ();
185  edgepts[epindex].pos.y = pos.y ();
186  prev_vec *= count;
187  edgepts[epindex].vec.x = prev_vec.x ();
188  edgepts[epindex].vec.y = prev_vec.y ();
189  pos += prev_vec;
190  edgepts[epindex].flags[RUNLENGTH] = count;
191  edgepts[epindex].flags[FLAGS] = 0;
192  edgepts[epindex].src_outline = c_outline;
193  edgepts[epindex].start_step = prev_stepindex;
194  edgepts[epindex].step_count = stepindex - prev_stepindex;
195  edgepts[epindex].prev = &edgepts[epindex - 1];
196  edgepts[epindex].next = &edgepts[0];
197  prevdir += 64;
198  epdir = DIR128(0) - prevdir;
199  epdir >>= 4;
200  epdir &= 7;
201  edgepts[epindex].flags[DIR] = epdir;
202  edgepts[0].prev = &edgepts[epindex];
203  ASSERT_HOST (pos.x () == c_outline->start_pos ().x ()

◆ fix2()

void fix2 ( EDGEPT start,
int  area 
)

Definition at line 211 of file polyaprx.cpp.

217  {
218  EDGEPT *edgept; /*current point */
219  EDGEPT *edgept1;
220  EDGEPT *loopstart; /*modified start of loop */
221  EDGEPT *linestart; /*start of line segment */
222  int dir1, dir2; /*directions of line */
223  int sum1, sum2; /*lengths in dir1,dir2 */
224  int stopped; /*completed flag */
225  int fixed_count; //no of fixed points
226  int d01, d12, d23, gapmin;
227  TPOINT d01vec, d12vec, d23vec;
228  EDGEPT *edgefix, *startfix;
229  EDGEPT *edgefix0, *edgefix1, *edgefix2, *edgefix3;
230 
231  edgept = start; /*start of loop */
232  while (((edgept->flags[DIR] - edgept->prev->flags[DIR] + 1) & 7) < 3
233  && (dir1 =
234  (edgept->prev->flags[DIR] - edgept->next->flags[DIR]) & 7) != 2
235  && dir1 != 6)
236  edgept = edgept->next; /*find suitable start */
237  loopstart = edgept; /*remember start */
238 
239  stopped = 0; /*not finished yet */
240  edgept->flags[FLAGS] |= FIXED; /*fix it */
241  do {
242  linestart = edgept; /*possible start of line */
243  dir1 = edgept->flags[DIR]; /*first direction */
244  /*length of dir1 */
245  sum1 = edgept->flags[RUNLENGTH];
246  edgept = edgept->next;
247  dir2 = edgept->flags[DIR]; /*2nd direction */
248  /*length in dir2 */
249  sum2 = edgept->flags[RUNLENGTH];
250  if (((dir1 - dir2 + 1) & 7) < 3) {
251  while (edgept->prev->flags[DIR] == edgept->next->flags[DIR]) {
252  edgept = edgept->next; /*look at next */
253  if (edgept->flags[DIR] == dir1)
254  /*sum lengths */
255  sum1 += edgept->flags[RUNLENGTH];
256  else
257  sum2 += edgept->flags[RUNLENGTH];
258  }
259 
260  if (edgept == loopstart)
261  stopped = 1; /*finished */
262  if (sum2 + sum1 > 2
263  && linestart->prev->flags[DIR] == dir2
264  && (linestart->prev->flags[RUNLENGTH] >
265  linestart->flags[RUNLENGTH] || sum2 > sum1)) {
266  /*start is back one */
267  linestart = linestart->prev;
268  linestart->flags[FLAGS] |= FIXED;
269  }
270 
271  if (((edgept->next->flags[DIR] - edgept->flags[DIR] + 1) & 7) >= 3
272  || (edgept->flags[DIR] == dir1 && sum1 >= sum2)
273  || ((edgept->prev->flags[RUNLENGTH] < edgept->flags[RUNLENGTH]
274  || (edgept->flags[DIR] == dir2 && sum2 >= sum1))
275  && linestart->next != edgept))
276  edgept = edgept->next;
277  }
278  /*sharp bend */
279  edgept->flags[FLAGS] |= FIXED;
280  }
281  /*do whole loop */
282  while (edgept != loopstart && !stopped);
283 
284  edgept = start;
285  do {
286  if (((edgept->flags[RUNLENGTH] >= 8) &&
287  (edgept->flags[DIR] != 2) && (edgept->flags[DIR] != 6)) ||
288  ((edgept->flags[RUNLENGTH] >= 8) &&
289  ((edgept->flags[DIR] == 2) || (edgept->flags[DIR] == 6)))) {
290  edgept->flags[FLAGS] |= FIXED;
291  edgept1 = edgept->next;
292  edgept1->flags[FLAGS] |= FIXED;
293  }
294  edgept = edgept->next;
295  }
296  while (edgept != start);
297 
298  edgept = start;
299  do {
300  /*single fixed step */
301  if (edgept->flags[FLAGS] & FIXED && edgept->flags[RUNLENGTH] == 1
302  /*and neighours free */
303  && edgept->next->flags[FLAGS] & FIXED && (edgept->prev->flags[FLAGS] & FIXED) == 0
304  /*same pair of dirs */
305  && (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]
306  && ((edgept->prev->flags[DIR] - edgept->flags[DIR] + 1) & 7) < 3) {
307  /*unfix it */
308  edgept->flags[FLAGS] &= ~FIXED;
309  edgept->next->flags[FLAGS] &= ~FIXED;
310  }
311  edgept = edgept->next; /*do all points */
312  }
313  while (edgept != start); /*until finished */
314 
315  stopped = 0;
316  if (area < 450)
317  area = 450;
318 
319  gapmin = area * fixed_dist * fixed_dist / 44000;
320 
321  edgept = start;
322  fixed_count = 0;
323  do {
324  if (edgept->flags[FLAGS] & FIXED)
325  fixed_count++;
326  edgept = edgept->next;
327  }
328  while (edgept != start);
329  while ((edgept->flags[FLAGS] & FIXED) == 0)
330  edgept = edgept->next;
331  edgefix0 = edgept;
332 
333  edgept = edgept->next;
334  while ((edgept->flags[FLAGS] & FIXED) == 0)
335  edgept = edgept->next;
336  edgefix1 = edgept;
337 
338  edgept = edgept->next;
339  while ((edgept->flags[FLAGS] & FIXED) == 0)
340  edgept = edgept->next;
341  edgefix2 = edgept;
342 
343  edgept = edgept->next;
344  while ((edgept->flags[FLAGS] & FIXED) == 0)
345  edgept = edgept->next;
346  edgefix3 = edgept;
347 
348  startfix = edgefix2;
349 
350  do {
351  if (fixed_count <= 3)
352  break; //already too few
353  d12vec.diff(edgefix1->pos, edgefix2->pos);
354  d12 = d12vec.length();
355  // TODO(rays) investigate this change:
356  // Only unfix a point if it is part of a low-curvature section
357  // of outline and the total angle change of the outlines is
358  // less than 90 degrees, ie the scalar product is positive.
359  // if (d12 <= gapmin && edgefix0->vec.dot(edgefix2->vec) > 0) {
360  if (d12 <= gapmin) {
361  d01vec.diff(edgefix0->pos, edgefix1->pos);
362  d01 = d01vec.length();
363  d23vec.diff(edgefix2->pos, edgefix3->pos);
364  d23 = d23vec.length();
365  if (d01 > d23) {
366  edgefix2->flags[FLAGS] &= ~FIXED;
367  fixed_count--;
368  }
369  else {
370  edgefix1->flags[FLAGS] &= ~FIXED;
371  fixed_count--;
372  edgefix1 = edgefix2;
373  }
374  }
375  else {
376  edgefix0 = edgefix1;
377  edgefix1 = edgefix2;
378  }
379  edgefix2 = edgefix3;
380  edgept = edgept->next;
381  while ((edgept->flags[FLAGS] & FIXED) == 0) {
382  if (edgept == startfix)
383  stopped = 1;
384  edgept = edgept->next;
385  }
386  edgefix3 = edgept;

◆ poly2()

EDGEPT* poly2 ( EDGEPT startpt,
int  area 
)

Definition at line 395 of file polyaprx.cpp.

403  {
404  EDGEPT *edgept; /*current outline point */
405  EDGEPT *loopstart; /*starting point */
406  EDGEPT *linestart; /*start of line */
407  int edgesum; /*correction count */
408 
409  if (area < 1200)
410  area = 1200; /*minimum value */
411 
412  loopstart = nullptr; /*not found it yet */
413  edgept = startpt; /*start of loop */
414 
415  do {
416  /*current point fixed */
417  if (edgept->flags[FLAGS] & FIXED
418  /*and next not */
419  && (edgept->next->flags[FLAGS] & FIXED) == 0) {
420  loopstart = edgept; /*start of repoly */
421  break;
422  }
423  edgept = edgept->next; /*next point */
424  }
425  while (edgept != startpt); /*until found or finished */
426 
427  if (loopstart == nullptr && (startpt->flags[FLAGS] & FIXED) == 0) {
428  /*fixed start of loop */
429  startpt->flags[FLAGS] |= FIXED;
430  loopstart = startpt; /*or start of loop */
431  }
432  if (loopstart) {
433  do {
434  edgept = loopstart; /*first to do */
435  do {
436  linestart = edgept;
437  edgesum = 0; /*sum of lengths */
438  do {
439  /*sum lengths */
440  edgesum += edgept->flags[RUNLENGTH];
441  edgept = edgept->next; /*move on */
442  }
443  while ((edgept->flags[FLAGS] & FIXED) == 0
444  && edgept != loopstart && edgesum < 126);
445  if (poly_debug)
446  tprintf
447  ("Poly2:starting at (%d,%d)+%d=(%d,%d),%d to (%d,%d)\n",
448  linestart->pos.x, linestart->pos.y, linestart->flags[DIR],
449  linestart->vec.x, linestart->vec.y, edgesum, edgept->pos.x,
450  edgept->pos.y);
451  /*reapproximate */
452  cutline(linestart, edgept, area);
453 
454  while ((edgept->next->flags[FLAGS] & FIXED)
455  && edgept != loopstart)
456  edgept = edgept->next; /*look for next non-fixed */
457  }
458  /*do all the loop */
459  while (edgept != loopstart);
460  edgesum = 0;
461  do {
462  if (edgept->flags[FLAGS] & FIXED)
463  edgesum++;
464  edgept = edgept->next;
465  }
466  //count fixed pts
467  while (edgept != loopstart);
468  if (edgesum < 3)
469  area /= 2; //must have 3 pts
470  }
471  while (edgesum < 3);
472  do {
473  linestart = edgept;
474  do {
475  edgept = edgept->next;
476  }
477  while ((edgept->flags[FLAGS] & FIXED) == 0);
478  linestart->next = edgept;
479  edgept->prev = linestart;
480  linestart->vec.x = edgept->pos.x - linestart->pos.x;
481  linestart->vec.y = edgept->pos.y - linestart->pos.y;
482  }
483  while (edgept != loopstart);
484  }
485  else

Variable Documentation

◆ par1

const int par1 = 4500 / (approx_dist * approx_dist)

Definition at line 46 of file polyaprx.cpp.

◆ par2

const int par2 = 6750 / (approx_dist * approx_dist)

Definition at line 47 of file polyaprx.cpp.

TPOINT
Definition: blobs.h:49
par1
const int par1
Definition: polyaprx.cpp:46
FIXED
#define FIXED
Definition: polyaprx.cpp:35
DIR128
Definition: mod128.h:28
EDGEPT::src_outline
C_OUTLINE * src_outline
Definition: blobs.h:192
RUNLENGTH
#define RUNLENGTH
Definition: polyaprx.cpp:37
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
par2
const int par2
Definition: polyaprx.cpp:47
EDGEPT::step_count
int step_count
Definition: blobs.h:195
ICOORD
integer coordinate
Definition: points.h:30
TPOINT::length
int length() const
Definition: blobs.h:87
edgesteps_to_edgepts
EDGEPT * edgesteps_to_edgepts(C_OUTLINE *c_outline, EDGEPT edgepts[])
Definition: polyaprx.cpp:113
cutline
void cutline(EDGEPT *first, EDGEPT *last, int area)
Definition: polyaprx.cpp:492
DIR
#define DIR
Definition: polyaprx.cpp:39
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
TBOX::height
int16_t height() const
Definition: rect.h:107
EDGEPT::prev
EDGEPT * prev
Definition: blobs.h:191
EDGEPT::start_step
int start_step
Definition: blobs.h:194
fixed_dist
#define fixed_dist
Definition: polyaprx.cpp:43
last
LIST last(LIST var_list)
Definition: oldlist.cpp:151
FASTEDGELENGTH
#define FASTEDGELENGTH
Definition: polyaprx.cpp:29
TPOINT::x
int16_t x
Definition: blobs.h:91
C_OUTLINE::step_dir
DIR128 step_dir(int index) const
Definition: coutln.h:138
TPOINT::y
int16_t y
Definition: blobs.h:92
TBOX::width
int16_t width() const
Definition: rect.h:114
TPOINT::diff
void diff(const TPOINT &p1, const TPOINT &p2)
Definition: blobs.h:71
EDGEPT::vec
VECTOR vec
Definition: blobs.h:185
FLAGS
#define FLAGS
Definition: polyaprx.cpp:41
EDGEPT::flags
char flags[EDGEPTFLAGS]
Definition: blobs.h:189
TPOINT::cross
int cross(const TPOINT &other) const
Definition: blobs.h:77
count
int count(LIST var_list)
Definition: oldlist.cpp:79
C_OUTLINE::bounding_box
const TBOX & bounding_box() const
Definition: coutln.h:112
DIR128::get_dir
int8_t get_dir() const
Definition: mod128.h:75
EDGEPT
Definition: blobs.h:97
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:34
poly2
EDGEPT * poly2(EDGEPT *startpt, int area)
Definition: polyaprx.cpp:395
C_OUTLINE::pathlength
int32_t pathlength() const
Definition: coutln.h:134
C_OUTLINE::step
ICOORD step(int index) const
Definition: coutln.h:143
EDGEPT::pos
TPOINT pos
Definition: blobs.h:184
C_OUTLINE::start_pos
const ICOORD & start_pos() const
Definition: coutln.h:147
EDGEPT::next
EDGEPT * next
Definition: blobs.h:190
fix2
void fix2(EDGEPT *start, int area)
Definition: polyaprx.cpp:211
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
TBOX
Definition: rect.h:33