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
33 #ifdef __UNIX__
34 #include <assert.h>
35 #endif
36
37 /*----------------------------------------------------------------------
38 F u n c t i o n s
39 ----------------------------------------------------------------------*/
40 /**********************************************************************
41 * crosses_outline
42 *
43 * Check to see if this line crosses over this outline. If it does
44 * return TRUE.
45 **********************************************************************/
crosses_outline(EDGEPT * p0,EDGEPT * p1,EDGEPT * outline)46 int crosses_outline(EDGEPT *p0, /* Start of line */
47 EDGEPT *p1, /* End of line */
48 EDGEPT *outline) { /* Outline to check */
49 EDGEPT *pt = outline;
50 do {
51 if (is_crossed (p0->pos, p1->pos, pt->pos, pt->next->pos))
52 return (TRUE);
53 pt = pt->next;
54 }
55 while (pt != outline);
56 return (FALSE);
57 }
58
59
60 /**********************************************************************
61 * is_crossed
62 *
63 * Return TRUE when the two line segments cross each other. Find out
64 * where the projected lines would cross and then check to see if the
65 * point of intersection lies on both of the line segments. If it does
66 * then these two segments cross.
67 **********************************************************************/
is_crossed(TPOINT a0,TPOINT a1,TPOINT b0,TPOINT b1)68 int is_crossed(TPOINT a0, TPOINT a1, TPOINT b0, TPOINT b1) {
69 int b0a1xb0b1, b0b1xb0a0;
70 int a1b1xa1a0, a1a0xa1b0;
71
72 TPOINT b0a1, b0a0, a1b1, b0b1, a1a0;
73
74 b0a1.x = a1.x - b0.x;
75 b0a0.x = a0.x - b0.x;
76 a1b1.x = b1.x - a1.x;
77 b0b1.x = b1.x - b0.x;
78 a1a0.x = a0.x - a1.x;
79 b0a1.y = a1.y - b0.y;
80 b0a0.y = a0.y - b0.y;
81 a1b1.y = b1.y - a1.y;
82 b0b1.y = b1.y - b0.y;
83 a1a0.y = a0.y - a1.y;
84
85 b0a1xb0b1 = CROSS (b0a1, b0b1);
86 b0b1xb0a0 = CROSS (b0b1, b0a0);
87 a1b1xa1a0 = CROSS (a1b1, a1a0);
88 /*a1a0xa1b0=CROSS(a1a0,a1b0); */
89 a1a0xa1b0 = -CROSS (a1a0, b0a1);
90
91 return ((b0a1xb0b1 > 0 && b0b1xb0a0 > 0)
92 || (b0a1xb0b1 < 0 && b0b1xb0a0 < 0))
93 && ((a1b1xa1a0 > 0 && a1a0xa1b0 > 0) || (a1b1xa1a0 < 0 && a1a0xa1b0 < 0));
94 }
95
96
97 /**********************************************************************
98 * is_same_edgept
99 *
100 * Return true if the points are identical.
101 **********************************************************************/
is_same_edgept(EDGEPT * p1,EDGEPT * p2)102 int is_same_edgept(EDGEPT *p1, EDGEPT *p2) {
103 return (p1 == p2);
104 }
105
106
107 /**********************************************************************
108 * near_point
109 *
110 * Find the point on a line segment that is closest to a point not on
111 * the line segment. Return that point.
112 **********************************************************************/
near_point(EDGEPT * point,EDGEPT * line_pt_0,EDGEPT * line_pt_1)113 EDGEPT *near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1) {
114 TPOINT p;
115
116 float slope;
117 float intercept;
118
119 float x0 = line_pt_0->pos.x;
120 float x1 = line_pt_1->pos.x;
121 float y0 = line_pt_0->pos.y;
122 float y1 = line_pt_1->pos.y;
123
124 if (x0 == x1) {
125 /* Handle vertical line */
126 p.x = (inT16) x0;
127 p.y = point->pos.y;
128 }
129 else {
130 /* Slope and intercept */
131 slope = (y0 - y1) / (x0 - x1);
132 intercept = y1 - x1 * slope;
133
134 /* Find perpendicular */
135 p.x = (inT16) ((point->pos.x + (point->pos.y - intercept) * slope) /
136 (slope * slope + 1));
137 p.y = (inT16) (slope * p.x + intercept);
138 }
139
140 if (is_on_line (p, line_pt_0->pos, line_pt_1->pos) &&
141 (!same_point (p, line_pt_0->pos)) && (!same_point (p, line_pt_1->pos)))
142 /* Intersection on line */
143 return (make_edgept (p.x, p.y, line_pt_1, line_pt_0));
144 else /* Intersection not on line */
145 return (closest (point, line_pt_0, line_pt_1));
146 }
147
148
149 /**********************************************************************
150 * reverse_outline
151 *
152 * Change the direction of the outline. If it was clockwise make it
153 * counter-clockwise and vice versa. Do this by swapping each of the
154 * next and prev fields of each edge point.
155 **********************************************************************/
reverse_outline(EDGEPT * outline)156 void reverse_outline(EDGEPT *outline) {
157 EDGEPT *edgept = outline;
158 EDGEPT *temp;
159
160 do {
161 /* Swap next and prev */
162 temp = edgept->prev;
163 edgept->prev = edgept->next;
164 edgept->next = temp;
165 /* Set up vec field */
166 edgept->vec.x = edgept->next->pos.x - edgept->pos.x;
167 edgept->vec.y = edgept->next->pos.y - edgept->pos.y;
168
169 edgept = edgept->prev; /* Go to next point */
170 }
171 while (edgept != outline);
172 }
173