1
2
3 #include "texception.h"
4 #include "tautoclose.h"
5 #include "trastercm.h"
6 #include "skeletonlut.h"
7
8 #define AUT_SPOT_SAMPLES 10
9
10 using namespace SkeletonLut;
11
12 class TAutocloser::Imp {
13 public:
14 struct Seed {
15 UCHAR *m_ptr;
16 UCHAR m_preseed;
SeedTAutocloser::Imp::Seed17 Seed(UCHAR *ptr, UCHAR preseed) : m_ptr(ptr), m_preseed(preseed) {}
18 };
19
20 int m_closingDistance;
21 double m_spotAngle;
22 int m_inkIndex;
23 TRasterP m_raster;
24 TRasterGR8P m_bRaster;
25 UCHAR *m_br;
26
27 int m_bWrap;
28
29 int m_displaceVector[8];
30 TPointD m_displAverage;
31 int m_visited;
32
33 double m_csp, m_snp, m_csm, m_snm, m_csa, m_sna, m_csb, m_snb;
34
Imp(const TRasterP & r)35 Imp(const TRasterP &r)
36 : m_raster(r)
37 , m_spotAngle((180 * TConsts::pi) / 360.0)
38 , m_closingDistance(10)
39 , m_inkIndex(0) {}
40
~Imp()41 ~Imp() {}
42
isInk(UCHAR * br)43 bool inline isInk(UCHAR *br) { return (*br) & 0x1; }
eraseInk(UCHAR * br)44 inline void eraseInk(UCHAR *br) { *(br) &= 0xfe; }
45
ePix(UCHAR * br)46 UCHAR inline ePix(UCHAR *br) { return (*(br + 1)); }
wPix(UCHAR * br)47 UCHAR inline wPix(UCHAR *br) { return (*(br - 1)); }
nPix(UCHAR * br)48 UCHAR inline nPix(UCHAR *br) { return (*(br + m_bWrap)); }
sPix(UCHAR * br)49 UCHAR inline sPix(UCHAR *br) { return (*(br - m_bWrap)); }
swPix(UCHAR * br)50 UCHAR inline swPix(UCHAR *br) { return (*(br - m_bWrap - 1)); }
nwPix(UCHAR * br)51 UCHAR inline nwPix(UCHAR *br) { return (*(br + m_bWrap - 1)); }
nePix(UCHAR * br)52 UCHAR inline nePix(UCHAR *br) { return (*(br + m_bWrap + 1)); }
sePix(UCHAR * br)53 UCHAR inline sePix(UCHAR *br) { return (*(br - m_bWrap + 1)); }
neighboursCode(UCHAR * seed)54 UCHAR inline neighboursCode(UCHAR *seed) {
55 return ((swPix(seed) & 0x1) | ((sPix(seed) & 0x1) << 1) |
56 ((sePix(seed) & 0x1) << 2) | ((wPix(seed) & 0x1) << 3) |
57 ((ePix(seed) & 0x1) << 4) | ((nwPix(seed) & 0x1) << 5) |
58 ((nPix(seed) & 0x1) << 6) | ((nePix(seed) & 0x1) << 7));
59 }
60
61 //.......................
62
notMarkedBorderInk(UCHAR * br)63 inline bool notMarkedBorderInk(UCHAR *br) {
64 return ((((*br) & 0x5) == 1) &&
65 (ePix(br) == 0 || wPix(br) == 0 || nPix(br) == 0 || sPix(br) == 0));
66 }
67
68 //.......................
getPtr(int x,int y)69 UCHAR *getPtr(int x, int y) { return m_br + m_bWrap * y + x; }
getPtr(const TPoint & p)70 UCHAR *getPtr(const TPoint &p) { return m_br + m_bWrap * p.y + p.x; }
71
getCoordinates(UCHAR * br)72 TPoint getCoordinates(UCHAR *br) {
73 TPoint p;
74 int pixelCount = br - m_bRaster->getRawData();
75 p.y = pixelCount / m_bWrap;
76 p.x = pixelCount - p.y * m_bWrap;
77 return p;
78 }
79
80 //.......................
81 void compute(vector<Segment> &closingSegmentArray);
82 void skeletonize(vector<TPoint> &endpoints);
83 void findSeeds(vector<Seed> &seeds, vector<TPoint> &endpoints);
84 void erase(vector<Seed> &seeds, vector<TPoint> &endpoints);
85 void circuitAndMark(UCHAR *seed, UCHAR preseed);
86 bool circuitAndCancel(UCHAR *seed, UCHAR preseed, vector<TPoint> &endpoints);
87 void findMeetingPoints(vector<TPoint> &endpoints,
88 vector<Segment> &closingSegments);
89 void calculateWeightAndDirection(vector<Segment> &orientedEndpoints);
90 bool spotResearchTwoPoints(vector<Segment> &endpoints,
91 vector<Segment> &closingSegments);
92 bool spotResearchOnePoint(vector<Segment> &endpoints,
93 vector<Segment> &closingSegments);
94
95 void copy(const TRasterGR8P &braux, TRaster32P &raux);
96 int exploreTwoSpots(const TAutocloser::Segment &s0,
97 const TAutocloser::Segment &s1);
98 int notInsidePath(const TPoint &p, const TPoint &q);
99 void drawInByteRaster(const TPoint &p0, const TPoint &p1);
100 TPoint visitEndpoint(UCHAR *br);
101 bool exploreSpot(const Segment &s, TPoint &p);
102 bool exploreRay(UCHAR *br, Segment s, TPoint &p);
103 void visitPix(UCHAR *br, int toVisit, const TPoint &dis);
104 void cancelMarks(UCHAR *br);
105 void cancelFromArray(vector<Segment> &array, TPoint p, int &count);
106 };
107
108 /*------------------------------------------------------------------------*/
109
110 /*------------------------------------------------------------------------*/
111
112 #define DRAW_SEGMENT(a, b, da, db, istr1, istr2, block) \
113 { \
114 d = 2 * db - da; \
115 incr_1 = 2 * db; \
116 incr_2 = 2 * (db - da); \
117 while (a < da) { \
118 if (d <= 0) { \
119 d += incr_1; \
120 a++; \
121 istr1; \
122 } else { \
123 d += incr_2; \
124 a++; \
125 b++; \
126 istr2; \
127 } \
128 block; \
129 } \
130 }
131
132 /*------------------------------------------------------------------------*/
133
134 #define EXPLORE_RAY_ISTR(istr) \
135 if (!inside_ink) { \
136 if (((*br) & 0x1) && !((*br) & 0x80)) { \
137 p.x = istr; \
138 p.y = (s.first.y < s.second.y) ? s.first.y + y : s.first.y - y; \
139 return true; \
140 } \
141 } else if (inside_ink && !((*br) & 0x1)) \
142 inside_ink = 0;
143
144 /*------------------------------------------------------------------------*/
145
146 //-------------------------------------------------
147
148 namespace {
149
isInk(const TPixel32 & pix)150 inline bool isInk(const TPixel32 &pix) { return pix.r < 80; }
151
152 /*------------------------------------------------------------------------*/
153
makeByteRaster(const TRasterCM32P & r)154 TRasterGR8P makeByteRaster(const TRasterCM32P &r) {
155 int lx = r->getLx();
156 int ly = r->getLy();
157 TRasterGR8P bRaster(lx + 4, ly + 4);
158 int i, j;
159
160 // bRaster->create(lx+4, ly+4);
161 bRaster->lock();
162 UCHAR *br = bRaster->getRawData();
163
164 for (i = 0; i < lx + 4; i++) *(br++) = 0;
165
166 for (i = 0; i < lx + 4; i++) *(br++) = 131;
167
168 r->lock();
169 for (i = 0; i < ly; i++) {
170 *(br++) = 0;
171 *(br++) = 131;
172 TPixelCM32 *pix = r->pixels(i);
173 for (j = 0; j < lx; j++, pix++) {
174 if (pix->getTone() != pix->getMaxTone())
175 *(br++) = 3;
176 else
177 *(br++) = 0;
178 }
179 *(br++) = 131;
180 *(br++) = 0;
181 }
182 r->unlock();
183 for (i = 0; i < lx + 4; i++) *(br++) = 131;
184
185 for (i = 0; i < lx + 4; i++) *(br++) = 0;
186
187 bRaster->unlock();
188 return bRaster;
189 }
190
191 /*------------------------------------------------------------------------*/
192
193 #define SET_INK \
194 if (buf->getTone() == buf->getMaxTone()) *buf = TPixelCM32(inkIndex, 22, 0);
195
drawSegment(TRasterCM32P & r,const TAutocloser::Segment & s,USHORT inkIndex)196 void drawSegment(TRasterCM32P &r, const TAutocloser::Segment &s,
197 USHORT inkIndex) {
198 int wrap = r->getWrap();
199 TPixelCM32 *buf = r->pixels();
200 /*
201 int i, j;
202 for (i=0; i<r->getLy();i++)
203 {
204 for (j=0; j<r->getLx();j++, buf++)
205 *buf = (1<<4)|0xf;
206 buf += wrap-r->getLx();
207 }
208 return;
209 */
210
211 int x, y, dx, dy, d, incr_1, incr_2;
212
213 int x1 = s.first.x;
214 int y1 = s.first.y;
215 int x2 = s.second.x;
216 int y2 = s.second.y;
217
218 if (x1 > x2) {
219 std::swap(x1, x2);
220 std::swap(y1, y2);
221 }
222
223 buf += y1 * wrap + x1;
224
225 dx = x2 - x1;
226 dy = y2 - y1;
227
228 x = y = 0;
229
230 if (dy >= 0) {
231 if (dy <= dx)
232 DRAW_SEGMENT(x, y, dx, dy, (buf++), (buf += wrap + 1), SET_INK)
233 else
234 DRAW_SEGMENT(y, x, dy, dx, (buf += wrap), (buf += wrap + 1), SET_INK)
235 } else {
236 dy = -dy;
237 if (dy <= dx)
238 DRAW_SEGMENT(x, y, dx, dy, (buf++), (buf -= (wrap - 1)), SET_INK)
239 else
240 DRAW_SEGMENT(y, x, dy, dx, (buf -= wrap), (buf -= (wrap - 1)), SET_INK)
241 }
242 }
243
244 /*------------------------------------------------------------------------*/
245
246 } // namespace
247 /*------------------------------------------------------------------------*/
248
compute(vector<Segment> & closingSegmentArray)249 void TAutocloser::Imp::compute(vector<Segment> &closingSegmentArray) {
250 vector<TPoint> endpoints;
251 try {
252 assert(closingSegmentArray.empty());
253
254 TRasterCM32P raux;
255
256 if (!(raux = (TRasterCM32P)m_raster))
257 throw TException("Unable to autoclose a not CM32 image.");
258
259 if (m_raster->getLx() == 0 || m_raster->getLy() == 0)
260 throw TException("Autoclose error: bad image size");
261
262 // Lx = r->lx;
263 // Ly = r->ly;
264
265 TRasterGR8P braux = makeByteRaster(raux);
266
267 m_bRaster =
268 braux->extract(TRect(2, 2, braux->getLx() - 3, braux->getLy() - 3));
269 m_bRaster->lock();
270 m_br = m_bRaster->getRawData();
271 m_bWrap = m_bRaster->getWrap();
272
273 m_displaceVector[0] = -m_bWrap - 1;
274 m_displaceVector[1] = -m_bWrap;
275 m_displaceVector[2] = -m_bWrap + 1;
276 m_displaceVector[3] = -1;
277 m_displaceVector[4] = +1;
278 m_displaceVector[5] = m_bWrap - 1;
279 m_displaceVector[6] = m_bWrap;
280 m_displaceVector[7] = m_bWrap + 1;
281
282 skeletonize(endpoints);
283
284 findMeetingPoints(endpoints, closingSegmentArray);
285 raux->lock();
286 for (int i = 0; i < (int)closingSegmentArray.size(); i++)
287 drawSegment(raux, closingSegmentArray[i], m_inkIndex);
288 raux->unlock();
289 // copy(m_bRaster, raux);
290 m_bRaster->unlock();
291 m_br = 0;
292 }
293
294 catch (TException &e) {
295 throw e;
296 }
297 }
298
299 /*------------------------------------------------------------------------*/
300
copy(const TRasterGR8P & br,TRaster32P & r)301 void TAutocloser::Imp::copy(const TRasterGR8P &br, TRaster32P &r) {
302 assert(r->getLx() == br->getLx() && r->getLy() == br->getLy());
303 int i, j;
304
305 int lx = r->getLx();
306 int ly = r->getLy();
307 br->lock();
308 r->lock();
309 UCHAR *bbuf = br->getRawData();
310 TPixel *buf = (TPixel *)r->getRawData();
311
312 for (i = 0; i < ly; i++) {
313 for (j = 0; j < lx; j++, buf++, bbuf++) {
314 buf->m = 255;
315 if ((*bbuf) & 0x40)
316 buf->r = 255, buf->g = buf->b = 0;
317 else if (isInk(bbuf))
318 buf->r = buf->g = buf->b = 0;
319 else
320 buf->r = buf->g = buf->b = 255;
321 }
322 buf += r->getWrap() - lx;
323 bbuf += br->getWrap() - lx;
324 }
325
326 br->unlock();
327 r->unlock();
328 }
329
330 /*=============================================================================*/
331
332 namespace {
333
intersect_segment(int x1,int y1,int x2,int y2,int i,double * ris)334 int intersect_segment(int x1, int y1, int x2, int y2, int i, double *ris) {
335 if ((i < tmin(y1, y2)) || (i > tmax(y1, y2)) || (y1 == y2)) return 0;
336
337 *ris = ((double)((x1 - x2) * (i - y2)) / (double)(y1 - y2) + x2);
338
339 return 1;
340 }
341
342 /*=============================================================================*/
343
distance2(const TPoint p0,const TPoint p1)344 inline int distance2(const TPoint p0, const TPoint p1) {
345 return (p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y);
346 }
347
348 /*=============================================================================*/
349
closerPoint(const vector<TAutocloser::Segment> & points,vector<bool> & marks,int index)350 int closerPoint(const vector<TAutocloser::Segment> &points, vector<bool> &marks,
351 int index) {
352 assert(points.size() == marks.size());
353
354 int min, curr;
355 int minval = 9999999;
356
357 min = index + 1;
358
359 for (curr = index + 1; curr < (int)points.size(); curr++)
360 if (!(marks[curr])) {
361 int distance = distance2(points[index].first, points[curr].first);
362
363 if (distance < minval) {
364 minval = distance;
365 min = curr;
366 }
367 }
368
369 marks[min] = true;
370 return min;
371 }
372
373 /*------------------------------------------------------------------------*/
374
intersect_triangle(int x1a,int y1a,int x2a,int y2a,int x3a,int y3a,int x1b,int y1b,int x2b,int y2b,int x3b,int y3b)375 int intersect_triangle(int x1a, int y1a, int x2a, int y2a, int x3a, int y3a,
376 int x1b, int y1b, int x2b, int y2b, int x3b, int y3b) {
377 int minx, maxx, miny, maxy, i;
378 double xamin, xamax, xbmin, xbmax, val;
379
380 miny = tmax(tmin(y1a, y2a, y3a), tmin(y1b, y2b, y3b));
381 maxy = tmin(tmax(y1a, y2a, y3a), tmax(y1b, y2b, y3b));
382 if (maxy < miny) return 0;
383
384 minx = tmax(tmin(x1a, x2a, x3a), tmin(x1b, x2b, x3b));
385 maxx = tmin(tmax(x1a, x2a, x3a), tmax(x1b, x2b, x3b));
386 if (maxx < minx) return 0;
387
388 for (i = miny; i <= maxy; i++) {
389 xamin = xamax = xbmin = xbmax = 0.0;
390
391 intersect_segment(x1a, y1a, x2a, y2a, i, &xamin);
392
393 if (intersect_segment(x1a, y1a, x3a, y3a, i, &val))
394 if (xamin)
395 xamax = val;
396 else
397 xamin = val;
398
399 if (!xamax) intersect_segment(x2a, y2a, x3a, y3a, i, &xamax);
400
401 if (xamax < xamin) {
402 val = xamin, xamin = xamax, xamax = val;
403 }
404
405 intersect_segment(x1b, y1b, x2b, y2b, i, &xbmin);
406
407 if (intersect_segment(x1b, y1b, x3b, y3b, i, &val))
408 if (xbmin)
409 xbmax = val;
410 else
411 xbmin = val;
412
413 if (!xbmax) intersect_segment(x2b, y2b, x3b, y3b, i, &xbmax);
414
415 if (xbmax < xbmin) {
416 val = xbmin, xbmin = xbmax, xbmax = val;
417 }
418
419 if (!((tceil(xamax) < tfloor(xbmin)) || (tceil(xbmax) < tfloor(xamin))))
420 return 1;
421 }
422 return 0;
423 }
424
425 /*------------------------------------------------------------------------*/
426
427 } // namespace
428
429 /*------------------------------------------------------------------------*/
430
notInsidePath(const TPoint & p,const TPoint & q)431 int TAutocloser::Imp::notInsidePath(const TPoint &p, const TPoint &q) {
432 int tmp, x, y, dx, dy, d, incr_1, incr_2;
433 int x1, y1, x2, y2;
434
435 x1 = p.x;
436 y1 = p.y;
437 x2 = q.x;
438 y2 = q.y;
439
440 if (x1 > x2) {
441 tmp = x1, x1 = x2, x2 = tmp;
442 tmp = y1, y1 = y2, y2 = tmp;
443 }
444 UCHAR *br = getPtr(x1, y1);
445
446 dx = x2 - x1;
447 dy = y2 - y1;
448 x = y = 0;
449
450 if (dy >= 0) {
451 if (dy <= dx)
452 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1),
453 if (!((*br) & 0x2)) return true)
454 else
455 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
456 if (!((*br) & 0x2)) return true)
457 } else {
458 dy = -dy;
459 if (dy <= dx)
460 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1),
461 if (!((*br) & 0x2)) return true)
462 else
463 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
464 if (!((*br) & 0x2)) return true)
465 }
466
467 return 0;
468 }
469
470 /*------------------------------------------------------------------------*/
471
exploreTwoSpots(const TAutocloser::Segment & s0,const TAutocloser::Segment & s1)472 int TAutocloser::Imp::exploreTwoSpots(const TAutocloser::Segment &s0,
473 const TAutocloser::Segment &s1) {
474 int x1a, y1a, x2a, y2a, x3a, y3a, x1b, y1b, x2b, y2b, x3b, y3b;
475
476 x1a = s0.first.x;
477 y1a = s0.first.y;
478 x1b = s1.first.x;
479 y1b = s1.first.y;
480
481 TPoint p0aux = s0.second;
482 TPoint p1aux = s1.second;
483
484 if (x1a == p0aux.x && y1a == p0aux.y) return 0;
485 if (x1b == p1aux.x && y1b == p1aux.y) return 0;
486
487 x2a = tround(x1a + (p0aux.x - x1a) * m_csp - (p0aux.y - y1a) * m_snp);
488 y2a = tround(y1a + (p0aux.x - x1a) * m_snp + (p0aux.y - y1a) * m_csp);
489 x3a = tround(x1a + (p0aux.x - x1a) * m_csm - (p0aux.y - y1a) * m_snm);
490 y3a = tround(y1a + (p0aux.x - x1a) * m_snm + (p0aux.y - y1a) * m_csm);
491
492 x2b = tround(x1b + (p1aux.x - x1b) * m_csp - (p1aux.y - y1b) * m_snp);
493 y2b = tround(y1b + (p1aux.x - x1b) * m_snp + (p1aux.y - y1b) * m_csp);
494 x3b = tround(x1b + (p1aux.x - x1b) * m_csm - (p1aux.y - y1b) * m_snm);
495 y3b = tround(y1b + (p1aux.x - x1b) * m_snm + (p1aux.y - y1b) * m_csm);
496
497 return (intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x2a, y2a, x1b, y1b,
498 p1aux.x, p1aux.y, x2b, y2b) ||
499 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x3a, y3a, x1b, y1b,
500 p1aux.x, p1aux.y, x2b, y2b) ||
501 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x2a, y2a, x1b, y1b,
502 p1aux.x, p1aux.y, x3b, y3b) ||
503 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x3a, y3a, x1b, y1b,
504 p1aux.x, p1aux.y, x3b, y3b));
505 }
506
507 /*------------------------------------------------------------------------*/
508
findMeetingPoints(vector<TPoint> & endpoints,vector<Segment> & closingSegments)509 void TAutocloser::Imp::findMeetingPoints(vector<TPoint> &endpoints,
510 vector<Segment> &closingSegments) {
511 int i;
512 double alfa;
513 alfa = m_spotAngle / AUT_SPOT_SAMPLES;
514 m_csp = cos(m_spotAngle / 5);
515 m_snp = sin(m_spotAngle / 5);
516 m_csm = cos(-m_spotAngle / 5);
517 m_snm = sin(-m_spotAngle / 5);
518 m_csa = cos(alfa);
519 m_sna = sin(alfa);
520 m_csb = cos(-alfa);
521 m_snb = sin(-alfa);
522
523 vector<Segment> orientedEndpoints(endpoints.size());
524 for (i = 0; i < (int)endpoints.size(); i++)
525 orientedEndpoints[i].first = endpoints[i];
526
527 int size = -1;
528
529 while ((int)closingSegments.size() > size && !orientedEndpoints.empty()) {
530 size = closingSegments.size();
531 do
532 calculateWeightAndDirection(orientedEndpoints);
533 while (spotResearchTwoPoints(orientedEndpoints, closingSegments));
534
535 do
536 calculateWeightAndDirection(orientedEndpoints);
537 while (spotResearchOnePoint(orientedEndpoints, closingSegments));
538 }
539 }
540
541 /*------------------------------------------------------------------------*/
542
allMarked(const vector<bool> & marks,int index)543 bool allMarked(const vector<bool> &marks, int index) {
544 int i;
545
546 for (i = index + 1; i < (int)marks.size(); i++)
547 if (!marks[i]) return false;
548 return true;
549 }
550
551 /*------------------------------------------------------------------------*/
552
spotResearchTwoPoints(vector<Segment> & endpoints,vector<Segment> & closingSegments)553 bool TAutocloser::Imp::spotResearchTwoPoints(vector<Segment> &endpoints,
554 vector<Segment> &closingSegments) {
555 int i, distance, current = 0, closerIndex;
556 int sqrDistance = m_closingDistance * m_closingDistance;
557 bool found = 0;
558 vector<bool> marks(endpoints.size());
559
560 while (current < (int)endpoints.size() - 1) {
561 found = 0;
562 for (i = current + 1; i < (int)marks.size(); i++) marks[i] = false;
563 distance = 0;
564
565 while (!found && (distance <= sqrDistance) && !allMarked(marks, current)) {
566 closerIndex = closerPoint(endpoints, marks, current);
567 if (exploreTwoSpots(endpoints[current], endpoints[closerIndex]) &&
568 notInsidePath(endpoints[current].first,
569 endpoints[closerIndex].first)) {
570 drawInByteRaster(endpoints[current].first,
571 endpoints[closerIndex].first);
572 closingSegments.push_back(
573 Segment(endpoints[current].first, endpoints[closerIndex].first));
574
575 if (!EndpointTable[neighboursCode(
576 getPtr(endpoints[closerIndex].first))]) {
577 std::vector<Segment>::iterator it = endpoints.begin();
578 std::advance(it, closerIndex);
579 endpoints.erase(it);
580 std::vector<bool>::iterator it1 = marks.begin();
581 std::advance(it1, closerIndex);
582 marks.erase(it1);
583 }
584 found = true;
585 }
586 }
587
588 if (found) {
589 std::vector<Segment>::iterator it = endpoints.begin();
590 std::advance(it, current);
591 endpoints.erase(it);
592 std::vector<bool>::iterator it1 = marks.begin();
593 std::advance(it1, current);
594 marks.erase(it1);
595 } else
596 current++;
597 }
598 return found;
599 }
600
601 /*------------------------------------------------------------------------*/
602 /*
603 static void clear_marks(POINT *p)
604 {
605 while (p)
606 {
607 p->mark = 0;
608 p = p->next;
609 }
610 }
611
612
613 static int there_are_unmarked(POINT *p)
614 {
615 while (p)
616 {
617 if (!p->mark) return 1;
618 p = p->next;
619 }
620 return 0;
621 }
622 */
623
624 /*------------------------------------------------------------------------*/
625
calculateWeightAndDirection(vector<Segment> & orientedEndpoints)626 void TAutocloser::Imp::calculateWeightAndDirection(
627 vector<Segment> &orientedEndpoints) {
628 // UCHAR *br;
629 int lx = m_raster->getLx();
630 int ly = m_raster->getLy();
631
632 std::vector<Segment>::iterator it = orientedEndpoints.begin();
633
634 while (it != orientedEndpoints.end()) {
635 TPoint p0 = it->first;
636 TPoint &p1 = it->second;
637
638 // br = (UCHAR *)m_bRaster->pixels(p0.y)+p0.x;
639 // code = neighboursCode(br);
640 /*if (!EndpointTable[code])
641 {
642 it = orientedEndpoints.erase(it);
643 continue;
644 }*/
645 TPoint displAverage = visitEndpoint(getPtr(p0));
646
647 p1 = p0 - displAverage;
648
649 /*if ((point->x2<0 && point->y2<0) || (point->x2>Lx && point->y2>Ly))
650 * printf("che palle!!!!!!\n");*/
651
652 if (p1.x < 0) {
653 p1.y = tround(p0.y - (float)((p0.y - p1.y) * p0.x) / (p0.x - p1.x));
654 p1.x = 0;
655 } else if (p1.x > lx) {
656 p1.y =
657 tround(p0.y - (float)((p0.y - p1.y) * (p0.x - lx)) / (p0.x - p1.x));
658 p1.x = lx;
659 }
660
661 if (p1.y < 0) {
662 p1.x = tround(p0.x - (float)((p0.x - p1.x) * p0.y) / (p0.y - p1.y));
663 p1.y = 0;
664 } else if (p1.y > ly) {
665 p1.x =
666 tround(p0.x - (float)((p0.x - p1.x) * (p0.y - ly)) / (p0.y - p1.y));
667 p1.y = ly;
668 }
669 it++;
670 }
671 }
672
673 /*------------------------------------------------------------------------*/
674
spotResearchOnePoint(vector<Segment> & endpoints,vector<Segment> & closingSegments)675 bool TAutocloser::Imp::spotResearchOnePoint(vector<Segment> &endpoints,
676 vector<Segment> &closingSegments) {
677 int count = 0;
678 bool ret = false;
679
680 while (count < (int)endpoints.size()) {
681 TPoint p;
682
683 if (exploreSpot(endpoints[count], p)) {
684 ret = true;
685 drawInByteRaster(endpoints[count].first, p);
686 closingSegments.push_back(Segment(endpoints[count].first, p));
687 cancelFromArray(endpoints, p, count);
688 if (!EndpointTable[neighboursCode(getPtr(endpoints[count].first))]) {
689 std::vector<Segment>::iterator it = endpoints.begin();
690 std::advance(it, count);
691 endpoints.erase(it);
692 continue;
693 }
694 }
695 count++;
696 }
697
698 return ret;
699 }
700
701 /*------------------------------------------------------------------------*/
702
exploreSpot(const Segment & s,TPoint & p)703 bool TAutocloser::Imp::exploreSpot(const Segment &s, TPoint &p) {
704 int x1, y1, x2, y2, x3, y3, i;
705 double x2a, y2a, x2b, y2b, xnewa, ynewa, xnewb, ynewb;
706 int lx = m_raster->getLx();
707 int ly = m_raster->getLy();
708
709 x1 = s.first.x;
710 y1 = s.first.y;
711 x2 = s.second.x;
712 y2 = s.second.y;
713
714 if (x1 == x2 && y1 == y2) return 0;
715
716 if (exploreRay(getPtr(x1, y1), s, p)) return true;
717
718 x2a = x2b = (double)x2;
719 y2a = y2b = (double)y2;
720
721 for (i = 0; i < AUT_SPOT_SAMPLES; i++) {
722 xnewa = x1 + (x2a - x1) * m_csa - (y2a - y1) * m_sna;
723 ynewa = y1 + (y2a - y1) * m_csa + (x2a - x1) * m_sna;
724 x3 = tround(xnewa);
725 y3 = tround(ynewa);
726 if ((x3 != tround(x2a) || y3 != tround(y2a)) && x3 > 0 && x3 < lx &&
727 y3 > 0 && y3 < ly &&
728 exploreRay(
729 getPtr(x1, y1),
730 Segment(TPoint(x1, y1), TPoint(tround(xnewa), tround(ynewa))), p))
731 return true;
732
733 x2a = xnewa;
734 y2a = ynewa;
735
736 xnewb = x1 + (x2b - x1) * m_csb - (y2b - y1) * m_snb;
737 ynewb = y1 + (y2b - y1) * m_csb + (x2b - x1) * m_snb;
738 x3 = tround(xnewb);
739 y3 = tround(ynewb);
740 if ((x3 != tround(x2b) || y3 != tround(y2b)) && x3 > 0 && x3 < lx &&
741 y3 > 0 && y3 < ly &&
742 exploreRay(
743 getPtr(x1, y1),
744 Segment(TPoint(x1, y1), TPoint(tround(xnewb), tround(ynewb))), p))
745 return true;
746
747 x2b = xnewb;
748 y2b = ynewb;
749 }
750 return false;
751 }
752
753 /*------------------------------------------------------------------------*/
754
exploreRay(UCHAR * br,Segment s,TPoint & p)755 bool TAutocloser::Imp::exploreRay(UCHAR *br, Segment s, TPoint &p) {
756 int x, y, dx, dy, d, incr_1, incr_2, inside_ink;
757
758 inside_ink = 1;
759
760 x = 0;
761 y = 0;
762
763 if (s.first.x < s.second.x) {
764 dx = s.second.x - s.first.x;
765 dy = s.second.y - s.first.y;
766 if (dy >= 0)
767 if (dy <= dx)
768 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1),
769 EXPLORE_RAY_ISTR((s.first.x + x)))
770 else
771 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
772 EXPLORE_RAY_ISTR((s.first.x + x)))
773 else {
774 dy = -dy;
775 if (dy <= dx)
776 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1),
777 EXPLORE_RAY_ISTR((s.first.x + x)))
778 else
779 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
780 EXPLORE_RAY_ISTR((s.first.x + x)))
781 }
782 } else {
783 dx = s.first.x - s.second.x;
784 dy = s.second.y - s.first.y;
785 if (dy >= 0)
786 if (dy <= dx)
787 DRAW_SEGMENT(x, y, dx, dy, (br--), (br += m_bWrap - 1),
788 EXPLORE_RAY_ISTR((s.first.x - x)))
789 else
790 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap - 1),
791 EXPLORE_RAY_ISTR((s.first.x - x)))
792 else {
793 dy = -dy;
794 if (dy <= dx)
795 DRAW_SEGMENT(x, y, dx, dy, (br--), (br -= m_bWrap + 1),
796 EXPLORE_RAY_ISTR((s.first.x - x)))
797 else
798 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap + 1),
799 EXPLORE_RAY_ISTR((s.first.x - x)))
800 }
801 }
802 return false;
803 }
804
805 /*------------------------------------------------------------------------*/
806
drawInByteRaster(const TPoint & p0,const TPoint & p1)807 void TAutocloser::Imp::drawInByteRaster(const TPoint &p0, const TPoint &p1) {
808 int x, y, dx, dy, d, incr_1, incr_2;
809 UCHAR *br;
810
811 if (p0.x > p1.x) {
812 br = getPtr(p1);
813 dx = p0.x - p1.x;
814 dy = p0.y - p1.y;
815 } else {
816 br = getPtr(p0);
817 dx = p1.x - p0.x;
818 dy = p1.y - p0.y;
819 }
820
821 x = y = 0;
822
823 if (dy >= 0) {
824 if (dy <= dx)
825 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1), ((*br) |= 0x41))
826 else
827 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
828 ((*br) |= 0x41))
829 } else {
830 dy = -dy;
831 if (dy <= dx)
832 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1), ((*br) |= 0x41))
833 else
834 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
835 ((*br) |= 0x41))
836 }
837 }
838
839 /*------------------------------------------------------------------------*/
840
visitEndpoint(UCHAR * br)841 TPoint TAutocloser::Imp::visitEndpoint(UCHAR *br)
842
843 {
844 m_displAverage = TPointD();
845
846 m_visited = 0;
847
848 visitPix(br, m_closingDistance, TPoint());
849 cancelMarks(br);
850
851 return TPoint(convert((1.0 / m_visited) * m_displAverage));
852 }
853
854 /*------------------------------------------------------------------------*/
855
visitPix(UCHAR * br,int toVisit,const TPoint & dis)856 void TAutocloser::Imp::visitPix(UCHAR *br, int toVisit, const TPoint &dis) {
857 UCHAR b = 0;
858 int i, pixToVisit = 0;
859
860 *br |= 0x10;
861 m_visited++;
862 m_displAverage.x += dis.x;
863 m_displAverage.y += dis.y;
864
865 toVisit--;
866 if (toVisit == 0) return;
867
868 for (i = 0; i < 8; i++) {
869 UCHAR *v = br + m_displaceVector[i];
870 if (isInk(v) && !((*v) & 0x10)) {
871 b |= (1 << i);
872 pixToVisit++;
873 }
874 }
875
876 if (pixToVisit == 0) return;
877
878 if (pixToVisit <= 4) toVisit = troundp(toVisit / (double)pixToVisit);
879
880 if (toVisit == 0) return;
881
882 int x[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
883 int y[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
884
885 for (i = 0; i < 8; i++)
886 if (b & (1 << i))
887 visitPix(br + m_displaceVector[i], toVisit, dis + TPoint(x[i], y[i]));
888 }
889
890 /*------------------------------------------------------------------------*/
891
cancelMarks(UCHAR * br)892 void TAutocloser::Imp::cancelMarks(UCHAR *br) {
893 *br &= 0xef;
894 int i;
895
896 for (i = 0; i < 8; i++) {
897 UCHAR *v = br + m_displaceVector[i];
898
899 if (isInk(v) && (*v) & 0x10) cancelMarks(v);
900 }
901 }
902
903 /*=============================================================================*/
904
905 /*=============================================================================*/
906 /*=============================================================================*/
907 /*=============================================================================*/
908 /*=============================================================================*/
909 /*=============================================================================*/
910 /*=============================================================================*/
911 /*=============================================================================*/
912 /*=============================================================================*/
913 /*=============================================================================*/
914 /*=============================================================================*/
915
916 /*=============================================================================*/
917
skeletonize(vector<TPoint> & endpoints)918 void TAutocloser::Imp::skeletonize(vector<TPoint> &endpoints) {
919 vector<Seed> seeds;
920
921 findSeeds(seeds, endpoints);
922
923 erase(seeds, endpoints);
924 }
925
926 /*------------------------------------------------------------------------*/
927
findSeeds(vector<Seed> & seeds,vector<TPoint> & endpoints)928 void TAutocloser::Imp::findSeeds(vector<Seed> &seeds,
929 vector<TPoint> &endpoints) {
930 int i, j;
931 UCHAR preseed;
932
933 UCHAR *br = m_br;
934
935 for (i = 0; i < m_bRaster->getLy(); i++) {
936 for (j = 0; j < m_bRaster->getLx(); j++, br++) {
937 if (notMarkedBorderInk(br)) {
938 preseed = FirstPreseedTable[neighboursCode(br)];
939
940 if (preseed != 8) /*non e' un pixel isolato*/
941 {
942 seeds.push_back(Seed(br, preseed));
943 circuitAndMark(br, preseed);
944 } else {
945 (*br) |= 0x8;
946 endpoints.push_back(getCoordinates(br));
947 }
948 }
949 }
950 br += m_bWrap - m_bRaster->getLx();
951 }
952 }
953
954 /*------------------------------------------------------------------------*/
955
circuitAndMark(UCHAR * seed,UCHAR preseed)956 void TAutocloser::Imp::circuitAndMark(UCHAR *seed, UCHAR preseed) {
957 UCHAR *walker;
958 UCHAR displ, prewalker;
959
960 *seed |= 0x4;
961
962 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
963 assert(displ >= 0 && displ < 8);
964
965 walker = seed + m_displaceVector[displ];
966 prewalker = displ ^ 0x7;
967
968 while ((walker != seed) || (preseed != prewalker)) {
969 *walker |= 0x4; /* metto la marca di passaggio */
970
971 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
972 assert(displ >= 0 && displ < 8);
973 walker += m_displaceVector[displ];
974 prewalker = displ ^ 0x7;
975 }
976
977 return;
978 }
979
980 /*------------------------------------------------------------------------*/
981
erase(vector<Seed> & seeds,vector<TPoint> & endpoints)982 void TAutocloser::Imp::erase(vector<Seed> &seeds, vector<TPoint> &endpoints) {
983 int i, size = 0, oldSize;
984 UCHAR *seed, preseed, code, displ;
985 oldSize = seeds.size();
986
987 while (oldSize != size) {
988 oldSize = size;
989 size = seeds.size();
990
991 for (i = oldSize; i < size; i++) {
992 seed = seeds[i].m_ptr;
993 preseed = seeds[i].m_preseed;
994
995 if (!isInk(seed)) {
996 code = NextSeedTable[neighboursCode(seed)];
997 seed += m_displaceVector[code & 0x7];
998 preseed = (code & 0x38) >> 3;
999 }
1000
1001 if (circuitAndCancel(seed, preseed, endpoints)) {
1002 if (isInk(seed)) {
1003 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
1004 assert(displ >= 0 && displ < 8);
1005 seeds.push_back(Seed(seed + m_displaceVector[displ], displ ^ 0x7));
1006
1007 } else /* il seed e' stato cancellato */
1008 {
1009 code = NextSeedTable[neighboursCode(seed)];
1010 seeds.push_back(
1011 Seed(seed + m_displaceVector[code & 0x7], (code & 0x38) >> 3));
1012 }
1013 }
1014 }
1015 }
1016 }
1017
1018 /*------------------------------------------------------------------------*/
1019
circuitAndCancel(UCHAR * seed,UCHAR preseed,vector<TPoint> & endpoints)1020 bool TAutocloser::Imp::circuitAndCancel(UCHAR *seed, UCHAR preseed,
1021 vector<TPoint> &endpoints) {
1022 UCHAR *walker, *previous;
1023 UCHAR displ, prewalker;
1024 bool ret = false;
1025
1026 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
1027 assert(displ >= 0 && displ < 8);
1028
1029 if ((displ == preseed) && !((*seed) & 0x8)) {
1030 endpoints.push_back(getCoordinates(seed));
1031 *seed |= 0x8;
1032 }
1033
1034 walker = seed + m_displaceVector[displ];
1035 prewalker = displ ^ 0x7;
1036
1037 while ((walker != seed) || (preseed != prewalker)) {
1038 assert(prewalker >= 0 && prewalker < 8);
1039 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
1040 assert(displ >= 0 && displ < 8);
1041
1042 if ((displ == prewalker) && !((*walker) & 0x8)) {
1043 endpoints.push_back(getCoordinates(walker));
1044 *walker |= 0x8;
1045 }
1046 previous = walker + m_displaceVector[prewalker];
1047 if (ConnectionTable[neighboursCode(previous)]) {
1048 ret = true;
1049 if (previous != seed) eraseInk(previous);
1050 }
1051 walker += m_displaceVector[displ];
1052 prewalker = displ ^ 0x7;
1053 }
1054
1055 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
1056
1057 if ((displ == preseed) && !((*seed) & 0x8)) {
1058 endpoints.push_back(getCoordinates(seed));
1059 *seed |= 0x8;
1060 }
1061
1062 if (ConnectionTable[neighboursCode(seed + m_displaceVector[preseed])]) {
1063 ret = true;
1064 eraseInk(seed + m_displaceVector[preseed]);
1065 }
1066
1067 if (ConnectionTable[neighboursCode(seed)]) {
1068 ret = true;
1069 eraseInk(seed);
1070 }
1071
1072 return ret;
1073 }
1074
1075 /*=============================================================================*/
1076
cancelFromArray(vector<Segment> & array,TPoint p,int & count)1077 void TAutocloser::Imp::cancelFromArray(vector<Segment> &array, TPoint p,
1078 int &count) {
1079 std::vector<Segment>::iterator it = array.begin();
1080 int i = 0;
1081
1082 for (; it != array.end(); ++it, i++)
1083 if (it->first == p) {
1084 if (!EndpointTable[neighboursCode(getPtr(p))]) {
1085 assert(i != count);
1086 if (i < count) count--;
1087 array.erase(it);
1088 }
1089 return;
1090 }
1091 }
1092
1093 /*------------------------------------------------------------------------*/
1094 /*
1095 int is_in_list(LIST list, UCHAR *br)
1096 {
1097 POINT *aux;
1098 aux = list.head;
1099
1100 while(aux)
1101 {
1102 if (aux->p == br) return 1;
1103 aux = aux->next;
1104 }
1105 return 0;
1106 }
1107 */
1108
1109 /*=============================================================================*/
1110
TAutocloser(const TRasterP & r)1111 TAutocloser::TAutocloser(const TRasterP &r) { m_imp = new Imp(r); }
1112
1113 //.......................
1114
~TAutocloser()1115 TAutocloser::~TAutocloser() { delete m_imp; }
1116
1117 //-------------------------------------------------
1118
1119 // if this function is never used, use default values
setClosingDistance(int d)1120 void TAutocloser::setClosingDistance(int d) { m_imp->m_closingDistance = d; }
1121
1122 //-------------------------------------------------
1123
getClosingDistance() const1124 int TAutocloser::getClosingDistance() const { return m_imp->m_closingDistance; }
1125
1126 //-------------------------------------------------
1127
setSpotAngle(double degrees)1128 void TAutocloser::setSpotAngle(double degrees) {
1129 if (degrees <= 0.0) degrees = 1.0;
1130
1131 m_imp->m_spotAngle = (degrees * TConsts::pi) / 360.0;
1132 }
1133
1134 //-------------------------------------------------
1135
getSpotAngle() const1136 double TAutocloser::getSpotAngle() const { return m_imp->m_spotAngle; }
1137
1138 //-------------------------------------------------
1139
setInkIndex(int inkIndex)1140 void TAutocloser::setInkIndex(int inkIndex) { m_imp->m_inkIndex = inkIndex; }
1141
1142 //-------------------------------------------------
1143
getInkIndex() const1144 int TAutocloser::getInkIndex() const { return m_imp->m_inkIndex; }
1145
1146 //-------------------------------------------------
1147
compute(vector<Segment> & closingSegmentArray)1148 void TAutocloser::compute(vector<Segment> &closingSegmentArray) {
1149 m_imp->compute(closingSegmentArray);
1150 }
1151 //-------------------------------------------------
1152