clipper.cpp
Go to the documentation of this file.
00001 /*******************************************************************************
00002 *                                                                              *
00003 * Author    :  Angus Johnson                                                   *
00004 * Version   :  4.8.8                                                           *
00005 * Date      :  30 August 2012                                                  *
00006 * Website   :  http://www.angusj.com                                           *
00007 * Copyright :  Angus Johnson 2010-2012                                         *
00008 *                                                                              *
00009 * License:                                                                     *
00010 * Use, modification & distribution is subject to Boost Software License Ver 1. *
00011 * http://www.boost.org/LICENSE_1_0.txt                                         *
00012 *                                                                              *
00013 * Attributions:                                                                *
00014 * The code in this library is an extension of Bala Vatti's clipping algorithm: *
00015 * "A generic solution to polygon clipping"                                     *
00016 * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63.             *
00017 * http://portal.acm.org/citation.cfm?id=129906                                 *
00018 *                                                                              *
00019 * Computer graphics and geometric modeling: implementation and algorithms      *
00020 * By Max K. Agoston                                                            *
00021 * Springer; 1 edition (January 4, 2005)                                        *
00022 * http://books.google.com/books?q=vatti+clipping+agoston                       *
00023 *                                                                              *
00024 * See also:                                                                    *
00025 * "Polygon Offsetting by Computing Winding Numbers"                            *
00026 * Paper no. DETC2005-85513 pp. 565-575                                         *
00027 * ASME 2005 International Design Engineering Technical Conferences             *
00028 * and Computers and Information in Engineering Conference (IDETC/CIE2005)      *
00029 * September 24�28, 2005 , Long Beach, California, USA                          *
00030 * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf              *
00031 *                                                                              *
00032 *******************************************************************************/
00033 
00034 /*******************************************************************************
00035 *                                                                              *
00036 * This is a translation of the Delphi Clipper library and the naming style     *
00037 * used has retained a Delphi flavour.                                          *
00038 *                                                                              *
00039 *******************************************************************************/
00040 
00041 #include <srs_env_model_percp/but_plane_detector/clipper.hpp>
00042 #include <cmath>
00043 #include <vector>
00044 #include <algorithm>
00045 #include <stdexcept>
00046 #include <cstring>
00047 #include <cstdlib>
00048 #include <ostream>
00049 
00050 namespace ClipperLib {
00051 
00052 static long64 const loRange = 0x3FFFFFFF;
00053 static long64 const hiRange = 0x3FFFFFFFFFFFFFFFLL;
00054 static double const pi = 3.141592653589793238;
00055 enum Direction { dRightToLeft, dLeftToRight };
00056 
00057 #define HORIZONTAL (-1.0E+40)
00058 #define TOLERANCE (1.0e-20)
00059 #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))
00060 #define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b))
00061 
00062 inline long64 Abs(long64 val)
00063 {
00064   return val < 0 ? -val : val;
00065 }
00066 //------------------------------------------------------------------------------
00067 
00068 //------------------------------------------------------------------------------
00069 // Int128 class (enables safe math on signed 64bit integers)
00070 // eg Int128 val1((long64)9223372036854775807); //ie 2^63 -1
00071 //    Int128 val2((long64)9223372036854775807);
00072 //    Int128 val3 = val1 * val2;
00073 //    val3.AsString => "85070591730234615847396907784232501249" (8.5e+37)
00074 //------------------------------------------------------------------------------
00075 
00076 class Int128
00077 {
00078   public:
00079 
00080     Int128(long64 _lo = 0)
00081     {
00082       lo = _lo;
00083       if (lo < 0) hi = -1; else hi = 0;
00084     }
00085 
00086     Int128(const Int128 &val): hi(val.hi), lo(val.lo){}
00087 
00088     long64 operator = (const long64 &val)
00089     {
00090       lo = val;
00091       if (lo < 0) hi = -1; else hi = 0;
00092       return val;
00093     }
00094 
00095     bool operator == (const Int128 &val) const
00096       {return (hi == val.hi && lo == val.lo);}
00097 
00098     bool operator != (const Int128 &val) const
00099       { return !(*this == val);}
00100 
00101     bool operator > (const Int128 &val) const
00102     {
00103       if (hi != val.hi)
00104         return hi > val.hi;
00105       else
00106         return lo > val.lo;
00107     }
00108 
00109     bool operator < (const Int128 &val) const
00110     {
00111       if (hi != val.hi)
00112         return hi < val.hi;
00113       else
00114         return lo < val.lo;
00115     }
00116 
00117     bool operator >= (const Int128 &val) const
00118       { return !(*this < val);}
00119 
00120     bool operator <= (const Int128 &val) const
00121       { return !(*this > val);}
00122 
00123     Int128& operator += (const Int128 &rhs)
00124     {
00125       hi += rhs.hi;
00126       lo += rhs.lo;
00127       if (ulong64(lo) < ulong64(rhs.lo)) hi++;
00128       return *this;
00129     }
00130 
00131     Int128 operator + (const Int128 &rhs) const
00132     {
00133       Int128 result(*this);
00134       result+= rhs;
00135       return result;
00136     }
00137 
00138     Int128& operator -= (const Int128 &rhs)
00139     {
00140       Int128 tmp(rhs);
00141       Negate(tmp);
00142       *this += tmp;
00143       return *this;
00144     }
00145 
00146     //Int128 operator -() const
00147     //{
00148     //  Int128 result(*this);
00149     //  if (result.lo == 0) {
00150     //    if (result.hi != 0) result.hi = -1;
00151     //  }
00152     //  else {
00153     //    result.lo = -result.lo;
00154     //    result.hi = ~result.hi;
00155     //  }
00156     //  return result;
00157     //}
00158 
00159     Int128 operator - (const Int128 &rhs) const
00160     {
00161       Int128 result(*this);
00162       result -= rhs;
00163       return result;
00164     }
00165 
00166     Int128 operator * (const Int128 &rhs) const
00167     {
00168       if ( !(hi == 0 || hi == -1) || !(rhs.hi == 0 || rhs.hi == -1))
00169         throw "Int128 operator*: overflow error";
00170       bool negate = (hi < 0) != (rhs.hi < 0);
00171 
00172       Int128 tmp(*this);
00173       if (tmp.hi < 0) Negate(tmp);
00174       ulong64 int1Hi = ulong64(tmp.lo) >> 32;
00175       ulong64 int1Lo = ulong64(tmp.lo & 0xFFFFFFFF);
00176 
00177       tmp = rhs;
00178       if (tmp.hi < 0) Negate(tmp);
00179       ulong64 int2Hi = ulong64(tmp.lo) >> 32;
00180       ulong64 int2Lo = ulong64(tmp.lo & 0xFFFFFFFF);
00181 
00182       //nb: see comments in clipper.pas
00183       ulong64 a = int1Hi * int2Hi;
00184       ulong64 b = int1Lo * int2Lo;
00185       ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi;
00186 
00187       tmp.hi = long64(a + (c >> 32));
00188       tmp.lo = long64(c << 32);
00189       tmp.lo += long64(b);
00190       if (ulong64(tmp.lo) < b) tmp.hi++;
00191       if (negate) Negate(tmp);
00192       return tmp;
00193     }
00194 
00195     Int128 operator/ (const Int128 &rhs) const
00196     {
00197       if (rhs.lo == 0 && rhs.hi == 0)
00198         throw "Int128 operator/: divide by zero";
00199       bool negate = (rhs.hi < 0) != (hi < 0);
00200       Int128 result(*this), denom(rhs);
00201       if (result.hi < 0) Negate(result);
00202       if (denom.hi < 0)  Negate(denom);
00203       if (denom > result) return Int128(0); //result is only a fraction of 1
00204       Negate(denom);
00205 
00206       Int128 p(0);
00207       for (int i = 0; i < 128; ++i)
00208       {
00209         p.hi = p.hi << 1;
00210         if (p.lo < 0) p.hi++;
00211         p.lo = long64(p.lo) << 1;
00212         if (result.hi < 0) p.lo++;
00213         result.hi = result.hi << 1;
00214         if (result.lo < 0) result.hi++;
00215         result.lo = long64(result.lo) << 1;
00216         Int128 p2(p);
00217         p += denom;
00218         if (p.hi < 0) p = p2;
00219         else result.lo++;
00220       }
00221       if (negate) Negate(result);
00222       return result;
00223     }
00224 
00225     double AsDouble() const
00226     {
00227       const double shift64 = 18446744073709551616.0; //2^64
00228       const double bit64 = 9223372036854775808.0;
00229       if (hi < 0)
00230       {
00231         Int128 tmp(*this);
00232         Negate(tmp);
00233         if (tmp.lo < 0)
00234           return (double)tmp.lo - bit64 - tmp.hi * shift64;
00235         else
00236           return -(double)tmp.lo - tmp.hi * shift64;
00237       }
00238       else if (lo < 0)
00239         return -(double)lo + bit64 + hi * shift64;
00240       else
00241         return (double)lo + (double)hi * shift64;
00242     }
00243 
00244     //for bug testing ...
00245     //std::string AsString() const
00246     //{
00247     //  std::string result;
00248     //  unsigned char r = 0;
00249     //  Int128 tmp(0), val(*this);
00250     //  if (hi < 0) Negate(val);
00251     //  result.resize(50);
00252     //  std::string::size_type i = result.size() -1;
00253     //  while (val.hi != 0 || val.lo != 0)
00254     //  {
00255     //    Div10(val, tmp, r);
00256     //    result[i--] = char('0' + r);
00257     //    val = tmp;
00258     //  }
00259     //  if (hi < 0) result[i--] = '-';
00260     //  result.erase(0,i+1);
00261     //  if (result.size() == 0) result = "0";
00262     //  return result;
00263     //}
00264 
00265 private:
00266     long64 hi;
00267     long64 lo;
00268 
00269     static void Negate(Int128 &val)
00270     {
00271       if (val.lo == 0) {
00272         if (val.hi != 0) val.hi = -val.hi;;
00273       }
00274       else {
00275         val.lo = -val.lo;
00276         val.hi = ~val.hi;
00277       }
00278     }
00279 
00280     //debugging only ...
00281     //void Div10(const Int128 val, Int128& result, unsigned char & remainder) const
00282     //{
00283     //  remainder = 0;
00284     //  result = 0;
00285     //  for (int i = 63; i >= 0; --i)
00286     //  {
00287     //    if ((val.hi & ((long64)1 << i)) != 0)
00288     //      remainder = char((remainder * 2) + 1); else
00289     //      remainder *= char(2);
00290     //    if (remainder >= 10)
00291     //    {
00292     //      result.hi += ((long64)1 << i);
00293     //      remainder -= char(10);
00294     //    }
00295     //  }
00296     //  for (int i = 63; i >= 0; --i)
00297     //  {
00298     //    if ((val.lo & ((long64)1 << i)) != 0)
00299     //      remainder = char((remainder * 2) + 1); else
00300     //      remainder *= char(2);
00301     //    if (remainder >= 10)
00302     //    {
00303     //      result.lo += ((long64)1 << i);
00304     //      remainder -= char(10);
00305     //    }
00306     //  }
00307     //}
00308 };
00309 
00310 //------------------------------------------------------------------------------
00311 //------------------------------------------------------------------------------
00312 
00313 bool FullRangeNeeded(const Polygon &pts)
00314 {
00315   bool result = false;
00316   for (Polygon::size_type i = 0; i <  pts.size(); ++i)
00317   {
00318     if (Abs(pts[i].X) > hiRange || Abs(pts[i].Y) > hiRange)
00319         throw "Coordinate exceeds range bounds.";
00320       else if (Abs(pts[i].X) > loRange || Abs(pts[i].Y) > loRange)
00321         result = true;
00322   }
00323   return result;
00324 }
00325 //------------------------------------------------------------------------------
00326   
00327 bool Orientation(const Polygon &poly)
00328 {
00329   int highI = (int)poly.size() -1;
00330   if (highI < 2) return false;
00331 
00332   int j = 0, jplus, jminus;
00333   for (int i = 0; i <= highI; ++i)
00334   {
00335     if (poly[i].Y < poly[j].Y) continue;
00336     if ((poly[i].Y > poly[j].Y || poly[i].X < poly[j].X)) j = i;
00337   };
00338   if (j == highI) jplus = 0;
00339   else jplus = j +1;
00340   if (j == 0) jminus = highI;
00341   else jminus = j -1;
00342 
00343   IntPoint vec1, vec2;
00344   //get cross product of vectors of the edges adjacent to highest point ...
00345   vec1.X = poly[j].X - poly[jminus].X;
00346   vec1.Y = poly[j].Y - poly[jminus].Y;
00347   vec2.X = poly[jplus].X - poly[j].X;
00348   vec2.Y = poly[jplus].Y - poly[j].Y;
00349 
00350   if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange ||
00351     Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange)
00352   {
00353     if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange ||
00354       Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange)
00355         throw "Coordinate exceeds range bounds.";
00356     Int128 cross = Int128(vec1.X) * Int128(vec2.Y) -
00357       Int128(vec2.X) * Int128(vec1.Y);
00358     return cross >= 0;
00359   }
00360   else
00361     return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0;
00362 }
00363 //------------------------------------------------------------------------------
00364 
00365 inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2)
00366 {
00367   return ( pt1.X == pt2.X && pt1.Y == pt2.Y );
00368 }
00369 //------------------------------------------------------------------------------
00370 
00371 bool Orientation(OutRec *outRec, bool UseFullInt64Range)
00372 {
00373   //first make sure bottomPt is correctly assigned ...
00374   OutPt *opBottom = outRec->pts, *op = outRec->pts->next;
00375   while (op != outRec->pts)
00376   {
00377     if (op->pt.Y >= opBottom->pt.Y)
00378     {
00379       if (op->pt.Y > opBottom->pt.Y || op->pt.X < opBottom->pt.X)
00380       opBottom = op;
00381     }
00382     op = op->next;
00383   }
00384   outRec->bottomPt = opBottom;
00385   opBottom->idx = outRec->idx;
00386 
00387   op = opBottom;
00388   //find vertices either side of bottomPt (skipping duplicate points) ....
00389   OutPt *opPrev = op->prev;
00390   OutPt *opNext = op->next;
00391   while (op != opPrev && PointsEqual(op->pt, opPrev->pt))
00392     opPrev = opPrev->prev;
00393   while (op != opNext && PointsEqual(op->pt, opNext->pt))
00394     opNext = opNext->next;
00395 
00396   IntPoint ip1, ip2;
00397   ip1.X = op->pt.X - opPrev->pt.X;
00398   ip1.Y = op->pt.Y - opPrev->pt.Y;
00399   ip2.X = opNext->pt.X - op->pt.X;
00400   ip2.Y = opNext->pt.Y - op->pt.Y;
00401 
00402   if (UseFullInt64Range)
00403     return Int128(ip1.X) * Int128(ip2.Y) - Int128(ip2.X) * Int128(ip1.Y) >= 0;
00404   else
00405     return (ip1.X * ip2.Y - ip2.X * ip1.Y) >= 0;
00406 }
00407 //------------------------------------------------------------------------------
00408 
00409 double Area(const Polygon &poly)
00410 {
00411   int highI = (int)poly.size() -1;
00412   if (highI < 2) return 0;
00413 
00414   if (FullRangeNeeded(poly)) {
00415     Int128 a;
00416     a = (Int128(poly[highI].X) * Int128(poly[0].Y)) -
00417       Int128(poly[0].X) * Int128(poly[highI].Y);
00418     for (int i = 0; i < highI; ++i)
00419       a += Int128(poly[i].X) * Int128(poly[i+1].Y) -
00420         Int128(poly[i+1].X) * Int128(poly[i].Y);
00421     return a.AsDouble() / 2;
00422   }
00423   else
00424   {
00425     double a;
00426     a = (double)poly[highI].X * poly[0].Y - (double)poly[0].X * poly[highI].Y;
00427     for (int i = 0; i < highI; ++i)
00428       a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * poly[i].Y;
00429     return a/2;
00430   }
00431 }
00432 //------------------------------------------------------------------------------
00433 
00434 double Area(const OutRec &outRec, bool UseFullInt64Range)
00435 {
00436   OutPt *op = outRec.pts;
00437   if (UseFullInt64Range) {
00438     Int128 a(0);
00439     do {
00440       a += (Int128(op->prev->pt.X) * Int128(op->pt.Y)) -
00441         Int128(op->pt.X) * Int128(op->prev->pt.Y);
00442       op = op->next;
00443     } while (op != outRec.pts);
00444     return a.AsDouble() / 2;
00445   }
00446   else
00447   {
00448     double a = 0;
00449     do {
00450       a += (op->prev->pt.X * op->pt.Y) - (op->pt.X * op->prev->pt.Y);
00451       op = op->next;
00452     } while (op != outRec.pts);
00453     return a/2;
00454   }
00455 }
00456 //------------------------------------------------------------------------------
00457 
00458 bool PointIsVertex(const IntPoint &pt, OutPt *pp)
00459 {
00460   OutPt *pp2 = pp;
00461   do
00462   {
00463     if (PointsEqual(pp2->pt, pt)) return true;
00464     pp2 = pp2->next;
00465   }
00466   while (pp2 != pp);
00467   return false;
00468 }
00469 //------------------------------------------------------------------------------
00470 
00471 bool PointInPolygon(const IntPoint &pt, OutPt *pp, bool UseFullInt64Range)
00472 {
00473   OutPt *pp2 = pp;
00474   bool result = false;
00475   if (UseFullInt64Range) {
00476     do
00477     {
00478       if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) ||
00479           ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) &&
00480           Int128(pt.X - pp2->pt.X) < (Int128(pp2->prev->pt.X - pp2->pt.X) *
00481           Int128(pt.Y - pp2->pt.Y)) / Int128(pp2->prev->pt.Y - pp2->pt.Y))
00482             result = !result;
00483       pp2 = pp2->next;
00484     }
00485     while (pp2 != pp);
00486   }
00487   else
00488   {
00489     do
00490     {
00491       if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) ||
00492         ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) &&
00493         (pt.X < (pp2->prev->pt.X - pp2->pt.X) * (pt.Y - pp2->pt.Y) /
00494         (pp2->prev->pt.Y - pp2->pt.Y) + pp2->pt.X )) result = !result;
00495       pp2 = pp2->next;
00496     }
00497     while (pp2 != pp);
00498   }
00499   return result;
00500 }
00501 //------------------------------------------------------------------------------
00502 
00503 bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range)
00504 {
00505   if (UseFullInt64Range)
00506     return Int128(e1.ytop - e1.ybot) * Int128(e2.xtop - e2.xbot) ==
00507       Int128(e1.xtop - e1.xbot) * Int128(e2.ytop - e2.ybot);
00508   else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) ==
00509       (e1.xtop - e1.xbot)*(e2.ytop - e2.ybot);
00510 }
00511 //------------------------------------------------------------------------------
00512 
00513 bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
00514   const IntPoint pt3, bool UseFullInt64Range)
00515 {
00516   if (UseFullInt64Range)
00517     return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) ==
00518       Int128(pt1.X-pt2.X) * Int128(pt2.Y-pt3.Y);
00519   else return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y);
00520 }
00521 //------------------------------------------------------------------------------
00522 
00523 bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
00524   const IntPoint pt3, const IntPoint pt4, bool UseFullInt64Range)
00525 {
00526   if (UseFullInt64Range)
00527     return Int128(pt1.Y-pt2.Y) * Int128(pt3.X-pt4.X) ==
00528       Int128(pt1.X-pt2.X) * Int128(pt3.Y-pt4.Y);
00529   else return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y);
00530 }
00531 //------------------------------------------------------------------------------
00532 
00533 double GetDx(const IntPoint pt1, const IntPoint pt2)
00534 {
00535   return (pt1.Y == pt2.Y) ?
00536     HORIZONTAL : (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y);
00537 }
00538 //---------------------------------------------------------------------------
00539 
00540 void SetDx(TEdge &e)
00541 {
00542   if (e.ybot == e.ytop) e.dx = HORIZONTAL;
00543   else e.dx = (double)(e.xtop - e.xbot) / (double)(e.ytop - e.ybot);
00544 }
00545 //---------------------------------------------------------------------------
00546 
00547 void SwapSides(TEdge &edge1, TEdge &edge2)
00548 {
00549   EdgeSide side =  edge1.side;
00550   edge1.side = edge2.side;
00551   edge2.side = side;
00552 }
00553 //------------------------------------------------------------------------------
00554 
00555 void SwapPolyIndexes(TEdge &edge1, TEdge &edge2)
00556 {
00557   int outIdx =  edge1.outIdx;
00558   edge1.outIdx = edge2.outIdx;
00559   edge2.outIdx = outIdx;
00560 }
00561 //------------------------------------------------------------------------------
00562 
00563 inline long64 Round(double val)
00564 {
00565   return (val < 0) ?
00566     static_cast<long64>(val - 0.5) : static_cast<long64>(val + 0.5);
00567 }
00568 //------------------------------------------------------------------------------
00569 
00570 long64 TopX(TEdge &edge, const long64 currentY)
00571 {
00572   return ( currentY == edge.ytop ) ?
00573     edge.xtop : edge.xbot + Round(edge.dx *(currentY - edge.ybot));
00574 }
00575 //------------------------------------------------------------------------------
00576 
00577 long64 TopX(const IntPoint pt1, const IntPoint pt2, const long64 currentY)
00578 {
00579   //preconditions: pt1.Y <> pt2.Y and pt1.Y > pt2.Y
00580   if (currentY >= pt1.Y) return pt1.X;
00581   else if (currentY == pt2.Y) return pt2.X;
00582   else if (pt1.X == pt2.X) return pt1.X;
00583   else
00584   {
00585     double q = (double)(pt1.X-pt2.X)/(double)(pt1.Y-pt2.Y);
00586     return Round(pt1.X + (currentY - pt1.Y) *q);
00587   }
00588 }
00589 //------------------------------------------------------------------------------
00590 
00591 bool IntersectPoint(TEdge &edge1, TEdge &edge2,
00592   IntPoint &ip, bool UseFullInt64Range)
00593 {
00594   double b1, b2;
00595   if (SlopesEqual(edge1, edge2, UseFullInt64Range)) return false;
00596   else if (NEAR_ZERO(edge1.dx))
00597   {
00598     ip.X = edge1.xbot;
00599     if (NEAR_EQUAL(edge2.dx, HORIZONTAL))
00600     {
00601       ip.Y = edge2.ybot;
00602     } else
00603     {
00604       b2 = edge2.ybot - (edge2.xbot/edge2.dx);
00605       ip.Y = Round(ip.X/edge2.dx + b2);
00606     }
00607   }
00608   else if (NEAR_ZERO(edge2.dx))
00609   {
00610     ip.X = edge2.xbot;
00611     if (NEAR_EQUAL(edge1.dx, HORIZONTAL))
00612     {
00613       ip.Y = edge1.ybot;
00614     } else
00615     {
00616       b1 = edge1.ybot - (edge1.xbot/edge1.dx);
00617       ip.Y = Round(ip.X/edge1.dx + b1);
00618     }
00619   } else
00620   {
00621     b1 = edge1.xbot - edge1.ybot * edge1.dx;
00622     b2 = edge2.xbot - edge2.ybot * edge2.dx;
00623     b2 = (b2-b1)/(edge1.dx - edge2.dx);
00624     ip.Y = Round(b2);
00625     ip.X = Round(edge1.dx * b2 + b1);
00626   }
00627 
00628   return
00629     //can be *so close* to the top of one edge that the rounded Y equals one ytop ...
00630     (ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > edge2.tmpX) ||
00631     (ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > edge2.tmpX) ||
00632     (ip.Y > edge1.ytop && ip.Y > edge2.ytop);
00633 }
00634 //------------------------------------------------------------------------------
00635 
00636 void ReversePolyPtLinks(OutPt &pp)
00637 {
00638   OutPt *pp1, *pp2;
00639   pp1 = &pp;
00640   do {
00641   pp2 = pp1->next;
00642   pp1->next = pp1->prev;
00643   pp1->prev = pp2;
00644   pp1 = pp2;
00645   } while( pp1 != &pp );
00646 }
00647 //------------------------------------------------------------------------------
00648 
00649 void DisposeOutPts(OutPt*& pp)
00650 {
00651   if (pp == 0) return;
00652   pp->prev->next = 0;
00653   while( pp )
00654   {
00655     OutPt *tmpPp = pp;
00656     pp = pp->next;
00657     delete tmpPp ;
00658   }
00659 }
00660 //------------------------------------------------------------------------------
00661 
00662 void InitEdge(TEdge *e, TEdge *eNext,
00663   TEdge *ePrev, const IntPoint &pt, PolyType polyType)
00664 {
00665   std::memset( e, 0, sizeof( TEdge ));
00666 
00667   e->next = eNext;
00668   e->prev = ePrev;
00669   e->xcurr = pt.X;
00670   e->ycurr = pt.Y;
00671   if (e->ycurr >= e->next->ycurr)
00672   {
00673     e->xbot = e->xcurr;
00674     e->ybot = e->ycurr;
00675     e->xtop = e->next->xcurr;
00676     e->ytop = e->next->ycurr;
00677     e->windDelta = 1;
00678   } else
00679   {
00680     e->xtop = e->xcurr;
00681     e->ytop = e->ycurr;
00682     e->xbot = e->next->xcurr;
00683     e->ybot = e->next->ycurr;
00684     e->windDelta = -1;
00685   }
00686   SetDx(*e);
00687   e->polyType = polyType;
00688   e->outIdx = -1;
00689 }
00690 //------------------------------------------------------------------------------
00691 
00692 inline void SwapX(TEdge &e)
00693 {
00694   //swap horizontal edges' top and bottom x's so they follow the natural
00695   //progression of the bounds - ie so their xbots will align with the
00696   //adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
00697   e.xcurr = e.xtop;
00698   e.xtop = e.xbot;
00699   e.xbot = e.xcurr;
00700 }
00701 //------------------------------------------------------------------------------
00702 
00703 void SwapPoints(IntPoint &pt1, IntPoint &pt2)
00704 {
00705   IntPoint tmp = pt1;
00706   pt1 = pt2;
00707   pt2 = tmp;
00708 }
00709 //------------------------------------------------------------------------------
00710 
00711 bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
00712   IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
00713 {
00714   //precondition: segments are colinear.
00715   if ( pt1a.Y == pt1b.Y || Abs((pt1a.X - pt1b.X)/(pt1a.Y - pt1b.Y)) > 1 )
00716   {
00717     if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b);
00718     if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b);
00719     if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
00720     if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
00721     return pt1.X < pt2.X;
00722   } else
00723   {
00724     if (pt1a.Y < pt1b.Y) SwapPoints(pt1a, pt1b);
00725     if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b);
00726     if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
00727     if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
00728     return pt1.Y > pt2.Y;
00729   }
00730 }
00731 //------------------------------------------------------------------------------
00732 
00733 bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
00734 {
00735   OutPt *p = btmPt1->prev;
00736   while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->prev;
00737   double dx1p = std::fabs(GetDx(btmPt1->pt, p->pt));
00738   p = btmPt1->next;
00739   while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->next;
00740   double dx1n = std::fabs(GetDx(btmPt1->pt, p->pt));
00741 
00742   p = btmPt2->prev;
00743   while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->prev;
00744   double dx2p = std::fabs(GetDx(btmPt2->pt, p->pt));
00745   p = btmPt2->next;
00746   while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->next;
00747   double dx2n = std::fabs(GetDx(btmPt2->pt, p->pt));
00748   return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
00749 }
00750 //------------------------------------------------------------------------------
00751 
00752 OutPt* GetBottomPt(OutPt *pp)
00753 {
00754   OutPt* dups = 0;
00755   OutPt* p = pp->next;
00756   while (p != pp)
00757   {
00758     if (p->pt.Y > pp->pt.Y)
00759     {
00760       pp = p;
00761       dups = 0;
00762     }
00763     else if (p->pt.Y == pp->pt.Y && p->pt.X <= pp->pt.X)
00764     {
00765       if (p->pt.X < pp->pt.X)
00766       {
00767         dups = 0;
00768         pp = p;
00769       } else
00770       {
00771         if (p->next != pp && p->prev != pp) dups = p;
00772       }
00773     }
00774     p = p->next;
00775   }
00776   if (dups)
00777   {
00778     //there appears to be at least 2 vertices at bottomPt so ...
00779     while (dups != p)
00780     {
00781       if (!FirstIsBottomPt(p, dups)) pp = dups;
00782       dups = dups->next;
00783       while (!PointsEqual(dups->pt, pp->pt)) dups = dups->next;
00784     }
00785   }
00786   return pp;
00787 }
00788 //------------------------------------------------------------------------------
00789 
00790 bool FindSegment(OutPt* &pp, IntPoint &pt1, IntPoint &pt2)
00791 {
00792   //outPt1 & outPt2 => the overlap segment (if the function returns true)
00793   if (!pp) return false;
00794   OutPt* pp2 = pp;
00795   IntPoint pt1a = pt1, pt2a = pt2;
00796   do
00797   {
00798     if (SlopesEqual(pt1a, pt2a, pp->pt, pp->prev->pt, true) &&
00799       SlopesEqual(pt1a, pt2a, pp->pt, true) &&
00800       GetOverlapSegment(pt1a, pt2a, pp->pt, pp->prev->pt, pt1, pt2))
00801         return true;
00802     pp = pp->next;
00803   }
00804   while (pp != pp2);
00805   return false;
00806 }
00807 //------------------------------------------------------------------------------
00808 
00809 bool Pt3IsBetweenPt1AndPt2(const IntPoint pt1,
00810   const IntPoint pt2, const IntPoint pt3)
00811 {
00812   if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true;
00813   else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X);
00814   else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.Y);
00815 }
00816 //------------------------------------------------------------------------------
00817 
00818 OutPt* InsertPolyPtBetween(OutPt* p1, OutPt* p2, const IntPoint pt)
00819 {
00820   if (p1 == p2) throw "JoinError";
00821   OutPt* result = new OutPt;
00822   result->pt = pt;
00823   if (p2 == p1->next)
00824   {
00825     p1->next = result;
00826     p2->prev = result;
00827     result->next = p2;
00828     result->prev = p1;
00829   } else
00830   {
00831     p2->next = result;
00832     p1->prev = result;
00833     result->next = p1;
00834     result->prev = p2;
00835   }
00836   return result;
00837 }
00838 
00839 //------------------------------------------------------------------------------
00840 // ClipperBase class methods ...
00841 //------------------------------------------------------------------------------
00842 
00843 ClipperBase::ClipperBase() //constructor
00844 {
00845   m_MinimaList = 0;
00846   m_CurrentLM = 0;
00847   m_UseFullRange = true;
00848 }
00849 //------------------------------------------------------------------------------
00850 
00851 ClipperBase::~ClipperBase() //destructor
00852 {
00853   Clear();
00854 }
00855 //------------------------------------------------------------------------------
00856 
00857 bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType)
00858 {
00859   int len = (int)pg.size();
00860   if (len < 3) return false;
00861   Polygon p(len);
00862   p[0] = pg[0];
00863   int j = 0;
00864 
00865   long64 maxVal;
00866   if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange;
00867 
00868   for (int i = 0; i < len; ++i)
00869   {
00870     if (Abs(pg[i].X) > maxVal || Abs(pg[i].Y) > maxVal)
00871     {
00872       if (Abs(pg[i].X) > hiRange || Abs(pg[i].Y) > hiRange)
00873         throw "Coordinate exceeds range bounds";
00874       maxVal = hiRange;
00875       m_UseFullRange = true;
00876     }
00877 
00878     if (i == 0 || PointsEqual(p[j], pg[i])) continue;
00879     else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i], m_UseFullRange))
00880     {
00881       if (PointsEqual(p[j-1], pg[i])) j--;
00882     } else j++;
00883     p[j] = pg[i];
00884   }
00885   if (j < 2) return false;
00886 
00887   len = j+1;
00888   while (len > 2)
00889   {
00890     //nb: test for point equality before testing slopes ...
00891     if (PointsEqual(p[j], p[0])) j--;
00892     else if (PointsEqual(p[0], p[1]) ||
00893       SlopesEqual(p[j], p[0], p[1], m_UseFullRange))
00894       p[0] = p[j--];
00895     else if (SlopesEqual(p[j-1], p[j], p[0], m_UseFullRange)) j--;
00896     else if (SlopesEqual(p[0], p[1], p[2], m_UseFullRange))
00897     {
00898       for (int i = 2; i <= j; ++i) p[i-1] = p[i];
00899       j--;
00900     }
00901     else break;
00902     len--;
00903   }
00904   if (len < 3) return false;
00905 
00906   //create a new edge array ...
00907   TEdge *edges = new TEdge [len];
00908   m_edges.push_back(edges);
00909 
00910   //convert vertices to a double-linked-list of edges and initialize ...
00911   edges[0].xcurr = p[0].X;
00912   edges[0].ycurr = p[0].Y;
00913   InitEdge(&edges[len-1], &edges[0], &edges[len-2], p[len-1], polyType);
00914   for (int i = len-2; i > 0; --i)
00915     InitEdge(&edges[i], &edges[i+1], &edges[i-1], p[i], polyType);
00916   InitEdge(&edges[0], &edges[1], &edges[len-1], p[0], polyType);
00917 
00918   //reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates
00919   //increase downward so the 'highest' edge will have the smallest ytop) ...
00920   TEdge *e = &edges[0];
00921   TEdge *eHighest = e;
00922   do
00923   {
00924     e->xcurr = e->xbot;
00925     e->ycurr = e->ybot;
00926     if (e->ytop < eHighest->ytop) eHighest = e;
00927     e = e->next;
00928   }
00929   while ( e != &edges[0]);
00930 
00931   //make sure eHighest is positioned so the following loop works safely ...
00932   if (eHighest->windDelta > 0) eHighest = eHighest->next;
00933   if (NEAR_EQUAL(eHighest->dx, HORIZONTAL)) eHighest = eHighest->next;
00934 
00935   //finally insert each local minima ...
00936   e = eHighest;
00937   do {
00938     e = AddBoundsToLML(e);
00939   }
00940   while( e != eHighest );
00941   return true;
00942 }
00943 //------------------------------------------------------------------------------
00944 
00945 void ClipperBase::InsertLocalMinima(LocalMinima *newLm)
00946 {
00947   if( ! m_MinimaList )
00948   {
00949     m_MinimaList = newLm;
00950   }
00951   else if( newLm->Y >= m_MinimaList->Y )
00952   {
00953     newLm->next = m_MinimaList;
00954     m_MinimaList = newLm;
00955   } else
00956   {
00957     LocalMinima* tmpLm = m_MinimaList;
00958     while( tmpLm->next  && ( newLm->Y < tmpLm->next->Y ) )
00959       tmpLm = tmpLm->next;
00960     newLm->next = tmpLm->next;
00961     tmpLm->next = newLm;
00962   }
00963 }
00964 //------------------------------------------------------------------------------
00965 
00966 TEdge* ClipperBase::AddBoundsToLML(TEdge *e)
00967 {
00968   //Starting at the top of one bound we progress to the bottom where there's
00969   //a local minima. We then go to the top of the next bound. These two bounds
00970   //form the left and right (or right and left) bounds of the local minima.
00971   e->nextInLML = 0;
00972   e = e->next;
00973   for (;;)
00974   {
00975     if (NEAR_EQUAL(e->dx, HORIZONTAL))
00976     {
00977       //nb: proceed through horizontals when approaching from their right,
00978       //    but break on horizontal minima if approaching from their left.
00979       //    This ensures 'local minima' are always on the left of horizontals.
00980       if (e->next->ytop < e->ytop && e->next->xbot > e->prev->xbot) break;
00981       if (e->xtop != e->prev->xbot) SwapX(*e);
00982       e->nextInLML = e->prev;
00983     }
00984     else if (e->ycurr == e->prev->ycurr) break;
00985     else e->nextInLML = e->prev;
00986     e = e->next;
00987   }
00988 
00989   //e and e.prev are now at a local minima ...
00990   LocalMinima* newLm = new LocalMinima;
00991   newLm->next = 0;
00992   newLm->Y = e->prev->ybot;
00993 
00994   if ( NEAR_EQUAL(e->dx, HORIZONTAL) ) //horizontal edges never start a left bound
00995   {
00996     if (e->xbot != e->prev->xbot) SwapX(*e);
00997     newLm->leftBound = e->prev;
00998     newLm->rightBound = e;
00999   } else if (e->dx < e->prev->dx)
01000   {
01001     newLm->leftBound = e->prev;
01002     newLm->rightBound = e;
01003   } else
01004   {
01005     newLm->leftBound = e;
01006     newLm->rightBound = e->prev;
01007   }
01008   newLm->leftBound->side = esLeft;
01009   newLm->rightBound->side = esRight;
01010   InsertLocalMinima( newLm );
01011 
01012   for (;;)
01013   {
01014     if ( e->next->ytop == e->ytop && !NEAR_EQUAL(e->next->dx, HORIZONTAL) ) break;
01015     e->nextInLML = e->next;
01016     e = e->next;
01017     if ( NEAR_EQUAL(e->dx, HORIZONTAL) && e->xbot != e->prev->xtop) SwapX(*e);
01018   }
01019   return e->next;
01020 }
01021 //------------------------------------------------------------------------------
01022 
01023 bool ClipperBase::AddPolygons(const Polygons &ppg, PolyType polyType)
01024 {
01025   bool result = false;
01026   for (Polygons::size_type i = 0; i < ppg.size(); ++i)
01027     if (AddPolygon(ppg[i], polyType)) result = true;
01028   return result;
01029 }
01030 //------------------------------------------------------------------------------
01031 
01032 void ClipperBase::Clear()
01033 {
01034   DisposeLocalMinimaList();
01035   for (EdgeList::size_type i = 0; i < m_edges.size(); ++i) delete [] m_edges[i];
01036   m_edges.clear();
01037   m_UseFullRange = false;
01038 }
01039 //------------------------------------------------------------------------------
01040 
01041 void ClipperBase::Reset()
01042 {
01043   m_CurrentLM = m_MinimaList;
01044   if( !m_CurrentLM ) return; //ie nothing to process
01045 
01046   //reset all edges ...
01047   LocalMinima* lm = m_MinimaList;
01048   while( lm )
01049   {
01050     TEdge* e = lm->leftBound;
01051     while( e )
01052     {
01053       e->xcurr = e->xbot;
01054       e->ycurr = e->ybot;
01055       e->side = esLeft;
01056       e->outIdx = -1;
01057       e = e->nextInLML;
01058     }
01059     e = lm->rightBound;
01060     while( e )
01061     {
01062       e->xcurr = e->xbot;
01063       e->ycurr = e->ybot;
01064       e->side = esRight;
01065       e->outIdx = -1;
01066       e = e->nextInLML;
01067     }
01068     lm = lm->next;
01069   }
01070 }
01071 //------------------------------------------------------------------------------
01072 
01073 void ClipperBase::DisposeLocalMinimaList()
01074 {
01075   while( m_MinimaList )
01076   {
01077     LocalMinima* tmpLm = m_MinimaList->next;
01078     delete m_MinimaList;
01079     m_MinimaList = tmpLm;
01080   }
01081   m_CurrentLM = 0;
01082 }
01083 //------------------------------------------------------------------------------
01084 
01085 void ClipperBase::PopLocalMinima()
01086 {
01087   if( ! m_CurrentLM ) return;
01088   m_CurrentLM = m_CurrentLM->next;
01089 }
01090 //------------------------------------------------------------------------------
01091 
01092 IntRect ClipperBase::GetBounds()
01093 {
01094   IntRect result;
01095   LocalMinima* lm = m_MinimaList;
01096   if (!lm)
01097   {
01098     result.left = result.top = result.right = result.bottom = 0;
01099     return result;
01100   }
01101   result.left = lm->leftBound->xbot;
01102   result.top = lm->leftBound->ybot;
01103   result.right = lm->leftBound->xbot;
01104   result.bottom = lm->leftBound->ybot;
01105   while (lm)
01106   {
01107     if (lm->leftBound->ybot > result.bottom)
01108       result.bottom = lm->leftBound->ybot;
01109     TEdge* e = lm->leftBound;
01110     for (;;) {
01111       TEdge* bottomE = e;
01112       while (e->nextInLML)
01113       {
01114         if (e->xbot < result.left) result.left = e->xbot;
01115         if (e->xbot > result.right) result.right = e->xbot;
01116         e = e->nextInLML;
01117       }
01118       if (e->xbot < result.left) result.left = e->xbot;
01119       if (e->xbot > result.right) result.right = e->xbot;
01120       if (e->xtop < result.left) result.left = e->xtop;
01121       if (e->xtop > result.right) result.right = e->xtop;
01122       if (e->ytop < result.top) result.top = e->ytop;
01123 
01124       if (bottomE == lm->leftBound) e = lm->rightBound;
01125       else break;
01126     }
01127     lm = lm->next;
01128   }
01129   return result;
01130 }
01131 
01132 
01133 //------------------------------------------------------------------------------
01134 // TClipper methods ...
01135 //------------------------------------------------------------------------------
01136 
01137 Clipper::Clipper() : ClipperBase() //constructor
01138 {
01139   m_Scanbeam = 0;
01140   m_ActiveEdges = 0;
01141   m_SortedEdges = 0;
01142   m_IntersectNodes = 0;
01143   m_ExecuteLocked = false;
01144   m_UseFullRange = false;
01145   m_ReverseOutput = false;
01146 }
01147 //------------------------------------------------------------------------------
01148 
01149 Clipper::~Clipper() //destructor
01150 {
01151   Clear();
01152   DisposeScanbeamList();
01153 }
01154 //------------------------------------------------------------------------------
01155 
01156 void Clipper::Clear()
01157 {
01158   if (m_edges.size() == 0) return; //avoids problems with ClipperBase destructor
01159   DisposeAllPolyPts();
01160   ClipperBase::Clear();
01161 }
01162 //------------------------------------------------------------------------------
01163 
01164 void Clipper::DisposeScanbeamList()
01165 {
01166   while ( m_Scanbeam ) {
01167   Scanbeam* sb2 = m_Scanbeam->next;
01168   delete m_Scanbeam;
01169   m_Scanbeam = sb2;
01170   }
01171 }
01172 //------------------------------------------------------------------------------
01173 
01174 void Clipper::Reset()
01175 {
01176   ClipperBase::Reset();
01177   m_Scanbeam = 0;
01178   m_ActiveEdges = 0;
01179   m_SortedEdges = 0;
01180   DisposeAllPolyPts();
01181   LocalMinima* lm = m_MinimaList;
01182   while (lm)
01183   {
01184     InsertScanbeam(lm->Y);
01185     InsertScanbeam(lm->leftBound->ytop);
01186     lm = lm->next;
01187   }
01188 }
01189 //------------------------------------------------------------------------------
01190 
01191 bool Clipper::Execute(ClipType clipType, Polygons &solution,
01192     PolyFillType subjFillType, PolyFillType clipFillType)
01193 {
01194   if( m_ExecuteLocked ) return false;
01195   m_ExecuteLocked = true;
01196   solution.resize(0);
01197   m_SubjFillType = subjFillType;
01198   m_ClipFillType = clipFillType;
01199   m_ClipType = clipType;
01200   bool succeeded = ExecuteInternal(false);
01201   if (succeeded) BuildResult(solution);
01202   m_ExecuteLocked = false;
01203   return succeeded;
01204 }
01205 //------------------------------------------------------------------------------
01206 
01207 bool Clipper::Execute(ClipType clipType, ExPolygons &solution,
01208     PolyFillType subjFillType, PolyFillType clipFillType)
01209 {
01210   if( m_ExecuteLocked ) return false;
01211   m_ExecuteLocked = true;
01212   solution.resize(0);
01213   m_SubjFillType = subjFillType;
01214   m_ClipFillType = clipFillType;
01215   m_ClipType = clipType;
01216   bool succeeded = ExecuteInternal(true);
01217   if (succeeded) BuildResultEx(solution);
01218   m_ExecuteLocked = false;
01219   return succeeded;
01220 }
01221 //------------------------------------------------------------------------------
01222 
01223 bool PolySort(OutRec *or1, OutRec *or2)
01224 {
01225   if (or1 == or2) return false;
01226   if (!or1->pts || !or2->pts)
01227   {
01228     if (or1->pts != or2->pts)
01229     {
01230       return or1->pts ? true : false;
01231     }
01232     else return false;
01233   }
01234   int i1, i2;
01235   if (or1->isHole)
01236     i1 = or1->FirstLeft->idx; else
01237     i1 = or1->idx;
01238   if (or2->isHole)
01239     i2 = or2->FirstLeft->idx; else
01240     i2 = or2->idx;
01241   int result = i1 - i2;
01242   if (result == 0 && (or1->isHole != or2->isHole))
01243   {
01244     return or1->isHole ? false : true;
01245   }
01246   else return result < 0;
01247 }
01248 //------------------------------------------------------------------------------
01249 
01250 OutRec* FindAppendLinkEnd(OutRec *outRec)
01251 {
01252   while (outRec->AppendLink) outRec = outRec->AppendLink;
01253   return outRec;
01254 }
01255 //------------------------------------------------------------------------------
01256 
01257 void Clipper::FixHoleLinkage(OutRec *outRec)
01258 {
01259   OutRec *tmp;
01260   if (outRec->bottomPt)
01261     tmp = m_PolyOuts[outRec->bottomPt->idx]->FirstLeft;
01262   else
01263     tmp = outRec->FirstLeft;
01264   if (outRec == tmp) throw clipperException("HoleLinkage error");
01265 
01266   if (tmp)
01267   {
01268     if (tmp->AppendLink) tmp = FindAppendLinkEnd(tmp);
01269     if (tmp == outRec) tmp = 0;
01270     else if (tmp->isHole)
01271     {
01272       FixHoleLinkage(tmp);
01273       tmp = tmp->FirstLeft;
01274     }
01275   }
01276   outRec->FirstLeft = tmp;
01277   if (!tmp) outRec->isHole = false;
01278   outRec->AppendLink = 0;
01279 }
01280 //------------------------------------------------------------------------------
01281 
01282 bool Clipper::ExecuteInternal(bool fixHoleLinkages)
01283 {
01284   bool succeeded;
01285   try {
01286     Reset();
01287     if (!m_CurrentLM ) return true;
01288     long64 botY = PopScanbeam();
01289     do {
01290       InsertLocalMinimaIntoAEL(botY);
01291       ClearHorzJoins();
01292       ProcessHorizontals();
01293       long64 topY = PopScanbeam();
01294       succeeded = ProcessIntersections(botY, topY);
01295       if (!succeeded) break;
01296       ProcessEdgesAtTopOfScanbeam(topY);
01297       botY = topY;
01298     } while( m_Scanbeam );
01299   }
01300   catch(...) {
01301     succeeded = false;
01302   }
01303 
01304   if (succeeded)
01305   {
01306     //tidy up output polygons and fix orientations where necessary ...
01307     for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
01308     {
01309       OutRec *outRec = m_PolyOuts[i];
01310       if (!outRec->pts) continue;
01311       FixupOutPolygon(*outRec);
01312       if (!outRec->pts) continue;
01313       if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec);
01314 
01315       if (outRec->bottomPt == outRec->bottomFlag &&
01316         (Orientation(outRec, m_UseFullRange) != (Area(*outRec, m_UseFullRange) > 0)))
01317           DisposeBottomPt(*outRec);
01318 
01319       if (outRec->isHole ==
01320         (m_ReverseOutput ^ Orientation(outRec, m_UseFullRange)))
01321           ReversePolyPtLinks(*outRec->pts);
01322     }
01323 
01324     JoinCommonEdges(fixHoleLinkages);
01325     if (fixHoleLinkages)
01326       std::sort(m_PolyOuts.begin(), m_PolyOuts.end(), PolySort);
01327   }
01328 
01329   ClearJoins();
01330   ClearHorzJoins();
01331   return succeeded;
01332 }
01333 //------------------------------------------------------------------------------
01334 
01335 void Clipper::InsertScanbeam(const long64 Y)
01336 {
01337   if( !m_Scanbeam )
01338   {
01339     m_Scanbeam = new Scanbeam;
01340     m_Scanbeam->next = 0;
01341     m_Scanbeam->Y = Y;
01342   }
01343   else if(  Y > m_Scanbeam->Y )
01344   {
01345     Scanbeam* newSb = new Scanbeam;
01346     newSb->Y = Y;
01347     newSb->next = m_Scanbeam;
01348     m_Scanbeam = newSb;
01349   } else
01350   {
01351     Scanbeam* sb2 = m_Scanbeam;
01352     while( sb2->next  && ( Y <= sb2->next->Y ) ) sb2 = sb2->next;
01353     if(  Y == sb2->Y ) return; //ie ignores duplicates
01354     Scanbeam* newSb = new Scanbeam;
01355     newSb->Y = Y;
01356     newSb->next = sb2->next;
01357     sb2->next = newSb;
01358   }
01359 }
01360 //------------------------------------------------------------------------------
01361 
01362 long64 Clipper::PopScanbeam()
01363 {
01364   long64 Y = m_Scanbeam->Y;
01365   Scanbeam* sb2 = m_Scanbeam;
01366   m_Scanbeam = m_Scanbeam->next;
01367   delete sb2;
01368   return Y;
01369 }
01370 //------------------------------------------------------------------------------
01371 
01372 void Clipper::DisposeAllPolyPts(){
01373   for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
01374     DisposeOutRec(i);
01375   m_PolyOuts.clear();
01376 }
01377 //------------------------------------------------------------------------------
01378 
01379 void Clipper::DisposeOutRec(PolyOutList::size_type index)
01380 {
01381   OutRec *outRec = m_PolyOuts[index];
01382   if (outRec->pts) DisposeOutPts(outRec->pts);
01383   delete outRec;
01384   m_PolyOuts[index] = 0;
01385 }
01386 //------------------------------------------------------------------------------
01387 
01388 void Clipper::SetWindingCount(TEdge &edge)
01389 {
01390   TEdge *e = edge.prevInAEL;
01391   //find the edge of the same polytype that immediately preceeds 'edge' in AEL
01392   while ( e  && e->polyType != edge.polyType ) e = e->prevInAEL;
01393   if ( !e )
01394   {
01395     edge.windCnt = edge.windDelta;
01396     edge.windCnt2 = 0;
01397     e = m_ActiveEdges; //ie get ready to calc windCnt2
01398   } else if ( IsEvenOddFillType(edge) )
01399   {
01400     //EvenOdd filling ...
01401     edge.windCnt = 1;
01402     edge.windCnt2 = e->windCnt2;
01403     e = e->nextInAEL; //ie get ready to calc windCnt2
01404   } else
01405   {
01406     //nonZero, Positive or Negative filling ...
01407     if ( e->windCnt * e->windDelta < 0 )
01408     {
01409       if (Abs(e->windCnt) > 1)
01410       {
01411         if (e->windDelta * edge.windDelta < 0) edge.windCnt = e->windCnt;
01412         else edge.windCnt = e->windCnt + edge.windDelta;
01413       } else
01414         edge.windCnt = e->windCnt + e->windDelta + edge.windDelta;
01415     } else
01416     {
01417       if ( Abs(e->windCnt) > 1 && e->windDelta * edge.windDelta < 0)
01418         edge.windCnt = e->windCnt;
01419       else if ( e->windCnt + edge.windDelta == 0 )
01420         edge.windCnt = e->windCnt;
01421       else edge.windCnt = e->windCnt + edge.windDelta;
01422     }
01423     edge.windCnt2 = e->windCnt2;
01424     e = e->nextInAEL; //ie get ready to calc windCnt2
01425   }
01426 
01427   //update windCnt2 ...
01428   if ( IsEvenOddAltFillType(edge) )
01429   {
01430     //EvenOdd filling ...
01431     while ( e != &edge )
01432     {
01433       edge.windCnt2 = (edge.windCnt2 == 0) ? 1 : 0;
01434       e = e->nextInAEL;
01435     }
01436   } else
01437   {
01438     //nonZero, Positive or Negative filling ...
01439     while ( e != &edge )
01440     {
01441       edge.windCnt2 += e->windDelta;
01442       e = e->nextInAEL;
01443     }
01444   }
01445 }
01446 //------------------------------------------------------------------------------
01447 
01448 bool Clipper::IsEvenOddFillType(const TEdge& edge) const
01449 {
01450   if (edge.polyType == ptSubject)
01451     return m_SubjFillType == pftEvenOdd; else
01452     return m_ClipFillType == pftEvenOdd;
01453 }
01454 //------------------------------------------------------------------------------
01455 
01456 bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const
01457 {
01458   if (edge.polyType == ptSubject)
01459     return m_ClipFillType == pftEvenOdd; else
01460     return m_SubjFillType == pftEvenOdd;
01461 }
01462 //------------------------------------------------------------------------------
01463 
01464 bool Clipper::IsContributing(const TEdge& edge) const
01465 {
01466   PolyFillType pft, pft2;
01467   if (edge.polyType == ptSubject)
01468   {
01469     pft = m_SubjFillType;
01470     pft2 = m_ClipFillType;
01471   } else
01472   {
01473     pft = m_ClipFillType;
01474     pft2 = m_SubjFillType;
01475   }
01476 
01477   switch(pft)
01478   {
01479     case pftEvenOdd: 
01480     case pftNonZero:
01481       if (Abs(edge.windCnt) != 1) return false;
01482       break;
01483     case pftPositive: 
01484       if (edge.windCnt != 1) return false;
01485       break;
01486     default: //pftNegative
01487       if (edge.windCnt != -1) return false;
01488   }
01489 
01490   switch(m_ClipType)
01491   {
01492     case ctIntersection:
01493       switch(pft2)
01494       {
01495         case pftEvenOdd: 
01496         case pftNonZero: 
01497           return (edge.windCnt2 != 0);
01498         case pftPositive: 
01499           return (edge.windCnt2 > 0);
01500         default: 
01501           return (edge.windCnt2 < 0);
01502       }
01503     case ctUnion:
01504       switch(pft2)
01505       {
01506         case pftEvenOdd: 
01507         case pftNonZero: 
01508           return (edge.windCnt2 == 0);
01509         case pftPositive: 
01510           return (edge.windCnt2 <= 0);
01511         default: 
01512           return (edge.windCnt2 >= 0);
01513       }
01514     case ctDifference:
01515       if (edge.polyType == ptSubject)
01516         switch(pft2)
01517         {
01518           case pftEvenOdd: 
01519           case pftNonZero: 
01520             return (edge.windCnt2 == 0);
01521           case pftPositive: 
01522             return (edge.windCnt2 <= 0);
01523           default: 
01524             return (edge.windCnt2 >= 0);
01525         }
01526       else
01527         switch(pft2)
01528         {
01529           case pftEvenOdd: 
01530           case pftNonZero: 
01531             return (edge.windCnt2 != 0);
01532           case pftPositive: 
01533             return (edge.windCnt2 > 0);
01534           default: 
01535             return (edge.windCnt2 < 0);
01536         }
01537     default:
01538       return true;
01539   }
01540 }
01541 //------------------------------------------------------------------------------
01542 
01543 void Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
01544 {
01545   TEdge *e, *prevE;
01546   if( NEAR_EQUAL(e2->dx, HORIZONTAL) || ( e1->dx > e2->dx ) )
01547   {
01548     AddOutPt( e1, pt );
01549     e2->outIdx = e1->outIdx;
01550     e1->side = esLeft;
01551     e2->side = esRight;
01552     e = e1;
01553     if (e->prevInAEL == e2)
01554       prevE = e2->prevInAEL; 
01555     else
01556       prevE = e->prevInAEL;
01557   } else
01558   {
01559     AddOutPt( e2, pt );
01560     e1->outIdx = e2->outIdx;
01561     e1->side = esRight;
01562     e2->side = esLeft;
01563     e = e2;
01564     if (e->prevInAEL == e1)
01565         prevE = e1->prevInAEL;
01566     else
01567         prevE = e->prevInAEL;
01568   }
01569   if (prevE && prevE->outIdx >= 0 &&
01570       (TopX(*prevE, pt.Y) == TopX(*e, pt.Y)) &&
01571         SlopesEqual(*e, *prevE, m_UseFullRange))
01572           AddJoin(e, prevE, -1, -1);
01573 }
01574 //------------------------------------------------------------------------------
01575 
01576 void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
01577 {
01578   AddOutPt( e1, pt );
01579   if( e1->outIdx == e2->outIdx )
01580   {
01581     e1->outIdx = -1;
01582     e2->outIdx = -1;
01583   }
01584   else if (e1->outIdx < e2->outIdx) 
01585     AppendPolygon(e1, e2); 
01586   else 
01587     AppendPolygon(e2, e1);
01588 }
01589 //------------------------------------------------------------------------------
01590 
01591 void Clipper::AddEdgeToSEL(TEdge *edge)
01592 {
01593   //SEL pointers in PEdge are reused to build a list of horizontal edges.
01594   //However, we don't need to worry about order with horizontal edge processing.
01595   if( !m_SortedEdges )
01596   {
01597     m_SortedEdges = edge;
01598     edge->prevInSEL = 0;
01599     edge->nextInSEL = 0;
01600   }
01601   else
01602   {
01603     edge->nextInSEL = m_SortedEdges;
01604     edge->prevInSEL = 0;
01605     m_SortedEdges->prevInSEL = edge;
01606     m_SortedEdges = edge;
01607   }
01608 }
01609 //------------------------------------------------------------------------------
01610 
01611 void Clipper::CopyAELToSEL()
01612 {
01613   TEdge* e = m_ActiveEdges;
01614   m_SortedEdges = e;
01615   if (!m_ActiveEdges) return;
01616   m_SortedEdges->prevInSEL = 0;
01617   e = e->nextInAEL;
01618   while ( e )
01619   {
01620     e->prevInSEL = e->prevInAEL;
01621     e->prevInSEL->nextInSEL = e;
01622     e->nextInSEL = 0;
01623     e = e->nextInAEL;
01624   }
01625 }
01626 //------------------------------------------------------------------------------
01627 
01628 void Clipper::AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx, int e2OutIdx)
01629 {
01630   JoinRec* jr = new JoinRec;
01631   if (e1OutIdx >= 0)
01632     jr->poly1Idx = e1OutIdx; else
01633     jr->poly1Idx = e1->outIdx;
01634   jr->pt1a = IntPoint(e1->xcurr, e1->ycurr);
01635   jr->pt1b = IntPoint(e1->xtop, e1->ytop);
01636   if (e2OutIdx >= 0)
01637     jr->poly2Idx = e2OutIdx; else
01638     jr->poly2Idx = e2->outIdx;
01639   jr->pt2a = IntPoint(e2->xcurr, e2->ycurr);
01640   jr->pt2b = IntPoint(e2->xtop, e2->ytop);
01641   m_Joins.push_back(jr);
01642 }
01643 //------------------------------------------------------------------------------
01644 
01645 void Clipper::ClearJoins()
01646 {
01647   for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
01648     delete m_Joins[i];
01649   m_Joins.resize(0);
01650 }
01651 //------------------------------------------------------------------------------
01652 
01653 void Clipper::AddHorzJoin(TEdge *e, int idx)
01654 {
01655   HorzJoinRec* hj = new HorzJoinRec;
01656   hj->edge = e;
01657   hj->savedIdx = idx;
01658   m_HorizJoins.push_back(hj);
01659 }
01660 //------------------------------------------------------------------------------
01661 
01662 void Clipper::ClearHorzJoins()
01663 {
01664   for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++)
01665     delete m_HorizJoins[i];
01666   m_HorizJoins.resize(0);
01667 }
01668 //------------------------------------------------------------------------------
01669 
01670 void Clipper::InsertLocalMinimaIntoAEL( const long64 botY)
01671 {
01672   while(  m_CurrentLM  && ( m_CurrentLM->Y == botY ) )
01673   {
01674     TEdge* lb = m_CurrentLM->leftBound;
01675     TEdge* rb = m_CurrentLM->rightBound;
01676 
01677     InsertEdgeIntoAEL( lb );
01678     InsertScanbeam( lb->ytop );
01679     InsertEdgeIntoAEL( rb );
01680 
01681     if (IsEvenOddFillType(*lb))
01682     {
01683       lb->windDelta = 1;
01684       rb->windDelta = 1;
01685     }
01686     else
01687     {
01688       rb->windDelta = -lb->windDelta;
01689     }
01690     SetWindingCount( *lb );
01691     rb->windCnt = lb->windCnt;
01692     rb->windCnt2 = lb->windCnt2;
01693 
01694     if( NEAR_EQUAL(rb->dx, HORIZONTAL) )
01695     {
01696       //nb: only rightbounds can have a horizontal bottom edge
01697       AddEdgeToSEL( rb );
01698       InsertScanbeam( rb->nextInLML->ytop );
01699     }
01700     else
01701       InsertScanbeam( rb->ytop );
01702 
01703     if( IsContributing(*lb) )
01704       AddLocalMinPoly( lb, rb, IntPoint(lb->xcurr, m_CurrentLM->Y) );
01705 
01706     //if any output polygons share an edge, they'll need joining later ...
01707     if (rb->outIdx >= 0)
01708     {
01709       if (NEAR_EQUAL(rb->dx, HORIZONTAL))
01710       {
01711         for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
01712         {
01713           IntPoint pt, pt2; //returned by GetOverlapSegment() but unused here.
01714           HorzJoinRec* hj = m_HorizJoins[i];
01715           //if horizontals rb and hj.edge overlap, flag for joining later ...
01716           if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot),
01717             IntPoint(hj->edge->xtop, hj->edge->ytop),
01718             IntPoint(rb->xbot, rb->ybot),
01719             IntPoint(rb->xtop, rb->ytop), pt, pt2))
01720               AddJoin(hj->edge, rb, hj->savedIdx);
01721         }
01722       }
01723     }
01724 
01725     if( lb->nextInAEL != rb )
01726     {
01727       if (rb->outIdx >= 0 && rb->prevInAEL->outIdx >= 0 &&
01728         SlopesEqual(*rb->prevInAEL, *rb, m_UseFullRange))
01729           AddJoin(rb, rb->prevInAEL);
01730 
01731       TEdge* e = lb->nextInAEL;
01732       IntPoint pt = IntPoint(lb->xcurr, lb->ycurr);
01733       while( e != rb )
01734       {
01735         if(!e) throw clipperException("InsertLocalMinimaIntoAEL: missing rightbound!");
01736         //nb: For calculating winding counts etc, IntersectEdges() assumes
01737         //that param1 will be to the right of param2 ABOVE the intersection ...
01738         IntersectEdges( rb , e , pt , ipNone); //order important here
01739         e = e->nextInAEL;
01740       }
01741     }
01742     PopLocalMinima();
01743   }
01744 }
01745 //------------------------------------------------------------------------------
01746 
01747 void Clipper::DeleteFromAEL(TEdge *e)
01748 {
01749   TEdge* AelPrev = e->prevInAEL;
01750   TEdge* AelNext = e->nextInAEL;
01751   if(  !AelPrev &&  !AelNext && (e != m_ActiveEdges) ) return; //already deleted
01752   if( AelPrev ) AelPrev->nextInAEL = AelNext;
01753   else m_ActiveEdges = AelNext;
01754   if( AelNext ) AelNext->prevInAEL = AelPrev;
01755   e->nextInAEL = 0;
01756   e->prevInAEL = 0;
01757 }
01758 //------------------------------------------------------------------------------
01759 
01760 void Clipper::DeleteFromSEL(TEdge *e)
01761 {
01762   TEdge* SelPrev = e->prevInSEL;
01763   TEdge* SelNext = e->nextInSEL;
01764   if( !SelPrev &&  !SelNext && (e != m_SortedEdges) ) return; //already deleted
01765   if( SelPrev ) SelPrev->nextInSEL = SelNext;
01766   else m_SortedEdges = SelNext;
01767   if( SelNext ) SelNext->prevInSEL = SelPrev;
01768   e->nextInSEL = 0;
01769   e->prevInSEL = 0;
01770 }
01771 //------------------------------------------------------------------------------
01772 
01773 void Clipper::IntersectEdges(TEdge *e1, TEdge *e2,
01774      const IntPoint &pt, IntersectProtects protects)
01775 {
01776   //e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before
01777   //e2 in AEL except when e1 is being inserted at the intersection point ...
01778   bool e1stops = !(ipLeft & protects) &&  !e1->nextInLML &&
01779     e1->xtop == pt.X && e1->ytop == pt.Y;
01780   bool e2stops = !(ipRight & protects) &&  !e2->nextInLML &&
01781     e2->xtop == pt.X && e2->ytop == pt.Y;
01782   bool e1Contributing = ( e1->outIdx >= 0 );
01783   bool e2contributing = ( e2->outIdx >= 0 );
01784 
01785   //update winding counts...
01786   //assumes that e1 will be to the right of e2 ABOVE the intersection
01787   if ( e1->polyType == e2->polyType )
01788   {
01789     if ( IsEvenOddFillType( *e1) )
01790     {
01791       int oldE1WindCnt = e1->windCnt;
01792       e1->windCnt = e2->windCnt;
01793       e2->windCnt = oldE1WindCnt;
01794     } else
01795     {
01796       if (e1->windCnt + e2->windDelta == 0 ) e1->windCnt = -e1->windCnt;
01797       else e1->windCnt += e2->windDelta;
01798       if ( e2->windCnt - e1->windDelta == 0 ) e2->windCnt = -e2->windCnt;
01799       else e2->windCnt -= e1->windDelta;
01800     }
01801   } else
01802   {
01803     if (!IsEvenOddFillType(*e2)) e1->windCnt2 += e2->windDelta;
01804     else e1->windCnt2 = ( e1->windCnt2 == 0 ) ? 1 : 0;
01805     if (!IsEvenOddFillType(*e1)) e2->windCnt2 -= e1->windDelta;
01806     else e2->windCnt2 = ( e2->windCnt2 == 0 ) ? 1 : 0;
01807   }
01808 
01809   PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
01810   if (e1->polyType == ptSubject)
01811   {
01812     e1FillType = m_SubjFillType;
01813     e1FillType2 = m_ClipFillType;
01814   } else
01815   {
01816     e1FillType = m_ClipFillType;
01817     e1FillType2 = m_SubjFillType;
01818   }
01819   if (e2->polyType == ptSubject)
01820   {
01821     e2FillType = m_SubjFillType;
01822     e2FillType2 = m_ClipFillType;
01823   } else
01824   {
01825     e2FillType = m_ClipFillType;
01826     e2FillType2 = m_SubjFillType;
01827   }
01828 
01829   long64 e1Wc, e2Wc;
01830   switch (e1FillType)
01831   {
01832     case pftPositive: e1Wc = e1->windCnt; break;
01833     case pftNegative: e1Wc = -e1->windCnt; break;
01834     default: e1Wc = Abs(e1->windCnt);
01835   }
01836   switch(e2FillType)
01837   {
01838     case pftPositive: e2Wc = e2->windCnt; break;
01839     case pftNegative: e2Wc = -e2->windCnt; break;
01840     default: e2Wc = Abs(e2->windCnt);
01841   }
01842 
01843   if ( e1Contributing && e2contributing )
01844   {
01845     if ( e1stops || e2stops || 
01846       (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
01847       (e1->polyType != e2->polyType && m_ClipType != ctXor) )
01848         AddLocalMaxPoly(e1, e2, pt); 
01849     else
01850         DoBothEdges( e1, e2, pt );
01851   }
01852   else if ( e1Contributing )
01853   {
01854     if ((e2Wc == 0 || e2Wc == 1) && 
01855       (m_ClipType != ctIntersection || 
01856       e2->polyType == ptSubject || (e2->windCnt2 != 0))) 
01857         DoEdge1(e1, e2, pt);
01858   }
01859   else if ( e2contributing )
01860   {
01861     if ((e1Wc == 0 || e1Wc == 1) && 
01862       (m_ClipType != ctIntersection || 
01863       e1->polyType == ptSubject || (e1->windCnt2 != 0))) 
01864         DoEdge2(e1, e2, pt);
01865   } 
01866   else if ( (e1Wc == 0 || e1Wc == 1) && 
01867     (e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops )
01868   {
01869     //neither edge is currently contributing ...
01870 
01871     long64 e1Wc2, e2Wc2;
01872     switch (e1FillType2)
01873     {
01874       case pftPositive: e1Wc2 = e1->windCnt2; break;
01875       case pftNegative : e1Wc2 = -e1->windCnt2; break;
01876       default: e1Wc2 = Abs(e1->windCnt2);
01877     }
01878     switch (e2FillType2)
01879     {
01880       case pftPositive: e2Wc2 = e2->windCnt2; break;
01881       case pftNegative: e2Wc2 = -e2->windCnt2; break;
01882       default: e2Wc2 = Abs(e2->windCnt2);
01883     }
01884 
01885     if (e1->polyType != e2->polyType)
01886         AddLocalMinPoly(e1, e2, pt);
01887     else if (e1Wc == 1 && e2Wc == 1)
01888       switch( m_ClipType ) {
01889         case ctIntersection:
01890           if (e1Wc2 > 0 && e2Wc2 > 0)
01891             AddLocalMinPoly(e1, e2, pt);
01892           break;
01893         case ctUnion:
01894           if ( e1Wc2 <= 0 && e2Wc2 <= 0 )
01895             AddLocalMinPoly(e1, e2, pt);
01896           break;
01897         case ctDifference:
01898           if (((e1->polyType == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
01899               ((e1->polyType == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
01900                 AddLocalMinPoly(e1, e2, pt);
01901           break;
01902         case ctXor:
01903           AddLocalMinPoly(e1, e2, pt);
01904       }
01905     else
01906       SwapSides( *e1, *e2 );
01907   }
01908 
01909   if(  (e1stops != e2stops) &&
01910     ( (e1stops && (e1->outIdx >= 0)) || (e2stops && (e2->outIdx >= 0)) ) )
01911   {
01912     SwapSides( *e1, *e2 );
01913     SwapPolyIndexes( *e1, *e2 );
01914   }
01915 
01916   //finally, delete any non-contributing maxima edges  ...
01917   if( e1stops ) DeleteFromAEL( e1 );
01918   if( e2stops ) DeleteFromAEL( e2 );
01919 }
01920 //------------------------------------------------------------------------------
01921 
01922 void Clipper::SetHoleState(TEdge *e, OutRec *outRec)
01923 {
01924   bool isHole = false;
01925   TEdge *e2 = e->prevInAEL;
01926   while (e2)
01927   {
01928     if (e2->outIdx >= 0)
01929     {
01930       isHole = !isHole;
01931       if (! outRec->FirstLeft)
01932         outRec->FirstLeft = m_PolyOuts[e2->outIdx];
01933     }
01934     e2 = e2->prevInAEL;
01935   }
01936   if (isHole) outRec->isHole = true;
01937 }
01938 //------------------------------------------------------------------------------
01939 
01940 OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2)
01941 {
01942   //work out which polygon fragment has the correct hole state ...
01943   OutPt *outPt1 = outRec1->bottomPt;
01944   OutPt *outPt2 = outRec2->bottomPt;
01945   if (outPt1->pt.Y > outPt2->pt.Y) return outRec1;
01946   else if (outPt1->pt.Y < outPt2->pt.Y) return outRec2;
01947   else if (outPt1->pt.X < outPt2->pt.X) return outRec1;
01948   else if (outPt1->pt.X > outPt2->pt.X) return outRec2;
01949   else if (outPt1->next == outPt1) return outRec2;
01950   else if (outPt2->next == outPt2) return outRec1;
01951   else if (FirstIsBottomPt(outPt1, outPt2)) return outRec1;
01952   else return outRec2;
01953 }
01954 //------------------------------------------------------------------------------
01955 
01956 bool Param1RightOfParam2(OutRec* outRec1, OutRec* outRec2)
01957 {
01958   do
01959   {
01960     outRec1 = outRec1->FirstLeft;
01961     if (outRec1 == outRec2) return true;
01962   } while (outRec1);
01963   return false;
01964 }
01965 //------------------------------------------------------------------------------
01966 
01967 void Clipper::AppendPolygon(TEdge *e1, TEdge *e2)
01968 {
01969   //get the start and ends of both output polygons ...
01970   OutRec *outRec1 = m_PolyOuts[e1->outIdx];
01971   OutRec *outRec2 = m_PolyOuts[e2->outIdx];
01972 
01973   OutRec *holeStateRec;
01974   if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
01975   else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
01976   else holeStateRec = GetLowermostRec(outRec1, outRec2);
01977 
01978   OutPt* p1_lft = outRec1->pts;
01979   OutPt* p1_rt = p1_lft->prev;
01980   OutPt* p2_lft = outRec2->pts;
01981   OutPt* p2_rt = p2_lft->prev;
01982 
01983   EdgeSide side;
01984   //join e2 poly onto e1 poly and delete pointers to e2 ...
01985   if(  e1->side == esLeft )
01986   {
01987     if(  e2->side == esLeft )
01988     {
01989       //z y x a b c
01990       ReversePolyPtLinks(*p2_lft);
01991       p2_lft->next = p1_lft;
01992       p1_lft->prev = p2_lft;
01993       p1_rt->next = p2_rt;
01994       p2_rt->prev = p1_rt;
01995       outRec1->pts = p2_rt;
01996     } else
01997     {
01998       //x y z a b c
01999       p2_rt->next = p1_lft;
02000       p1_lft->prev = p2_rt;
02001       p2_lft->prev = p1_rt;
02002       p1_rt->next = p2_lft;
02003       outRec1->pts = p2_lft;
02004     }
02005     side = esLeft;
02006   } else
02007   {
02008     if(  e2->side == esRight )
02009     {
02010       //a b c z y x
02011       ReversePolyPtLinks( *p2_lft );
02012       p1_rt->next = p2_rt;
02013       p2_rt->prev = p1_rt;
02014       p2_lft->next = p1_lft;
02015       p1_lft->prev = p2_lft;
02016     } else
02017     {
02018       //a b c x y z
02019       p1_rt->next = p2_lft;
02020       p2_lft->prev = p1_rt;
02021       p1_lft->prev = p2_rt;
02022       p2_rt->next = p1_lft;
02023     }
02024     side = esRight;
02025   }
02026 
02027   if (holeStateRec == outRec2)
02028   {
02029     outRec1->bottomPt = outRec2->bottomPt;
02030     outRec1->bottomPt->idx = outRec1->idx;
02031     if (outRec2->FirstLeft != outRec1)
02032       outRec1->FirstLeft = outRec2->FirstLeft;
02033     outRec1->isHole = outRec2->isHole;
02034   }
02035   outRec2->pts = 0;
02036   outRec2->bottomPt = 0;
02037   outRec2->AppendLink = outRec1;
02038   int OKIdx = e1->outIdx;
02039   int ObsoleteIdx = e2->outIdx;
02040 
02041   e1->outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly
02042   e2->outIdx = -1;
02043 
02044   TEdge* e = m_ActiveEdges;
02045   while( e )
02046   {
02047     if( e->outIdx == ObsoleteIdx )
02048     {
02049       e->outIdx = OKIdx;
02050       e->side = side;
02051       break;
02052     }
02053     e = e->nextInAEL;
02054   }
02055 
02056   for (JoinList::size_type i = 0; i < m_Joins.size(); ++i)
02057   {
02058       if (m_Joins[i]->poly1Idx == ObsoleteIdx) m_Joins[i]->poly1Idx = OKIdx;
02059       if (m_Joins[i]->poly2Idx == ObsoleteIdx) m_Joins[i]->poly2Idx = OKIdx;
02060   }
02061 
02062   for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
02063   {
02064       if (m_HorizJoins[i]->savedIdx == ObsoleteIdx)
02065         m_HorizJoins[i]->savedIdx = OKIdx;
02066   }
02067 
02068 }
02069 //------------------------------------------------------------------------------
02070 
02071 OutRec* Clipper::CreateOutRec()
02072 {
02073   OutRec* result = new OutRec;
02074   result->isHole = false;
02075   result->FirstLeft = 0;
02076   result->AppendLink = 0;
02077   result->pts = 0;
02078   result->bottomPt = 0;
02079   result->sides = esNeither;
02080   result->bottomFlag = 0;
02081 
02082   return result;
02083 }
02084 //------------------------------------------------------------------------------
02085 
02086 void Clipper::DisposeBottomPt(OutRec &outRec)
02087 {
02088   OutPt* next = outRec.bottomPt->next;
02089   OutPt* prev = outRec.bottomPt->prev;
02090   if (outRec.pts == outRec.bottomPt) outRec.pts = next;
02091   delete outRec.bottomPt;
02092   next->prev = prev;
02093   prev->next = next;
02094   outRec.bottomPt = next;
02095   FixupOutPolygon(outRec);
02096 }
02097 //------------------------------------------------------------------------------
02098 
02099 void Clipper::AddOutPt(TEdge *e, const IntPoint &pt)
02100 {
02101   bool ToFront = (e->side == esLeft);
02102   if(  e->outIdx < 0 )
02103   {
02104     OutRec *outRec = CreateOutRec();
02105     m_PolyOuts.push_back(outRec);
02106     outRec->idx = (int)m_PolyOuts.size()-1;
02107     e->outIdx = outRec->idx;
02108     OutPt* op = new OutPt;
02109     outRec->pts = op;
02110     outRec->bottomPt = op;
02111     op->pt = pt;
02112     op->idx = outRec->idx;
02113     op->next = op;
02114     op->prev = op;
02115     SetHoleState(e, outRec);
02116   } else
02117   {
02118     OutRec *outRec = m_PolyOuts[e->outIdx];
02119     OutPt* op = outRec->pts;
02120     if ((ToFront && PointsEqual(pt, op->pt)) ||
02121       (!ToFront && PointsEqual(pt, op->prev->pt))) return;
02122 
02123     if ((e->side | outRec->sides) != outRec->sides)
02124     {
02125       //check for 'rounding' artefacts ...
02126       if (outRec->sides == esNeither && pt.Y == op->pt.Y)
02127         if (ToFront)
02128         {
02129           if (pt.X == op->pt.X +1) return;    //ie wrong side of bottomPt
02130         }
02131         else if (pt.X == op->pt.X -1) return; //ie wrong side of bottomPt
02132 
02133       outRec->sides = (EdgeSide)(outRec->sides | e->side);
02134       if (outRec->sides == esBoth)
02135       {
02136         //A vertex from each side has now been added.
02137         //Vertices of one side of an output polygon are quite commonly close to
02138         //or even 'touching' edges of the other side of the output polygon.
02139         //Very occasionally vertices from one side can 'cross' an edge on the
02140         //the other side. The distance 'crossed' is always less that a unit
02141         //and is purely an artefact of coordinate rounding. Nevertheless, this
02142         //results in very tiny self-intersections. Because of the way
02143         //orientation is calculated, even tiny self-intersections can cause
02144         //the Orientation function to return the wrong result. Therefore, it's
02145         //important to ensure that any self-intersections close to BottomPt are
02146         //detected and removed before orientation is assigned.
02147 
02148         OutPt *opBot, *op2;
02149         if (ToFront)
02150         {
02151           opBot = outRec->pts;
02152           op2 = opBot->next; //op2 == right side
02153           if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y &&
02154             ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) <
02155             (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y)))
02156                outRec->bottomFlag = opBot;
02157         } else
02158         {
02159           opBot = outRec->pts->prev;
02160           op2 = opBot->prev; //op2 == left side
02161           if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y &&
02162             ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) >
02163             (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y)))
02164                outRec->bottomFlag = opBot;
02165         }
02166       }
02167     }
02168 
02169     OutPt* op2 = new OutPt;
02170     op2->pt = pt;
02171     op2->idx = outRec->idx;
02172     if (op2->pt.Y == outRec->bottomPt->pt.Y &&
02173       op2->pt.X < outRec->bottomPt->pt.X)
02174         outRec->bottomPt = op2;
02175     op2->next = op;
02176     op2->prev = op->prev;
02177     op2->prev->next = op2;
02178     op->prev = op2;
02179     if (ToFront) outRec->pts = op2;
02180   }
02181 }
02182 //------------------------------------------------------------------------------
02183 
02184 void Clipper::ProcessHorizontals()
02185 {
02186   TEdge* horzEdge = m_SortedEdges;
02187   while( horzEdge )
02188   {
02189     DeleteFromSEL( horzEdge );
02190     ProcessHorizontal( horzEdge );
02191     horzEdge = m_SortedEdges;
02192   }
02193 }
02194 //------------------------------------------------------------------------------
02195 
02196 bool Clipper::IsTopHorz(const long64 XPos)
02197 {
02198   TEdge* e = m_SortedEdges;
02199   while( e )
02200   {
02201     if(  ( XPos >= std::min(e->xcurr, e->xtop) ) &&
02202       ( XPos <= std::max(e->xcurr, e->xtop) ) ) return false;
02203     e = e->nextInSEL;
02204   }
02205   return true;
02206 }
02207 //------------------------------------------------------------------------------
02208 
02209 bool IsMinima(TEdge *e)
02210 {
02211   return e  && (e->prev->nextInLML != e) && (e->next->nextInLML != e);
02212 }
02213 //------------------------------------------------------------------------------
02214 
02215 bool IsMaxima(TEdge *e, const long64 Y)
02216 {
02217   return e && e->ytop == Y && !e->nextInLML;
02218 }
02219 //------------------------------------------------------------------------------
02220 
02221 bool IsIntermediate(TEdge *e, const long64 Y)
02222 {
02223   return e->ytop == Y && e->nextInLML;
02224 }
02225 //------------------------------------------------------------------------------
02226 
02227 TEdge *GetMaximaPair(TEdge *e)
02228 {
02229   if( !IsMaxima(e->next, e->ytop) || e->next->xtop != e->xtop )
02230     return e->prev; else
02231     return e->next;
02232 }
02233 //------------------------------------------------------------------------------
02234 
02235 void Clipper::SwapPositionsInAEL(TEdge *edge1, TEdge *edge2)
02236 {
02237   if(  !edge1->nextInAEL &&  !edge1->prevInAEL ) return;
02238   if(  !edge2->nextInAEL &&  !edge2->prevInAEL ) return;
02239 
02240   if(  edge1->nextInAEL == edge2 )
02241   {
02242     TEdge* next = edge2->nextInAEL;
02243     if( next ) next->prevInAEL = edge1;
02244     TEdge* prev = edge1->prevInAEL;
02245     if( prev ) prev->nextInAEL = edge2;
02246     edge2->prevInAEL = prev;
02247     edge2->nextInAEL = edge1;
02248     edge1->prevInAEL = edge2;
02249     edge1->nextInAEL = next;
02250   }
02251   else if(  edge2->nextInAEL == edge1 )
02252   {
02253     TEdge* next = edge1->nextInAEL;
02254     if( next ) next->prevInAEL = edge2;
02255     TEdge* prev = edge2->prevInAEL;
02256     if( prev ) prev->nextInAEL = edge1;
02257     edge1->prevInAEL = prev;
02258     edge1->nextInAEL = edge2;
02259     edge2->prevInAEL = edge1;
02260     edge2->nextInAEL = next;
02261   }
02262   else
02263   {
02264     TEdge* next = edge1->nextInAEL;
02265     TEdge* prev = edge1->prevInAEL;
02266     edge1->nextInAEL = edge2->nextInAEL;
02267     if( edge1->nextInAEL ) edge1->nextInAEL->prevInAEL = edge1;
02268     edge1->prevInAEL = edge2->prevInAEL;
02269     if( edge1->prevInAEL ) edge1->prevInAEL->nextInAEL = edge1;
02270     edge2->nextInAEL = next;
02271     if( edge2->nextInAEL ) edge2->nextInAEL->prevInAEL = edge2;
02272     edge2->prevInAEL = prev;
02273     if( edge2->prevInAEL ) edge2->prevInAEL->nextInAEL = edge2;
02274   }
02275 
02276   if( !edge1->prevInAEL ) m_ActiveEdges = edge1;
02277   else if( !edge2->prevInAEL ) m_ActiveEdges = edge2;
02278 }
02279 //------------------------------------------------------------------------------
02280 
02281 void Clipper::SwapPositionsInSEL(TEdge *edge1, TEdge *edge2)
02282 {
02283   if(  !( edge1->nextInSEL ) &&  !( edge1->prevInSEL ) ) return;
02284   if(  !( edge2->nextInSEL ) &&  !( edge2->prevInSEL ) ) return;
02285 
02286   if(  edge1->nextInSEL == edge2 )
02287   {
02288     TEdge* next = edge2->nextInSEL;
02289     if( next ) next->prevInSEL = edge1;
02290     TEdge* prev = edge1->prevInSEL;
02291     if( prev ) prev->nextInSEL = edge2;
02292     edge2->prevInSEL = prev;
02293     edge2->nextInSEL = edge1;
02294     edge1->prevInSEL = edge2;
02295     edge1->nextInSEL = next;
02296   }
02297   else if(  edge2->nextInSEL == edge1 )
02298   {
02299     TEdge* next = edge1->nextInSEL;
02300     if( next ) next->prevInSEL = edge2;
02301     TEdge* prev = edge2->prevInSEL;
02302     if( prev ) prev->nextInSEL = edge1;
02303     edge1->prevInSEL = prev;
02304     edge1->nextInSEL = edge2;
02305     edge2->prevInSEL = edge1;
02306     edge2->nextInSEL = next;
02307   }
02308   else
02309   {
02310     TEdge* next = edge1->nextInSEL;
02311     TEdge* prev = edge1->prevInSEL;
02312     edge1->nextInSEL = edge2->nextInSEL;
02313     if( edge1->nextInSEL ) edge1->nextInSEL->prevInSEL = edge1;
02314     edge1->prevInSEL = edge2->prevInSEL;
02315     if( edge1->prevInSEL ) edge1->prevInSEL->nextInSEL = edge1;
02316     edge2->nextInSEL = next;
02317     if( edge2->nextInSEL ) edge2->nextInSEL->prevInSEL = edge2;
02318     edge2->prevInSEL = prev;
02319     if( edge2->prevInSEL ) edge2->prevInSEL->nextInSEL = edge2;
02320   }
02321 
02322   if( !edge1->prevInSEL ) m_SortedEdges = edge1;
02323   else if( !edge2->prevInSEL ) m_SortedEdges = edge2;
02324 }
02325 //------------------------------------------------------------------------------
02326 
02327 TEdge* GetNextInAEL(TEdge *e, Direction dir)
02328 {
02329   return dir == dLeftToRight ? e->nextInAEL : e->prevInAEL;
02330 }
02331 //------------------------------------------------------------------------------
02332 
02333 void Clipper::ProcessHorizontal(TEdge *horzEdge)
02334 {
02335   Direction dir;
02336   long64 horzLeft, horzRight;
02337 
02338   if( horzEdge->xcurr < horzEdge->xtop )
02339   {
02340     horzLeft = horzEdge->xcurr;
02341     horzRight = horzEdge->xtop;
02342     dir = dLeftToRight;
02343   } else
02344   {
02345     horzLeft = horzEdge->xtop;
02346     horzRight = horzEdge->xcurr;
02347     dir = dRightToLeft;
02348   }
02349 
02350   TEdge* eMaxPair;
02351   if( horzEdge->nextInLML ) eMaxPair = 0;
02352   else eMaxPair = GetMaximaPair(horzEdge);
02353 
02354   TEdge* e = GetNextInAEL( horzEdge , dir );
02355   while( e )
02356   {
02357     TEdge* eNext = GetNextInAEL( e, dir );
02358 
02359     if (eMaxPair ||
02360       ((dir == dLeftToRight) && (e->xcurr <= horzRight)) ||
02361       ((dir == dRightToLeft) && (e->xcurr >= horzLeft)))
02362     {
02363       //ok, so far it looks like we're still in range of the horizontal edge
02364       if ( e->xcurr == horzEdge->xtop && !eMaxPair )
02365       {
02366         if (SlopesEqual(*e, *horzEdge->nextInLML, m_UseFullRange))
02367         {
02368           //if output polygons share an edge, they'll need joining later ...
02369           if (horzEdge->outIdx >= 0 && e->outIdx >= 0)
02370             AddJoin(horzEdge->nextInLML, e, horzEdge->outIdx);
02371           break; //we've reached the end of the horizontal line
02372         }
02373         else if (e->dx < horzEdge->nextInLML->dx)
02374         //we really have got to the end of the intermediate horz edge so quit.
02375         //nb: More -ve slopes follow more +ve slopes ABOVE the horizontal.
02376           break;
02377       }
02378 
02379       if( e == eMaxPair )
02380       {
02381         //horzEdge is evidently a maxima horizontal and we've arrived at its end.
02382         if (dir == dLeftToRight)
02383           IntersectEdges(horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
02384         else
02385           IntersectEdges(e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
02386         if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error");
02387         return;
02388       }
02389       else if( NEAR_EQUAL(e->dx, HORIZONTAL) &&  !IsMinima(e) && !(e->xcurr > e->xtop) )
02390       {
02391         //An overlapping horizontal edge. Overlapping horizontal edges are
02392         //processed as if layered with the current horizontal edge (horizEdge)
02393         //being infinitesimally lower that the next (e). Therfore, we
02394         //intersect with e only if e.xcurr is within the bounds of horzEdge ...
02395         if( dir == dLeftToRight )
02396           IntersectEdges( horzEdge , e, IntPoint(e->xcurr, horzEdge->ycurr),
02397             (IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
02398         else
02399           IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
02400             (IsTopHorz( e->xcurr ))? ipRight : ipBoth );
02401       }
02402       else if( dir == dLeftToRight )
02403       {
02404         IntersectEdges( horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr),
02405           (IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
02406       }
02407       else
02408       {
02409         IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
02410           (IsTopHorz( e->xcurr ))? ipRight : ipBoth );
02411       }
02412       SwapPositionsInAEL( horzEdge, e );
02413     }
02414     else if( (dir == dLeftToRight && e->xcurr > horzRight  && m_SortedEdges) ||
02415      (dir == dRightToLeft && e->xcurr < horzLeft && m_SortedEdges) ) break;
02416     e = eNext;
02417   } //end while
02418 
02419   if( horzEdge->nextInLML )
02420   {
02421     if( horzEdge->outIdx >= 0 )
02422       AddOutPt( horzEdge, IntPoint(horzEdge->xtop, horzEdge->ytop));
02423     UpdateEdgeIntoAEL( horzEdge );
02424   }
02425   else
02426   {
02427     if ( horzEdge->outIdx >= 0 )
02428       IntersectEdges( horzEdge, eMaxPair,
02429       IntPoint(horzEdge->xtop, horzEdge->ycurr), ipBoth);
02430     if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error");
02431     DeleteFromAEL(eMaxPair);
02432     DeleteFromAEL(horzEdge);
02433   }
02434 }
02435 //------------------------------------------------------------------------------
02436 
02437 void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
02438 {
02439   if( !e->nextInLML ) throw
02440     clipperException("UpdateEdgeIntoAEL: invalid call");
02441   TEdge* AelPrev = e->prevInAEL;
02442   TEdge* AelNext = e->nextInAEL;
02443   e->nextInLML->outIdx = e->outIdx;
02444   if( AelPrev ) AelPrev->nextInAEL = e->nextInLML;
02445   else m_ActiveEdges = e->nextInLML;
02446   if( AelNext ) AelNext->prevInAEL = e->nextInLML;
02447   e->nextInLML->side = e->side;
02448   e->nextInLML->windDelta = e->windDelta;
02449   e->nextInLML->windCnt = e->windCnt;
02450   e->nextInLML->windCnt2 = e->windCnt2;
02451   e = e->nextInLML;
02452   e->prevInAEL = AelPrev;
02453   e->nextInAEL = AelNext;
02454   if( !NEAR_EQUAL(e->dx, HORIZONTAL) ) InsertScanbeam( e->ytop );
02455 }
02456 //------------------------------------------------------------------------------
02457 
02458 bool Clipper::ProcessIntersections(const long64 botY, const long64 topY)
02459 {
02460   if( !m_ActiveEdges ) return true;
02461   try {
02462     BuildIntersectList(botY, topY);
02463     if ( !m_IntersectNodes) return true;
02464     if ( FixupIntersections() ) ProcessIntersectList();
02465     else return false;
02466   }
02467   catch(...) {
02468     m_SortedEdges = 0;
02469     DisposeIntersectNodes();
02470     throw clipperException("ProcessIntersections error");
02471   }
02472   return true;
02473 }
02474 //------------------------------------------------------------------------------
02475 
02476 void Clipper::DisposeIntersectNodes()
02477 {
02478   while ( m_IntersectNodes )
02479   {
02480     IntersectNode* iNode = m_IntersectNodes->next;
02481     delete m_IntersectNodes;
02482     m_IntersectNodes = iNode;
02483   }
02484 }
02485 //------------------------------------------------------------------------------
02486 
02487 void Clipper::BuildIntersectList(const long64 botY, const long64 topY)
02488 {
02489   if ( !m_ActiveEdges ) return;
02490 
02491   //prepare for sorting ...
02492   TEdge* e = m_ActiveEdges;
02493   e->tmpX = TopX( *e, topY );
02494   m_SortedEdges = e;
02495   m_SortedEdges->prevInSEL = 0;
02496   e = e->nextInAEL;
02497   while( e )
02498   {
02499     e->prevInSEL = e->prevInAEL;
02500     e->prevInSEL->nextInSEL = e;
02501     e->nextInSEL = 0;
02502     e->tmpX = TopX( *e, topY );
02503     e = e->nextInAEL;
02504   }
02505 
02506   //bubblesort ...
02507   bool isModified = true;
02508   while( isModified && m_SortedEdges )
02509   {
02510     isModified = false;
02511     e = m_SortedEdges;
02512     while( e->nextInSEL )
02513     {
02514       TEdge *eNext = e->nextInSEL;
02515       IntPoint pt;
02516       if(e->tmpX > eNext->tmpX &&
02517         IntersectPoint(*e, *eNext, pt, m_UseFullRange))
02518       {
02519         if (pt.Y > botY)
02520         {
02521             pt.Y = botY;
02522             pt.X = TopX(*e, pt.Y);
02523         }
02524         AddIntersectNode( e, eNext, pt );
02525         SwapPositionsInSEL(e, eNext);
02526         isModified = true;
02527       }
02528       else
02529         e = eNext;
02530     }
02531     if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0;
02532     else break;
02533   }
02534   m_SortedEdges = 0;
02535 }
02536 //------------------------------------------------------------------------------
02537 
02538 bool ProcessParam1BeforeParam2(IntersectNode &node1, IntersectNode &node2)
02539 {
02540   bool result;
02541   if (node1.pt.Y == node2.pt.Y)
02542   {
02543     if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1)
02544     {
02545       result = node2.pt.X > node1.pt.X;
02546       return node2.edge1->dx > 0 ? !result : result;
02547     }
02548     else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2)
02549     {
02550       result = node2.pt.X > node1.pt.X;
02551       return node2.edge2->dx > 0 ? !result : result;
02552     }
02553     else return node2.pt.X > node1.pt.X;
02554   }
02555   else return node1.pt.Y > node2.pt.Y;
02556 }
02557 //------------------------------------------------------------------------------
02558 
02559 void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt)
02560 {
02561   IntersectNode* newNode = new IntersectNode;
02562   newNode->edge1 = e1;
02563   newNode->edge2 = e2;
02564   newNode->pt = pt;
02565   newNode->next = 0;
02566   if( !m_IntersectNodes ) m_IntersectNodes = newNode;
02567   else if(  ProcessParam1BeforeParam2(*newNode, *m_IntersectNodes) )
02568   {
02569     newNode->next = m_IntersectNodes;
02570     m_IntersectNodes = newNode;
02571   }
02572   else
02573   {
02574     IntersectNode* iNode = m_IntersectNodes;
02575     while( iNode->next  && ProcessParam1BeforeParam2(*iNode->next, *newNode) )
02576         iNode = iNode->next;
02577     newNode->next = iNode->next;
02578     iNode->next = newNode;
02579   }
02580 }
02581 //------------------------------------------------------------------------------
02582 
02583 void Clipper::ProcessIntersectList()
02584 {
02585   while( m_IntersectNodes )
02586   {
02587     IntersectNode* iNode = m_IntersectNodes->next;
02588     {
02589       IntersectEdges( m_IntersectNodes->edge1 ,
02590         m_IntersectNodes->edge2 , m_IntersectNodes->pt, ipBoth );
02591       SwapPositionsInAEL( m_IntersectNodes->edge1 , m_IntersectNodes->edge2 );
02592     }
02593     delete m_IntersectNodes;
02594     m_IntersectNodes = iNode;
02595   }
02596 }
02597 //------------------------------------------------------------------------------
02598 
02599 void Clipper::DoMaxima(TEdge *e, long64 topY)
02600 {
02601   TEdge* eMaxPair = GetMaximaPair(e);
02602   long64 X = e->xtop;
02603   TEdge* eNext = e->nextInAEL;
02604   while( eNext != eMaxPair )
02605   {
02606     if (!eNext) throw clipperException("DoMaxima error");
02607     IntersectEdges( e, eNext, IntPoint(X, topY), ipBoth );
02608     eNext = eNext->nextInAEL;
02609   }
02610   if( e->outIdx < 0 && eMaxPair->outIdx < 0 )
02611   {
02612     DeleteFromAEL( e );
02613     DeleteFromAEL( eMaxPair );
02614   }
02615   else if( e->outIdx >= 0 && eMaxPair->outIdx >= 0 )
02616   {
02617     IntersectEdges( e, eMaxPair, IntPoint(X, topY), ipNone );
02618   }
02619   else throw clipperException("DoMaxima error");
02620 }
02621 //------------------------------------------------------------------------------
02622 
02623 void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY)
02624 {
02625   TEdge* e = m_ActiveEdges;
02626   while( e )
02627   {
02628     //1. process maxima, treating them as if they're 'bent' horizontal edges,
02629     //   but exclude maxima with horizontal edges. nb: e can't be a horizontal.
02630     if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, HORIZONTAL) )
02631     {
02632       //'e' might be removed from AEL, as may any following edges so ...
02633       TEdge* ePrior = e->prevInAEL;
02634       DoMaxima(e, topY);
02635       if( !ePrior ) e = m_ActiveEdges;
02636       else e = ePrior->nextInAEL;
02637     }
02638     else
02639     {
02640       //2. promote horizontal edges, otherwise update xcurr and ycurr ...
02641       if(  IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, HORIZONTAL) )
02642       {
02643         if (e->outIdx >= 0)
02644         {
02645           AddOutPt(e, IntPoint(e->xtop, e->ytop));
02646 
02647           for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
02648           {
02649             IntPoint pt, pt2;
02650             HorzJoinRec* hj = m_HorizJoins[i];
02651             if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot),
02652               IntPoint(hj->edge->xtop, hj->edge->ytop),
02653               IntPoint(e->nextInLML->xbot, e->nextInLML->ybot),
02654               IntPoint(e->nextInLML->xtop, e->nextInLML->ytop), pt, pt2))
02655                 AddJoin(hj->edge, e->nextInLML, hj->savedIdx, e->outIdx);
02656           }
02657 
02658           AddHorzJoin(e->nextInLML, e->outIdx);
02659         }
02660         UpdateEdgeIntoAEL(e);
02661         AddEdgeToSEL(e);
02662       } else
02663       {
02664         //this just simplifies horizontal processing ...
02665         e->xcurr = TopX( *e, topY );
02666         e->ycurr = topY;
02667       }
02668       e = e->nextInAEL;
02669     }
02670   }
02671 
02672   //3. Process horizontals at the top of the scanbeam ...
02673   ProcessHorizontals();
02674 
02675   //4. Promote intermediate vertices ...
02676   e = m_ActiveEdges;
02677   while( e )
02678   {
02679     if( IsIntermediate( e, topY ) )
02680     {
02681       if( e->outIdx >= 0 ) AddOutPt(e, IntPoint(e->xtop,e->ytop));
02682       UpdateEdgeIntoAEL(e);
02683 
02684       //if output polygons share an edge, they'll need joining later ...
02685       if (e->outIdx >= 0 && e->prevInAEL && e->prevInAEL->outIdx >= 0 &&
02686         e->prevInAEL->xcurr == e->xbot && e->prevInAEL->ycurr == e->ybot &&
02687         SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop),
02688           IntPoint(e->xbot,e->ybot),
02689           IntPoint(e->prevInAEL->xtop, e->prevInAEL->ytop), m_UseFullRange))
02690       {
02691         AddOutPt(e->prevInAEL, IntPoint(e->xbot, e->ybot));
02692         AddJoin(e, e->prevInAEL);
02693       }
02694       else if (e->outIdx >= 0 && e->nextInAEL && e->nextInAEL->outIdx >= 0 &&
02695         e->nextInAEL->ycurr > e->nextInAEL->ytop &&
02696         e->nextInAEL->ycurr <= e->nextInAEL->ybot &&
02697         e->nextInAEL->xcurr == e->xbot && e->nextInAEL->ycurr == e->ybot &&
02698         SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop),
02699           IntPoint(e->xbot,e->ybot),
02700           IntPoint(e->nextInAEL->xtop, e->nextInAEL->ytop), m_UseFullRange))
02701       {
02702         AddOutPt(e->nextInAEL, IntPoint(e->xbot, e->ybot));
02703         AddJoin(e, e->nextInAEL);
02704       }
02705     }
02706     e = e->nextInAEL;
02707   }
02708 }
02709 //------------------------------------------------------------------------------
02710 
02711 void Clipper::FixupOutPolygon(OutRec &outRec)
02712 {
02713   //FixupOutPolygon() - removes duplicate points and simplifies consecutive
02714   //parallel edges by removing the middle vertex.
02715   OutPt *lastOK = 0;
02716   outRec.pts = outRec.bottomPt;
02717   OutPt *pp = outRec.bottomPt;
02718 
02719   for (;;)
02720   {
02721     if (pp->prev == pp || pp->prev == pp->next )
02722     {
02723       DisposeOutPts(pp);
02724       outRec.pts = 0;
02725       outRec.bottomPt = 0;
02726       return;
02727     }
02728     //test for duplicate points and for same slope (cross-product) ...
02729     if ( PointsEqual(pp->pt, pp->next->pt) ||
02730       SlopesEqual(pp->prev->pt, pp->pt, pp->next->pt, m_UseFullRange) )
02731     {
02732       lastOK = 0;
02733       OutPt *tmp = pp;
02734       if (pp == outRec.bottomPt)
02735         outRec.bottomPt = 0; //flags need for updating
02736       pp->prev->next = pp->next;
02737       pp->next->prev = pp->prev;
02738       pp = pp->prev;
02739       delete tmp;
02740     }
02741     else if (pp == lastOK) break;
02742     else
02743     {
02744       if (!lastOK) lastOK = pp;
02745       pp = pp->next;
02746     }
02747   }
02748   if (!outRec.bottomPt) {
02749     outRec.bottomPt = GetBottomPt(pp);
02750     outRec.bottomPt->idx = outRec.idx;
02751     outRec.pts = outRec.bottomPt;
02752   }
02753 }
02754 //------------------------------------------------------------------------------
02755 
02756 void Clipper::BuildResult(Polygons &polys)
02757 {
02758   int k = 0;
02759   polys.resize(m_PolyOuts.size());
02760   for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
02761   {
02762     if (m_PolyOuts[i]->pts)
02763     {
02764       Polygon* pg = &polys[k];
02765       pg->clear();
02766       OutPt* p = m_PolyOuts[i]->pts;
02767       do
02768       {
02769         pg->push_back(p->pt);
02770         p = p->next;
02771       } while (p != m_PolyOuts[i]->pts);
02772       //make sure each polygon has at least 3 vertices ...
02773       if (pg->size() < 3) pg->clear(); else k++;
02774     }
02775   }
02776   polys.resize(k);
02777 }
02778 //------------------------------------------------------------------------------
02779 
02780 void Clipper::BuildResultEx(ExPolygons &polys)
02781 {
02782   PolyOutList::size_type i = 0;
02783   int k = 0;
02784   polys.resize(0);
02785   polys.reserve(m_PolyOuts.size());
02786   while (i < m_PolyOuts.size() && m_PolyOuts[i]->pts)
02787   {
02788     ExPolygon epg;
02789     OutPt* p = m_PolyOuts[i]->pts;
02790     do {
02791       epg.outer.push_back(p->pt);
02792       p = p->next;
02793     } while (p != m_PolyOuts[i]->pts);
02794     i++;
02795     //make sure polygons have at least 3 vertices ...
02796     if (epg.outer.size() < 3) continue;
02797     while (i < m_PolyOuts.size()
02798       && m_PolyOuts[i]->pts && m_PolyOuts[i]->isHole)
02799     {
02800       Polygon pg;
02801       p = m_PolyOuts[i]->pts;
02802       do {
02803         pg.push_back(p->pt);
02804         p = p->next;
02805       } while (p != m_PolyOuts[i]->pts);
02806       epg.holes.push_back(pg);
02807       i++;
02808     }
02809     polys.push_back(epg);
02810     k++;
02811   }
02812   polys.resize(k);
02813 }
02814 //------------------------------------------------------------------------------
02815 
02816 void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)
02817 {
02818   TEdge *e1 = int1.edge1;
02819   TEdge *e2 = int1.edge2;
02820   IntPoint p = int1.pt;
02821 
02822   int1.edge1 = int2.edge1;
02823   int1.edge2 = int2.edge2;
02824   int1.pt = int2.pt;
02825 
02826   int2.edge1 = e1;
02827   int2.edge2 = e2;
02828   int2.pt = p;
02829 }
02830 //------------------------------------------------------------------------------
02831 
02832 bool Clipper::FixupIntersections()
02833 {
02834   if ( !m_IntersectNodes->next ) return true;
02835 
02836   CopyAELToSEL();
02837   IntersectNode *int1 = m_IntersectNodes;
02838   IntersectNode *int2 = m_IntersectNodes->next;
02839   while (int2)
02840   {
02841     TEdge *e1 = int1->edge1;
02842     TEdge *e2;
02843     if (e1->prevInSEL == int1->edge2) e2 = e1->prevInSEL;
02844     else if (e1->nextInSEL == int1->edge2) e2 = e1->nextInSEL;
02845     else
02846     {
02847       //The current intersection is out of order, so try and swap it with
02848       //a subsequent intersection ...
02849       while (int2)
02850       {
02851         if (int2->edge1->nextInSEL == int2->edge2 ||
02852           int2->edge1->prevInSEL == int2->edge2) break;
02853         else int2 = int2->next;
02854       }
02855       if ( !int2 ) return false; //oops!!!
02856 
02857       //found an intersect node that can be swapped ...
02858       SwapIntersectNodes(*int1, *int2);
02859       e1 = int1->edge1;
02860       e2 = int1->edge2;
02861     }
02862     SwapPositionsInSEL(e1, e2);
02863     int1 = int1->next;
02864     int2 = int1->next;
02865   }
02866 
02867   m_SortedEdges = 0;
02868 
02869   //finally, check the last intersection too ...
02870   return (int1->edge1->prevInSEL == int1->edge2 ||
02871     int1->edge1->nextInSEL == int1->edge2);
02872 }
02873 //------------------------------------------------------------------------------
02874 
02875 bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
02876 {
02877   return e2.xcurr == e1.xcurr ? e2.dx > e1.dx : e2.xcurr < e1.xcurr;
02878 }
02879 //------------------------------------------------------------------------------
02880 
02881 void Clipper::InsertEdgeIntoAEL(TEdge *edge)
02882 {
02883   edge->prevInAEL = 0;
02884   edge->nextInAEL = 0;
02885   if( !m_ActiveEdges )
02886   {
02887     m_ActiveEdges = edge;
02888   }
02889   else if( E2InsertsBeforeE1(*m_ActiveEdges, *edge) )
02890   {
02891     edge->nextInAEL = m_ActiveEdges;
02892     m_ActiveEdges->prevInAEL = edge;
02893     m_ActiveEdges = edge;
02894   } else
02895   {
02896     TEdge* e = m_ActiveEdges;
02897     while( e->nextInAEL  && !E2InsertsBeforeE1(*e->nextInAEL , *edge) )
02898       e = e->nextInAEL;
02899     edge->nextInAEL = e->nextInAEL;
02900     if( e->nextInAEL ) e->nextInAEL->prevInAEL = edge;
02901     edge->prevInAEL = e;
02902     e->nextInAEL = edge;
02903   }
02904 }
02905 //----------------------------------------------------------------------
02906 
02907 void Clipper::DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
02908 {
02909   AddOutPt(edge1, pt);
02910   SwapSides(*edge1, *edge2);
02911   SwapPolyIndexes(*edge1, *edge2);
02912 }
02913 //----------------------------------------------------------------------
02914 
02915 void Clipper::DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
02916 {
02917   AddOutPt(edge2, pt);
02918   SwapSides(*edge1, *edge2);
02919   SwapPolyIndexes(*edge1, *edge2);
02920 }
02921 //----------------------------------------------------------------------
02922 
02923 void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
02924 {
02925   AddOutPt(edge1, pt);
02926   AddOutPt(edge2, pt);
02927   SwapSides( *edge1 , *edge2 );
02928   SwapPolyIndexes( *edge1 , *edge2 );
02929 }
02930 //----------------------------------------------------------------------
02931 
02932 void Clipper::CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2)
02933 {
02934   //when a polygon is split into 2 polygons, make sure any holes the original
02935   //polygon contained link to the correct polygon ...
02936   for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
02937   {
02938     OutRec *orec = m_PolyOuts[i];
02939     if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec1 &&
02940       !PointInPolygon(orec->bottomPt->pt, outRec1->pts, m_UseFullRange))
02941         orec->FirstLeft = outRec2;
02942   }
02943 }
02944 //----------------------------------------------------------------------
02945 
02946 void Clipper::CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2)
02947 {
02948   //if a hole is owned by outRec2 then make it owned by outRec1 ...
02949   for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
02950     if (m_PolyOuts[i]->isHole && m_PolyOuts[i]->bottomPt &&
02951       m_PolyOuts[i]->FirstLeft == outRec2)
02952         m_PolyOuts[i]->FirstLeft = outRec1;
02953 }
02954 //----------------------------------------------------------------------
02955 
02956 void Clipper::JoinCommonEdges(bool fixHoleLinkages)
02957 {
02958   for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
02959   {
02960     JoinRec* j = m_Joins[i];
02961     OutRec *outRec1 = m_PolyOuts[j->poly1Idx];
02962     OutPt *pp1a = outRec1->pts;
02963     OutRec *outRec2 = m_PolyOuts[j->poly2Idx];
02964     OutPt *pp2a = outRec2->pts;
02965     IntPoint pt1 = j->pt2a, pt2 = j->pt2b;
02966     IntPoint pt3 = j->pt1a, pt4 = j->pt1b;
02967     if (!FindSegment(pp1a, pt1, pt2)) continue;
02968     if (j->poly1Idx == j->poly2Idx)
02969     {
02970       //we're searching the same polygon for overlapping segments so
02971       //segment 2 mustn't be the same as segment 1 ...
02972       pp2a = pp1a->next;
02973       if (!FindSegment(pp2a, pt3, pt4) || (pp2a == pp1a)) continue;
02974     }
02975     else if (!FindSegment(pp2a, pt3, pt4)) continue;
02976 
02977     if (!GetOverlapSegment(pt1, pt2, pt3, pt4, pt1, pt2)) continue;
02978 
02979     OutPt *p1, *p2, *p3, *p4;
02980     OutPt *prev = pp1a->prev;
02981     //get p1 & p2 polypts - the overlap start & endpoints on poly1
02982     if (PointsEqual(pp1a->pt, pt1)) p1 = pp1a;
02983     else if (PointsEqual(prev->pt, pt1)) p1 = prev;
02984     else p1 = InsertPolyPtBetween(pp1a, prev, pt1);
02985 
02986     if (PointsEqual(pp1a->pt, pt2)) p2 = pp1a;
02987     else if (PointsEqual(prev->pt, pt2)) p2 = prev;
02988     else if ((p1 == pp1a) || (p1 == prev))
02989       p2 = InsertPolyPtBetween(pp1a, prev, pt2);
02990     else if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2))
02991       p2 = InsertPolyPtBetween(pp1a, p1, pt2); else
02992       p2 = InsertPolyPtBetween(p1, prev, pt2);
02993 
02994     //get p3 & p4 polypts - the overlap start & endpoints on poly2
02995     prev = pp2a->prev;
02996     if (PointsEqual(pp2a->pt, pt1)) p3 = pp2a;
02997     else if (PointsEqual(prev->pt, pt1)) p3 = prev;
02998     else p3 = InsertPolyPtBetween(pp2a, prev, pt1);
02999 
03000     if (PointsEqual(pp2a->pt, pt2)) p4 = pp2a;
03001     else if (PointsEqual(prev->pt, pt2)) p4 = prev;
03002     else if ((p3 == pp2a) || (p3 == prev))
03003       p4 = InsertPolyPtBetween(pp2a, prev, pt2);
03004     else if (Pt3IsBetweenPt1AndPt2(pp2a->pt, p3->pt, pt2))
03005       p4 = InsertPolyPtBetween(pp2a, p3, pt2); else
03006       p4 = InsertPolyPtBetween(p3, prev, pt2);
03007 
03008     //p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ...
03009     if (p1->next == p2 && p3->prev == p4)
03010     {
03011       p1->next = p3;
03012       p3->prev = p1;
03013       p2->prev = p4;
03014       p4->next = p2;
03015     }
03016     else if (p1->prev == p2 && p3->next == p4)
03017     {
03018       p1->prev = p3;
03019       p3->next = p1;
03020       p2->next = p4;
03021       p4->prev = p2;
03022     }
03023     else
03024       continue; //an orientation is probably wrong
03025 
03026     if (j->poly2Idx == j->poly1Idx)
03027     {
03028       //instead of joining two polygons, we've just created a new one by
03029       //splitting one polygon into two.
03030       outRec1->pts = GetBottomPt(p1);
03031       outRec1->bottomPt = outRec1->pts;
03032       outRec1->bottomPt->idx = outRec1->idx;
03033       outRec2 = CreateOutRec();
03034       m_PolyOuts.push_back(outRec2);
03035       outRec2->idx = (int)m_PolyOuts.size()-1;
03036       j->poly2Idx = outRec2->idx;
03037       outRec2->pts = GetBottomPt(p2);
03038       outRec2->bottomPt = outRec2->pts;
03039       outRec2->bottomPt->idx = outRec2->idx;
03040 
03041       if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange))
03042       {
03043         //outRec2 is contained by outRec1 ...
03044         outRec2->isHole = !outRec1->isHole;
03045         outRec2->FirstLeft = outRec1;
03046         if (outRec2->isHole ==
03047           (m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange)))
03048             ReversePolyPtLinks(*outRec2->pts);
03049       } else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRange))
03050       {
03051         //outRec1 is contained by outRec2 ...
03052         outRec2->isHole = outRec1->isHole;
03053         outRec1->isHole = !outRec2->isHole;
03054         outRec2->FirstLeft = outRec1->FirstLeft;
03055         outRec1->FirstLeft = outRec2;
03056         if (outRec1->isHole ==
03057           (m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange)))
03058             ReversePolyPtLinks(*outRec1->pts);
03059         //make sure any contained holes now link to the correct polygon ...
03060         if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2);
03061       } else
03062       {
03063         outRec2->isHole = outRec1->isHole;
03064         outRec2->FirstLeft = outRec1->FirstLeft;
03065         //make sure any contained holes now link to the correct polygon ...
03066         if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2);
03067       }
03068 
03069       //now fixup any subsequent joins that match this polygon
03070       for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
03071       {
03072         JoinRec* j2 = m_Joins[k];
03073         if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2))
03074           j2->poly1Idx = j->poly2Idx;
03075         if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2))
03076           j2->poly2Idx = j->poly2Idx;
03077       }
03078 
03079       //now cleanup redundant edges too ...
03080       FixupOutPolygon(*outRec1);
03081       FixupOutPolygon(*outRec2);
03082 
03083       if (Orientation(outRec1, m_UseFullRange) != (Area(*outRec1, m_UseFullRange) > 0))
03084           DisposeBottomPt(*outRec1);
03085       if (Orientation(outRec2, m_UseFullRange) != (Area(*outRec2, m_UseFullRange) > 0))
03086           DisposeBottomPt(*outRec2);
03087 
03088     } else
03089     {
03090       //joined 2 polygons together ...
03091 
03092       //make sure any holes contained by outRec2 now link to outRec1 ...
03093       if (fixHoleLinkages) CheckHoleLinkages2(outRec1, outRec2);
03094 
03095       //now cleanup redundant edges too ...
03096       FixupOutPolygon(*outRec1);
03097 
03098       if (outRec1->pts)
03099       {
03100         outRec1->isHole = !Orientation(outRec1, m_UseFullRange);
03101         if (outRec1->isHole && !outRec1->FirstLeft)
03102           outRec1->FirstLeft = outRec2->FirstLeft;
03103       }
03104 
03105       //delete the obsolete pointer ...
03106       int OKIdx = outRec1->idx;
03107       int ObsoleteIdx = outRec2->idx;
03108       outRec2->pts = 0;
03109       outRec2->bottomPt = 0;
03110       outRec2->AppendLink = outRec1;
03111 
03112       //now fixup any subsequent Joins that match this polygon
03113       for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
03114       {
03115         JoinRec* j2 = m_Joins[k];
03116         if (j2->poly1Idx == ObsoleteIdx) j2->poly1Idx = OKIdx;
03117         if (j2->poly2Idx == ObsoleteIdx) j2->poly2Idx = OKIdx;
03118       }
03119     }
03120   }
03121 }
03122 //------------------------------------------------------------------------------
03123 
03124 void ReversePolygon(Polygon& p)
03125 {
03126   std::reverse(p.begin(), p.end());
03127 }
03128 //------------------------------------------------------------------------------
03129 
03130 void ReversePolygons(Polygons& p)
03131 {
03132   for (Polygons::size_type i = 0; i < p.size(); ++i)
03133     ReversePolygon(p[i]);
03134 }
03135 
03136 //------------------------------------------------------------------------------
03137 // OffsetPolygon functions ...
03138 //------------------------------------------------------------------------------
03139 
03140 struct DoublePoint
03141 {
03142   double X;
03143   double Y;
03144   DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
03145 };
03146 //------------------------------------------------------------------------------
03147 
03148 Polygon BuildArc(const IntPoint &pt,
03149   const double a1, const double a2, const double r)
03150 {
03151   long64 steps = std::max(6, int(std::sqrt(std::fabs(r)) * std::fabs(a2 - a1)));
03152   if (steps > 0x100000) steps = 0x100000;
03153   int n = (unsigned)steps;
03154   Polygon result(n);
03155   double da = (a2 - a1) / (n -1);
03156   double a = a1;
03157   for (int i = 0; i < n; ++i)
03158   {
03159     result[i].X = pt.X + Round(std::cos(a)*r);
03160     result[i].Y = pt.Y + Round(std::sin(a)*r);
03161     a += da;
03162   }
03163   return result;
03164 }
03165 //------------------------------------------------------------------------------
03166 
03167 DoublePoint GetUnitNormal( const IntPoint &pt1, const IntPoint &pt2)
03168 {
03169   if(pt2.X == pt1.X && pt2.Y == pt1.Y) 
03170     return DoublePoint(0, 0);
03171 
03172   double dx = (double)(pt2.X - pt1.X);
03173   double dy = (double)(pt2.Y - pt1.Y);
03174   double f = 1 *1.0/ std::sqrt( dx*dx + dy*dy );
03175   dx *= f;
03176   dy *= f;
03177   return DoublePoint(dy, -dx);
03178 }
03179 
03180 //------------------------------------------------------------------------------
03181 //------------------------------------------------------------------------------
03182 
03183 class PolyOffsetBuilder
03184 {
03185 private:
03186   Polygons m_p;
03187   Polygon* m_curr_poly;
03188   std::vector<DoublePoint> normals;
03189   double m_delta, m_RMin, m_R;
03190   size_t m_i, m_j, m_k;
03191   static const int buffLength = 128;
03192   JoinType m_jointype;
03193  
03194 public:
03195 
03196 PolyOffsetBuilder(const Polygons& in_polys, Polygons& out_polys,
03197   double delta, JoinType jointype, double MiterLimit)
03198 {
03199     //nb precondition - out_polys != ptsin_polys
03200     if (NEAR_ZERO(delta))
03201     {
03202         out_polys = in_polys;
03203         return;
03204     }
03205 
03206     this->m_p = in_polys;
03207     this->m_delta = delta;
03208     this->m_jointype = jointype;
03209     if (MiterLimit <= 1) MiterLimit = 1;
03210     m_RMin = 2/(MiterLimit*MiterLimit);
03211  
03212     double deltaSq = delta*delta;
03213     out_polys.clear();
03214     out_polys.resize(in_polys.size());
03215     for (m_i = 0; m_i < in_polys.size(); m_i++)
03216     {
03217         m_curr_poly = &out_polys[m_i];
03218         size_t len = in_polys[m_i].size();
03219         if (len > 1 && m_p[m_i][0].X == m_p[m_i][len - 1].X &&
03220             m_p[m_i][0].Y == m_p[m_i][len-1].Y) len--;
03221 
03222         //when 'shrinking' polygons - to minimize artefacts
03223         //strip those polygons that have an area < pi * delta^2 ...
03224         double a1 = Area(in_polys[m_i]);
03225         if (delta < 0) { if (a1 > 0 && a1 < deltaSq *pi) len = 0; }
03226         else if (a1 < 0 && -a1 < deltaSq *pi) len = 0; //holes have neg. area
03227 
03228         if (len == 0 || (len < 3 && delta <= 0))
03229           continue;
03230         else if (len == 1)
03231         {
03232             Polygon arc;
03233             arc = BuildArc(in_polys[m_i][len-1], 0, 2 * pi, delta);
03234             out_polys[m_i] = arc;
03235             continue;
03236         }
03237 
03238         //build normals ...
03239         normals.clear();
03240         normals.resize(len);
03241         normals[len-1] = GetUnitNormal(in_polys[m_i][len-1], in_polys[m_i][0]);
03242         for (m_j = 0; m_j < len -1; ++m_j)
03243             normals[m_j] = GetUnitNormal(in_polys[m_i][m_j], in_polys[m_i][m_j+1]);
03244         
03245         m_k = len -1;
03246         for (m_j = 0; m_j < len; ++m_j)
03247         {
03248           switch (jointype)
03249           {
03250             case jtMiter:
03251             {
03252               m_R = 1 + (normals[m_j].X*normals[m_k].X + 
03253                 normals[m_j].Y*normals[m_k].Y);
03254               if (m_R >= m_RMin) DoMiter(); else DoSquare(MiterLimit);
03255               break;
03256             }
03257             case jtSquare: DoSquare(); break;
03258             case jtRound: DoRound(); break;
03259           }
03260         m_k = m_j;
03261         }
03262     }
03263 
03264     //finally, clean up untidy corners using Clipper ...
03265     Clipper clpr;
03266     clpr.AddPolygons(out_polys, ptSubject);
03267     if (delta > 0)
03268     {
03269         if (!clpr.Execute(ctUnion, out_polys, pftPositive, pftPositive))
03270             out_polys.clear();
03271     }
03272     else
03273     {
03274         IntRect r = clpr.GetBounds();
03275         Polygon outer(4);
03276         outer[0] = IntPoint(r.left - 10, r.bottom + 10);
03277         outer[1] = IntPoint(r.right + 10, r.bottom + 10);
03278         outer[2] = IntPoint(r.right + 10, r.top - 10);
03279         outer[3] = IntPoint(r.left - 10, r.top - 10);
03280 
03281         clpr.AddPolygon(outer, ptSubject);
03282         if (clpr.Execute(ctUnion, out_polys, pftNegative, pftNegative))
03283         {
03284             out_polys.erase(out_polys.begin());
03285             ReversePolygons(out_polys);
03286 
03287         } else
03288             out_polys.clear();
03289     }
03290 }
03291 //------------------------------------------------------------------------------
03292 
03293 private:
03294 
03295 void AddPoint(const IntPoint& pt)
03296 {
03297     Polygon::size_type len = m_curr_poly->size();
03298     if (len == m_curr_poly->capacity())
03299         m_curr_poly->reserve(len + buffLength);
03300     m_curr_poly->push_back(pt);
03301 }
03302 //------------------------------------------------------------------------------
03303 
03304 void DoSquare(double mul = 1.0)
03305 {
03306     IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
03307         (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
03308     IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
03309         (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
03310     if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
03311     {
03312       double a1 = std::atan2(normals[m_k].Y, normals[m_k].X);
03313       double a2 = std::atan2(-normals[m_j].Y, -normals[m_j].X);
03314       a1 = std::fabs(a2 - a1);
03315       if (a1 > pi) a1 = pi * 2 - a1;
03316       double dx = std::tan((pi - a1)/4) * std::fabs(m_delta * mul);
03317       pt1 = IntPoint((long64)(pt1.X -normals[m_k].Y * dx),
03318         (long64)(pt1.Y + normals[m_k].X * dx));
03319       AddPoint(pt1);
03320       pt2 = IntPoint((long64)(pt2.X + normals[m_j].Y * dx),
03321         (long64)(pt2.Y -normals[m_j].X * dx));
03322       AddPoint(pt2);
03323     }
03324     else
03325     {
03326       AddPoint(pt1);
03327       AddPoint(m_p[m_i][m_j]);
03328       AddPoint(pt2);
03329     }
03330 }
03331 //------------------------------------------------------------------------------
03332 
03333 void DoMiter()
03334 {
03335     if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
03336     {
03337         double q = m_delta / m_R;
03338         AddPoint(IntPoint((long64)Round(m_p[m_i][m_j].X + 
03339             (normals[m_k].X + normals[m_j].X) * q),
03340             (long64)Round(m_p[m_i][m_j].Y + (normals[m_k].Y + normals[m_j].Y) * q)));
03341     }
03342     else
03343     {
03344         IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X *
03345           m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
03346         IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X *
03347           m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
03348         AddPoint(pt1);
03349         AddPoint(m_p[m_i][m_j]);
03350         AddPoint(pt2);
03351     }
03352 }
03353 //------------------------------------------------------------------------------
03354 
03355 void DoRound()
03356 {
03357     IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
03358         (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
03359     IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
03360         (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
03361     AddPoint(pt1);
03362     //round off reflex angles (ie > 180 deg) unless almost flat (ie < ~10deg).
03363     if ((normals[m_k].X*normals[m_j].Y - normals[m_j].X*normals[m_k].Y) * m_delta >= 0)
03364     {
03365       if (normals[m_j].X * normals[m_k].X + normals[m_j].Y * normals[m_k].Y < 0.985)
03366       {
03367         double a1 = std::atan2(normals[m_k].Y, normals[m_k].X);
03368         double a2 = std::atan2(normals[m_j].Y, normals[m_j].X);
03369         if (m_delta > 0 && a2 < a1) a2 += pi *2;
03370         else if (m_delta < 0 && a2 > a1) a2 -= pi *2;
03371         Polygon arc = BuildArc(m_p[m_i][m_j], a1, a2, m_delta);
03372         for (Polygon::size_type m = 0; m < arc.size(); m++)
03373           AddPoint(arc[m]);
03374       }
03375     }
03376     else
03377       AddPoint(m_p[m_i][m_j]);
03378     AddPoint(pt2);
03379 }
03380 //--------------------------------------------------------------------------
03381 
03382 }; //end PolyOffsetBuilder
03383 
03384 //------------------------------------------------------------------------------
03385 //------------------------------------------------------------------------------
03386 
03387 void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
03388   double delta, JoinType jointype, double MiterLimit)
03389 {
03390   if (&out_polys == &in_polys)
03391   {
03392     Polygons poly2(in_polys);
03393     PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit);
03394   }
03395   else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit);
03396 }
03397 //------------------------------------------------------------------------------
03398 
03399 void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType)
03400 {
03401   Clipper c;
03402   c.AddPolygon(in_poly, ptSubject);
03403   c.Execute(ctUnion, out_polys, fillType, fillType);
03404 }
03405 //------------------------------------------------------------------------------
03406 
03407 void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType)
03408 {
03409   Clipper c;
03410   c.AddPolygons(in_polys, ptSubject);
03411   c.Execute(ctUnion, out_polys, fillType, fillType);
03412 }
03413 //------------------------------------------------------------------------------
03414 
03415 void SimplifyPolygons(Polygons &polys, PolyFillType fillType)
03416 {
03417   SimplifyPolygons(polys, polys, fillType);
03418 }
03419 //------------------------------------------------------------------------------
03420 
03421 std::ostream& operator <<(std::ostream &s, IntPoint& p)
03422 {
03423   s << p.X << ' ' << p.Y << "\n";
03424   return s;
03425 }
03426 //------------------------------------------------------------------------------
03427 
03428 std::ostream& operator <<(std::ostream &s, Polygon &p)
03429 {
03430   for (Polygon::size_type i = 0; i < p.size(); i++)
03431     s << p[i];
03432   s << "\n";
03433   return s;
03434 }
03435 //------------------------------------------------------------------------------
03436 
03437 std::ostream& operator <<(std::ostream &s, Polygons &p)
03438 {
03439   for (Polygons::size_type i = 0; i < p.size(); i++)
03440     s << p[i];
03441   s << "\n";
03442   return s;
03443 }
03444 //------------------------------------------------------------------------------
03445 
03446 } //ClipperLib namespace


srs_env_model_percp
Author(s): Rostislav Hulik (ihulik@fit.vutbr.cz), Tomas Hodan, Michal Spanel (spanel@fit.vutbr.cz)
autogenerated on Mon Oct 6 2014 08:07:19