Skip to content

Commit c40f982

Browse files
AngusJohnsonAngusJohnson
committed
Fixed a potential infinite loop in clipping operations (#975 & #979)
1 parent fa165fe commit c40f982

File tree

3 files changed

+20
-16
lines changed

3 files changed

+20
-16
lines changed

‎CPP/Clipper2Lib/src/clipper.engine.cpp

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
/*******************************************************************************
22
* Author : Angus Johnson *
3-
* Date : 4 May 2025 *
3+
* Date : 30 May 2025 *
44
* Website : https://www.angusj.com *
55
* Copyright : Angus Johnson 2010-2025 *
66
* Purpose : This is the main polygon clipping module *
@@ -2119,10 +2119,9 @@ namespace Clipper2Lib {
21192119
e->prev_in_sel = e->prev_in_ael;
21202120
e->next_in_sel = e->next_in_ael;
21212121
e->jump = e->next_in_sel;
2122-
if (e->join_with == JoinWith::Left)
2123-
e->curr_x = e->prev_in_ael->curr_x; // also avoids complications
2124-
else
2125-
e->curr_x = TopX(*e, top_y);
2122+
// it is safe to ignore 'joined' edges here because
2123+
// if necessary they will be split in IntersectEdges()
2124+
e->curr_x = TopX(*e, top_y);
21262125
e = e->next_in_ael;
21272126
}
21282127
}

‎CSharp/Clipper2Lib/Clipper.Engine.cs

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
/*******************************************************************************
22
* Author : Angus Johnson *
3-
* Date : 4 May 2025 *
3+
* Date : 30 May 2025 *
44
* Website : https://www.angusj.com *
55
* Copyright : Angus Johnson 2010-2025 *
66
* Purpose : This is the main polygon clipping module *
@@ -1822,8 +1822,9 @@ private void AdjustCurrXAndCopyToSEL(long topY)
18221822
ae.prevInSEL = ae.prevInAEL;
18231823
ae.nextInSEL = ae.nextInAEL;
18241824
ae.jump = ae.nextInSEL;
1825-
ae.curX = ae.joinWith == JoinWith.Left ? ae.prevInAEL!.curX : // this also avoids complications
1826-
TopX(ae, topY);
1825+
// it is safe to ignore 'joined' edges here because
1826+
// if necessary they will be split in IntersectEdges()
1827+
ae.curX = TopX(ae, topY);
18271828
// NB don't update ae.curr.Y yet (see AddNewIntersectNode)
18281829
ae = ae.nextInAEL;
18291830
}

‎Delphi/Clipper2Lib/Clipper.Engine.pas

Lines changed: 12 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
(*******************************************************************************
44
* Author : Angus Johnson *
5-
* Date : 10 May 2025 *
5+
* Date : 30 May 2025 *
66
* Website : https://www.angusj.com *
77
* Copyright : Angus Johnson 2010-2025 *
88
* Purpose : This is the main polygon clipping module *
@@ -942,8 +942,6 @@ function PointInOpPolygon(const pt: TPoint64; op: POutPt): TPointInPolygonResult
942942
function Path1InsidePath2(const op1, op2: POutPt): Boolean;
943943
var
944944
op: POutPt;
945-
mp: TPoint64;
946-
path: TPath64;
947945
pip: TPointInPolygonResult;
948946
begin
949947
// accommodate rounding errors
@@ -2390,6 +2388,8 @@ procedure TClipperBase.CheckJoinLeft(e: PActive;
23902388
not IsHotEdge(e) or not IsHotEdge(prev) or
23912389
IsHorizontal(e) or IsHorizontal(prev) or
23922390
IsOpen(e) or IsOpen(prev) then Exit;
2391+
// Also exit if pt is within a unit of the top of either edge
2392+
// unless one of the edges is almost horizontal ...
23932393
if ((pt.Y < e.top.Y +2) or (pt.Y < prev.top.Y +2)) and
23942394
((e.bot.Y > pt.Y) or (prev.bot.Y > pt.Y)) then Exit; // (#490)
23952395

@@ -2421,6 +2421,9 @@ procedure TClipperBase.CheckJoinRight(e: PActive;
24212421
not IsHotEdge(e) or not IsHotEdge(next) or
24222422
IsHorizontal(e) or IsHorizontal(next) or
24232423
IsOpen(e) or IsOpen(next) then Exit;
2424+
2425+
// Also exit if pt is within a unit of the top of either edge
2426+
// unless one of the edges is almost horizontal ...
24242427
if ((pt.Y < e.top.Y +2) or (pt.Y < next.top.Y +2)) and
24252428
((e.bot.Y > pt.Y) or (next.bot.Y > pt.Y)) then Exit; // (#490)
24262429

@@ -2633,6 +2636,7 @@ procedure TClipperBase.IntersectEdges(e1, e2: PActive; pt: TPoint64);
26332636
end;
26342637

26352638
// MANAGING CLOSED PATHS FROM HERE ON
2639+
26362640
if IsJoined(e1) then UndoJoin(e1, pt);
26372641
if IsJoined(e2) then UndoJoin(e2, pt);
26382642

@@ -2839,10 +2843,9 @@ procedure TClipperBase.AdjustCurrXAndCopyToSEL(topY: Int64);
28392843
e.prevInSEL := e.prevInAEL;
28402844
e.nextInSEL := e.nextInAEL;
28412845
e.jump := e.nextInSEL;
2842-
if (e.joinedWith = jwLeft) then
2843-
e.currX := e.prevInAEL.currX // this also avoids complications
2844-
else
2845-
e.currX := TopX(e, topY);
2846+
// it is safe to ignore 'joined' edges here because
2847+
// if necessary they will be split in IntersectEdges()
2848+
e.currX := TopX(e, topY);
28462849
e := e.nextInAEL;
28472850
end;
28482851
end;
@@ -3402,7 +3405,7 @@ procedure TClipperBase.DoHorizontal(horzEdge: PActive);
34023405
Result := assigned(e);
34033406
// nb: this block isn't yet redundant
34043407
end
3405-
else if horzEdge.currX < horzEdge.top.X then
3408+
else if (horzEdge.currX < horzEdge.top.X) then
34063409
begin
34073410
horzLeft := horzEdge.currX;
34083411
horzRight := horzEdge.top.X;
@@ -3442,6 +3445,7 @@ procedure TClipperBase.DoHorizontal(horzEdge: PActive);
34423445
Y := horzEdge.bot.Y;
34433446
maxVertex := nil;
34443447

3448+
// maxVertex - manages consecutive horizontal edges
34453449
if horzIsOpen then
34463450
maxVertex := GetCurrYMaximaVertexOpen(horzEdge) else
34473451
maxVertex := GetCurrYMaximaVertex(horzEdge);

0 commit comments

Comments
 (0)