~ubuntu-branches/ubuntu/saucy/mapserver/saucy-security
» Revision
31
: renderers/agg/src/clipper.cpp
« back to all changes in this revision
Viewing changes to renderers/agg/src/clipper.cpp
- browse files at revision 31
- compare with another revision
- download diff
- download tarball
- view history from revision 31
- Committer: Package Import Robot
- Author(s): Francesco Paolo Lovergine
- Date: 2011-12-23 14:02:06 UTC
- mfrom: (26.1.2 sid)
- Revision ID: package-import@ubuntu.com-20111223140206-n3h9t2hsa8hyslmu
Tags: 6.0.1-2
Added missed stuff for libmapscript-perl.
- files added:
- MIGRATION_GUIDE.txt
- mapscript/php
- mapscript/php/examples
- files removed:
- .pc
- .pc/debian-changes-5.6.6-1.1ubuntu1
- .pc/symbol_index_overflow
- .pc/wfs_sql_injection.patch
- mapscript/php3
- mapscript/php3/examples
- files modified:
- COMMITERS
- aclocal.m4 *
- tests/home.png *
added
removed
renderers/agg/src/clipper.cpp
1
/*******************************************************************************
2
* *
3
* Author : Angus Johnson *
4
* Version : 4.2.0 *
5
* Date : 11 April 2011 *
6
* Website : http://www.angusj.com *
7
* Copyright : Angus Johnson 2010-2011 *
8
* *
9
* License: *
10
* Use, modification & distribution is subject to Boost Software License Ver 1. *
11
* http://www.boost.org/LICENSE_1_0.txt *
12
* *
13
* Attributions: *
14
* The code in this library is an extension of Bala Vatti's clipping algorithm: *
15
* "A generic solution to polygon clipping" *
16
* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
17
* http://portal.acm.org/citation.cfm?id=129906 *
18
* *
19
* Computer graphics and geometric modeling: implementation and algorithms *
20
* By Max K. Agoston *
21
* Springer; 1 edition (January 4, 2005) *
22
* http://books.google.com/books?q=vatti+clipping+agoston *
23
* *
24
*******************************************************************************/
25
26
/*******************************************************************************
27
* *
28
* This is a translation of the Delphi Clipper library and the naming style *
29
* used has retained a Delphi flavour. *
30
* *
31
*******************************************************************************/
32
33
#include "clipper.hpp"
34
#include <cmath>
35
#include <ctime>
36
#include <vector>
37
#include <algorithm>
38
#include <stdexcept>
39
#include <cstring>
40
#include <cstdlib>
41
42
namespace clipper {
43
44
static double const horizontal = -3.4E+38;
45
static double const pi = 3.14159265359;
46
enum Direction { dRightToLeft, dLeftToRight };
47
enum Position { pFirst, pMiddle, pSecond };
48
49
//------------------------------------------------------------------------------
50
//------------------------------------------------------------------------------
51
52
bool IsClockwise(const Polygon &poly)
53
{
54
int highI = poly.size() -1;
55
if (highI < 2) return false;
56
double a;
57
a = static_cast<double>(poly[highI].X) * static_cast<double>(poly[0].Y) -
58
static_cast<double>(poly[0].X) * static_cast<double>(poly[highI].Y);
59
for (int i = 0; i < highI; ++i)
60
a += static_cast<double>(poly[i].X) * static_cast<double>(poly[i+1].Y) -
61
static_cast<double>(poly[i+1].X) * static_cast<double>(poly[i].Y);
62
//area := area/2;
63
return a > 0; //ie reverse of normal formula because assume Y axis inverted
64
}
65
//------------------------------------------------------------------------------
66
67
bool IsClockwise(PolyPt *pt)
68
{
69
double a = 0;
70
PolyPt* startPt = pt;
71
do
72
{
73
a += static_cast<double>(pt->pt.X) * static_cast<double>(pt->next->pt.Y) -
74
static_cast<double>(pt->next->pt.X) * static_cast<double>(pt->pt.Y);
75
pt = pt->next;
76
}
77
while (pt != startPt);
78
//area = area /2;
79
return a > 0; //ie reverse of normal formula because Y axis inverted
80
}
81
//------------------------------------------------------------------------------
82
83
inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2)
84
{
85
return ( pt1.X == pt2.X && pt1.Y == pt2.Y );
86
}
87
//------------------------------------------------------------------------------
88
89
double Area(const Polygon &poly)
90
{
91
int highI = poly.size() -1;
92
if (highI < 2) return 0;
93
double a;
94
a = static_cast<double>(poly[highI].X) * static_cast<double>(poly[0].Y) -
95
static_cast<double>(poly[0].X) * static_cast<double>(poly[highI].Y);
96
for (int i = 0; i < highI; ++i)
97
a += static_cast<double>(poly[i].X) * static_cast<double>(poly[i+1].Y) -
98
static_cast<double>(poly[i+1].X) * static_cast<double>(poly[i].Y);
99
return a/2;
100
}
101
//------------------------------------------------------------------------------
102
103
bool PointIsVertex(const IntPoint &pt, PolyPt *pp)
104
{
105
PolyPt *pp2 = pp;
106
do
107
{
108
if (PointsEqual(pp2->pt, pt)) return true;
109
pp2 = pp2->next;
110
}
111
while (pp2 != pp);
112
return false;
113
}
114
//------------------------------------------------------------------------------
115
116
bool PointInPolygon(const IntPoint &pt, PolyPt *pp)
117
{
118
PolyPt *pp2 = pp;
119
bool result = false;
120
do
121
{
122
if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) ||
123
((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) &&
124
(pt.X - pp2->pt.X < (pp2->prev->pt.X - pp2->pt.X) * (pt.Y - pp2->pt.Y) /
125
(pp2->prev->pt.Y - pp2->pt.Y))) result = !result;
126
pp2 = pp2->next;
127
}
128
while (pp2 != pp);
129
return result;
130
}
131
//------------------------------------------------------------------------------
132
133
bool SlopesEqual(TEdge &e1, TEdge &e2)
134
{
135
if (e1.ybot == e1.ytop) return (e2.ybot == e2.ytop);
136
else if (e2.ybot == e2.ytop) return false;
137
else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) -
138
(e1.xtop - e1.xbot)*(e2.ytop - e2.ybot) == 0;
139
}
140
//------------------------------------------------------------------------------
141
142
bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, const IntPoint pt3)
143
{
144
if (pt1.Y == pt2.Y) return (pt2.Y == pt3.Y);
145
else if (pt2.Y == pt3.Y) return false;
146
else return
147
(pt1.Y-pt2.Y)*(pt2.X-pt3.X) - (pt1.X-pt2.X)*(pt2.Y-pt3.Y) == 0;
148
}
149
//------------------------------------------------------------------------------
150
151
void SetDx(TEdge &e)
152
{
153
if (e.ybot == e.ytop) e.dx = horizontal;
154
else e.dx =
155
static_cast<double>(e.xtop - e.xbot) / static_cast<double>(e.ytop - e.ybot);
156
}
157
//---------------------------------------------------------------------------
158
159
double GetDx(const IntPoint pt1, const IntPoint pt2)
160
{
161
if (pt1.Y == pt2.Y) return horizontal;
162
else return
163
static_cast<double>(pt2.X - pt1.X) / static_cast<double>(pt2.Y - pt1.Y);
164
}
165
//---------------------------------------------------------------------------
166
167
void SwapSides(TEdge &edge1, TEdge &edge2)
168
{
169
EdgeSide side = edge1.side;
170
edge1.side = edge2.side;
171
edge2.side = side;
172
}
173
//------------------------------------------------------------------------------
174
175
void SwapPolyIndexes(TEdge &edge1, TEdge &edge2)
176
{
177
int outIdx = edge1.outIdx;
178
edge1.outIdx = edge2.outIdx;
179
edge2.outIdx = outIdx;
180
}
181
//------------------------------------------------------------------------------
182
183
inline long64 Round(double val)
184
{
185
if ((val < 0)) return static_cast<long64>(val - 0.5);
186
else return static_cast<long64>(val + 0.5);
187
}
188
//------------------------------------------------------------------------------
189
190
inline long64 Abs(long64 val)
191
{
192
if ((val < 0)) return -val; else return val;
193
}
194
//------------------------------------------------------------------------------
195
196
long64 TopX(TEdge &edge, const long64 currentY)
197
{
198
if( currentY == edge.ytop ) return edge.xtop;
199
return edge.xbot + Round(edge.dx *(currentY - edge.ybot));
200
}
201
//------------------------------------------------------------------------------
202
203
long64 TopX(const IntPoint pt1, const IntPoint pt2, const long64 currentY)
204
{
205
//preconditions: pt1.Y <> pt2.Y and pt1.Y > pt2.Y
206
if (currentY >= pt1.Y) return pt1.X;
207
else if (currentY == pt2.Y) return pt2.X;
208
else if (pt1.X == pt2.X) return pt1.X;
209
else
210
{
211
double q = static_cast<double>(pt1.X-pt2.X)/static_cast<double>(pt1.Y-pt2.Y);
212
return static_cast<long64>(pt1.X + (currentY - pt1.Y) *q);
213
}
214
}
215
//------------------------------------------------------------------------------
216
217
bool IntersectPoint(TEdge &edge1, TEdge &edge2, IntPoint &ip)
218
{
219
double b1, b2;
220
if (SlopesEqual(edge1, edge2)) return false;
221
else if (edge1.dx == 0)
222
{
223
ip.X = edge1.xbot;
224
if (edge2.dx == horizontal)
225
{
226
ip.Y = edge2.ybot;
227
} else
228
{
229
b2 = edge2.ybot - (edge2.xbot/edge2.dx);
230
ip.Y = Round(ip.X/edge2.dx + b2);
231
}
232
}
233
else if (edge2.dx == 0)
234
{
235
ip.X = edge2.xbot;
236
if (edge1.dx == horizontal)
237
{
238
ip.Y = edge1.ybot;
239
} else
240
{
241
b1 = edge1.ybot - (edge1.xbot/edge1.dx);
242
ip.Y = Round(ip.X/edge1.dx + b1);
243
}
244
} else
245
{
246
b1 = edge1.xbot - edge1.ybot * edge1.dx;
247
b2 = edge2.xbot - edge2.ybot * edge2.dx;
248
b2 = (b2-b1)/(edge1.dx - edge2.dx);
249
ip.Y = Round(b2);
250
ip.X = Round(edge1.dx * b2 + b1);
251
}
252
253
return
254
//can be *so close* to the top of one edge that the rounded Y equals one ytop ...
255
(ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > edge2.tmpX) ||
256
(ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > edge2.tmpX) ||
257
(ip.Y > edge1.ytop && ip.Y > edge2.ytop);
258
}
259
//------------------------------------------------------------------------------
260
261
void ReversePolyPtLinks(PolyPt &pp)
262
{
263
PolyPt *pp1, *pp2;
264
pp1 = &pp;
265
do {
266
pp2 = pp1->next;
267
pp1->next = pp1->prev;
268
pp1->prev = pp2;
269
pp1 = pp2;
270
} while( pp1 != &pp );
271
}
272
//------------------------------------------------------------------------------
273
274
void DisposePolyPts(PolyPt*& pp)
275
{
276
if (pp == 0) return;
277
PolyPt *tmpPp;
278
pp->prev->next = 0;
279
while( pp )
280
{
281
tmpPp = pp;
282
pp = pp->next;
283
delete tmpPp ;
284
}
285
}
286
//------------------------------------------------------------------------------
287
288
void InitEdge(TEdge *e, TEdge *eNext,
289
TEdge *ePrev, const IntPoint &pt, PolyType polyType)
290
{
291
std::memset( e, 0, sizeof( TEdge ));
292
293
e->next = eNext;
294
e->prev = ePrev;
295
e->xcurr = pt.X;
296
e->ycurr = pt.Y;
297
if (e->ycurr >= e->next->ycurr)
298
{
299
e->xbot = e->xcurr;
300
e->ybot = e->ycurr;
301
e->xtop = e->next->xcurr;
302
e->ytop = e->next->ycurr;
303
e->windDelta = 1;
304
} else
305
{
306
e->xtop = e->xcurr;
307
e->ytop = e->ycurr;
308
e->xbot = e->next->xcurr;
309
e->ybot = e->next->ycurr;
310
e->windDelta = -1;
311
}
312
SetDx(*e);
313
e->polyType = polyType;
314
e->outIdx = -1;
315
}
316
//------------------------------------------------------------------------------
317
318
inline void SwapX(TEdge &e)
319
{
320
//swap horizontal edges' top and bottom x's so they follow the natural
321
//progression of the bounds - ie so their xbots will align with the
322
//adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
323
e.xcurr = e.xtop;
324
e.xtop = e.xbot;
325
e.xbot = e.xcurr;
326
}
327
//------------------------------------------------------------------------------
328
329
void SwapPoints(IntPoint &pt1, IntPoint &pt2)
330
{
331
IntPoint tmp = pt1;
332
pt1 = pt2;
333
pt2 = tmp;
334
}
335
//------------------------------------------------------------------------------
336
337
bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
338
IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
339
{
340
//precondition: segments are colinear.
341
if ( pt1a.Y == pt1b.Y || Abs((pt1a.X - pt1b.X)/(pt1a.Y - pt1b.Y)) > 1 )
342
{
343
if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b);
344
if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b);
345
if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
346
if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
347
return pt1.X < pt2.X;
348
} else
349
{
350
if (pt1a.Y < pt1b.Y) SwapPoints(pt1a, pt1b);
351
if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b);
352
if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
353
if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
354
return pt1.Y > pt2.Y;
355
}
356
}
357
//------------------------------------------------------------------------------
358
359
PolyPt* PolygonBottom(PolyPt* pp)
360
{
361
PolyPt* p = pp->next;
362
PolyPt* result = pp;
363
while (p != pp)
364
{
365
if (p->pt.Y > result->pt.Y) result = p;
366
else if (p->pt.Y == result->pt.Y && p->pt.X < result->pt.X) result = p;
367
p = p->next;
368
}
369
return result;
370
}
371
//------------------------------------------------------------------------------
372
373
bool FindSegment(PolyPt* &pp, const IntPoint pt1, const IntPoint pt2)
374
{
375
if (!pp) return false;
376
PolyPt* pp2 = pp;
377
do
378
{
379
if (PointsEqual(pp->pt, pt1) &&
380
(PointsEqual(pp->next->pt, pt2) || PointsEqual(pp->prev->pt, pt2)))
381
return true;
382
pp = pp->next;
383
}
384
while (pp != pp2);
385
return false;
386
}
387
//------------------------------------------------------------------------------
388
389
Position GetPosition(const IntPoint pt1, const IntPoint pt2, const IntPoint pt)
390
{
391
if (PointsEqual(pt1, pt)) return pFirst;
392
else if (PointsEqual(pt2, pt)) return pSecond;
393
else return pMiddle;
394
}
395
//------------------------------------------------------------------------------
396
397
bool Pt3IsBetweenPt1AndPt2(const IntPoint pt1,
398
const IntPoint pt2, const IntPoint pt3)
399
{
400
if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true;
401
else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X);
402
else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.Y);
403
}
404
//------------------------------------------------------------------------------
405
406
PolyPt* InsertPolyPtBetween(PolyPt* p1, PolyPt* p2, const IntPoint pt)
407
{
408
PolyPt* result = new PolyPt;
409
result->pt = pt;
410
result->isHole = p1->isHole;
411
if (p2 == p1->next)
412
{
413
p1->next = result;
414
p2->prev = result;
415
result->next = p2;
416
result->prev = p1;
417
} else
418
{
419
p2->next = result;
420
p1->prev = result;
421
result->next = p1;
422
result->prev = p2;
423
}
424
return result;
425
}
426
427
//------------------------------------------------------------------------------
428
// ClipperBase class methods ...
429
//------------------------------------------------------------------------------
430
431
ClipperBase::ClipperBase() //constructor
432
{
433
m_MinimaList = 0;
434
m_CurrentLM = 0;
435
}
436
//------------------------------------------------------------------------------
437
438
ClipperBase::~ClipperBase() //destructor
439
{
440
Clear();
441
}
442
//------------------------------------------------------------------------------
443
444
bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType)
445
{
446
int len = pg.size();
447
if (len < 3) return false;
448
Polygon p(len);
449
p[0] = pg[0];
450
int j = 0;
451
const long64 MaxVal = 1500000000; //~ Sqrt(2^63)/2
452
453
for (int i = 1; i < len; ++i)
454
{
455
if (Abs(pg[i].X) > MaxVal|| Abs(pg[i].Y) > MaxVal)
456
throw clipperException("Integer exceeds range bounds");
457
else if (PointsEqual(p[j], pg[i])) continue;
458
else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i]))
459
{
460
if (PointsEqual(p[j-1], pg[i])) j--;
461
} else j++;
462
p[j] = pg[i];
463
}
464
if (j < 2) return false;
465
466
len = j+1;
467
for (;;)
468
{
469
//nb: test for point equality before testing slopes ...
470
if (PointsEqual(p[j], p[0])) j--;
471
else if (PointsEqual(p[0], p[1]) || SlopesEqual(p[j], p[0], p[1]))
472
p[0] = p[j--];
473
else if (SlopesEqual(p[j-1], p[j], p[0])) j--;
474
else if (SlopesEqual(p[0], p[1], p[2]))
475
{
476
for (int i = 2; i <= j; ++i) p[i-1] = p[i];
477
j--;
478
}
479
//exit loop if nothing is changed or there are too few vertices ...
480
if (j == len-1 || j < 2) break;
481
len = j +1;
482
}
483
if (len < 3) return false;
484
485
//create a new edge array ...
486
TEdge *edges = new TEdge [len];
487
m_edges.push_back(edges);
488
489
//convert vertices to a double-linked-list of edges and initialize ...
490
edges[0].xcurr = p[0].X;
491
edges[0].ycurr = p[0].Y;
492
InitEdge(&edges[len-1], &edges[0], &edges[len-2], p[len-1], polyType);
493
for (int i = len-2; i > 0; --i)
494
InitEdge(&edges[i], &edges[i+1], &edges[i-1], p[i], polyType);
495
InitEdge(&edges[0], &edges[1], &edges[len-1], p[0], polyType);
496
497
//reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates
498
//increase downward so the 'highest' edge will have the smallest ytop) ...
499
TEdge *e = &edges[0];
500
TEdge *eHighest = e;
501
do
502
{
503
e->xcurr = e->xbot;
504
e->ycurr = e->ybot;
505
if (e->ytop < eHighest->ytop) eHighest = e;
506
e = e->next;
507
}
508
while ( e != &edges[0]);
509
510
//make sure eHighest is positioned so the following loop works safely ...
511
if (eHighest->windDelta > 0) eHighest = eHighest->next;
512
if (eHighest->dx == horizontal) eHighest = eHighest->next;
513
514
//finally insert each local minima ...
515
e = eHighest;
516
do {
517
e = AddBoundsToLML(e);
518
}
519
while( e != eHighest );
520
return true;
521
}
522
//------------------------------------------------------------------------------
523
524
void ClipperBase::InsertLocalMinima(LocalMinima *newLm)
525
{
526
if( ! m_MinimaList )
527
{
528
m_MinimaList = newLm;
529
}
530
else if( newLm->Y >= m_MinimaList->Y )
531
{
532
newLm->next = m_MinimaList;
533
m_MinimaList = newLm;
534
} else
535
{
536
LocalMinima* tmpLm = m_MinimaList;
537
while( tmpLm->next && ( newLm->Y < tmpLm->next->Y ) )
538
tmpLm = tmpLm->next;
539
newLm->next = tmpLm->next;
540
tmpLm->next = newLm;
541
}
542
}
543
//------------------------------------------------------------------------------
544
545
TEdge* ClipperBase::AddBoundsToLML(TEdge *e)
546
{
547
//Starting at the top of one bound we progress to the bottom where there's
548
//a local minima. We then go to the top of the next bound. These two bounds
549
//form the left and right (or right and left) bounds of the local minima.
550
e->nextInLML = 0;
551
e = e->next;
552
for (;;)
553
{
554
if ( e->dx == horizontal )
555
{
556
//nb: proceed through horizontals when approaching from their right,
557
// but break on horizontal minima if approaching from their left.
558
// This ensures 'local minima' are always on the left of horizontals.
559
if (e->next->ytop < e->ytop && e->next->xbot > e->prev->xbot) break;
560
if (e->xtop != e->prev->xbot) SwapX(*e);
561
e->nextInLML = e->prev;
562
}
563
else if (e->ycurr == e->prev->ycurr) break;
564
else e->nextInLML = e->prev;
565
e = e->next;
566
}
567
568
//e and e.prev are now at a local minima ...
569
LocalMinima* newLm = new LocalMinima;
570
newLm->next = 0;
571
newLm->Y = e->prev->ybot;
572
573
if ( e->dx == horizontal ) //horizontal edges never start a left bound
574
{
575
if (e->xbot != e->prev->xbot) SwapX(*e);
576
newLm->leftBound = e->prev;
577
newLm->rightBound = e;
578
} else if (e->dx < e->prev->dx)
579
{
580
newLm->leftBound = e->prev;
581
newLm->rightBound = e;
582
} else
583
{
584
newLm->leftBound = e;
585
newLm->rightBound = e->prev;
586
}
587
newLm->leftBound->side = esLeft;
588
newLm->rightBound->side = esRight;
589
InsertLocalMinima( newLm );
590
591
for (;;)
592
{
593
if ( e->next->ytop == e->ytop && e->next->dx != horizontal ) break;
594
e->nextInLML = e->next;
595
e = e->next;
596
if ( e->dx == horizontal && e->xbot != e->prev->xtop) SwapX(*e);
597
}
598
return e->next;
599
}
600
//------------------------------------------------------------------------------
601
602
bool ClipperBase::AddPolygons(const Polygons &ppg, PolyType polyType)
603
{
604
bool result = false;
605
for (Polygons::size_type i = 0; i < ppg.size(); ++i)
606
if (AddPolygon(ppg[i], polyType)) result = true;
607
return result;
608
}
609
//------------------------------------------------------------------------------
610
611
void ClipperBase::Clear()
612
{
613
DisposeLocalMinimaList();
614
for (EdgeList::size_type i = 0; i < m_edges.size(); ++i) delete [] m_edges[i];
615
m_edges.clear();
616
}
617
//------------------------------------------------------------------------------
618
619
void ClipperBase::Reset()
620
{
621
m_CurrentLM = m_MinimaList;
622
if( !m_CurrentLM ) return; //ie nothing to process
623
624
//reset all edges ...
625
LocalMinima* lm = m_MinimaList;
626
while( lm )
627
{
628
TEdge* e = lm->leftBound;
629
while( e )
630
{
631
e->xcurr = e->xbot;
632
e->ycurr = e->ybot;
633
e->side = esLeft;
634
e->outIdx = -1;
635
e = e->nextInLML;
636
}
637
e = lm->rightBound;
638
while( e )
639
{
640
e->xcurr = e->xbot;
641
e->ycurr = e->ybot;
642
e->side = esRight;
643
e->outIdx = -1;
644
e = e->nextInLML;
645
}
646
lm = lm->next;
647
}
648
}
649
//------------------------------------------------------------------------------
650
651
void ClipperBase::DisposeLocalMinimaList()
652
{
653
while( m_MinimaList )
654
{
655
LocalMinima* tmpLm = m_MinimaList->next;
656
delete m_MinimaList;
657
m_MinimaList = tmpLm;
658
}
659
m_CurrentLM = 0;
660
}
661
//------------------------------------------------------------------------------
662
663
void ClipperBase::PopLocalMinima()
664
{
665
if( ! m_CurrentLM ) return;
666
m_CurrentLM = m_CurrentLM->next;
667
}
668
//------------------------------------------------------------------------------
669
670
IntRect ClipperBase::GetBounds()
671
{
672
IntRect result;
673
LocalMinima* lm = m_MinimaList;
674
if (!lm)
675
{
676
result.left = result.top = result.right = result.bottom = 0;
677
return result;
678
}
679
result.left = lm->leftBound->xbot;
680
result.top = lm->leftBound->ybot;
681
result.right = lm->leftBound->xbot;
682
result.bottom = lm->leftBound->ybot;
683
while (lm)
684
{
685
if (lm->leftBound->ybot > result.bottom)
686
result.bottom = lm->leftBound->ybot;
687
TEdge* e = lm->leftBound;
688
for (;;) {
689
while (e->nextInLML)
690
{
691
if (e->xbot < result.left) result.left = e->xbot;
692
if (e->xbot > result.right) result.right = e->xbot;
693
e = e->nextInLML;
694
}
695
if (e->xbot < result.left) result.left = e->xbot;
696
if (e->xbot > result.right) result.right = e->xbot;
697
if (e->xtop < result.left) result.left = e->xtop;
698
if (e->xtop > result.right) result.right = e->xtop;
699
if (e->ytop < result.top) result.top = e->ytop;
700
701
if (e == lm->leftBound) e = lm->rightBound;
702
else break;
703
}
704
lm = lm->next;
705
}
706
return result;
707
}
708
709
710
//------------------------------------------------------------------------------
711
// TClipper methods ...
712
//------------------------------------------------------------------------------
713
714
Clipper::Clipper() : ClipperBase() //constructor
715
{
716
m_Scanbeam = 0;
717
m_ActiveEdges = 0;
718
m_SortedEdges = 0;
719
m_IntersectNodes = 0;
720
m_ExecuteLocked = false;
721
};
722
//------------------------------------------------------------------------------
723
724
Clipper::~Clipper() //destructor
725
{
726
DisposeScanbeamList();
727
};
728
//------------------------------------------------------------------------------
729
730
void Clipper::DisposeScanbeamList()
731
{
732
while ( m_Scanbeam ) {
733
Scanbeam* sb2 = m_Scanbeam->next;
734
delete m_Scanbeam;
735
m_Scanbeam = sb2;
736
}
737
}
738
//------------------------------------------------------------------------------
739
740
void Clipper::Reset()
741
{
742
ClipperBase::Reset();
743
m_Scanbeam = 0;
744
m_ActiveEdges = 0;
745
m_SortedEdges = 0;
746
LocalMinima* lm = m_MinimaList;
747
while (lm)
748
{
749
InsertScanbeam(lm->Y);
750
InsertScanbeam(lm->leftBound->ytop);
751
lm = lm->next;
752
}
753
}
754
//------------------------------------------------------------------------------
755
756
bool Clipper::Execute(ClipType clipType, Polygons &solution,
757
PolyFillType subjFillType, PolyFillType clipFillType)
758
{
759
if( m_ExecuteLocked ) return false;
760
bool succeeded;
761
try {
762
m_ExecuteLocked = true;
763
solution.resize(0);
764
Reset();
765
if (!m_CurrentLM )
766
{
767
m_ExecuteLocked = false;
768
return true;
769
}
770
m_SubjFillType = subjFillType;
771
m_ClipFillType = clipFillType;
772
m_ClipType = clipType;
773
774
long64 botY = PopScanbeam();
775
do {
776
InsertLocalMinimaIntoAEL(botY);
777
ClearHorzJoins();
778
ProcessHorizontals();
779
long64 topY = PopScanbeam();
780
succeeded = ProcessIntersections(topY);
781
if (succeeded) ProcessEdgesAtTopOfScanbeam(topY);
782
botY = topY;
783
} while( succeeded && m_Scanbeam );
784
785
//build the return polygons ...
786
if (succeeded) BuildResult(solution);
787
}
788
catch(...) {
789
ClearJoins();
790
ClearHorzJoins();
791
solution.resize(0);
792
succeeded = false;
793
}
794
ClearJoins();
795
ClearHorzJoins();
796
DisposeAllPolyPts();
797
m_ExecuteLocked = false;
798
return succeeded;
799
}
800
//------------------------------------------------------------------------------
801
802
void Clipper::InsertScanbeam(const long64 Y)
803
{
804
if( !m_Scanbeam )
805
{
806
m_Scanbeam = new Scanbeam;
807
m_Scanbeam->next = 0;
808
m_Scanbeam->Y = Y;
809
}
810
else if( Y > m_Scanbeam->Y )
811
{
812
Scanbeam* newSb = new Scanbeam;
813
newSb->Y = Y;
814
newSb->next = m_Scanbeam;
815
m_Scanbeam = newSb;
816
} else
817
{
818
Scanbeam* sb2 = m_Scanbeam;
819
while( sb2->next && ( Y <= sb2->next->Y ) ) sb2 = sb2->next;
820
if( Y == sb2->Y ) return; //ie ignores duplicates
821
Scanbeam* newSb = new Scanbeam;
822
newSb->Y = Y;
823
newSb->next = sb2->next;
824
sb2->next = newSb;
825
}
826
}
827
//------------------------------------------------------------------------------
828
829
long64 Clipper::PopScanbeam()
830
{
831
long64 Y = m_Scanbeam->Y;
832
Scanbeam* sb2 = m_Scanbeam;
833
m_Scanbeam = m_Scanbeam->next;
834
delete sb2;
835
return Y;
836
}
837
//------------------------------------------------------------------------------
838
839
void Clipper::DisposeAllPolyPts(){
840
for (PolyPtList::size_type i = 0; i < m_PolyPts.size(); ++i)
841
DisposePolyPts(m_PolyPts[i]);
842
m_PolyPts.clear();
843
}
844
//------------------------------------------------------------------------------
845
846
void Clipper::SetWindingCount(TEdge &edge)
847
{
848
TEdge *e = edge.prevInAEL;
849
//find the edge of the same polytype that immediately preceeds 'edge' in AEL
850
while ( e && e->polyType != edge.polyType ) e = e->prevInAEL;
851
if ( !e )
852
{
853
edge.windCnt = edge.windDelta;
854
edge.windCnt2 = 0;
855
e = m_ActiveEdges; //ie get ready to calc windCnt2
856
} else if ( IsNonZeroFillType(edge) )
857
{
858
//nonZero filling ...
859
if ( e->windCnt * e->windDelta < 0 )
860
{
861
if (Abs(e->windCnt) > 1)
862
{
863
if (e->windDelta * edge.windDelta < 0) edge.windCnt = e->windCnt;
864
else edge.windCnt = e->windCnt + edge.windDelta;
865
} else
866
edge.windCnt = e->windCnt + e->windDelta + edge.windDelta;
867
} else
868
{
869
if ( Abs(e->windCnt) > 1 && e->windDelta * edge.windDelta < 0)
870
edge.windCnt = e->windCnt;
871
else if ( e->windCnt + edge.windDelta == 0 )
872
edge.windCnt = e->windCnt;
873
else edge.windCnt = e->windCnt + edge.windDelta;
874
}
875
edge.windCnt2 = e->windCnt2;
876
e = e->nextInAEL; //ie get ready to calc windCnt2
877
} else
878
{
879
//even-odd filling ...
880
edge.windCnt = 1;
881
edge.windCnt2 = e->windCnt2;
882
e = e->nextInAEL; //ie get ready to calc windCnt2
883
}
884
885
//update windCnt2 ...
886
if ( IsNonZeroAltFillType(edge) )
887
{
888
//nonZero filling ...
889
while ( e != &edge )
890
{
891
edge.windCnt2 += e->windDelta;
892
e = e->nextInAEL;
893
}
894
} else
895
{
896
//even-odd filling ...
897
while ( e != &edge )
898
{
899
edge.windCnt2 = (edge.windCnt2 == 0) ? 1 : 0;
900
e = e->nextInAEL;
901
}
902
}
903
}
904
//------------------------------------------------------------------------------
905
906
bool Clipper::IsNonZeroFillType(const TEdge& edge) const
907
{
908
if (edge.polyType == ptSubject)
909
return m_SubjFillType == pftNonZero; else
910
return m_ClipFillType == pftNonZero;
911
}
912
//------------------------------------------------------------------------------
913
914
bool Clipper::IsNonZeroAltFillType(const TEdge& edge) const
915
{
916
if (edge.polyType == ptSubject)
917
return m_ClipFillType == pftNonZero; else
918
return m_SubjFillType == pftNonZero;
919
}
920
//------------------------------------------------------------------------------
921
922
bool Clipper::IsContributing(const TEdge& edge) const
923
{
924
switch( m_ClipType ){
925
case ctIntersection:
926
if ( edge.polyType == ptSubject )
927
return Abs(edge.windCnt) == 1 && edge.windCnt2 != 0; else
928
return Abs(edge.windCnt2) > 0 && Abs(edge.windCnt) == 1;
929
case ctUnion:
930
return Abs(edge.windCnt) == 1 && edge.windCnt2 == 0;
931
case ctDifference:
932
if ( edge.polyType == ptSubject )
933
return std::abs(edge.windCnt) == 1 && edge.windCnt2 == 0; else
934
return std::abs(edge.windCnt) == 1 && edge.windCnt2 != 0;
935
default: //case ctXor:
936
return std::abs(edge.windCnt) == 1;
937
}
938
}
939
//------------------------------------------------------------------------------
940
941
void Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
942
{
943
if( e2->dx == horizontal || ( e1->dx > e2->dx ) )
944
{
945
AddPolyPt( e1, pt );
946
e2->outIdx = e1->outIdx;
947
e1->side = esLeft;
948
e2->side = esRight;
949
} else
950
{
951
AddPolyPt( e2, pt );
952
e1->outIdx = e2->outIdx;
953
e1->side = esRight;
954
e2->side = esLeft;
955
}
956
}
957
//------------------------------------------------------------------------------
958
959
void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
960
{
961
AddPolyPt( e1, pt );
962
if( e1->outIdx == e2->outIdx )
963
{
964
e1->outIdx = -1;
965
e2->outIdx = -1;
966
}
967
else
968
AppendPolygon( e1, e2 );
969
}
970
//------------------------------------------------------------------------------
971
972
void Clipper::AddEdgeToSEL(TEdge *edge)
973
{
974
//SEL pointers in PEdge are reused to build a list of horizontal edges.
975
//However, we don't need to worry about order with horizontal edge processing.
976
if( !m_SortedEdges )
977
{
978
m_SortedEdges = edge;
979
edge->prevInSEL = 0;
980
edge->nextInSEL = 0;
981
}
982
else
983
{
984
edge->nextInSEL = m_SortedEdges;
985
edge->prevInSEL = 0;
986
m_SortedEdges->prevInSEL = edge;
987
m_SortedEdges = edge;
988
}
989
}
990
//------------------------------------------------------------------------------
991
992
void Clipper::CopyAELToSEL()
993
{
994
TEdge* e = m_ActiveEdges;
995
m_SortedEdges = e;
996
if (!m_ActiveEdges) return;
997
m_SortedEdges->prevInSEL = 0;
998
e = e->nextInAEL;
999
while ( e )
1000
{
1001
e->prevInSEL = e->prevInAEL;
1002
e->prevInSEL->nextInSEL = e;
1003
e->nextInSEL = 0;
1004
e = e->nextInAEL;
1005
}
1006
}
1007
//------------------------------------------------------------------------------
1008
1009
void Clipper::AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx)
1010
{
1011
JoinRec* jr = new JoinRec;
1012
if (e1OutIdx >= 0)
1013
jr->poly1Idx = e1OutIdx; else
1014
jr->poly1Idx = e1->outIdx;
1015
jr->pt1a = IntPoint(e1->xbot, e1->ybot);
1016
jr->pt1b = IntPoint(e1->xtop, e1->ytop);
1017
jr->poly2Idx = e2->outIdx;
1018
jr->pt2a = IntPoint(e2->xbot, e2->ybot);
1019
jr->pt2b = IntPoint(e2->xtop, e2->ytop);
1020
m_Joins.push_back(jr);
1021
}
1022
//------------------------------------------------------------------------------
1023
1024
void Clipper::ClearJoins()
1025
{
1026
for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
1027
delete m_Joins[i];
1028
m_Joins.resize(0);
1029
}
1030
//------------------------------------------------------------------------------
1031
1032
void Clipper::AddHorzJoin(TEdge *e, int idx)
1033
{
1034
HorzJoinRec* hj = new HorzJoinRec;
1035
hj->edge = e;
1036
hj->savedIdx = idx;
1037
m_HorizJoins.push_back(hj);
1038
}
1039
//------------------------------------------------------------------------------
1040
1041
void Clipper::ClearHorzJoins()
1042
{
1043
for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++)
1044
delete m_HorizJoins[i];
1045
m_HorizJoins.resize(0);
1046
}
1047
//------------------------------------------------------------------------------
1048
1049
void Clipper::InsertLocalMinimaIntoAEL( const long64 botY)
1050
{
1051
while( m_CurrentLM && ( m_CurrentLM->Y == botY ) )
1052
{
1053
TEdge* lb = m_CurrentLM->leftBound;
1054
TEdge* rb = m_CurrentLM->rightBound;
1055
1056
InsertEdgeIntoAEL( lb );
1057
InsertScanbeam( lb->ytop );
1058
InsertEdgeIntoAEL( rb );
1059
1060
if ( IsNonZeroFillType( *lb) )
1061
rb->windDelta = -lb->windDelta;
1062
else
1063
{
1064
lb->windDelta = 1;
1065
rb->windDelta = 1;
1066
}
1067
SetWindingCount( *lb );
1068
rb->windCnt = lb->windCnt;
1069
rb->windCnt2 = lb->windCnt2;
1070
1071
if( rb->dx == horizontal )
1072
{
1073
//nb: only rightbounds can have a horizontal bottom edge
1074
AddEdgeToSEL( rb );
1075
InsertScanbeam( rb->nextInLML->ytop );
1076
}
1077
else
1078
InsertScanbeam( rb->ytop );
1079
1080
if( IsContributing(*lb) )
1081
AddLocalMinPoly( lb, rb, IntPoint(lb->xcurr, m_CurrentLM->Y) );
1082
1083
//if output polygons share an edge, they'll need joining later ...
1084
if (lb->outIdx >= 0 && lb->prevInAEL &&
1085
lb->prevInAEL->outIdx >= 0 && lb->prevInAEL->xcurr == lb->xbot &&
1086
SlopesEqual(*lb, *lb->prevInAEL))
1087
AddJoin(lb, lb->prevInAEL);
1088
1089
//if any output polygons share an edge, they'll need joining later ...
1090
if (rb->outIdx >= 0)
1091
{
1092
if (rb->dx == horizontal)
1093
{
1094
for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
1095
{
1096
IntPoint pt, pt2; //returned by GetOverlapSegment() but unused here.
1097
HorzJoinRec* hj = m_HorizJoins[i];
1098
//if horizontals rb and hj.edge overlap, flag for joining later ...
1099
if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot),
1100
IntPoint(hj->edge->xtop, hj->edge->ytop),
1101
IntPoint(rb->xbot, rb->ybot),
1102
IntPoint(rb->xtop, rb->ytop), pt, pt2))
1103
AddJoin(hj->edge, rb, hj->savedIdx);
1104
}
1105
}
1106
}
1107
1108
if( lb->nextInAEL != rb )
1109
{
1110
TEdge* e = lb->nextInAEL;
1111
IntPoint pt = IntPoint(lb->xcurr, lb->ycurr);
1112
while( e != rb )
1113
{
1114
if(!e) throw clipperException("InsertLocalMinimaIntoAEL: missing rightbound!");
1115
//nb: For calculating winding counts etc, IntersectEdges() assumes
1116
//that param1 will be to the right of param2 ABOVE the intersection ...
1117
IntersectEdges( rb , e , pt , ipNone); //order important here
1118
e = e->nextInAEL;
1119
}
1120
}
1121
PopLocalMinima();
1122
}
1123
}
1124
//------------------------------------------------------------------------------
1125
1126
void Clipper::DeleteFromAEL(TEdge *e)
1127
{
1128
TEdge* AelPrev = e->prevInAEL;
1129
TEdge* AelNext = e->nextInAEL;
1130
if( !AelPrev && !AelNext && (e != m_ActiveEdges) ) return; //already deleted
1131
if( AelPrev ) AelPrev->nextInAEL = AelNext;
1132
else m_ActiveEdges = AelNext;
1133
if( AelNext ) AelNext->prevInAEL = AelPrev;
1134
e->nextInAEL = 0;
1135
e->prevInAEL = 0;
1136
}
1137
//------------------------------------------------------------------------------
1138
1139
void Clipper::DeleteFromSEL(TEdge *e)
1140
{
1141
TEdge* SelPrev = e->prevInSEL;
1142
TEdge* SelNext = e->nextInSEL;
1143
if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted
1144
if( SelPrev ) SelPrev->nextInSEL = SelNext;
1145
else m_SortedEdges = SelNext;
1146
if( SelNext ) SelNext->prevInSEL = SelPrev;
1147
e->nextInSEL = 0;
1148
e->prevInSEL = 0;
1149
}
1150
//------------------------------------------------------------------------------
1151
1152
void Clipper::IntersectEdges(TEdge *e1, TEdge *e2,
1153
const IntPoint &pt, IntersectProtects protects)
1154
{
1155
//e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before
1156
//e2 in AEL except when e1 is being inserted at the intersection point ...
1157
bool e1stops = !(ipLeft & protects) && !e1->nextInLML &&
1158
e1->xtop == pt.X && e1->ytop == pt.Y;
1159
bool e2stops = !(ipRight & protects) && !e2->nextInLML &&
1160
e2->xtop == pt.X && e2->ytop == pt.Y;
1161
bool e1Contributing = ( e1->outIdx >= 0 );
1162
bool e2contributing = ( e2->outIdx >= 0 );
1163
1164
//update winding counts...
1165
//assumes that e1 will be to the right of e2 ABOVE the intersection
1166
if ( e1->polyType == e2->polyType )
1167
{
1168
if ( IsNonZeroFillType( *e1) )
1169
{
1170
if (e1->windCnt + e2->windDelta == 0 ) e1->windCnt = -e1->windCnt;
1171
else e1->windCnt += e2->windDelta;
1172
if ( e2->windCnt - e1->windDelta == 0 ) e2->windCnt = -e2->windCnt;
1173
else e2->windCnt -= e1->windDelta;
1174
} else
1175
{
1176
int oldE1WindCnt = e1->windCnt;
1177
e1->windCnt = e2->windCnt;
1178
e2->windCnt = oldE1WindCnt;
1179
}
1180
} else
1181
{
1182
if ( IsNonZeroFillType(*e2) ) e1->windCnt2 += e2->windDelta;
1183
else e1->windCnt2 = ( e1->windCnt2 == 0 ) ? 1 : 0;
1184
if ( IsNonZeroFillType(*e1) ) e2->windCnt2 -= e1->windDelta;
1185
else e2->windCnt2 = ( e2->windCnt2 == 0 ) ? 1 : 0;
1186
}
1187
1188
if ( e1Contributing && e2contributing )
1189
{
1190
if ( e1stops || e2stops || std::abs(e1->windCnt) > 1 ||
1191
std::abs(e2->windCnt) > 1 ||
1192
(e1->polyType != e2->polyType && m_ClipType != ctXor) )
1193
AddLocalMaxPoly(e1, e2, pt); else
1194
DoBothEdges( e1, e2, pt );
1195
}
1196
else if ( e1Contributing )
1197
{
1198
switch( m_ClipType ) {
1199
case ctIntersection:
1200
if ( (e2->polyType == ptSubject || e2->windCnt2 != 0) &&
1201
std::abs(e2->windCnt) < 2 ) DoEdge1( e1, e2, pt);
1202
break;
1203
default:
1204
if ( std::abs(e2->windCnt) < 2 ) DoEdge1(e1, e2, pt);
1205
}
1206
}
1207
else if ( e2contributing )
1208
{
1209
if ( m_ClipType == ctIntersection )
1210
{
1211
if ( (e1->polyType == ptSubject || e1->windCnt2 != 0) &&
1212
std::abs(e1->windCnt) < 2 ) DoEdge2( e1, e2, pt );
1213
}
1214
else
1215
if (std::abs(e1->windCnt) < 2) DoEdge2( e1, e2, pt );
1216
1217
} else
1218
{
1219
//neither edge is currently contributing ...
1220
if ( std::abs(e1->windCnt) > 1 && std::abs(e2->windCnt) > 1 ) ;// do nothing
1221
else if ( e1->polyType != e2->polyType && !e1stops && !e2stops &&
1222
std::abs(e1->windCnt) < 2 && std::abs(e2->windCnt) < 2 )
1223
AddLocalMinPoly(e1, e2, pt);
1224
else if ( std::abs(e1->windCnt) == 1 && std::abs(e2->windCnt) == 1 )
1225
switch( m_ClipType ) {
1226
case ctIntersection:
1227
if ( std::abs(e1->windCnt2) > 0 && std::abs(e2->windCnt2) > 0 )
1228
AddLocalMinPoly(e1, e2, pt);
1229
break;
1230
case ctUnion:
1231
if ( e1->windCnt2 == 0 && e2->windCnt2 == 0 )
1232
AddLocalMinPoly(e1, e2, pt);
1233
break;
1234
case ctDifference:
1235
if ( (e1->polyType == ptClip && e2->polyType == ptClip &&
1236
e1->windCnt2 != 0 && e2->windCnt2 != 0) ||
1237
(e1->polyType == ptSubject && e2->polyType == ptSubject &&
1238
e1->windCnt2 == 0 && e2->windCnt2 == 0) )
1239
AddLocalMinPoly(e1, e2, pt);
1240
break;
1241
case ctXor:
1242
AddLocalMinPoly(e1, e2, pt);
1243
}
1244
else if ( std::abs(e1->windCnt) < 2 && std::abs(e2->windCnt) < 2 )
1245
SwapSides( *e1, *e2 );
1246
}
1247
1248
if( (e1stops != e2stops) &&
1249
( (e1stops && (e1->outIdx >= 0)) || (e2stops && (e2->outIdx >= 0)) ) )
1250
{
1251
SwapSides( *e1, *e2 );
1252
SwapPolyIndexes( *e1, *e2 );
1253
}
1254
1255
//finally, delete any non-contributing maxima edges ...
1256
if( e1stops ) DeleteFromAEL( e1 );
1257
if( e2stops ) DeleteFromAEL( e2 );
1258
}
1259
//------------------------------------------------------------------------------
1260
1261
void SetHoleState(PolyPt *pp, bool isHole)
1262
{
1263
PolyPt *pp2 = pp;
1264
do
1265
{
1266
pp2->isHole = isHole;
1267
pp2 = pp2->next;
1268
}
1269
while (pp2 != pp);
1270
}
1271
//------------------------------------------------------------------------------
1272
1273
void Clipper::AppendPolygon(TEdge *e1, TEdge *e2)
1274
{
1275
//get the start and ends of both output polygons ...
1276
PolyPt* p1_lft = m_PolyPts[e1->outIdx];
1277
PolyPt* p1_rt = p1_lft->prev;
1278
PolyPt* p2_lft = m_PolyPts[e2->outIdx];
1279
PolyPt* p2_rt = p2_lft->prev;
1280
1281
//fixup orientation (hole) flag if necessary ...
1282
if (p1_lft->isHole != p2_lft->isHole)
1283
{
1284
PolyPt *p;
1285
PolyPt *bottom1 = PolygonBottom(p1_lft);
1286
PolyPt *bottom2 = PolygonBottom(p2_lft);
1287
if (bottom1->pt.Y > bottom2->pt.Y) p = p2_lft;
1288
else if (bottom1->pt.Y < bottom2->pt.Y) p = p1_lft;
1289
else if (bottom1->pt.X < bottom2->pt.X) p = p2_lft;
1290
else if (bottom1->pt.X > bottom2->pt.X) p = p1_lft;
1291
//todo - the following line really only a best guess ...
1292
else if (bottom1->isHole) p = p1_lft; else p = p2_lft;
1293
1294
SetHoleState(p, !p->isHole);
1295
}
1296
1297
EdgeSide side;
1298
//join e2 poly onto e1 poly and delete pointers to e2 ...
1299
if( e1->side == esLeft )
1300
{
1301
if( e2->side == esLeft )
1302
{
1303
//z y x a b c
1304
ReversePolyPtLinks(*p2_lft);
1305
p2_lft->next = p1_lft;
1306
p1_lft->prev = p2_lft;
1307
p1_rt->next = p2_rt;
1308
p2_rt->prev = p1_rt;
1309
m_PolyPts[e1->outIdx] = p2_rt;
1310
} else
1311
{
1312
//x y z a b c
1313
p2_rt->next = p1_lft;
1314
p1_lft->prev = p2_rt;
1315
p2_lft->prev = p1_rt;
1316
p1_rt->next = p2_lft;
1317
m_PolyPts[e1->outIdx] = p2_lft;
1318
}
1319
side = esLeft;
1320
} else
1321
{
1322
if( e2->side == esRight )
1323
{
1324
//a b c z y x
1325
ReversePolyPtLinks( *p2_lft );
1326
p1_rt->next = p2_rt;
1327
p2_rt->prev = p1_rt;
1328
p2_lft->next = p1_lft;
1329
p1_lft->prev = p2_lft;
1330
} else
1331
{
1332
//a b c x y z
1333
p1_rt->next = p2_lft;
1334
p2_lft->prev = p1_rt;
1335
p1_lft->prev = p2_rt;
1336
p2_rt->next = p1_lft;
1337
}
1338
side = esRight;
1339
}
1340
1341
int OKIdx = e1->outIdx;
1342
int ObsoleteIdx = e2->outIdx;
1343
m_PolyPts[ObsoleteIdx] = 0;
1344
1345
e1->outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly
1346
e2->outIdx = -1;
1347
1348
TEdge* e = m_ActiveEdges;
1349
while( e )
1350
{
1351
if( e->outIdx == ObsoleteIdx )
1352
{
1353
e->outIdx = OKIdx;
1354
e->side = side;
1355
break;
1356
}
1357
e = e->nextInAEL;
1358
}
1359
1360
for (JoinList::size_type i = 0; i < m_Joins.size(); ++i)
1361
{
1362
if (m_Joins[i]->poly1Idx == ObsoleteIdx) m_Joins[i]->poly1Idx = OKIdx;
1363
if (m_Joins[i]->poly2Idx == ObsoleteIdx) m_Joins[i]->poly2Idx = OKIdx;
1364
}
1365
1366
for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
1367
{
1368
if (m_HorizJoins[i]->savedIdx == ObsoleteIdx)
1369
m_HorizJoins[i]->savedIdx = OKIdx;
1370
}
1371
1372
}
1373
//------------------------------------------------------------------------------
1374
1375
PolyPt* Clipper::AddPolyPt(TEdge *e, const IntPoint &pt)
1376
{
1377
bool ToFront = (e->side == esLeft);
1378
if( e->outIdx < 0 )
1379
{
1380
PolyPt* newPolyPt = new PolyPt;
1381
newPolyPt->pt = pt;
1382
newPolyPt->isHole = IsHole(e);
1383
m_PolyPts.push_back(newPolyPt);
1384
newPolyPt->next = newPolyPt;
1385
newPolyPt->prev = newPolyPt;
1386
e->outIdx = m_PolyPts.size()-1;
1387
return newPolyPt;
1388
} else
1389
{
1390
PolyPt* pp = m_PolyPts[e->outIdx];
1391
if (ToFront && PointsEqual(pt, pp->pt)) return pp;
1392
if (!ToFront && PointsEqual(pt, pp->prev->pt)) return pp->prev;
1393
1394
PolyPt* newPolyPt = new PolyPt;
1395
newPolyPt->pt = pt;
1396
newPolyPt->isHole = pp->isHole;
1397
newPolyPt->next = pp;
1398
newPolyPt->prev = pp->prev;
1399
newPolyPt->prev->next = newPolyPt;
1400
pp->prev = newPolyPt;
1401
if (ToFront) m_PolyPts[e->outIdx] = newPolyPt;
1402
return newPolyPt;
1403
}
1404
}
1405
//------------------------------------------------------------------------------
1406
1407
void Clipper::ProcessHorizontals()
1408
{
1409
TEdge* horzEdge = m_SortedEdges;
1410
while( horzEdge )
1411
{
1412
DeleteFromSEL( horzEdge );
1413
ProcessHorizontal( horzEdge );
1414
horzEdge = m_SortedEdges;
1415
}
1416
}
1417
//------------------------------------------------------------------------------
1418
1419
bool Clipper::IsTopHorz(const long64 XPos)
1420
{
1421
TEdge* e = m_SortedEdges;
1422
while( e )
1423
{
1424
if( ( XPos >= std::min(e->xcurr, e->xtop) ) &&
1425
( XPos <= std::max(e->xcurr, e->xtop) ) ) return false;
1426
e = e->nextInSEL;
1427
}
1428
return true;
1429
}
1430
//------------------------------------------------------------------------------
1431
1432
bool IsMinima(TEdge *e)
1433
{
1434
return e && (e->prev->nextInLML != e) && (e->next->nextInLML != e);
1435
}
1436
//------------------------------------------------------------------------------
1437
1438
bool IsMaxima(TEdge *e, const long64 Y)
1439
{
1440
return e && e->ytop == Y && !e->nextInLML;
1441
}
1442
//------------------------------------------------------------------------------
1443
1444
bool IsIntermediate(TEdge *e, const long64 Y)
1445
{
1446
return e->ytop == Y && e->nextInLML;
1447
}
1448
//------------------------------------------------------------------------------
1449
1450
TEdge *GetMaximaPair(TEdge *e)
1451
{
1452
if( !IsMaxima(e->next, e->ytop) || (e->next->xtop != e->xtop) )
1453
return e->prev; else
1454
return e->next;
1455
}
1456
//------------------------------------------------------------------------------
1457
1458
void Clipper::SwapPositionsInAEL(TEdge *edge1, TEdge *edge2)
1459
{
1460
if( !( edge1->nextInAEL ) && !( edge1->prevInAEL ) ) return;
1461
if( !( edge2->nextInAEL ) && !( edge2->prevInAEL ) ) return;
1462
1463
if( edge1->nextInAEL == edge2 )
1464
{
1465
TEdge* next = edge2->nextInAEL;
1466
if( next ) next->prevInAEL = edge1;
1467
TEdge* prev = edge1->prevInAEL;
1468
if( prev ) prev->nextInAEL = edge2;
1469
edge2->prevInAEL = prev;
1470
edge2->nextInAEL = edge1;
1471
edge1->prevInAEL = edge2;
1472
edge1->nextInAEL = next;
1473
}
1474
else if( edge2->nextInAEL == edge1 )
1475
{
1476
TEdge* next = edge1->nextInAEL;
1477
if( next ) next->prevInAEL = edge2;
1478
TEdge* prev = edge2->prevInAEL;
1479
if( prev ) prev->nextInAEL = edge1;
1480
edge1->prevInAEL = prev;
1481
edge1->nextInAEL = edge2;
1482
edge2->prevInAEL = edge1;
1483
edge2->nextInAEL = next;
1484
}
1485
else
1486
{
1487
TEdge* next = edge1->nextInAEL;
1488
TEdge* prev = edge1->prevInAEL;
1489
edge1->nextInAEL = edge2->nextInAEL;
1490
if( edge1->nextInAEL ) edge1->nextInAEL->prevInAEL = edge1;
1491
edge1->prevInAEL = edge2->prevInAEL;
1492
if( edge1->prevInAEL ) edge1->prevInAEL->nextInAEL = edge1;
1493
edge2->nextInAEL = next;
1494
if( edge2->nextInAEL ) edge2->nextInAEL->prevInAEL = edge2;
1495
edge2->prevInAEL = prev;
1496
if( edge2->prevInAEL ) edge2->prevInAEL->nextInAEL = edge2;
1497
}
1498
1499
if( !edge1->prevInAEL ) m_ActiveEdges = edge1;
1500
else if( !edge2->prevInAEL ) m_ActiveEdges = edge2;
1501
}
1502
//------------------------------------------------------------------------------
1503
1504
void Clipper::SwapPositionsInSEL(TEdge *edge1, TEdge *edge2)
1505
{
1506
if( !( edge1->nextInSEL ) && !( edge1->prevInSEL ) ) return;
1507
if( !( edge2->nextInSEL ) && !( edge2->prevInSEL ) ) return;
1508
1509
if( edge1->nextInSEL == edge2 )
1510
{
1511
TEdge* next = edge2->nextInSEL;
1512
if( next ) next->prevInSEL = edge1;
1513
TEdge* prev = edge1->prevInSEL;
1514
if( prev ) prev->nextInSEL = edge2;
1515
edge2->prevInSEL = prev;
1516
edge2->nextInSEL = edge1;
1517
edge1->prevInSEL = edge2;
1518
edge1->nextInSEL = next;
1519
}
1520
else if( edge2->nextInSEL == edge1 )
1521
{
1522
TEdge* next = edge1->nextInSEL;
1523
if( next ) next->prevInSEL = edge2;
1524
TEdge* prev = edge2->prevInSEL;
1525
if( prev ) prev->nextInSEL = edge1;
1526
edge1->prevInSEL = prev;
1527
edge1->nextInSEL = edge2;
1528
edge2->prevInSEL = edge1;
1529
edge2->nextInSEL = next;
1530
}
1531
else
1532
{
1533
TEdge* next = edge1->nextInSEL;
1534
TEdge* prev = edge1->prevInSEL;
1535
edge1->nextInSEL = edge2->nextInSEL;
1536
if( edge1->nextInSEL ) edge1->nextInSEL->prevInSEL = edge1;
1537
edge1->prevInSEL = edge2->prevInSEL;
1538
if( edge1->prevInSEL ) edge1->prevInSEL->nextInSEL = edge1;
1539
edge2->nextInSEL = next;
1540
if( edge2->nextInSEL ) edge2->nextInSEL->prevInSEL = edge2;
1541
edge2->prevInSEL = prev;
1542
if( edge2->prevInSEL ) edge2->prevInSEL->nextInSEL = edge2;
1543
}
1544
1545
if( !edge1->prevInSEL ) m_SortedEdges = edge1;
1546
else if( !edge2->prevInSEL ) m_SortedEdges = edge2;
1547
}
1548
//------------------------------------------------------------------------------
1549
1550
TEdge* GetNextInAEL(TEdge *e, Direction dir)
1551
{
1552
if( dir == dLeftToRight ) return e->nextInAEL;
1553
else return e->prevInAEL;
1554
}
1555
//------------------------------------------------------------------------------
1556
1557
void Clipper::ProcessHorizontal(TEdge *horzEdge)
1558
{
1559
Direction dir;
1560
long64 horzLeft, horzRight;
1561
1562
if( horzEdge->xcurr < horzEdge->xtop )
1563
{
1564
horzLeft = horzEdge->xcurr;
1565
horzRight = horzEdge->xtop;
1566
dir = dLeftToRight;
1567
} else
1568
{
1569
horzLeft = horzEdge->xtop;
1570
horzRight = horzEdge->xcurr;
1571
dir = dRightToLeft;
1572
}
1573
1574
TEdge* eMaxPair;
1575
if( horzEdge->nextInLML ) eMaxPair = 0;
1576
else eMaxPair = GetMaximaPair(horzEdge);
1577
1578
TEdge* e = GetNextInAEL( horzEdge , dir );
1579
while( e )
1580
{
1581
TEdge* eNext = GetNextInAEL( e, dir );
1582
if( e->xcurr >= horzLeft && e->xcurr <= horzRight )
1583
{
1584
//ok, so far it looks like we're still in range of the horizontal edge
1585
if ( e->xcurr == horzEdge->xtop && horzEdge->nextInLML)
1586
{
1587
if (SlopesEqual(*e, *horzEdge->nextInLML))
1588
{
1589
//if output polygons share an edge, they'll need joining later ...
1590
if (horzEdge->outIdx >= 0 && e->outIdx >= 0)
1591
AddJoin(horzEdge->nextInLML, e, horzEdge->outIdx);
1592
break; //we've reached the end of the horizontal line
1593
}
1594
else if (e->dx < horzEdge->nextInLML->dx)
1595
//we really have got to the end of the intermediate horz edge so quit.
1596
//nb: More -ve slopes follow more +ve slopes ABOVE the horizontal.
1597
break;
1598
}
1599
1600
if( e == eMaxPair )
1601
{
1602
//horzEdge is evidently a maxima horizontal and we've arrived at its end.
1603
if (dir == dLeftToRight)
1604
IntersectEdges(horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
1605
else
1606
IntersectEdges(e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
1607
return;
1608
}
1609
else if( e->dx == horizontal && !IsMinima(e) && !(e->xcurr > e->xtop) )
1610
{
1611
//An overlapping horizontal edge. Overlapping horizontal edges are
1612
//processed as if layered with the current horizontal edge (horizEdge)
1613
//being infinitesimally lower that the next (e). Therfore, we
1614
//intersect with e only if e.xcurr is within the bounds of horzEdge ...
1615
if( dir == dLeftToRight )
1616
IntersectEdges( horzEdge , e, IntPoint(e->xcurr, horzEdge->ycurr),
1617
(IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
1618
else
1619
IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
1620
(IsTopHorz( e->xcurr ))? ipRight : ipBoth );
1621
}
1622
else if( dir == dLeftToRight )
1623
{
1624
IntersectEdges( horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr),
1625
(IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
1626
}
1627
else
1628
{
1629
IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
1630
(IsTopHorz( e->xcurr ))? ipRight : ipBoth );
1631
}
1632
SwapPositionsInAEL( horzEdge, e );
1633
}
1634
else if( dir == dLeftToRight &&
1635
e->xcurr > horzRight && m_SortedEdges ) break;
1636
else if( dir == dRightToLeft &&
1637
e->xcurr < horzLeft && m_SortedEdges ) break;
1638
e = eNext;
1639
} //end while
1640
1641
if( horzEdge->nextInLML )
1642
{
1643
if( horzEdge->outIdx >= 0 )
1644
AddPolyPt( horzEdge, IntPoint(horzEdge->xtop, horzEdge->ytop));
1645
UpdateEdgeIntoAEL( horzEdge );
1646
}
1647
else
1648
{
1649
if ( horzEdge->outIdx >= 0 )
1650
IntersectEdges( horzEdge, eMaxPair,
1651
IntPoint(horzEdge->xtop, horzEdge->ycurr), ipBoth);
1652
if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error");
1653
DeleteFromAEL(eMaxPair);
1654
DeleteFromAEL(horzEdge);
1655
}
1656
}
1657
//------------------------------------------------------------------------------
1658
1659
void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
1660
{
1661
if( !e->nextInLML ) throw
1662
clipperException("UpdateEdgeIntoAEL: invalid call");
1663
TEdge* AelPrev = e->prevInAEL;
1664
TEdge* AelNext = e->nextInAEL;
1665
e->nextInLML->outIdx = e->outIdx;
1666
if( AelPrev ) AelPrev->nextInAEL = e->nextInLML;
1667
else m_ActiveEdges = e->nextInLML;
1668
if( AelNext ) AelNext->prevInAEL = e->nextInLML;
1669
e->nextInLML->side = e->side;
1670
e->nextInLML->windDelta = e->windDelta;
1671
e->nextInLML->windCnt = e->windCnt;
1672
e->nextInLML->windCnt2 = e->windCnt2;
1673
e = e->nextInLML;
1674
e->prevInAEL = AelPrev;
1675
e->nextInAEL = AelNext;
1676
if( e->dx != horizontal )
1677
{
1678
InsertScanbeam( e->ytop );
1679
//if output polygons share an edge, they'll need joining later ...
1680
if (e->outIdx >= 0 && AelPrev && AelPrev->outIdx >= 0 &&
1681
AelPrev->xbot == e->xcurr && SlopesEqual(*e, *AelPrev))
1682
AddJoin(e, AelPrev);
1683
}
1684
}
1685
//------------------------------------------------------------------------------
1686
1687
bool Clipper::ProcessIntersections( const long64 topY)
1688
{
1689
if( !m_ActiveEdges ) return true;
1690
try {
1691
BuildIntersectList(topY);
1692
if ( !m_IntersectNodes) return true;
1693
if ( FixupIntersections() ) ProcessIntersectList();
1694
else return false;
1695
}
1696
catch(...) {
1697
m_SortedEdges = 0;
1698
DisposeIntersectNodes();
1699
throw clipperException("ProcessIntersections error");
1700
}
1701
return true;
1702
}
1703
//------------------------------------------------------------------------------
1704
1705
void Clipper::DisposeIntersectNodes()
1706
{
1707
while ( m_IntersectNodes )
1708
{
1709
IntersectNode* iNode = m_IntersectNodes->next;
1710
delete m_IntersectNodes;
1711
m_IntersectNodes = iNode;
1712
}
1713
}
1714
//------------------------------------------------------------------------------
1715
1716
void Clipper::BuildIntersectList(const long64 topY)
1717
{
1718
if ( !m_ActiveEdges ) return;
1719
1720
//prepare for sorting ...
1721
TEdge* e = m_ActiveEdges;
1722
e->tmpX = TopX( *e, topY );
1723
m_SortedEdges = e;
1724
m_SortedEdges->prevInSEL = 0;
1725
e = e->nextInAEL;
1726
while( e )
1727
{
1728
e->prevInSEL = e->prevInAEL;
1729
e->prevInSEL->nextInSEL = e;
1730
e->nextInSEL = 0;
1731
e->tmpX = TopX( *e, topY );
1732
e = e->nextInAEL;
1733
}
1734
1735
//bubblesort ...
1736
bool isModified = true;
1737
while( isModified && m_SortedEdges )
1738
{
1739
isModified = false;
1740
e = m_SortedEdges;
1741
while( e->nextInSEL )
1742
{
1743
TEdge *eNext = e->nextInSEL;
1744
IntPoint pt;
1745
if(e->tmpX > eNext->tmpX && IntersectPoint(*e, *eNext, pt))
1746
{
1747
AddIntersectNode( e, eNext, pt );
1748
SwapPositionsInSEL(e, eNext);
1749
isModified = true;
1750
}
1751
else
1752
e = eNext;
1753
}
1754
if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0;
1755
else break;
1756
}
1757
m_SortedEdges = 0;
1758
}
1759
//------------------------------------------------------------------------------
1760
1761
bool Process1Before2(IntersectNode &node1, IntersectNode &node2)
1762
{
1763
bool result;
1764
if (node1.pt.Y == node2.pt.Y)
1765
{
1766
if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1)
1767
{
1768
result = node2.pt.X > node1.pt.X;
1769
if (node2.edge1->dx > 0) return result; else return !result;
1770
}
1771
else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2)
1772
{
1773
result = node2.pt.X > node1.pt.X;
1774
if (node2.edge2->dx > 0) return result; else return !result;
1775
}
1776
else return node2.pt.X > node1.pt.X;
1777
}
1778
else return node1.pt.Y > node2.pt.Y;
1779
}
1780
//------------------------------------------------------------------------------
1781
1782
void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt)
1783
{
1784
IntersectNode* newNode = new IntersectNode;
1785
newNode->edge1 = e1;
1786
newNode->edge2 = e2;
1787
newNode->pt = pt;
1788
newNode->next = 0;
1789
if( !m_IntersectNodes ) m_IntersectNodes = newNode;
1790
else if( Process1Before2(*newNode, *m_IntersectNodes) )
1791
{
1792
newNode->next = m_IntersectNodes;
1793
m_IntersectNodes = newNode;
1794
}
1795
else
1796
{
1797
IntersectNode* iNode = m_IntersectNodes;
1798
while( iNode->next && Process1Before2(*iNode->next, *newNode) )
1799
iNode = iNode->next;
1800
newNode->next = iNode->next;
1801
iNode->next = newNode;
1802
}
1803
}
1804
//------------------------------------------------------------------------------
1805
1806
void Clipper::ProcessIntersectList()
1807
{
1808
while( m_IntersectNodes )
1809
{
1810
IntersectNode* iNode = m_IntersectNodes->next;
1811
{
1812
IntersectEdges( m_IntersectNodes->edge1 ,
1813
m_IntersectNodes->edge2 , m_IntersectNodes->pt, ipBoth );
1814
SwapPositionsInAEL( m_IntersectNodes->edge1 , m_IntersectNodes->edge2 );
1815
}
1816
delete m_IntersectNodes;
1817
m_IntersectNodes = iNode;
1818
}
1819
}
1820
//------------------------------------------------------------------------------
1821
1822
void Clipper::DoMaxima(TEdge *e, long64 topY)
1823
{
1824
TEdge* eMaxPair = GetMaximaPair(e);
1825
long64 X = e->xtop;
1826
TEdge* eNext = e->nextInAEL;
1827
while( eNext != eMaxPair )
1828
{
1829
if (!eNext) throw clipperException("DoMaxima error");
1830
IntersectEdges( e, eNext, IntPoint(X, topY), ipBoth );
1831
eNext = eNext->nextInAEL;
1832
}
1833
if( e->outIdx < 0 && eMaxPair->outIdx < 0 )
1834
{
1835
DeleteFromAEL( e );
1836
DeleteFromAEL( eMaxPair );
1837
}
1838
else if( e->outIdx >= 0 && eMaxPair->outIdx >= 0 )
1839
{
1840
IntersectEdges( e, eMaxPair, IntPoint(X, topY), ipNone );
1841
}
1842
else throw clipperException("DoMaxima error");
1843
}
1844
//------------------------------------------------------------------------------
1845
1846
void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY)
1847
{
1848
TEdge* e = m_ActiveEdges;
1849
while( e )
1850
{
1851
//1. process maxima, treating them as if they're 'bent' horizontal edges,
1852
// but exclude maxima with horizontal edges. nb: e can't be a horizontal.
1853
if( IsMaxima(e, topY) && GetMaximaPair(e)->dx != horizontal )
1854
{
1855
//'e' might be removed from AEL, as may any following edges so ...
1856
TEdge* ePrior = e->prevInAEL;
1857
DoMaxima(e, topY);
1858
if( !ePrior ) e = m_ActiveEdges;
1859
else e = ePrior->nextInAEL;
1860
}
1861
else
1862
{
1863
//2. promote horizontal edges, otherwise update xcurr and ycurr ...
1864
if( IsIntermediate(e, topY) && e->nextInLML->dx == horizontal )
1865
{
1866
if (e->outIdx >= 0)
1867
{
1868
AddPolyPt(e, IntPoint(e->xtop, e->ytop));
1869
AddHorzJoin(e->nextInLML, e->outIdx);
1870
}
1871
UpdateEdgeIntoAEL(e);
1872
AddEdgeToSEL(e);
1873
} else
1874
{
1875
//this just simplifies horizontal processing ...
1876
e->xcurr = TopX( *e, topY );
1877
e->ycurr = topY;
1878
}
1879
e = e->nextInAEL;
1880
}
1881
}
1882
1883
//3. Process horizontals at the top of the scanbeam ...
1884
ProcessHorizontals();
1885
1886
//4. Promote intermediate vertices ...
1887
e = m_ActiveEdges;
1888
while( e )
1889
{
1890
if( IsIntermediate( e, topY ) )
1891
{
1892
if( e->outIdx >= 0 ) AddPolyPt(e, IntPoint(e->xtop,e->ytop));
1893
UpdateEdgeIntoAEL(e);
1894
}
1895
e = e->nextInAEL;
1896
}
1897
}
1898
//------------------------------------------------------------------------------
1899
1900
PolyPt* FixupOutPolygon(PolyPt *p)
1901
{
1902
//FixupOutPolygon() - removes duplicate points and simplifies consecutive
1903
//parallel edges by removing the middle vertex.
1904
if (!p) return 0;
1905
PolyPt *pp = p, *result = p, *lastOK = 0;
1906
for (;;)
1907
{
1908
if (pp->prev == pp || pp->prev == pp->next )
1909
{
1910
DisposePolyPts(pp);
1911
return 0;
1912
}
1913
//test for duplicate points and for same slope (cross-product) ...
1914
if ( PointsEqual(pp->pt, pp->next->pt) ||
1915
SlopesEqual(pp->prev->pt, pp->pt, pp->next->pt) )
1916
{
1917
lastOK = 0;
1918
pp->prev->next = pp->next;
1919
pp->next->prev = pp->prev;
1920
PolyPt* tmp = pp;
1921
if (pp == result) result = pp->prev;
1922
pp = pp->prev;
1923
delete tmp;
1924
}
1925
else if (pp == lastOK) break;
1926
else
1927
{
1928
if (!lastOK) lastOK = pp;
1929
pp = pp->next;
1930
}
1931
}
1932
return result;
1933
}
1934
//------------------------------------------------------------------------------
1935
1936
void Clipper::BuildResult(Polygons &polypoly)
1937
{
1938
for (PolyPtList::size_type i = 0; i < m_PolyPts.size(); ++i)
1939
if (m_PolyPts[i])
1940
{
1941
m_PolyPts[i] = FixupOutPolygon(m_PolyPts[i]);
1942
//fix orientation ...
1943
PolyPt *p = m_PolyPts[i];
1944
if (p && p->isHole == IsClockwise(p))
1945
ReversePolyPtLinks(*p);
1946
}
1947
JoinCommonEdges();
1948
1949
int k = 0;
1950
polypoly.resize(m_PolyPts.size());
1951
for (unsigned i = 0; i < m_PolyPts.size(); ++i) {
1952
if (m_PolyPts[i]) {
1953
Polygon* pg = &polypoly[k];
1954
pg->clear();
1955
PolyPt* p = m_PolyPts[i];
1956
1957
do {
1958
pg->push_back(p->pt);
1959
p = p->next;
1960
} while (p != m_PolyPts[i]);
1961
//make sure each polygon has at least 3 vertices ...
1962
if (pg->size() < 3) pg->clear(); else k++;
1963
}
1964
}
1965
polypoly.resize(k);
1966
}
1967
//------------------------------------------------------------------------------
1968
1969
void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)
1970
{
1971
TEdge *e1 = int1.edge1;
1972
TEdge *e2 = int1.edge2;
1973
IntPoint p = int1.pt;
1974
1975
int1.edge1 = int2.edge1;
1976
int1.edge2 = int2.edge2;
1977
int1.pt = int2.pt;
1978
1979
int2.edge1 = e1;
1980
int2.edge2 = e2;
1981
int2.pt = p;
1982
}
1983
//------------------------------------------------------------------------------
1984
1985
bool Clipper::FixupIntersections()
1986
{
1987
if ( !m_IntersectNodes->next ) return true;
1988
1989
CopyAELToSEL();
1990
IntersectNode *int1 = m_IntersectNodes;
1991
IntersectNode *int2 = m_IntersectNodes->next;
1992
while (int2)
1993
{
1994
TEdge *e1 = int1->edge1;
1995
TEdge *e2;
1996
if (e1->prevInSEL == int1->edge2) e2 = e1->prevInSEL;
1997
else if (e1->nextInSEL == int1->edge2) e2 = e1->nextInSEL;
1998
else
1999
{
2000
//The current intersection is out of order, so try and swap it with
2001
//a subsequent intersection ...
2002
while (int2)
2003
{
2004
if (int2->edge1->nextInSEL == int2->edge2 ||
2005
int2->edge1->prevInSEL == int2->edge2) break;
2006
else int2 = int2->next;
2007
}
2008
if ( !int2 ) return false; //oops!!!
2009
2010
//found an intersect node that can be swapped ...
2011
SwapIntersectNodes(*int1, *int2);
2012
e1 = int1->edge1;
2013
e2 = int1->edge2;
2014
}
2015
SwapPositionsInSEL(e1, e2);
2016
int1 = int1->next;
2017
int2 = int1->next;
2018
}
2019
2020
m_SortedEdges = 0;
2021
2022
//finally, check the last intersection too ...
2023
return (int1->edge1->prevInSEL == int1->edge2 ||
2024
int1->edge1->nextInSEL == int1->edge2);
2025
}
2026
//------------------------------------------------------------------------------
2027
2028
bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
2029
{
2030
if (e2.xcurr == e1.xcurr) return e2.dx > e1.dx;
2031
else return e2.xcurr < e1.xcurr;
2032
}
2033
//------------------------------------------------------------------------------
2034
2035
void Clipper::InsertEdgeIntoAEL(TEdge *edge)
2036
{
2037
edge->prevInAEL = 0;
2038
edge->nextInAEL = 0;
2039
if( !m_ActiveEdges )
2040
{
2041
m_ActiveEdges = edge;
2042
}
2043
else if( E2InsertsBeforeE1(*m_ActiveEdges, *edge) )
2044
{
2045
edge->nextInAEL = m_ActiveEdges;
2046
m_ActiveEdges->prevInAEL = edge;
2047
m_ActiveEdges = edge;
2048
} else
2049
{
2050
TEdge* e = m_ActiveEdges;
2051
while( e->nextInAEL && !E2InsertsBeforeE1(*e->nextInAEL , *edge) )
2052
e = e->nextInAEL;
2053
edge->nextInAEL = e->nextInAEL;
2054
if( e->nextInAEL ) e->nextInAEL->prevInAEL = edge;
2055
edge->prevInAEL = e;
2056
e->nextInAEL = edge;
2057
}
2058
}
2059
//----------------------------------------------------------------------
2060
2061
void Clipper::DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2062
{
2063
AddPolyPt(edge1, pt);
2064
SwapSides(*edge1, *edge2);
2065
SwapPolyIndexes(*edge1, *edge2);
2066
}
2067
//----------------------------------------------------------------------
2068
2069
void Clipper::DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2070
{
2071
AddPolyPt(edge2, pt);
2072
SwapSides(*edge1, *edge2);
2073
SwapPolyIndexes(*edge1, *edge2);
2074
}
2075
//----------------------------------------------------------------------
2076
2077
void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2078
{
2079
AddPolyPt(edge1, pt);
2080
AddPolyPt(edge2, pt);
2081
SwapSides( *edge1 , *edge2 );
2082
SwapPolyIndexes( *edge1 , *edge2 );
2083
}
2084
//----------------------------------------------------------------------
2085
2086
bool Clipper::IsHole(TEdge *e)
2087
{
2088
bool hole = false;
2089
TEdge *e2 = m_ActiveEdges;
2090
while (e2 && e2 != e)
2091
{
2092
if (e2->outIdx >= 0) hole = !hole;
2093
e2 = e2->nextInAEL;
2094
}
2095
return hole;
2096
}
2097
//----------------------------------------------------------------------
2098
2099
PolyPt* DeletePolyPt(PolyPt* pp)
2100
{
2101
if (pp->next == pp)
2102
{
2103
delete pp;
2104
return 0;
2105
} else
2106
{
2107
PolyPt* result = pp->prev;
2108
pp->next->prev = result;
2109
result->next = pp->next;
2110
delete pp;
2111
return result;
2112
}
2113
}
2114
//------------------------------------------------------------------------------
2115
2116
PolyPt* FixSpikes(PolyPt *pp)
2117
{
2118
PolyPt *pp2 = pp, *pp3;
2119
PolyPt *result = pp;
2120
do
2121
{
2122
if (SlopesEqual(pp2->prev->pt, pp2->pt, pp2->next->pt) &&
2123
((((pp2->prev->pt.X < pp2->pt.X) == (pp2->next->pt.X < pp2->pt.X)) &&
2124
((pp2->prev->pt.X != pp2->pt.X) || (pp2->next->pt.X != pp2->pt.X))) ||
2125
((((pp2->prev->pt.Y < pp2->pt.Y) == (pp2->next->pt.Y < pp2->pt.Y))) &&
2126
((pp2->prev->pt.Y != pp2->pt.Y) || (pp2->next->pt.Y != pp2->pt.Y)))))
2127
{
2128
if (pp2 == result) result = pp2->prev;
2129
pp3 = pp2->next;
2130
DeletePolyPt(pp2);
2131
pp2 = pp3;
2132
} else
2133
pp2 = pp2->next;
2134
}
2135
while (pp2 != result);
2136
return result;
2137
}
2138
//------------------------------------------------------------------------------
2139
2140
void Clipper::JoinCommonEdges()
2141
{
2142
for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
2143
{
2144
PolyPt *pp1a, *pp1b, *pp2a, *pp2b;
2145
IntPoint pt1, pt2;
2146
JoinRec* j = m_Joins[i];
2147
2148
pp1a = m_PolyPts[j->poly1Idx];
2149
pp2a = m_PolyPts[j->poly2Idx];
2150
bool found = FindSegment(pp1a, j->pt1a, j->pt1b);
2151
if (found)
2152
{
2153
if (j->poly1Idx == j->poly2Idx)
2154
{
2155
//we're searching the same polygon for overlapping segments so
2156
//we really don't want segment 2 to be the same as segment 1 ...
2157
pp2a = pp1a->next;
2158
found = FindSegment(pp2a, j->pt2a, j->pt2b) && (pp2a != pp1a);
2159
}
2160
else
2161
found = FindSegment(pp2a, j->pt2a, j->pt2b);
2162
}
2163
2164
if (found)
2165
{
2166
if (PointsEqual(pp1a->next->pt, j->pt1b))
2167
pp1b = pp1a->next; else pp1b = pp1a->prev;
2168
if (PointsEqual(pp2a->next->pt, j->pt2b))
2169
pp2b = pp2a->next; else pp2b = pp2a->prev;
2170
if (GetOverlapSegment(pp1a->pt, pp1b->pt, pp2a->pt, pp2b->pt, pt1, pt2))
2171
{
2172
PolyPt *p1, *p2, *p3, *p4;
2173
//get p1 & p2 polypts - the overlap start & endpoints on poly1
2174
Position pos1 = GetPosition(pp1a->pt, pp1b->pt, pt1);
2175
if (pos1 == pFirst) p1 = pp1a;
2176
else if (pos1 == pSecond) p1 = pp1b;
2177
else p1 = InsertPolyPtBetween(pp1a, pp1b, pt1);
2178
Position pos2 = GetPosition(pp1a->pt, pp1b->pt, pt2);
2179
if (pos2 == pMiddle)
2180
{
2181
if (pos1 == pMiddle)
2182
{
2183
if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2))
2184
p2 = InsertPolyPtBetween(pp1a, p1, pt2); else
2185
p2 = InsertPolyPtBetween(p1, pp1b, pt2);
2186
}
2187
else if (pos2 == pFirst) p2 = pp1a;
2188
else p2 = pp1b;
2189
}
2190
else if (pos2 == pFirst) p2 = pp1a;
2191
else p2 = pp1b;
2192
//get p3 & p4 polypts - the overlap start & endpoints on poly2
2193
pos1 = GetPosition(pp2a->pt, pp2b->pt, pt1);
2194
if (pos1 == pFirst) p3 = pp2a;
2195
else if (pos1 == pSecond) p3 = pp2b;
2196
else p3 = InsertPolyPtBetween(pp2a, pp2b, pt1);
2197
pos2 = GetPosition(pp2a->pt, pp2b->pt, pt2);
2198
if (pos2 == pMiddle)
2199
{
2200
if (pos1 == pMiddle)
2201
{
2202
if (Pt3IsBetweenPt1AndPt2(pp2a->pt, p3->pt, pt2))
2203
p4 = InsertPolyPtBetween(pp2a, p3, pt2); else
2204
p4 = InsertPolyPtBetween(p3, pp2b, pt2);
2205
}
2206
else if (pos2 == pFirst) p4 = pp2a;
2207
else p4 = pp2b;
2208
}
2209
else if (pos2 == pFirst) p4 = pp2a;
2210
else p4 = pp2b;
2211
2212
//p1.pt should equal p3.pt and p2.pt should equal p4.pt here, so ...
2213
//join p1 to p3 and p2 to p4 ...
2214
if (p1->next == p2 && p3->prev == p4)
2215
{
2216
p1->next = p3;
2217
p3->prev = p1;
2218
p2->prev = p4;
2219
p4->next = p2;
2220
}
2221
else if (p1->prev == p2 && p3->next == p4)
2222
{
2223
p1->prev = p3;
2224
p3->next = p1;
2225
p2->next = p4;
2226
p4->prev = p2;
2227
}
2228
else
2229
continue; //an orientation is probably wrong
2230
2231
//delete duplicate points ...
2232
if (PointsEqual(p1->pt, p3->pt)) DeletePolyPt(p3);
2233
if (PointsEqual(p2->pt, p4->pt)) DeletePolyPt(p4);
2234
2235
if (j->poly2Idx == j->poly1Idx)
2236
{
2237
//instead of joining two polygons, we've just created
2238
//a new one by splitting one polygon into two.
2239
m_PolyPts[j->poly1Idx] = p1;
2240
m_PolyPts.push_back(p2);
2241
j->poly2Idx = m_PolyPts.size()-1;
2242
2243
if (PointInPolygon(p2->pt, p1)) SetHoleState(p2, !p1->isHole);
2244
else if (PointInPolygon(p1->pt, p2)) SetHoleState(p1, !p2->isHole);
2245
2246
//now fixup any subsequent m_Joins that match this polygon
2247
for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
2248
{
2249
JoinRec* j2 = m_Joins[k];
2250
if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2))
2251
j2->poly1Idx = j->poly2Idx;
2252
if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2))
2253
j2->poly2Idx = j->poly2Idx;
2254
}
2255
} else
2256
{
2257
//having joined 2 polygons together, delete the obsolete pointer ...
2258
m_PolyPts[j->poly2Idx] = 0;
2259
2260
//now fixup any subsequent fJoins that match this polygon
2261
for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
2262
{
2263
JoinRec* j2 = m_Joins[k];
2264
if (j2->poly1Idx == j->poly2Idx) j2->poly1Idx = j->poly1Idx;
2265
if (j2->poly2Idx == j->poly2Idx) j2->poly2Idx = j->poly1Idx;
2266
}
2267
j->poly2Idx = j->poly1Idx;
2268
}
2269
2270
//now cleanup redundant edges too ...
2271
m_PolyPts[j->poly1Idx] = FixSpikes(p1);
2272
if (j->poly2Idx != j->poly1Idx)
2273
m_PolyPts[j->poly2Idx] = FixSpikes(p2);
2274
2275
}
2276
}
2277
}
2278
}
2279
2280
//------------------------------------------------------------------------------
2281
// OffsetPolygon functions ...
2282
//------------------------------------------------------------------------------
2283
2284
struct DoublePoint
2285
{
2286
double X;
2287
double Y;
2288
DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
2289
};
2290
2291
Polygon BuildArc(const IntPoint &pt,
2292
const double a1, const double a2, const double r)
2293
{
2294
int steps = std::max(6, int(std::sqrt(std::abs(r)) * std::abs(a2 - a1)));
2295
Polygon result(steps);
2296
int n = steps - 1;
2297
double da = (a2 - a1) / n;
2298
double a = a1;
2299
for (int i = 0; i <= n; ++i)
2300
{
2301
result[i].X = pt.X + Round(std::cos(a)*r);
2302
result[i].Y = pt.Y + Round(std::sin(a)*r);
2303
a += da;
2304
}
2305
return result;
2306
}
2307
//------------------------------------------------------------------------------
2308
2309
DoublePoint GetUnitNormal( const IntPoint &pt1, const IntPoint &pt2)
2310
{
2311
double dx = static_cast<double>(pt2.X - pt1.X);
2312
double dy = static_cast<double>(pt2.Y - pt1.Y);
2313
if( ( dx == 0 ) && ( dy == 0 ) ) return DoublePoint( 0, 0 );
2314
2315
double f = 1 *1.0/ std::sqrt( dx*dx + dy*dy );
2316
dx *= f;
2317
dy *= f;
2318
return DoublePoint(dy, -dx);
2319
}
2320
//------------------------------------------------------------------------------
2321
2322
Polygons OffsetPolygons(const Polygons &pts, const float &delta)
2323
{
2324
if (delta == 0) return pts;
2325
2326
double deltaSq = delta*delta;
2327
Polygons result(pts.size());
2328
2329
for (int j = 0; j < (int)pts.size(); ++j)
2330
{
2331
int highI = (int)pts[j].size() -1;
2332
//to minimize artefacts, strip out those polygons where
2333
//it's shrinking and where its area < Sqr(delta) ...
2334
double a1 = Area(pts[j]);
2335
if (delta < 0) { if (a1 > 0 && a1 < deltaSq) highI = 0;}
2336
else if (a1 < 0 && -a1 < deltaSq) highI = 0; //nb: a hole if area < 0
2337
2338
Polygon pg;
2339
pg.reserve(highI*2+2);
2340
2341
if (highI < 2)
2342
{
2343
result.push_back(pg);
2344
continue;
2345
}
2346
2347
std::vector < DoublePoint > normals(highI+1);
2348
normals[0] = GetUnitNormal(pts[j][highI], pts[j][0]);
2349
for (int i = 1; i <= highI; ++i)
2350
normals[i] = GetUnitNormal(pts[j][i-1], pts[j][i]);
2351
2352
for (int i = 0; i < highI; ++i)
2353
{
2354
pg.push_back(IntPoint(pts[j][i].X + Round(delta *normals[i].X),
2355
pts[j][i].Y + Round(delta *normals[i].Y)));
2356
pg.push_back(IntPoint(pts[j][i].X + Round(delta *normals[i+1].X),
2357
pts[j][i].Y + Round(delta *normals[i+1].Y)));
2358
}
2359
pg.push_back(IntPoint(pts[j][highI].X + Round(delta *normals[highI].X),
2360
pts[j][highI].Y + Round(delta *normals[highI].Y)));
2361
pg.push_back(IntPoint(pts[j][highI].X + Round(delta *normals[0].X),
2362
pts[j][highI].Y + Round(delta *normals[0].Y)));
2363
2364
//round off reflex angles (ie > 180 deg) unless it's almost flat (ie < 10deg angle) ...
2365
//cross product normals < 0 -> reflex angle; dot product normals == 1 -> no angle
2366
if ((normals[highI].X *normals[0].Y - normals[0].X *normals[highI].Y) *delta > 0 &&
2367
(normals[0].X *normals[highI].X + normals[0].Y *normals[highI].Y) < 0.985)
2368
{
2369
double a1 = std::atan2(normals[highI].Y, normals[highI].X);
2370
double a2 = std::atan2(normals[0].Y, normals[0].X);
2371
if (delta > 0 && a2 < a1) a2 = a2 + pi*2;
2372
else if (delta < 0 && a2 > a1) a2 = a2 - pi*2;
2373
Polygon arc = BuildArc(pts[j][highI], a1, a2, delta);
2374
Polygon::iterator it = pg.begin() +highI*2+1;
2375
pg.insert(it, arc.begin(), arc.end());
2376
}
2377
for (int i = highI; i > 0; --i)
2378
if ((normals[i-1].X*normals[i].Y - normals[i].X*normals[i-1].Y) *delta > 0 &&
2379
(normals[i].X*normals[i-1].X + normals[i].Y*normals[i-1].Y) < 0.985)
2380
{
2381
double a1 = std::atan2(normals[i-1].Y, normals[i-1].X);
2382
double a2 = std::atan2(normals[i].Y, normals[i].X);
2383
if (delta > 0 && a2 < a1) a2 = a2 + pi*2;
2384
else if (delta < 0 && a2 > a1) a2 = a2 - pi*2;
2385
Polygon arc = BuildArc(pts[j][i-1], a1, a2, delta);
2386
Polygon::iterator it = pg.begin() +(i-1)*2+1;
2387
pg.insert(it, arc.begin(), arc.end());
2388
}
2389
result.push_back(pg);
2390
}
2391
2392
//finally, clean up untidy corners ...
2393
Clipper c4;
2394
c4.AddPolygons(result, ptSubject);
2395
if (delta > 0){
2396
if(!c4.Execute(ctUnion, result, pftNonZero, pftNonZero))
2397
result.clear();
2398
}
2399
else
2400
{
2401
IntRect r = c4.GetBounds();
2402
Polygon outer(4);
2403
outer[0] = IntPoint(r.left-10, r.bottom+10);
2404
outer[1] = IntPoint(r.right+10, r.bottom+10);
2405
outer[2] = IntPoint(r.right+10, r.top-10);
2406
outer[3] = IntPoint(r.left-10, r.top-10);
2407
c4.AddPolygon(outer, ptSubject);
2408
if (c4.Execute(ctUnion, result, pftNonZero, pftNonZero))
2409
{
2410
Polygons::iterator it = result.begin();
2411
result.erase(it);
2412
}
2413
else
2414
result.clear();
2415
}
2416
return result;
2417
}
2418
//------------------------------------------------------------------------------
2419
2420
} //namespace clipper
2421
2422
Loggerhead is a web-based interface for Breezy
Version: 2.0.1