1 /**********************************************************************
2 * File: polyaprx.cpp (Formerly polygon.c)
3 * Description: Code for polygonal approximation from old edgeprog.
4 * Author: Ray Smith
5 * Created: Thu Nov 25 11:42:04 GMT 1993
6 *
7 * (C) Copyright 1993, Hewlett-Packard Ltd.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 *
18 **********************************************************************/
19
20 #include "mfcpch.h"
21 #include <stdio.h>
22 #ifdef __UNIX__
23 #include <assert.h>
24 #endif
25 #define FASTEDGELENGTH 256
26 #include "polyaprx.h"
27 #include "varable.h"
28 #include "tprintf.h"
29
30 #define EXTERN
31
32 EXTERN BOOL_VAR (poly_debug, FALSE, "Debug old poly");
33 EXTERN BOOL_VAR (poly_wide_objects_better, TRUE,
34 "More accurate approx on wide things");
35
36 static int par1, par2;
37
38 #define CONVEX 1 /*OUTLINE point is convex */
39 #define CONCAVE 2 /*used and set only in edges */
40 #define FIXED 4 /*OUTLINE point is fixed */
41 #define ONHULL 8 /*on convex hull */
42
43 #define RUNLENGTH 1 /*length of run */
44
45 #define DIR 2 /*direction of run */
46
47 #define CORRECTION 3 /*correction of run */
48 //#define MAXSHORT 32767 /*max value of short*/
49 #define FLAGS 0
50
51 #define fixed_dist 20 //really an int_variable
52 #define approx_dist 15 //really an int_variable
53
54 #define point_diff(p,p1,p2) (p).x = (p1).x - (p2).x ; (p).y = (p1).y - (p2).y
55 #define CROSS(a,b) ((a).x * (b).y - (a).y * (b).x)
56 #define LENGTH(a) ((a).x * (a).x + (a).y * (a).y)
57
58 #define DISTANCE(a,b) (((b).x-(a).x) * ((b).x-(a).x) \
59 + ((b).y-(a).y) * ((b).y-(a).y))
60
61 /**********************************************************************
62 * tesspoly_outline
63 *
64 * Approximate an outline from c form using the old tess algorithm.
65 **********************************************************************/
66
tesspoly_outline(C_OUTLINE * c_outline,float)67 OUTLINE *tesspoly_outline( //old approximation
68 C_OUTLINE *c_outline, //input
69 float //xheight
70 ) {
71 EDGEPT *edgept; //converted steps
72 EDGEPT *startpt; //start of outline
73 TBOX loop_box; //bounding box
74 inT32 area; //loop area
75 FCOORD pos; //vertex
76 FCOORD vec; //vector
77 POLYPT_LIST polypts; //output polygon
78 POLYPT *polypt; //converted point
79 POLYPT_IT poly_it = &polypts; //iterator
80 EDGEPT stack_edgepts[FASTEDGELENGTH]; // converted path
81 EDGEPT* edgepts = stack_edgepts;
82
83 // Use heap memory if the stack buffer is not big enough.
84 if (c_outline->pathlength() > FASTEDGELENGTH)
85 edgepts = new EDGEPT[c_outline->pathlength()];
86
87 loop_box = c_outline->bounding_box ();
88 area = loop_box.height ();
89 if (!poly_wide_objects_better && loop_box.width () > area)
90 area = loop_box.width ();
91 area *= area;
92 edgept = edgesteps_to_edgepts (c_outline, edgepts);
93 fix2(edgepts, area);
94 edgept = poly2 (edgepts, area);/*2nd approximation */
95 startpt = edgept;
96 do {
97 pos = FCOORD (edgept->pos.x, edgept->pos.y);
98 vec = FCOORD (edgept->vec.x, edgept->vec.y);
99 polypt = new POLYPT (pos, vec);
100 //add to list
101 poly_it.add_after_then_move (polypt);
102 edgept = edgept->next;
103 }
104 while (edgept != startpt);
105 if (edgepts != stack_edgepts)
106 delete [] edgepts;
107 if (poly_it.length() <= 2)
108 return NULL;
109 else
110 return new OUTLINE(&poly_it);
111 }
112
113
114 /**********************************************************************
115 * edgesteps_to_edgepts
116 *
117 * Convert a C_OUTLINE to EDGEPTs.
118 **********************************************************************/
119
120 EDGEPT *
edgesteps_to_edgepts(C_OUTLINE * c_outline,EDGEPT edgepts[])121 edgesteps_to_edgepts ( //convert outline
122 C_OUTLINE * c_outline, //input
123 EDGEPT edgepts[] //output is array
124 ) {
125 inT32 length; //steps in path
126 ICOORD pos; //current coords
127 inT32 stepindex; //current step
128 inT32 stepinc; //increment
129 inT32 epindex; //current EDGEPT
130 inT32 count; //repeated steps
131 ICOORD vec; //for this 8 step
132 ICOORD prev_vec;
133 inT8 epdir; //of this step
134 DIR128 prevdir; //prvious dir
135 DIR128 dir; //of this step
136
137 pos = c_outline->start_pos (); //start of loop
138 length = c_outline->pathlength ();
139 stepindex = 0;
140 epindex = 0;
141 prevdir = -1;
142 count = 0;
143 do {
144 dir = c_outline->step_dir (stepindex);
145 vec = c_outline->step (stepindex);
146 if (stepindex < length - 1
147 && c_outline->step_dir (stepindex + 1) - dir == -32) {
148 dir += 128 - 16;
149 vec += c_outline->step (stepindex + 1);
150 stepinc = 2;
151 }
152 else
153 stepinc = 1;
154 if (count == 0) {
155 prevdir = dir;
156 prev_vec = vec;
157 }
158 if (prevdir.get_dir () != dir.get_dir ()) {
159 edgepts[epindex].pos.x = pos.x ();
160 edgepts[epindex].pos.y = pos.y ();
161 prev_vec *= count;
162 edgepts[epindex].vec.x = prev_vec.x ();
163 edgepts[epindex].vec.y = prev_vec.y ();
164 pos += prev_vec;
165 edgepts[epindex].flags[RUNLENGTH] = count;
166 edgepts[epindex].prev = &edgepts[epindex - 1];
167 edgepts[epindex].flags[FLAGS] = 0;
168 edgepts[epindex].next = &edgepts[epindex + 1];
169 prevdir += 64;
170 epdir = (DIR128) 0 - prevdir;
171 epdir >>= 4;
172 epdir &= 7;
173 edgepts[epindex].flags[DIR] = epdir;
174 epindex++;
175 prevdir = dir;
176 prev_vec = vec;
177 count = 1;
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].prev = &edgepts[epindex - 1];
193 edgepts[epindex].next = &edgepts[0];
194 prevdir += 64;
195 epdir = (DIR128) 0 - prevdir;
196 epdir >>= 4;
197 epdir &= 7;
198 edgepts[epindex].flags[DIR] = epdir;
199 edgepts[0].prev = &edgepts[epindex];
200 ASSERT_HOST (pos.x () == c_outline->start_pos ().x ()
201 && pos.y () == c_outline->start_pos ().y ());
202 return &edgepts[0];
203 }
204
205
206 /**********************************************************************
207 *fix2(start,area) fixes points on the outline according to a trial method*
208 **********************************************************************/
209
210 //#pragma OPT_LEVEL 1 /*stop compiler bugs*/
211
fix2(EDGEPT * start,int area)212 void fix2( //polygonal approx
213 EDGEPT *start, /*loop to approimate */
214 int area) {
215 register EDGEPT *edgept; /*current point */
216 register EDGEPT *edgept1;
217 register EDGEPT *loopstart; /*modified start of loop */
218 register EDGEPT *linestart; /*start of line segment */
219 register int dir1, dir2; /*directions of line */
220 register int sum1, sum2; /*lengths in dir1,dir2 */
221 int stopped; /*completed flag */
222 int fixed_count; //no of fixed points
223 int d01, d12, d23, gapmin;
224 TPOINT d01vec, d12vec, d23vec;
225 register EDGEPT *edgefix, *startfix;
226 register EDGEPT *edgefix0, *edgefix1, *edgefix2, *edgefix3;
227
228 edgept = start; /*start of loop */
229 while (((edgept->flags[DIR] - edgept->prev->flags[DIR] + 1) & 7) < 3
230 && (dir1 =
231 (edgept->prev->flags[DIR] - edgept->next->flags[DIR]) & 7) != 2
232 && dir1 != 6)
233 edgept = edgept->next; /*find suitable start */
234 loopstart = edgept; /*remember start */
235
236 stopped = 0; /*not finished yet */
237 edgept->flags[FLAGS] |= FIXED; /*fix it */
238 do {
239 linestart = edgept; /*possible start of line */
240 dir1 = edgept->flags[DIR]; /*first direction */
241 /*length of dir1 */
242 sum1 = edgept->flags[RUNLENGTH];
243 edgept = edgept->next;
244 dir2 = edgept->flags[DIR]; /*2nd direction */
245 /*length in dir2 */
246 sum2 = edgept->flags[RUNLENGTH];
247 if (((dir1 - dir2 + 1) & 7) < 3) {
248 while (edgept->prev->flags[DIR] == edgept->next->flags[DIR]) {
249 edgept = edgept->next; /*look at next */
250 if (edgept->flags[DIR] == dir1)
251 /*sum lengths */
252 sum1 += edgept->flags[RUNLENGTH];
253 else
254 sum2 += edgept->flags[RUNLENGTH];
255 }
256
257 if (edgept == loopstart)
258 stopped = 1; /*finished */
259 if (sum2 + sum1 > 2
260 && linestart->prev->flags[DIR] == dir2
261 && (linestart->prev->flags[RUNLENGTH] >
262 linestart->flags[RUNLENGTH] || sum2 > sum1)) {
263 /*start is back one */
264 linestart = linestart->prev;
265 linestart->flags[FLAGS] |= FIXED;
266 }
267
268 if (((edgept->next->flags[DIR] - edgept->flags[DIR] + 1) & 7) >= 3
269 || (edgept->flags[DIR] == dir1 && sum1 >= sum2)
270 || ((edgept->prev->flags[RUNLENGTH] < edgept->flags[RUNLENGTH]
271 || (edgept->flags[DIR] == dir2 && sum2 >= sum1))
272 && linestart->next != edgept))
273 edgept = edgept->next;
274 }
275 /*sharp bend */
276 edgept->flags[FLAGS] |= FIXED;
277 }
278 /*do whole loop */
279 while (edgept != loopstart && !stopped);
280
281 edgept = start;
282 do {
283 if (((edgept->flags[RUNLENGTH] >= 8) &&
284 (edgept->flags[DIR] != 2) && (edgept->flags[DIR] != 6)) ||
285 ((edgept->flags[RUNLENGTH] >= 8) &&
286 ((edgept->flags[DIR] == 2) || (edgept->flags[DIR] == 6)))) {
287 edgept->flags[FLAGS] |= FIXED;
288 edgept1 = edgept->next;
289 edgept1->flags[FLAGS] |= FIXED;
290 }
291 edgept = edgept->next;
292 }
293 while (edgept != start);
294
295 edgept = start;
296 do {
297 /*single fixed step */
298 if (edgept->flags[FLAGS] & FIXED && edgept->flags[RUNLENGTH] == 1
299 /*and neighours free */
300 && edgept->next->flags[FLAGS] & FIXED && (edgept->prev->flags[FLAGS] & FIXED) == 0
301 /*same pair of dirs */
302 && (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]
303 && ((edgept->prev->flags[DIR] - edgept->flags[DIR] + 1) & 7) < 3) {
304 /*unfix it */
305 edgept->flags[FLAGS] &= ~FIXED;
306 edgept->next->flags[FLAGS] &= ~FIXED;
307 }
308 edgept = edgept->next; /*do all points */
309 }
310 while (edgept != start); /*until finished */
311
312 stopped = 0;
313 if (area < 450)
314 area = 450;
315
316 gapmin = area * fixed_dist * fixed_dist / 44000;
317
318 edgept = start;
319 fixed_count = 0;
320 do {
321 if (edgept->flags[FLAGS] & FIXED)
322 fixed_count++;
323 edgept = edgept->next;
324 }
325 while (edgept != start);
326 while ((edgept->flags[FLAGS] & FIXED) == 0)
327 edgept = edgept->next;
328 edgefix0 = edgept;
329
330 edgept = edgept->next;
331 while ((edgept->flags[FLAGS] & FIXED) == 0)
332 edgept = edgept->next;
333 edgefix1 = edgept;
334
335 edgept = edgept->next;
336 while ((edgept->flags[FLAGS] & FIXED) == 0)
337 edgept = edgept->next;
338 edgefix2 = edgept;
339
340 edgept = edgept->next;
341 while ((edgept->flags[FLAGS] & FIXED) == 0)
342 edgept = edgept->next;
343 edgefix3 = edgept;
344
345 startfix = edgefix2;
346
347 do {
348 if (fixed_count <= 3)
349 break; //already too few
350 point_diff (d12vec, edgefix1->pos, edgefix2->pos);
351 d12 = LENGTH (d12vec);
352 if (d12 <= gapmin) {
353 point_diff (d01vec, edgefix0->pos, edgefix1->pos);
354 d01 = LENGTH (d01vec);
355 point_diff (d23vec, edgefix2->pos, edgefix3->pos);
356 d23 = LENGTH (d23vec);
357 if (d01 > d23) {
358 edgefix2->flags[FLAGS] &= ~FIXED;
359 fixed_count--;
360 /* if ( plots[EDGE] & PATHS )
361 mark(edgefd,edgefix2->pos.x,edgefix2->pos.y,PLUS);
362 */
363 }
364 else {
365 edgefix1->flags[FLAGS] &= ~FIXED;
366 fixed_count--;
367 /* if ( plots[EDGE] & PATHS )
368 mark(edgefd,edgefix1->pos.x,edgefix1->pos.y,PLUS);
369 */
370 edgefix1 = edgefix2;
371 }
372 }
373 else {
374 edgefix0 = edgefix1;
375 edgefix1 = edgefix2;
376 }
377 edgefix2 = edgefix3;
378 edgept = edgept->next;
379 while ((edgept->flags[FLAGS] & FIXED) == 0) {
380 if (edgept == startfix)
381 stopped = 1;
382 edgept = edgept->next;
383 }
384 edgefix3 = edgept;
385 edgefix = edgefix2;
386 }
387 while ((edgefix != startfix) && (!stopped));
388 }
389
390
391 //#pragma OPT_LEVEL 2 /*stop compiler bugs*/
392
393 /**********************************************************************
394 *poly2(startpt,area,path) applies a second approximation to the outline
395 *using the points which have been fixed by the first approximation*
396 **********************************************************************/
397
poly2(EDGEPT * startpt,int area)398 EDGEPT *poly2( //second poly
399 EDGEPT *startpt, /*start of loop */
400 int area /*area of blob box */
401 ) {
402 register EDGEPT *edgept; /*current outline point */
403 EDGEPT *loopstart; /*starting point */
404 register EDGEPT *linestart; /*start of line */
405 register int edgesum; /*correction count */
406
407 if (area < 1200)
408 area = 1200; /*minimum value */
409
410 /*1200(4) */
411 par1 = 4500 / (approx_dist * approx_dist);
412 /*1200(6) */
413 par2 = 6750 / (approx_dist * approx_dist);
414
415 loopstart = NULL; /*not found it yet */
416 edgept = startpt; /*start of loop */
417
418 do {
419 /*current point fixed */
420 if (edgept->flags[FLAGS] & FIXED
421 /*and next not */
422 && (edgept->next->flags[FLAGS] & FIXED) == 0) {
423 loopstart = edgept; /*start of repoly */
424 break;
425 }
426 edgept = edgept->next; /*next point */
427 }
428 while (edgept != startpt); /*until found or finished */
429
430 if (loopstart == NULL && (startpt->flags[FLAGS] & FIXED) == 0) {
431 /*fixed start of loop */
432 startpt->flags[FLAGS] |= FIXED;
433 loopstart = startpt; /*or start of loop */
434 }
435 if (loopstart) {
436 do {
437 edgept = loopstart; /*first to do */
438 do {
439 linestart = edgept;
440 edgesum = 0; /*sum of lengths */
441 do {
442 /*sum lengths */
443 edgesum += edgept->flags[RUNLENGTH];
444 edgept = edgept->next; /*move on */
445 }
446 while ((edgept->flags[FLAGS] & FIXED) == 0
447 && edgept != loopstart && edgesum < 126);
448 if (poly_debug)
449 tprintf
450 ("Poly2:starting at (%d,%d)+%d=(%d,%d),%d to (%d,%d)\n",
451 linestart->pos.x, linestart->pos.y, linestart->flags[DIR],
452 linestart->vec.x, linestart->vec.y, edgesum, edgept->pos.x,
453 edgept->pos.y);
454 /*reapproximate */
455 cutline(linestart, edgept, area);
456
457 while ((edgept->next->flags[FLAGS] & FIXED)
458 && edgept != loopstart)
459 edgept = edgept->next; /*look for next non-fixed */
460 }
461 /*do all the loop */
462 while (edgept != loopstart);
463 edgesum = 0;
464 do {
465 if (edgept->flags[FLAGS] & FIXED)
466 edgesum++;
467 edgept = edgept->next;
468 }
469 //count fixed pts
470 while (edgept != loopstart);
471 if (edgesum < 3)
472 area /= 2; //must have 3 pts
473 }
474 while (edgesum < 3);
475 do {
476 linestart = edgept;
477 do {
478 edgept = edgept->next;
479 }
480 while ((edgept->flags[FLAGS] & FIXED) == 0);
481 linestart->next = edgept;
482 edgept->prev = linestart;
483 linestart->vec.x = edgept->pos.x - linestart->pos.x;
484 linestart->vec.y = edgept->pos.y - linestart->pos.y;
485 }
486 while (edgept != loopstart);
487 }
488 else
489 edgept = startpt; /*start of loop */
490
491 loopstart = edgept; /*new start */
492 return loopstart; /*correct exit */
493 }
494
495
496 /**********************************************************************
497 *cutline(first,last,area) straightens out a line by partitioning
498 *and joining the ends by a straight line*
499 **********************************************************************/
500
cutline(EDGEPT * first,EDGEPT * last,int area)501 void cutline( //recursive refine
502 EDGEPT *first, /*ends of line */
503 EDGEPT *last,
504 int area /*area of object */
505 ) {
506 register EDGEPT *edge; /*current edge */
507 TPOINT vecsum; /*vector sum */
508 int vlen; /*approx length of vecsum */
509 TPOINT vec; /*accumulated vector */
510 EDGEPT *maxpoint; /*worst point */
511 int maxperp; /*max deviation */
512 register int perp; /*perp distance */
513 int ptcount; /*no of points */
514 int squaresum; /*sum of perps */
515
516 edge = first; /*start of line */
517 if (edge->next == last)
518 return; /*simple line */
519
520 /*vector sum */
521 vecsum.x = last->pos.x - edge->pos.x;
522 vecsum.y = last->pos.y - edge->pos.y;
523 if (vecsum.x == 0 && vecsum.y == 0) {
524 /*special case */
525 vecsum.x = -edge->prev->vec.x;
526 vecsum.y = -edge->prev->vec.y;
527 }
528 /*absolute value */
529 vlen = vecsum.x > 0 ? vecsum.x : -vecsum.x;
530 if (vecsum.y > vlen)
531 vlen = vecsum.y; /*maximum */
532 else if (-vecsum.y > vlen)
533 vlen = -vecsum.y; /*absolute value */
534
535 vec.x = edge->vec.x; /*accumulated vector */
536 vec.y = edge->vec.y;
537 maxperp = 0; /*none yet */
538 squaresum = ptcount = 0;
539 edge = edge->next; /*move to actual point */
540 maxpoint = edge; /*in case there isn't one */
541 do {
542 perp = CROSS (vec, vecsum); /*get perp distance */
543 if (perp != 0) {
544 perp *= perp; /*squared deviation */
545 }
546 squaresum += perp; /*sum squares */
547 ptcount++; /*count points */
548 if (poly_debug)
549 tprintf ("Cutline:Final perp=%d\n", perp);
550 if (perp > maxperp) {
551 maxperp = perp;
552 maxpoint = edge; /*find greatest deviation */
553 }
554 vec.x += edge->vec.x; /*accumulate vectors */
555 vec.y += edge->vec.y;
556 edge = edge->next;
557 }
558 while (edge != last); /*test all line */
559
560 perp = LENGTH (vecsum);
561 ASSERT_HOST (perp != 0);
562
563 if (maxperp < 256 * MAX_INT16) {
564 maxperp <<= 8;
565 maxperp /= perp; /*true max perp */
566 }
567 else {
568 maxperp /= perp;
569 maxperp <<= 8; /*avoid overflow */
570 }
571 if (squaresum < 256 * MAX_INT16)
572 /*mean squared perp */
573 perp = (squaresum << 8) / (perp * ptcount);
574 else
575 /*avoid overflow */
576 perp = (squaresum / perp << 8) / ptcount;
577
578 if (poly_debug)
579 tprintf ("Cutline:A=%d, max=%.2f(%.2f%%), msd=%.2f(%.2f%%)\n",
580 area, maxperp / 256.0, maxperp * 200.0 / area,
581 perp / 256.0, perp * 300.0 / area);
582 if (maxperp * par1 >= 10 * area || perp * par2 >= 10 * area || vlen >= 126) {
583 maxpoint->flags[FLAGS] |= FIXED;
584 /*partitions */
585 cutline(first, maxpoint, area);
586 cutline(maxpoint, last, area);
587 }
588 }
589