1 
2 
3 #include "tregion.h"
4 
5 // TnzCore includes
6 #include "tregionprop.h"
7 #include "tcurves.h"
8 #include "tstroke.h"
9 #include "tcurveutil.h"
10 
11 // tcg includes
12 #include "tcg/numeric_ops.h"
13 #include "tcg/poly_ops.h"
14 
15 // STD includes
16 #include <set>
17 
18 // DEFINE_CLASS_CODE(TEdge, 40)
19 
20 //=============================================================================
21 /*
22 void foo()
23 {
24   TEdgeP p1 = new TEdge();
25   TEdgeP p2 = new TEdge(*p1);
26   p1 = 0;
27 
28   TEdge *e = new TEdge;
29 
30 
31 
32 }
33 */
34 
35 //=============================================================================
36 
compareEdge(const TEdge & a,const TEdge & b)37 static bool compareEdge(const TEdge &a, const TEdge &b) {
38   return a.m_s == b.m_s;
39 }
40 
41 //-----------------------------------------------------------------------------
42 
43 class TRegion::Imp {
44   double m_polyStep;
45 
46 public:
47   TRegionProp *m_prop;
48 
49   mutable TRectD m_bBox;
50   mutable bool m_isValidBBox;
51 
52   std::vector<TEdge *> m_edge;
53   std::vector<TRegion *> m_includedRegionArray;
54 
55 public:
Imp()56   Imp()
57       : m_polyStep(-1)
58       , m_prop(0)
59       , m_bBox()
60       , m_isValidBBox(true)
61       , m_edge()
62       , m_includedRegionArray() {}
63 
~Imp()64   ~Imp() {
65     delete m_prop;
66     for (UINT i = 0; i < m_includedRegionArray.size(); i++)
67       delete m_includedRegionArray[i];
68   }
69 
70   void printContains(const TPointD &p) const;
71 
invalidateBBox()72   void invalidateBBox() { m_isValidBBox = false; }
73 
74 #ifdef _DEBUG
checkRegion()75   void checkRegion() {
76     for (UINT i = 0; i < m_edge.size(); i++) {
77       TEdge *e = m_edge[i];
78       assert(e->getStyle() >= 0 && e->getStyle() <= 1000);
79       assert(e->m_w0 >= 0 && e->m_w1 <= 1);
80       assert(e->m_s->getChunkCount() >= 0 && e->m_s->getChunkCount() <= 10000);
81     }
82   }
83 #endif
84 
getBBox() const85   TRectD getBBox() const {
86     if (!m_isValidBBox) {
87       m_bBox = TRectD();
88 
89       for (UINT i = 0; i < m_edge.size(); i++)
90         m_bBox +=
91             m_edge[i]->m_s->getBBox(std::min(m_edge[i]->m_w0, m_edge[i]->m_w1),
92                                     std::max(m_edge[i]->m_w0, m_edge[i]->m_w1));
93 
94       m_isValidBBox = true;
95     }
96     return m_bBox;
97   }
98 
99   bool contains(const TPointD &p) const;
100   bool contains(const TRegion::Imp &p) const;
101 
102   // this function returns true only if p is contained in the region, taking
103   // into account holes in it.
104   bool noSubregionContains(const TPointD &p) const;
105   void addSubregion(TRegion *region);
106   // bool getPointInside(TPointD &p) const;
107   bool slowContains(const TRegion::Imp &r) const;
108   bool contains(const TStroke &s, bool mayIntersect) const;
109   bool isSubRegionOf(const TRegion::Imp &r) const;
110   bool getInternalPoint(TPointD &p, double left, double right, double y);
111   void computeScanlineIntersections(double y,
112                                     std::vector<double> &intersections) const;
113   bool thereAreintersections(const TStroke &s) const;
114 
115   int leftScanlineIntersections(const TPointD &p, double(TPointD::*h),
116                                 double(TPointD::*v)) const;
117 };
118 
119 //=============================================================================
120 
findRegion(const TRegion & r) const121 TRegion *TRegion::findRegion(const TRegion &r) const {
122   if (areAlmostEqual(r.getBBox(), getBBox(), 1e-3)) return (TRegion *)this;
123 
124   if (!getBBox().contains(r.getBBox())) return 0;
125   TRegion *ret;
126 
127   for (UINT i = 0; i < m_imp->m_includedRegionArray.size(); i++)
128     if ((ret = m_imp->m_includedRegionArray[i]->findRegion(r)) != 0) return ret;
129 
130   return 0;
131 }
132 
133 //=============================================================================
134 
TRegion()135 TRegion::TRegion() : m_imp(new TRegion::Imp()) {
136   // m_imp->m_fillStyle->setRegion(this);
137 }
138 
139 //-----------------------------------------------------------------------------
140 
~TRegion()141 TRegion::~TRegion() {}
142 
143 //-----------------------------------------------------------------------------
144 /*
145 bool TRegion::Imp::contains(const TPointD &p) const
146 {
147   bool leftIntersectionsAreOdd=false, rightIntersectionsAreOdd=false;
148 
149   if (!getBBox().contains(p))
150     return false;
151 
152   vector<TPointD> poly;
153   UINT i=0 ;
154   //region2polyline(poly, *this);
155 
156   for(; i<m_edge.size(); i++)
157     stroke2polyline( poly, *m_edge[i]->m_s, 1.0, m_edge[i]->m_w0,
158 m_edge[i]->m_w1);
159 
160   poly.push_back(poly.front());
161 
162   TRectD bbox = getBBox();
163 
164   double dist = (bbox.x1-bbox.x0)*0.5;
165 
166   TSegment horizSegment = TSegment(TPointD(bbox.x0-dist,
167 p.y),TPointD(bbox.x1+dist, p.y));
168 
169   for (i=0; i<poly.size()-1; i++)
170   {
171     vector<DoublePair> intersections;
172 
173     if (poly[i].y==poly[i+1].y && poly[i+1].y==p.y)
174       continue;
175 
176     if (intersect(TSegment(poly[i], poly[i+1]), horizSegment,
177       intersections))
178     {
179       assert(intersections.size()==1);
180 
181       TPointD pInt = horizSegment.getPoint(intersections[0].second);
182       if (pInt==poly[i+1])
183         continue;
184       if (pInt.x>p.x)
185         rightIntersectionsAreOdd = !rightIntersectionsAreOdd;
186       else
187         leftIntersectionsAreOdd = !leftIntersectionsAreOdd;
188     }
189   }
190 
191 
192   //assert(!(leftIntersectionsAreOdd^rightIntersectionsAreOdd)); //intersections
193 must be even!
194 
195   return leftIntersectionsAreOdd;
196 }
197 */
198 //-----------------------------------------------------------------------------
199 
200 // questa funzione fa l'intersezione della porzione [t0, t1) della quadratica q
201 // con una retta orizzontale passante per p.y,
202 // e setta i due booleani in base a quante intersezioni stanno a sx e a dx di p
203 
204 // il valore di ritorno dice se l'intersezione e' ad un estremo e se la curva
205 // sta tutta sopra(1) o tutta sotto) -1;
206 // questo valore viene riusato come input della successiva chiamata a findSide:
207 // se anche questa ha l'intersezione allo stesso estremo e sullo stesso
208 // lato (cuspide) quell'intersezione non conta(doppia, come con la tangente)
209 
210 //-----------------------------------------------------------------------------
211 
212 namespace {
213 
computeSide(const TQuadratic & q,double t,bool forward)214 inline int computeSide(const TQuadratic &q, double t, bool forward) {
215   double speedY = q.getSpeedY(t);
216   if (speedY == 0)  // se la tangente e' zero, non si riesce a capire su che
217                     // semipiano sta la curva rispetto alla semiretta
218                     // orizzontale campione. in questo caso e' sufficiente
219                     // vedere dove giace il terzo controlpoint della quad .
220     speedY =
221         (forward
222              ? (q.getP2().y - q.getPoint(t).y)
223              : (q.getPoint(t).y -
224                 q.getP0().y));  // q.getSpeedY(t+(forward?0.00001:-0.00001));
225   return speedY > 0 ? 1 : -1;
226 }
227 
computeIntersection(const TQuadratic & q,double t,double t0,double t1,double x,int sideOfPrevious,bool & leftAreOdd)228 inline void computeIntersection(const TQuadratic &q, double t, double t0,
229                                 double t1, double x, int sideOfPrevious,
230                                 bool &leftAreOdd) {
231   if (((t0 < t1 && t >= t0 && t < t1) || (t0 > t1 && t > t1 && t <= t0)) &&
232       q.getX(t) <= x) {
233     if (t == t0) {
234       assert(sideOfPrevious != 0);
235       if (computeSide(q, t0, t0 < t1) !=
236           sideOfPrevious)  // cuspide! non considero l'intersezione
237         return;
238     }
239     leftAreOdd = !leftAreOdd;
240   }
241 }
242 
243 //-----------------------------------------------------------------------------
244 
findSides(const TPointD & p,const TQuadratic & q,double t0,double t1,bool & leftAreOdd,int sideOfPrevious)245 __inline int findSides(const TPointD &p, const TQuadratic &q, double t0,
246                        double t1, bool &leftAreOdd, int sideOfPrevious) {
247   TRectD bbox = q.getBBox();
248 
249   // assert(!(t0==t1 && q.getPoint(t0).y==p.y));
250 
251   if (bbox.y0 > p.y || bbox.y1 < p.y) return 0;
252 
253   if (t0 == t1) return sideOfPrevious;
254 
255   double y0 = q.getP0().y;
256   double y1 = q.getP1().y;
257   double y2 = q.getP2().y;
258 
259   /* ottimizzazione....lenta.
260 if((q.getPoint(t0).y-p.y)*(q.getPoint(t1).y-p.y)<0)
261 {
262    if(bbox.x1<p.x) {leftAreOdd = !leftAreOdd; return; }
263    else if(bbox.x0>p.x) {rightAreOdd = !rightAreOdd; return; }
264   }
265 */
266 
267   double det;
268   double alfa = y0 - 2 * y1 + y2;
269 
270   if (!areAlmostEqual(
271           alfa, 0,
272           1e-10))  // alfa, il coefficiente di t^2, non e' zero: due soluzioni
273   {
274     det = y1 * y1 - y0 * y2 + p.y * alfa;
275     if (det < 0 ||
276         (det == 0 && y0 != p.y &&
277          y2 !=
278              p.y))  // con det<0 no soluzioni reali o due soluzioni coincidenti
279       // (a meno che le soluzioni non siano agli estremi, in quel caso e'
280       //  una sola!), due intersezioni stesso lato, posso scartare
281       return 0;
282     else {
283       double ta, tb;
284       det = sqrt(det);
285       ta = tb = (y0 - y1 + det) / alfa;
286       computeIntersection(q, ta, t0, t1, p.x, sideOfPrevious, leftAreOdd);
287 
288       if (det != 0) {
289         tb = (y0 - y1 - det) / alfa;
290         computeIntersection(q, tb, t0, t1, p.x, sideOfPrevious, leftAreOdd);
291       }
292 
293       if (ta == t1 || tb == t1)
294         return computeSide(q, t1, t1 < t0);  // q.getSpeedY(t1)>0?1:-1;
295       else
296         return 0;
297     }
298   } else  // alfa, il coefficiente di t^2 e' zero: una  sola soluzione
299   {
300     if (y2 == y0)  // segmento orizzontale
301       return sideOfPrevious;
302     double t = (p.y - y0) / (y2 - y0);
303 
304     if ((t0 < t1 && t >= t0 && t < t1) || (t0 > t1 && t > t1 && t <= t0)) {
305       if ((q.getP2().x - q.getP0().x) * t + q.getP0().x <= p.x) {
306         leftAreOdd = !leftAreOdd;
307         if (t == t0) {
308           assert(sideOfPrevious != 0);
309           if (((y2 - y0 > 0) ? 1 : -1) != sideOfPrevious)
310             leftAreOdd = !leftAreOdd;
311         }
312       }
313     }
314     if (t == t1)
315       return (y2 - y0 > 0) ? 1 : -1;  // q.getPoint(t0).y>p.y?1:-1;
316     else
317       return 0;
318   }
319 }
320 
321 //-----------------------------------------------------------------------------
322 
addIntersection(const TQuadratic & q,double t,double t0,double t1,std::vector<double> & intersections,double intersection,std::vector<int> & sides)323 void addIntersection(const TQuadratic &q, double t, double t0, double t1,
324                      std::vector<double> &intersections, double intersection,
325                      std::vector<int> &sides) {
326   int side = 0;
327 
328   if (areAlmostEqual(t, t0, 1e-4))
329     side =
330         (q.getPoint(t0 + ((t1 > t0) ? 0.01 : -0.01)).y - q.getPoint(t0).y) > 0
331             ? 1
332             : -1;
333   else if (areAlmostEqual(t, t1, 1e-4))
334     side =
335         (q.getPoint(t1 + ((t0 > t1) ? 0.01 : -0.01)).y - q.getPoint(t1).y) > 0
336             ? 1
337             : -1;
338 
339   if (!intersections.empty() &&
340       areAlmostEqual(intersection, intersections.back(), 1e-4)) {
341     // assert(areAlmostEqual(t, t0, 1e-3));
342     assert(sides.back() != 0);
343 
344     if (side == sides.back()) {
345       intersections.pop_back();
346       sides.pop_back();
347     }
348   } else {
349     intersections.push_back(intersection);
350     sides.push_back(side);
351   }
352 }
353 
354 //-----------------------------------------------------------------------------
355 
findIntersections(double y,const TQuadratic & q,double t0,double t1,std::vector<double> & intersections,std::vector<int> & sides)356 void findIntersections(double y, const TQuadratic &q, double t0, double t1,
357                        std::vector<double> &intersections,
358                        std::vector<int> &sides) {
359   TRectD bbox = q.getBBox();
360 
361   int side = 0;
362   if (t0 == t1 || bbox.y0 > y || bbox.y1 < y) return;
363 
364   double y0 = q.getP0().y;
365   double y1 = q.getP1().y;
366   double y2 = q.getP2().y;
367 
368   double alfa = y0 - 2 * y1 + y2;
369 
370   if (!areAlmostEqual(alfa, 0, 1e-10))  // la quadratica non e' un segmento
371   {
372     double det = y1 * y1 - y0 * y2 + y * alfa;
373     assert(det >= 0);
374 
375     if (det < 1e-6)  // con det==0 soluzioni coincidenti
376     {
377       double t = (y0 - y1) / alfa;
378       if (areAlmostEqual(t, t0, 1e-5) || areAlmostEqual(t, t1, 1e-5)) {
379         double s = 1 - t;
380         double intersection =
381             q.getP0().x * s * s + 2 * t * s * q.getP1().x + t * t * q.getP2().x;
382         addIntersection(q, t, t0, t1, intersections, intersection, sides);
383       }
384     } else {
385       double ta, tb;
386       bool rev = q.getPoint(t0).x > q.getPoint(t1).x;
387       // if (alfa<0) rev = !rev;
388 
389       det = sqrt(det);
390 
391       ta                   = (y0 - y1 + det) / alfa;
392       double sa            = 1 - ta;
393       double intersectiona = q.getP0().x * sa * sa + 2 * ta * sa * q.getP1().x +
394                              ta * ta * q.getP2().x;
395 
396       tb                   = (y0 - y1 - det) / alfa;
397       double sb            = 1 - tb;
398       double intersectionb = q.getP0().x * sb * sb + 2 * tb * sb * q.getP1().x +
399                              tb * tb * q.getP2().x;
400 
401       if ((rev && intersectiona < intersectionb) ||
402           (!rev && intersectiona > intersectionb))
403         std::swap(intersectiona, intersectionb), std::swap(ta, tb);
404 
405       if ((t0 < t1 && ta >= t0 && ta <= t1) ||
406           (t0 >= t1 && ta >= t1 && ta <= t0))
407         addIntersection(q, ta, t0, t1, intersections, intersectiona, sides);
408 
409       if ((t0 < t1 && tb >= t0 && tb <= t1) ||
410           (t0 >= t1 && tb >= t1 && tb <= t0))
411         addIntersection(q, tb, t0, t1, intersections, intersectionb, sides);
412     }
413   } else if (y2 != y0)  // la quadratica e' un segmento non orizzontale
414   {
415     if (y2 == y0) return;
416     double t = (y - y0) / (y2 - y0);
417 
418     if (!((t0 < t1 && t >= t0 && t <= t1) || (t0 >= t1 && t >= t1 && t <= t0)))
419       return;
420 
421     double intersection = (q.getP2().x - q.getP0().x) * t + q.getP0().x;
422     if (areAlmostEqual(t, t1, 1e-4))
423       side = (q.getPoint(t0).y > q.getPoint(t1).y) ? 1 : -1;
424     else if (areAlmostEqual(t, t0, 1e-4))
425       side = (q.getPoint(t1).y > q.getPoint(t0).y) ? 1 : -1;
426     if (!intersections.empty() &&
427         areAlmostEqual(intersection, intersections.back(), 1e-4)) {
428       // assert(areAlmostEqual(t, t0, 1e-4));
429       assert(sides.back() != 0);
430       assert(side != 0);
431       if (side == sides.back()) {
432         intersections.pop_back();
433         sides.pop_back();
434       }
435     } else {
436       intersections.push_back(intersection);
437       sides.push_back(side);
438     }
439 
440   } else  // la quadratica e' un segmento orizzontale
441     findIntersections(
442         y, TQuadratic(q.getPoint(t0),
443                       0.5 * (q.getPoint(t0) + q.getPoint(t1)) + TPointD(0, 1.0),
444                       q.getPoint(t1)),
445         0, 1, intersections, sides);
446 }
447 }
448 //-----------------------------------------------------------------------------
449 
contains(const TPointD & p) const450 bool TRegion::contains(const TPointD &p) const { return m_imp->contains(p); }
451 
452 //-----------------------------------------------------------------------------
453 
contains(const TStroke & s,bool mayIntersect) const454 bool TRegion::contains(const TStroke &s, bool mayIntersect) const {
455   return m_imp->contains(s, mayIntersect);
456 }
457 
458 //-----------------------------------------------------------------------------
459 #ifdef _DEBUG
checkRegion()460 void TRegion::checkRegion() { m_imp->checkRegion(); }
461 #endif
462 //-----------------------------------------------------------------------------
463 
contains(const TRegion & r) const464 bool TRegion::contains(const TRegion &r) const {
465   return m_imp->contains(*r.m_imp);
466 }
467 
468 //-----------------------------------------------------------------------------
469 /*
470 bool TRegion::getPointInside(TPointD &p) const
471 {
472   return m_imp->getPointInside(p);
473 }
474 */
475 //-----------------------------------------------------------------------------
476 
getProp()477 TRegionProp *TRegion::getProp() {
478   // if(m_working)  buttato m_working
479   return m_imp->m_prop;
480   /*
481 int styleId = getStyle();
482 if(!styleId ) return 0;
483 TColorStyle * style = palette->getStyle(styleId);
484 if (!style->isRegionStyle() || style->isEnabled() == false)
485 return 0;
486 if( !m_imp->m_prop || style != m_imp->m_prop->getColorStyle() )
487 {
488 delete m_imp->m_prop;
489 m_imp->m_prop = style->makeRegionProp(this);
490 }
491 return m_imp->m_prop;
492 */
493 }
494 
495 //-----------------------------------------------------------------------------
496 
setProp(TRegionProp * prop)497 void TRegion::setProp(TRegionProp *prop) {
498   assert(prop);
499   delete m_imp->m_prop;
500   m_imp->m_prop = prop;
501 }
502 
503 //-----------------------------------------------------------------------------
504 
505 /*
506 void TRegion::draw(const TVectorRenderData &rd)
507 {
508 
509   int styleId = getStyle();
510 
511   if(!styleId )
512     return;
513 
514   TColorStyle * style = rd.m_palette->getStyle(styleId);
515 
516   if (!style->isRegionStyle() || style->isEnabled() == false)
517     return;
518 
519 
520   if( !m_imp->m_prop || style != m_imp->m_prop->getColorStyle() )
521   {
522     delete m_imp->m_prop;
523     m_imp->m_prop = style->makeRegionProp(this);
524   }
525 
526   m_imp->m_prop->draw(rd);
527 }
528 */
529 
530 //-----------------------------------------------------------------------------
531 
checkPolyline(const std::vector<T3DPointD> & p)532 static void checkPolyline(const std::vector<T3DPointD> &p) {
533   int ret;
534 
535   if (p.size() < 3) return;
536 
537   TPointD p1;
538   TPointD p2;
539 
540   int pointSize = (int)p.size() - 1;
541 
542   for (int i = 0; i < pointSize; i++) {
543     for (int j = i + 1; j < pointSize; j++) {
544       std::vector<DoublePair> res;
545 
546       p1 = TPointD(p[i].x, p[i].y);
547       p2 = TPointD(p[i + 1].x, p[i + 1].y);
548 
549       TSegment s0(p1, p2);
550 
551       p1 = TPointD(p[j].x, p[j].y);
552       p2 = TPointD(p[j + 1].x, p[j + 1].y);
553 
554       TSegment s1(p1, p2);
555 
556       ret = intersect(s0, s1, res);
557       if (ret)
558         assert((ret == 1) && (areAlmostEqual(res[0].first, 1) ||
559                               areAlmostEqual(res[0].first, 0)) &&
560                (areAlmostEqual(res[0].second, 1) ||
561                 areAlmostEqual(res[0].second, 0)));
562     }
563   }
564 
565   p1 = TPointD(p.back().x, p.back().y);
566   p2 = TPointD(p[0].x, p[0].y);
567 
568   TSegment s0(p1, p2);
569 
570   for (int j = 0; j < pointSize; j++) {
571     std::vector<DoublePair> res;
572 
573     p1 = TPointD(p[j].x, p[j].y);
574     p2 = TPointD(p[j + 1].x, p[j + 1].y);
575     TSegment s1(p1, p2);
576 
577     ret = intersect(s0, s1, res);
578     if (ret)
579       assert((ret == 1) && (areAlmostEqual(res[0].first, 1) ||
580                             areAlmostEqual(res[0].first, 0)) &&
581              (areAlmostEqual(res[0].second, 1) ||
582               areAlmostEqual(res[0].second, 0)));
583   }
584 }
585 
586 //-----------------------------------------------------------------------------
587 
getInternalPoint(TPointD & p,double left,double right,double y)588 bool TRegion::Imp::getInternalPoint(TPointD &p, double left, double right,
589                                     double y) {
590   assert(left < right);
591 
592   if (areAlmostEqual(left, right, 1e-2)) return false;
593 
594   double mid = 0.5 * (left + right);
595 
596   p = TPointD(mid, y);
597 
598   if (noSubregionContains(p)) return true;
599 
600   if (!getInternalPoint(p, left, mid, y))
601     return getInternalPoint(p, mid, right, y);
602   else
603     return true;
604 }
605 
606 //-----------------------------------------------------------------------------
607 
noSubregionContains(const TPointD & p) const608 bool TRegion::Imp::noSubregionContains(const TPointD &p) const {
609   if (contains(p)) {
610     for (int i = 0; i < (int)m_includedRegionArray.size(); i++)
611       if (m_includedRegionArray[i]->contains(p)) return false;
612     return true;
613   } else
614     return false;
615 }
616 
617 //-----------------------------------------------------------------------------
618 
computeScanlineIntersections(double y,std::vector<double> & intersections) const619 void TRegion::computeScanlineIntersections(
620     double y, std::vector<double> &intersections) const {
621   m_imp->computeScanlineIntersections(y, intersections);
622 }
623 
624 //-----------------------------------------------------------------------------
625 
computeScanlineIntersections(double y,std::vector<double> & intersections) const626 void TRegion::Imp::computeScanlineIntersections(
627     double y, std::vector<double> &intersections) const {
628   TRectD bbox = getBBox();
629   if (y <= bbox.y0 || y >= bbox.y1) return;
630 
631   assert(intersections.empty());
632 
633   UINT i, firstSide = 0;
634   std::vector<int> sides;
635 
636   for (i = 0; i < m_edge.size(); i++) {
637     TEdge *e = m_edge[i];
638 
639     TStroke *s = e->m_s;
640     if (s->getBBox().y0 > y || s->getBBox().y1 < y) continue;
641     int chunkIndex0, chunkIndex1;
642     double t0, t1;
643     s->getChunkAndT(e->m_w0, chunkIndex0, t0);
644     s->getChunkAndT(e->m_w1, chunkIndex1, t1);
645 
646     if (chunkIndex0 > chunkIndex1) {
647       findIntersections(y, *s->getChunk(chunkIndex0), t0, 0, intersections,
648                         sides);
649       for (int j = chunkIndex0 - 1; j > chunkIndex1; j--)
650         findIntersections(y, *s->getChunk(j), 1, 0, intersections, sides);
651       findIntersections(y, *s->getChunk(chunkIndex1), 1, t1, intersections,
652                         sides);
653     } else if (chunkIndex0 < chunkIndex1) {
654       findIntersections(y, *s->getChunk(chunkIndex0), t0, 1, intersections,
655                         sides);
656       for (int j = chunkIndex0 + 1; j < chunkIndex1; j++)
657         findIntersections(y, *s->getChunk(j), 0, 1, intersections, sides);
658       findIntersections(y, *s->getChunk(chunkIndex1), 0, t1, intersections,
659                         sides);
660     } else {
661       findIntersections(y, *s->getChunk(chunkIndex0), t0, t1, intersections,
662                         sides);
663     }
664   }
665 
666   if (intersections.size() > 0 &&
667       intersections.front() == intersections.back()) {
668     intersections.pop_back();
669     if (!sides.empty() && sides.front() == sides.back() &&
670         intersections.size() > 0)
671       intersections.erase(intersections.begin());
672   }
673 
674   std::sort(intersections.begin(), intersections.end());
675   assert(intersections.size() % 2 == 0);
676 }
677 
678 //-----------------------------------------------------------------------------
contains(const TPointD & p) const679 bool TRegion::Imp::contains(const TPointD &p) const {
680   bool leftAreOdd = false;
681 
682   if (!getBBox().contains(p)) return false;
683 
684   // printContains(p);
685 
686   UINT i;
687 
688   int side = 0;
689 
690   for (i = 0; i < m_edge.size() * 2; i++)  // i pari, esplora gli edge,
691   // i dispari esplora i segmenti di autoclose tra un edge e il successivo
692   {
693     if (i & 0x1) {
694       TPointD p0 = m_edge[i / 2]->m_s->getPoint(m_edge[i / 2]->m_w1);
695       TPointD p1;
696       if (i / 2 < m_edge.size() - 1)
697         p1 = m_edge[i / 2 + 1]->m_s->getPoint(m_edge[i / 2 + 1]->m_w0);
698       else
699         p1 = m_edge[0]->m_s->getPoint(m_edge[0]->m_w0);
700 
701       if (std::min(p0.y, p1.y) > p.y || std::max(p0.y, p1.y) < p.y) continue;
702 
703       if (!areAlmostEqual(p0, p1, 1e-2))
704         side = findSides(p, TQuadratic(p0, 0.5 * (p0 + p1), p1), 0.0, 1.0,
705                          leftAreOdd, side);
706 
707       continue;
708     }
709 
710     TEdge *e = m_edge[i / 2];
711 
712     TStroke *s = e->m_s;
713     if (s->getBBox().y0 > p.y || s->getBBox().y1 < p.y) continue;
714 
715     double t0, t1;
716     int chunkIndex0, chunkIndex1;
717     const TThickQuadratic *q0, *q1;
718 
719     s->getChunkAndT(e->m_w0, chunkIndex0, t0);
720     s->getChunkAndT(e->m_w1, chunkIndex1, t1);
721     q0 = s->getChunk(chunkIndex0);
722     q1 = s->getChunk(chunkIndex1);
723 
724     if (i == 0 && areAlmostEqual(q0->getPoint(t0).y, p.y)) {
725       double tEnd;
726       int chunkIndexEnd;
727       TEdge *edgeEnd = m_edge.back();
728       edgeEnd->m_s->getChunkAndT(edgeEnd->m_w1, chunkIndexEnd, tEnd);
729       assert(areAlmostEqual(
730           edgeEnd->m_s->getChunk(chunkIndexEnd)->getPoint(tEnd).y, p.y));
731       side =
732           edgeEnd->m_s->getChunk(chunkIndexEnd)->getSpeed(tEnd).y > 0 ? 1 : -1;
733     }
734 
735     if (chunkIndex0 != chunkIndex1) {
736       /*if (chunkIndex0>chunkIndex1)
737 {
738 std::swap(chunkIndex0, chunkIndex1);
739 std::swap(t0, t1);
740 }*/
741       if (chunkIndex0 > chunkIndex1) {
742         side = findSides(p, *q0, t0, 0, leftAreOdd, side);
743         for (int j = chunkIndex0 - 1; j > chunkIndex1; j--)
744           side = findSides(p, *s->getChunk(j), 1, 0, leftAreOdd, side);
745         side   = findSides(p, *q1, 1, t1, leftAreOdd, side);
746       } else {
747         side = findSides(p, *q0, t0, 1, leftAreOdd, side);
748         for (int j = chunkIndex0 + 1; j < chunkIndex1; j++)
749           side = findSides(p, *s->getChunk(j), 0, 1, leftAreOdd, side);
750         side   = findSides(p, *q1, 0, t1, leftAreOdd, side);
751       }
752 
753     } else
754       side = findSides(p, *q0, t0, t1, leftAreOdd, side);
755 
756     if (i & 0x1) delete q0;
757   }
758 
759   return leftAreOdd;
760 }
761 
762 //-----------------------------------------------------------------------------
763 
leftScanlineIntersections(const TPointD & p,double (TPointD::* h),double (TPointD::* v)) const764 int TRegion::Imp::leftScanlineIntersections(const TPointD &p,
765                                             double(TPointD::*h),
766                                             double(TPointD::*v)) const {
767   struct Locals {
768     const Imp *m_this;
769     double m_x, m_y, m_tol;
770     double TPointD::*m_h, TPointD::*m_v;
771 
772     inline double x(const TPointD &p) const { return p.*m_h; }
773     inline double y(const TPointD &p) const { return p.*m_v; }
774 
775     inline double get(const TQuadratic &q, double t,
776                       double(TPointD::*val)) const {
777       double one_t = 1.0 - t;
778       return one_t * (one_t * q.getP0().*val + t * q.getP1().*val) +
779              t * (one_t * q.getP1().*val + t * q.getP2().*val);
780     }
781 
782     inline double getX(const TQuadratic &q, double t) const {
783       return get(q, t, m_h);
784     }
785     inline double getY(const TQuadratic &q, double t) const {
786       return get(q, t, m_v);
787     }
788 
789     void getEdgeData(int e, TEdge *&ed, TStroke *&s, int &chunk0,
790                      const TThickQuadratic *&q0, double &t0, int &chunk1,
791                      const TThickQuadratic *&q1, double &t1) const {
792       ed = m_this->m_edge[e];
793       s  = ed->m_s;
794 
795       s->getChunkAndT(ed->m_w0, chunk0, t0);
796       s->getChunkAndT(ed->m_w1, chunk1, t1);
797 
798       q0 = s->getChunk(chunk0);
799       q1 = s->getChunk(chunk1);
800     }
801 
802     bool isInYRange(double y0, double y1) const {
803       return (y0 <= m_y &&
804               m_y < y1)  // Assuming the first endpoint is vertical-including,
805              || (y1 < m_y && m_y <= y0);  // while the latter is not. Vertical
806                                           // conditions are EXACT.
807     }
808 
809     bool areInYRange(const TQuadratic &q, double t0, double t1,
810                      int (&solIdx)[2]) const {
811       assert(0.0 <= t0 && t0 <= 1.0), assert(0.0 <= t1 && t1 <= 1.0);
812 
813       const TPointD &p0 = q.getP0(), &p1 = q.getP1(), &p2 = q.getP2();
814 
815       double der[2] = {y(p1) - y(p0), y(p0) - y(p1) + y(p2) - y(p1)}, s;
816 
817       double y0 = getY(q, t0), y1 = getY(q, t1);
818 
819       if (tcg::poly_ops::solve_1(der, &s, m_tol)) {
820         if (t0 <= s && s < t1) {
821           double ys = getY(q, s);
822 
823           solIdx[0] = ((ys < m_y && m_y <= y0) || (y0 <= m_y && m_y < ys)) ? 0 : -1;
824           solIdx[1] = ((ys < m_y && m_y < y1) || (y1 < m_y && m_y < ys)) ? 1 : -1;
825         } else if (t1 < s && s <= t0) {
826           double ys = getY(q, s);
827 
828           solIdx[0] = ((ys < m_y && m_y <= y0) || (y0 <= m_y && m_y < ys)) ? 1 : -1;
829           solIdx[1] = ((ys < m_y && m_y < y1) || (y1 < m_y && m_y < ys)) ? 0 : -1;
830         } else {
831           solIdx[0] = isInYRange(y0, y1) ? (t0 < s) ? 0 : 1 : -1;
832           solIdx[1] = -1;
833         }
834       } else
835         solIdx[1] = solIdx[0] = -1;
836 
837       return (solIdx[0] >= 0 || solIdx[1] >= 0);
838     }
839 
840     int leftScanlineIntersections(const TSegment &seg, bool &ascending) {
841       const TPointD &p0 = seg.getP0(), &p1 = seg.getP1();
842       bool wasAscending = ascending;
843 
844       ascending = (y(p1) > y(p0))
845                       ? true
846                       : (y(p1) < y(p0))
847                             ? false
848                             : (wasAscending = !ascending,
849                                ascending);  // Couples with the cusp check below
850 
851       if (!isInYRange(y(p0), y(p1))) return 0;
852 
853       if (m_y == y(p0))
854         return int(x(p0) < m_x &&
855                    ascending == wasAscending);  // Cusps treated here
856 
857       double y1_y0 = y(p1) - y(p0),  // (x, m_y) in (p0, p1) from here on
858           poly[2]  = {(m_y - y(p0)) * (x(p1) - x(p0)), -y1_y0}, sx_x0;
859 
860       return tcg::poly_ops::solve_1(poly, &sx_x0, m_tol)
861                  ? int(sx_x0 < m_x - x(p0))
862                  : int(x(p0) < m_x &&
863                        x(p1) < m_x);  // Almost horizontal segments are
864     }                                 // flattened along the axes
865 
866     int isAscending(const TThickQuadratic &q, double t, bool forward) {
867       double y0 = y(q.getP0()), y1 = y(q.getP1()), y2 = y(q.getP2()),
868              y1_y0 = y1 - y0, y2_y1 = y2 - y1;
869 
870       double yspeed_2 = tcg::numeric_ops::lerp(y1_y0, y2_y1, t) *
871                         (2 * int(forward) - 1),
872              yaccel = y2_y1 - y1_y0;
873 
874       return (yspeed_2 > 0.0)
875                  ? 1
876                  : (yspeed_2 < 0.0) ? -1 : tcg::numeric_ops::sign(yaccel);
877     }
878 
879     int leftScanlineIntersections(const TQuadratic &q, double t0, double t1,
880                                   bool &ascending) {
881       const TPointD &p0 = q.getP0(), &p1 = q.getP1(), &p2 = q.getP2();
882 
883       double y1_y0 = y(p1) - y(p0), accel = y(p2) - y(p1) - y1_y0;
884 
885       // Fallback to segment case whenever we have too flat quads
886       if (std::fabs(accel) < m_tol)
887         return leftScanlineIntersections(
888             TSegment(q.getPoint(t0), q.getPoint(t1)), ascending);
889 
890       // Calculate new ascension
891       int ascends       = isAscending(q, t1, t0 < t1);
892       bool wasAscending = ascending;
893 
894       ascending =
895           (ascends > 0)
896               ? true
897               : (ascends < 0)
898                     ? false
899                     : (wasAscending = !ascending,
900                        ascending);  // Couples with the cusps check below
901 
902       // In case the y coords are not in range, quit
903       int solIdx[2];
904       if (!areInYRange(q, t0, t1, solIdx)) return 0;
905 
906       // Identify coordinates for which  q(t) == y
907       double poly[3] = {y(p0) - m_y, 2.0 * y1_y0, accel}, s[2];
908 
909       int sCount = tcg::poly_ops::solve_2(
910           poly, s);  // Tolerance dealt at the first bailout above
911       if (sCount == 2) {
912         // Calculate result
913         int result = 0;
914 
915         if (solIdx[0] >= 0) {
916           result += int(
917               getX(q, s[solIdx[0]]) < m_x &&
918               (getY(q, t0) != m_y || ascending == wasAscending));  // Cusp check
919         }
920 
921         if (solIdx[1] >= 0) result += int(getX(q, s[solIdx[1]]) < m_x);
922 
923         return result;
924       }
925 
926       return (assert(sCount == 0), 0);  // Should never happen, since m_y is in
927                                         // range. If it ever happens,
928       // it must be close to the extremal - so quit with no intersections.
929     }
930 
931   } locals = {this, p.*h, p.*v, 1e-4, h, v};
932 
933   TEdge *ed;
934   TStroke *s;
935   int chunk0, chunk1;
936   const TThickQuadratic *q0, *q1;
937   double t0, t1;
938 
939   UINT e, eCount = m_edge.size();
940 
941   int leftInters = 0;
942   bool ascending =
943       (locals.getEdgeData(eCount - 1, ed, s, chunk0, q0, t0, chunk1, q1, t1),
944        locals.isAscending(*q1, t1, (t0 < t1)));
945 
946   for (e = 0; e != eCount; ++e) {
947     // Explore current edge
948     {
949       // Retrieve edge data
950       locals.getEdgeData(e, ed, s, chunk0, q0, t0, chunk1, q1, t1);
951 
952       // Compare edge against scanline segment
953       if (chunk0 != chunk1) {
954         if (chunk0 < chunk1) {
955           leftInters +=
956               locals.leftScanlineIntersections(*q0, t0, 1.0, ascending);
957 
958           for (int c = chunk0 + 1; c != chunk1; ++c)
959             leftInters += locals.leftScanlineIntersections(*s->getChunk(c), 0.0,
960                                                            1.0, ascending);
961 
962           leftInters +=
963               locals.leftScanlineIntersections(*q1, 0.0, t1, ascending);
964         } else {
965           leftInters +=
966               locals.leftScanlineIntersections(*q0, t0, 0.0, ascending);
967 
968           for (int c = chunk0 - 1; c != chunk1; --c)
969             leftInters += locals.leftScanlineIntersections(*s->getChunk(c), 1.0,
970                                                            0.0, ascending);
971 
972           leftInters +=
973               locals.leftScanlineIntersections(*q1, 1.0, t1, ascending);
974         }
975       } else
976         leftInters += locals.leftScanlineIntersections(*q0, t0, t1, ascending);
977     }
978 
979     // Explore autoclose segment at the end of current edge
980     {
981       int nextE = (e + 1) % int(m_edge.size());
982 
983       const TPointD &p0 = m_edge[e]->m_s->getPoint(m_edge[e]->m_w1),
984                     &p1 = m_edge[nextE]->m_s->getPoint(m_edge[nextE]->m_w0);
985 
986       leftInters +=
987           locals.leftScanlineIntersections(TSegment(p0, p1), ascending);
988     }
989   }
990 
991   return leftInters;
992 }
993 
994 //-----------------------------------------------------------------------------
995 
scanlineIntersectionsBefore(double x,double y,bool horizontal) const996 int TRegion::scanlineIntersectionsBefore(double x, double y,
997                                          bool horizontal) const {
998   static double TPointD::*const dir[2] = {&TPointD::x, &TPointD::y};
999   return m_imp->leftScanlineIntersections(TPointD(x, y), dir[!horizontal],
1000                                           dir[horizontal]);
1001 }
1002 
1003 //-----------------------------------------------------------------------------
1004 
contains(const TEdge & e) const1005 bool TRegion::contains(const TEdge &e) const {
1006   for (UINT i = 0; i < m_imp->m_edge.size(); i++)
1007     if (*m_imp->m_edge[i] == e) return true;
1008 
1009   return false;
1010 }
1011 
1012 // Una regione contiene un'altra se  non hanno strokes in comune e un qualsiasi
1013 // punto
1014 // della seconda e' contenuto nella prima.
1015 
contains(const TRegion::Imp & r) const1016 bool TRegion::Imp::contains(const TRegion::Imp &r) const {
1017   if (!getBBox().contains(r.getBBox())) return false;
1018 
1019   for (UINT i = 0; i < r.m_edge.size(); i++)
1020     for (UINT j = 0; j < m_edge.size(); j++)
1021       if (*r.m_edge[i] == *m_edge[j]) return false;
1022   // nessuno stroke in comune!!
1023 
1024   /*
1025 for ( i=0; i<r.m_edge.size(); i++)
1026 {
1027   TEdge *e = r.m_edge[i];
1028   if (!contains(e->m_s->getThickPoint(e->m_w0)))
1029     return false;
1030   if (!contains(e->m_s->getThickPoint((e->m_w0+e->m_w1)/2.0)))
1031     return false;
1032   if (!contains(e->m_s->getThickPoint(e->m_w1)))
1033     return false;
1034   }
1035 */
1036   TEdge *e = r.m_edge[0];
1037   return contains(e->m_s->getThickPoint((e->m_w0 + e->m_w1) / 2.0));
1038 }
1039 
1040 //-----------------------------------------------------------------------------
1041 
thereAreintersections(const TStroke & s) const1042 bool TRegion::Imp::thereAreintersections(const TStroke &s) const {
1043   for (UINT i = 0; i < m_edge.size(); i++) {
1044     std::vector<DoublePair> dummy;
1045     if (intersect(m_edge[i]->m_s, &s, dummy, true)) return true;
1046   }
1047 
1048   return false;
1049 }
1050 
1051 //-----------------------------------------------------------------------------
1052 
contains(const TStroke & s,bool mayIntersect) const1053 bool TRegion::Imp::contains(const TStroke &s, bool mayIntersect) const {
1054   if (!getBBox().contains(s.getBBox())) return false;
1055   if (mayIntersect && thereAreintersections(s)) return false;
1056 
1057   return contains(s.getThickPoint(0.5));
1058 }
1059 //-----------------------------------------------------------------------------
1060 
isSubRegionOf(const TRegion & r) const1061 bool TRegion::isSubRegionOf(const TRegion &r) const {
1062   return m_imp->isSubRegionOf(*r.m_imp);
1063 }
1064 
1065 //-----------------------------------------------------------------------------
1066 /*
1067 bool TRegion::Imp::isSubRegionOf(const TRegion::Imp &r) const
1068 {
1069 UINT i, j;
1070 bool found, areTouching=false;
1071 
1072 if (!r.getBBox().contains(getBBox()))
1073   return false;
1074 
1075 for (i=0; i<m_edge.size(); i++)
1076   {
1077   for (j=0, found=false; !found && j<r.m_edge.size(); j++)
1078     if (m_edge[i]->m_s==r.m_edge[j]->m_s)
1079       {
1080       double w0 = std::min(m_edge[i]->m_w0, m_edge[i]->m_w1) ;
1081       double w1 = std::max(m_edge[i]->m_w0, m_edge[i]->m_w1) ;
1082       double r_w0 = std::min(r.m_edge[j]->m_w0, r.m_edge[j]->m_w1);
1083       double r_w1 = std::max(r.m_edge[j]->m_w0, r.m_edge[j]->m_w1);
1084 
1085       if ((w0>=r_w0 || areAlmostEqual(w0, r_w0, 0.1)) &&
1086           (w1<=r_w1 || areAlmostEqual(w1, r_w1, 0.1)))
1087         {
1088         found=true;
1089         areTouching = true;
1090         }
1091       else
1092         found=false;
1093       //found=true;
1094       }
1095   if ((!found) &&
1096 !r.contains(m_edge[i]->m_s->getPoint(0.5*(m_edge[i]->m_w0+m_edge[i]->m_w1))))
1097     return false;
1098   }
1099 return areTouching;
1100 }
1101 */
1102 //-----------------------------------------------------------------------------
1103 
isSubRegionOf(const TRegion::Imp & r) const1104 bool TRegion::Imp::isSubRegionOf(const TRegion::Imp &r) const {
1105   if (!r.getBBox().contains(getBBox())) return false;
1106 
1107   for (UINT i = 0; i < m_edge.size(); i++) {
1108     for (UINT j = 0; j < r.m_edge.size(); j++) {
1109       TEdge *e    = r.m_edge[j];
1110       TEdge *subE = m_edge[i];
1111       if (subE->m_index == e->m_index &&
1112           (subE->m_w0 < m_edge[i]->m_w1) == (e->m_w0 < e->m_w1)) {
1113         bool forward = (e->m_w0 < e->m_w1);
1114 
1115         if (forward && (subE->m_w0 >= e->m_w0 ||
1116                         areAlmostEqual(subE->m_w0, e->m_w0, 1e-3)) &&
1117             (subE->m_w1 <= e->m_w1 ||
1118              areAlmostEqual(subE->m_w1, e->m_w1, 1e-3)))
1119           return true;
1120 
1121         if (!forward && (subE->m_w0 <= e->m_w0 ||
1122                          areAlmostEqual(subE->m_w0, e->m_w0, 1e-3)) &&
1123             (subE->m_w1 >= e->m_w1 ||
1124              areAlmostEqual(subE->m_w1, e->m_w1, 1e-3)))
1125           return true;
1126       }
1127     }
1128   }
1129   return false;
1130 }
1131 
1132 //------------------------------------------------------------------------------
getRegion(const TPointD & p)1133 TRegion *TRegion::getRegion(const TPointD &p) {
1134   for (UINT i = 0; i < m_imp->m_includedRegionArray.size(); i++)
1135     if (m_imp->m_includedRegionArray[i]->contains(p))
1136       return m_imp->m_includedRegionArray[i]->getRegion(p);
1137 
1138   return this;
1139 }
1140 
1141 //-----------------------------------------------------------------------------
1142 
getInternalPoint(TPointD & p)1143 bool TRegion::getInternalPoint(TPointD &p) {
1144   return m_imp->getInternalPoint(p, getBBox().x0, getBBox().x1,
1145                                  0.5 * (getBBox().y0 + getBBox().y1));
1146 }
1147 
1148 //-----------------------------------------------------------------------------
1149 
fill(const TPointD & p,int styleId)1150 int TRegion::fill(const TPointD &p, int styleId) {
1151   UINT i;
1152 
1153   for (i = 0; i < m_imp->m_includedRegionArray.size(); i++)
1154     if (m_imp->m_includedRegionArray[i]->contains(p))
1155       return m_imp->m_includedRegionArray[i]->fill(p, styleId);
1156 
1157   int ret = getStyle();
1158   setStyle(styleId);
1159 
1160   return ret;
1161 }
1162 
1163 //-----------------------------------------------------------------------------
1164 
selectFill(const TRectD & selArea,int styleId)1165 bool TRegion::selectFill(const TRectD &selArea, int styleId) {
1166   bool hitSomeRegions = false;
1167 
1168   if (selArea.contains(getBBox())) {
1169     hitSomeRegions = true;
1170     setStyle(styleId);
1171   }
1172 
1173   int regNum = m_imp->m_includedRegionArray.size();
1174 
1175   for (int i = 0; i < regNum; i++)
1176     hitSomeRegions |=
1177         m_imp->m_includedRegionArray[i]->selectFill(selArea, styleId);
1178 
1179   return hitSomeRegions;
1180 }
1181 
1182 //-----------------------------------------------------------------------------
1183 
invalidateBBox()1184 void TRegion::invalidateBBox() {
1185   m_imp->invalidateBBox();
1186   for (UINT i = 0; i < m_imp->m_includedRegionArray.size(); i++)
1187     m_imp->m_includedRegionArray[i]->invalidateBBox();
1188 }
1189 
1190 //-----------------------------------------------------------------------------
1191 /*
1192 TRectD TRegion::getBBox(vector<TRectD>& bboxReg,vector<TPointD>& intersPoint)
1193 const
1194 {
1195   return m_imp->getBBox(bboxReg,intersPoint);
1196 }
1197 */
1198 //-----------------------------------------------------------------------------
1199 
getBBox() const1200 TRectD TRegion::getBBox() const { return m_imp->getBBox(); }
1201 
1202 //-----------------------------------------------------------------------------
1203 
addEdge(TEdge * e,bool minimizeEdges)1204 void TRegion::addEdge(TEdge *e, bool minimizeEdges) {
1205   if (minimizeEdges &&
1206       e->m_s->getMaxThickness() > 0.0 &&  // outline strokes ignore this
1207       !m_imp->m_edge.empty() && m_imp->m_edge.back()->m_index == e->m_index &&
1208       areAlmostEqual(m_imp->m_edge.back()->m_w1, e->m_w0, 1e-5))
1209     m_imp->m_edge.back()->m_w1 = e->m_w1;
1210   else
1211     m_imp->m_edge.push_back(e);
1212   m_imp->m_isValidBBox = false;
1213   // if (e->m_s->isSelfLoop())
1214   //  assert(m_imp->m_edge.size()==1);
1215 }
1216 
1217 //-----------------------------------------------------------------------------
1218 
getLastEdge() const1219 TEdge *TRegion::getLastEdge() const {
1220   if (m_imp->m_edge.empty()) return 0;
1221 
1222   return m_imp->m_edge.back();
1223 }
1224 
1225 //-----------------------------------------------------------------------------
1226 
popBackEdge()1227 TEdge *TRegion::popBackEdge() {
1228   TEdge *ret;
1229   if (m_imp->m_edge.empty()) return 0;
1230 
1231   ret = m_imp->m_edge.back();
1232   m_imp->m_edge.pop_back();
1233   return ret;
1234 }
1235 
1236 //-----------------------------------------------------------------------------
1237 
popFrontEdge()1238 TEdge *TRegion::popFrontEdge() {
1239   TEdge *ret;
1240   if (m_imp->m_edge.empty()) return 0;
1241 
1242   ret = m_imp->m_edge.front();
1243   m_imp->m_edge.erase(m_imp->m_edge.begin());
1244   return ret;
1245 }
1246 
1247 //-----------------------------------------------------------------------------
1248 
getEdge(UINT index) const1249 TEdge *TRegion::getEdge(UINT index) const { return m_imp->m_edge[index]; }
1250 
1251 //-----------------------------------------------------------------------------
1252 
getEdgeCount() const1253 UINT TRegion::getEdgeCount() const { return m_imp->m_edge.size(); }
1254 
1255 //-----------------------------------------------------------------------------
1256 
getSubregion(UINT index) const1257 TRegion *TRegion::getSubregion(UINT index) const {
1258   return m_imp->m_includedRegionArray[index];
1259 }
1260 
1261 //-----------------------------------------------------------------------------
1262 
getSubregionCount() const1263 UINT TRegion::getSubregionCount() const {
1264   return m_imp->m_includedRegionArray.size();
1265 }
1266 
1267 //-----------------------------------------------------------------------------
1268 
deleteSubregion(UINT index)1269 void TRegion::deleteSubregion(UINT index) {
1270   assert(m_imp->m_includedRegionArray[index]->getSubregionCount() == 0);
1271 
1272   // delete m_imp->m_includedRegionArray[index];
1273   m_imp->m_includedRegionArray.erase(m_imp->m_includedRegionArray.begin() +
1274                                      index);
1275 }
1276 
1277 //-----------------------------------------------------------------------------
1278 
moveSubregionsTo(TRegion * r)1279 void TRegion::moveSubregionsTo(TRegion *r) {
1280   while (m_imp->m_includedRegionArray.size()) {
1281     r->m_imp->m_includedRegionArray.push_back(
1282         m_imp->m_includedRegionArray.back());
1283     m_imp->m_includedRegionArray.pop_back();
1284   }
1285 }
1286 
1287 //-----------------------------------------------------------------------------
1288 
printContains(const TPointD & p) const1289 void TRegion::Imp::printContains(const TPointD &p) const {
1290   std::ofstream of("C:\\temp\\region.txt");
1291 
1292   of << "point: " << p.x << " " << p.y << std::endl;
1293 
1294   for (UINT i = 0; i < (UINT)m_edge.size(); i++) {
1295     for (UINT j = 0; j < (UINT)m_edge[i]->m_s->getChunkCount(); j++) {
1296       const TThickQuadratic *q = m_edge[i]->m_s->getChunk(j);
1297 
1298       of << "******quad # " << j << std::endl;
1299       of << "   p0 " << q->getP0() << std::endl;
1300       of << "   p1 " << q->getP1() << std::endl;
1301       of << "   p2 " << q->getP2() << std::endl;
1302       of << "****** " << std::endl;
1303     }
1304   }
1305 
1306   of << std::endl;
1307 }
1308 
1309 //-----------------------------------------------------------------------------
1310 
print()1311 void TRegion::print() {
1312   std::cout << "\nNum edges: " << getEdgeCount() << std::endl;
1313   for (UINT i = 0; i < getEdgeCount(); i++) {
1314     std::cout << "\nEdge #" << i;
1315     std::cout << ":P0(" << getEdge(i)->m_s->getChunk(0)->getP0().x << ","
1316               << getEdge(i)->m_s->getChunk(0)->getP0().y << ")";
1317     std::cout << ":P2("
1318               << getEdge(i)
1319                      ->m_s->getChunk(getEdge(i)->m_s->getChunkCount() - 1)
1320                      ->getP2()
1321                      .x
1322               << ","
1323               << getEdge(i)
1324                      ->m_s->getChunk(getEdge(i)->m_s->getChunkCount() - 1)
1325                      ->getP2()
1326                      .y
1327               << ")";
1328     std::cout << std::endl;
1329   }
1330   if (m_imp->m_includedRegionArray.size()) {
1331     std::cout << "***** questa regione contiene:" << std::endl;
1332     for (UINT i = 0; i < m_imp->m_includedRegionArray.size(); i++)
1333       m_imp->m_includedRegionArray[i]->print();
1334     std::cout << "***** fine" << std::endl;
1335   }
1336 }
1337 
1338 //-----------------------------------------------------------------------------
1339 
setStyle(int colorStyle)1340 void TRegion::setStyle(int colorStyle) {
1341   for (UINT i = 0; i < getEdgeCount(); i++) getEdge(i)->setStyle(colorStyle);
1342 
1343   /*
1344 if (!colorStyle || (colorStyle && colorStyle->isFillStyle())  )
1345 {
1346 for (UINT i=0; i<getEdgeCount(); i++)
1347 getEdge(i)->setColorStyle(colorStyle);
1348 
1349 delete m_imp->m_prop;
1350 m_imp->m_prop = 0;
1351 }
1352 */
1353 }
1354 
1355 //-----------------------------------------------------------------------------
1356 
getId()1357 TRegionId TRegion::getId() {
1358   assert(getEdgeCount() > 0);
1359   TEdge *edge;
1360 
1361   for (UINT i = 0; i < m_imp->m_edge.size(); i++)
1362     if (m_imp->m_edge[i]->m_index >= 0) {
1363       edge = m_imp->m_edge[i];
1364       return TRegionId(edge->m_s->getId(),
1365                        (float)((edge->m_w0 + edge->m_w1) * 0.5),
1366                        edge->m_w0 < edge->m_w1);
1367     }
1368 
1369   edge = m_imp->m_edge[0];
1370   return TRegionId(edge->m_s->getId(), (float)((edge->m_w0 + edge->m_w1) * 0.5),
1371                    edge->m_w0 < edge->m_w1);
1372 }
1373 
1374 //-----------------------------------------------------------------------------
1375 
invalidateProp()1376 void TRegion::invalidateProp() {
1377   if (m_imp->m_prop) m_imp->m_prop->notifyRegionChange();
1378 }
1379 
1380 //-----------------------------------------------------------------------------
1381 
getStyle() const1382 int TRegion::getStyle() const {
1383   int ret = 0;
1384   UINT i = 0, j, n = getEdgeCount();
1385   for (; i < n; i++) {
1386     int styleId = getEdge(i)->getStyle();
1387     if (styleId != 0 && ret == 0) {
1388       // assert(styleId<100);
1389       ret = styleId;
1390       if (i > 0)
1391         for (j = 0; j < i; j++) getEdge(i)->setStyle(ret);
1392     } else if (styleId != ret)
1393       getEdge(i)->setStyle(ret);
1394   }
1395   return ret;
1396 }
1397 
1398 //-----------------------------------------------------------------------------
addSubregion(TRegion * region)1399 void TRegion::addSubregion(TRegion *region) { m_imp->addSubregion(region); }
1400 
addSubregion(TRegion * region)1401 void TRegion::Imp::addSubregion(TRegion *region) {
1402   for (std::vector<TRegion *>::iterator it = m_includedRegionArray.begin();
1403        it != m_includedRegionArray.end(); ++it) {
1404     if (region->contains(**it)) {
1405       // region->addSubregion(*it);
1406       region->addSubregion(*it);
1407       it = m_includedRegionArray.erase(it);
1408       while (it != m_includedRegionArray.end()) {
1409         if (region->contains(**it)) {
1410           region->addSubregion(*it);
1411           // region->addSubregion(*it);
1412           it = m_includedRegionArray.erase(it);
1413         } else
1414           it++;
1415       }
1416 
1417       m_includedRegionArray.push_back(region);
1418       return;
1419     } else if ((*it)->contains(*region)) {
1420       (*it)->addSubregion(region);
1421       //(*it)->addSubregion(region);
1422       return;
1423     }
1424   }
1425   m_includedRegionArray.push_back(region);
1426 }
1427 //-----------------------------------------------------------------------------
1428 //  End Of File
1429 //-----------------------------------------------------------------------------
1430