Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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 **********************************************************************/
70 int Wordrec::is_crossed(TPOINT a0, TPOINT a1, TPOINT b0, TPOINT b1) {
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 **********************************************************************/
104 int Wordrec::is_same_edgept(EDGEPT *p1, EDGEPT *p2) {
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 **********************************************************************/
116 bool Wordrec::near_point(EDGEPT *point,
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 **********************************************************************/
164 void Wordrec::reverse_outline(EDGEPT *outline) {
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