Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
outlines.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: outlines.c (Formerly outlines.c)
5  * Description: Combinatorial Splitter
6  * Author: Mark Seaman, OCR Technology
7  * Created: Thu Jul 27 08:59:01 1989
8  * Modified: Wed Jul 10 14:56:49 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Experimental (Do Not Distribute)
12  *
13  * (c) Copyright 1989, Hewlett-Packard Company.
14  ** Licensed under the Apache License, Version 2.0 (the "License");
15  ** you may not use this file except in compliance with the License.
16  ** You may obtain a copy of the License at
17  ** http://www.apache.org/licenses/LICENSE-2.0
18  ** Unless required by applicable law or agreed to in writing, software
19  ** distributed under the License is distributed on an "AS IS" BASIS,
20  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21  ** See the License for the specific language governing permissions and
22  ** limitations under the License.
23  *
24  ********************************************************************************
25  * Revision 1.2 89/09/15 09:24:41 09:24:41 marks (Mark Seaman)
26  * First released version of Combinatorial splitter code
27 **/
28 /*----------------------------------------------------------------------
29  I n c l u d e s
30 ----------------------------------------------------------------------*/
31 #include "outlines.h"
32 #include "wordrec.h"
33 
34 #ifdef __UNIX__
35 #include <assert.h>
36 #endif
37 
38 namespace tesseract {
39 /*----------------------------------------------------------------------
40  F u n c t i o n s
41 ----------------------------------------------------------------------*/
42 /**********************************************************************
43  * crosses_outline
44  *
45  * Check to see if this line crosses over this outline. If it does
46  * return TRUE.
47  **********************************************************************/
48 int Wordrec::crosses_outline(EDGEPT *p0, /* Start of line */
49  EDGEPT *p1, /* End of line */
50  EDGEPT *outline) { /* Outline to check */
51  EDGEPT *pt = outline;
52  do {
53  if (is_crossed (p0->pos, p1->pos, pt->pos, pt->next->pos))
54  return (TRUE);
55  pt = pt->next;
56  }
57  while (pt != outline);
58  return (FALSE);
59 }
60 
61 
62 /**********************************************************************
63  * is_crossed
64  *
65  * Return TRUE when the two line segments cross each other. Find out
66  * where the projected lines would cross and then check to see if the
67  * point of intersection lies on both of the line segments. If it does
68  * then these two segments cross.
69  **********************************************************************/
71  int b0a1xb0b1, b0b1xb0a0;
72  int a1b1xa1a0, a1a0xa1b0;
73 
74  TPOINT b0a1, b0a0, a1b1, b0b1, a1a0;
75 
76  b0a1.x = a1.x - b0.x;
77  b0a0.x = a0.x - b0.x;
78  a1b1.x = b1.x - a1.x;
79  b0b1.x = b1.x - b0.x;
80  a1a0.x = a0.x - a1.x;
81  b0a1.y = a1.y - b0.y;
82  b0a0.y = a0.y - b0.y;
83  a1b1.y = b1.y - a1.y;
84  b0b1.y = b1.y - b0.y;
85  a1a0.y = a0.y - a1.y;
86 
87  b0a1xb0b1 = CROSS (b0a1, b0b1);
88  b0b1xb0a0 = CROSS (b0b1, b0a0);
89  a1b1xa1a0 = CROSS (a1b1, a1a0);
90  /*a1a0xa1b0=CROSS(a1a0,a1b0); */
91  a1a0xa1b0 = -CROSS (a1a0, b0a1);
92 
93  return ((b0a1xb0b1 > 0 && b0b1xb0a0 > 0)
94  || (b0a1xb0b1 < 0 && b0b1xb0a0 < 0))
95  && ((a1b1xa1a0 > 0 && a1a0xa1b0 > 0) || (a1b1xa1a0 < 0 && a1a0xa1b0 < 0));
96 }
97 
98 
99 /**********************************************************************
100  * is_same_edgept
101  *
102  * Return true if the points are identical.
103  **********************************************************************/
105  return (p1 == p2);
106 }
107 
108 
109 /**********************************************************************
110  * near_point
111  *
112  * Find the point on a line segment that is closest to a point not on
113  * the line segment. Return that point in near_pt. Returns whether
114  * near_pt was newly created.
115  **********************************************************************/
117  EDGEPT *line_pt_0, EDGEPT *line_pt_1,
118  EDGEPT **near_pt) {
119  TPOINT p;
120 
121  float slope;
122  float intercept;
123 
124  float x0 = line_pt_0->pos.x;
125  float x1 = line_pt_1->pos.x;
126  float y0 = line_pt_0->pos.y;
127  float y1 = line_pt_1->pos.y;
128 
129  if (x0 == x1) {
130  /* Handle vertical line */
131  p.x = (inT16) x0;
132  p.y = point->pos.y;
133  }
134  else {
135  /* Slope and intercept */
136  slope = (y0 - y1) / (x0 - x1);
137  intercept = y1 - x1 * slope;
138 
139  /* Find perpendicular */
140  p.x = (inT16) ((point->pos.x + (point->pos.y - intercept) * slope) /
141  (slope * slope + 1));
142  p.y = (inT16) (slope * p.x + intercept);
143  }
144 
145  if (is_on_line (p, line_pt_0->pos, line_pt_1->pos) &&
146  (!same_point (p, line_pt_0->pos)) && (!same_point (p, line_pt_1->pos))) {
147  /* Intersection on line */
148  *near_pt = make_edgept(p.x, p.y, line_pt_1, line_pt_0);
149  return true;
150  } else { /* Intersection not on line */
151  *near_pt = closest(point, line_pt_0, line_pt_1);
152  return false;
153  }
154 }
155 
156 
157 /**********************************************************************
158  * reverse_outline
159  *
160  * Change the direction of the outline. If it was clockwise make it
161  * counter-clockwise and vice versa. Do this by swapping each of the
162  * next and prev fields of each edge point.
163  **********************************************************************/
165  EDGEPT *edgept = outline;
166  EDGEPT *temp;
167 
168  do {
169  /* Swap next and prev */
170  temp = edgept->prev;
171  edgept->prev = edgept->next;
172  edgept->next = temp;
173  /* Set up vec field */
174  edgept->vec.x = edgept->next->pos.x - edgept->pos.x;
175  edgept->vec.y = edgept->next->pos.y - edgept->pos.y;
176 
177  edgept = edgept->prev; /* Go to next point */
178  }
179  while (edgept != outline);
180 }
181 
182 } // namespace tesseract