#include <src/clipper/clipper.hpp>

Inheritance diagram for ClipperLib::Clipper:

Collaboration diagram for ClipperLib::Clipper:

Public Member Functions
	Clipper (int initOptions=0)

	~Clipper ()

void	Clear ()

bool	Execute (ClipType clipType, Paths &solution, PolyFillType fillType=pftEvenOdd)

bool	Execute (ClipType clipType, Paths &solution, PolyFillType subjFillType, PolyFillType clipFillType)

bool	Execute (ClipType clipType, PolyTree &polytree, PolyFillType fillType=pftEvenOdd)

bool	Execute (ClipType clipType, PolyTree &polytree, PolyFillType subjFillType, PolyFillType clipFillType)

bool	ReverseSolution () const

void	ReverseSolution (bool value)

bool	StrictlySimple () const

void	StrictlySimple (bool value)

bool	AddPath (const Path &pg, PolyType PolyTyp, bool Closed)

template<typename PathsProvider >
bool	AddPaths (PathsProvider &&paths_provider, PolyType PolyTyp, bool Closed)

IntRect	GetBounds ()

bool	PreserveCollinear () const

void	PreserveCollinear (bool value)

Protected Types
using	Edges = std::vector< TEdge, Allocator< TEdge > >

Protected Member Functions
void	Reset ()

virtual bool	ExecuteInternal ()

bool	AddPathInternal (const Path &pg, int highI, PolyType PolyTyp, bool Closed, TEdge *edges)

TEdge *	AddBoundsToLML (TEdge *e, bool IsClosed)

TEdge *	ProcessBound (TEdge *E, bool IsClockwise)

TEdge *	DescendToMin (TEdge *&E)

void	AscendToMax (TEdge *&E, bool Appending, bool IsClosed)

Protected Attributes
std::vector< LocalMinimum, Allocator< LocalMinimum > >	m_MinimaList

std::vector< Edges, Allocator< Edges > >	m_edges

bool	m_PreserveCollinear

bool	m_HasOpenPaths

Static Protected Attributes
static constexpr const bool	m_UseFullRange = false

Private Types
using	cInts = std::vector< cInt, Allocator< cInt > >

Private Member Functions
void	SetWindingCount (TEdge &edge) const

bool	IsEvenOddFillType (const TEdge &edge) const

bool	IsEvenOddAltFillType (const TEdge &edge) const

void	InsertLocalMinimaIntoAEL (const cInt botY)

void	InsertEdgeIntoAEL (TEdge edge, TEdge startEdge)

void	AddEdgeToSEL (TEdge *edge)

void	CopyAELToSEL ()

void	DeleteFromSEL (TEdge *e)

void	DeleteFromAEL (TEdge *e)

void	UpdateEdgeIntoAEL (TEdge *&e)

void	SwapPositionsInSEL (TEdge edge1, TEdge edge2)

bool	IsContributing (const TEdge &edge) const

bool	IsTopHorz (const cInt XPos)

void	SwapPositionsInAEL (TEdge edge1, TEdge edge2)

void	DoMaxima (TEdge *e)

void	ProcessHorizontals ()

void	ProcessHorizontal (TEdge *horzEdge)

void	AddLocalMaxPoly (TEdge e1, TEdge e2, const IntPoint &pt)

OutPt *	AddLocalMinPoly (TEdge e1, TEdge e2, const IntPoint &pt)

OutRec *	GetOutRec (int idx)

void	AppendPolygon (TEdge e1, TEdge e2)

void	IntersectEdges (TEdge e1, TEdge e2, IntPoint &pt)

OutRec *	CreateOutRec ()

OutPt *	AddOutPt (TEdge *e, const IntPoint &pt)

OutPt *	GetLastOutPt (TEdge *e)

OutPt *	AllocateOutPt ()

OutPt *	DupOutPt (OutPt *outPt, bool InsertAfter)

void	DisposeOutPt (OutPt *pt)

void	DisposeOutPts (OutPt *&pp)

void	DisposeAllOutRecs ()

bool	ProcessIntersections (const cInt topY)

void	BuildIntersectList (const cInt topY)

void	ProcessEdgesAtTopOfScanbeam (const cInt topY)

void	BuildResult (Paths &polys)

void	BuildResult2 (PolyTree &polytree)

void	SetHoleState (TEdge e, OutRec outrec)

bool	FixupIntersectionOrder ()

void	FixupOutPolygon (OutRec &outrec)

void	FixupOutPolyline (OutRec &outrec)

bool	FindOwnerFromSplitRecs (OutRec &outRec, OutRec *&currOrfl)

void	FixHoleLinkage (OutRec &outrec)

bool	JoinPoints (Join j, OutRec outRec1, OutRec *outRec2)

bool	JoinHorz (OutPt op1, OutPt op1b, OutPt op2, OutPt op2b, const IntPoint &Pt, bool DiscardLeft)

void	JoinCommonEdges ()

void	DoSimplePolygons ()

void	FixupFirstLefts1 (OutRec OldOutRec, OutRec NewOutRec)

void	FixupFirstLefts2 (OutRec OldOutRec, OutRec NewOutRec)

Private Attributes
std::deque< OutRec, Allocator< OutRec > >	m_PolyOuts

std::deque< std::array< OutPt, m_OutPtsChunkSize >, Allocator< std::array< OutPt, m_OutPtsChunkSize > > >	m_OutPts

OutPt *	m_OutPtsFree

size_t	m_OutPtsChunkLast

std::vector< Join, Allocator< Join > >	m_Joins

std::vector< Join, Allocator< Join > >	m_GhostJoins

std::vector< IntersectNode, Allocator< IntersectNode > >	m_IntersectList

ClipType	m_ClipType

std::priority_queue< cInt, cInts >	m_Scanbeam

cInts	m_Maxima

TEdge *	m_ActiveEdges

TEdge *	m_SortedEdges

PolyFillType	m_ClipFillType

PolyFillType	m_SubjFillType

bool	m_ReverseOutput

bool	m_UsingPolyTree

bool	m_StrictSimple

Static Private Attributes
static constexpr const size_t	m_OutPtsChunkSize = 32

Detailed Description

Member Typedef Documentation

◆ cInts

using ClipperLib::Clipper::cInts = std::vector<cInt, Allocator<cInt> >

private

◆ Edges

using ClipperLib::ClipperBase::Edges = std::vector<TEdge, Allocator<TEdge> >

protectedinherited

Constructor & Destructor Documentation

◆ Clipper()

ClipperLib::Clipper::Clipper ( int initOptions = 0 )

                                : 
  ClipperBase(),
  m_OutPtsFree(nullptr),
  m_OutPtsChunkLast(m_OutPtsChunkSize),
  m_ActiveEdges(nullptr),
  m_SortedEdges(nullptr)
{
  m_ReverseOutput = ((initOptions & ioReverseSolution) != 0);
  m_StrictSimple = ((initOptions & ioStrictlySimple) != 0);
  m_PreserveCollinear = ((initOptions & ioPreserveCollinear) != 0);
  m_HasOpenPaths = false;
#ifdef CLIPPERLIB_USE_XYZ  
  m_ZFill = 0;
#endif
}

References ClipperLib::ioPreserveCollinear, ClipperLib::ioReverseSolution, ClipperLib::ioStrictlySimple, ClipperLib::ClipperBase::m_HasOpenPaths, ClipperLib::ClipperBase::m_PreserveCollinear, m_ReverseOutput, and m_StrictSimple.

◆ ~Clipper()

ClipperLib::Clipper::~Clipper ( )

inline

423{ Clear(); }

ClipperLib::Clipper::Clear

void Clear()

Definition clipper.hpp:424

Member Function Documentation

◆ AddBoundsToLML()

TEdge * ClipperLib::ClipperBase::AddBoundsToLML	(	TEdge *	e,
		bool	IsClosed
	)

protectedinherited

◆ AddEdgeToSEL()

void ClipperLib::Clipper::AddEdgeToSEL ( TEdge * edge )

private

{
  //SEL pointers in PEdge are reused to build a list of horizontal edges.
  //However, we don't need to worry about order with horizontal edge processing.
  if( !m_SortedEdges )
  {
    m_SortedEdges = edge;
    edge->PrevInSEL = 0;
    edge->NextInSEL = 0;
  }
  else
  {
    edge->NextInSEL = m_SortedEdges;
    edge->PrevInSEL = 0;
    m_SortedEdges->PrevInSEL = edge;
    m_SortedEdges = edge;
  }
}

References m_SortedEdges, ClipperLib::TEdge::NextInSEL, and ClipperLib::TEdge::PrevInSEL.

Referenced by InsertLocalMinimaIntoAEL(), and ProcessEdgesAtTopOfScanbeam().

Here is the caller graph for this function:

◆ AddLocalMaxPoly()

void ClipperLib::Clipper::AddLocalMaxPoly	(	TEdge *	e1,
		TEdge *	e2,
		const IntPoint &	pt
	)

private

{
  AddOutPt( e1, Pt );
  if (e2->WindDelta == 0) AddOutPt(e2, Pt);
  if( e1->OutIdx == e2->OutIdx )
  {
    e1->OutIdx = Unassigned;
    e2->OutIdx = Unassigned;
  }
  else if (e1->OutIdx < e2->OutIdx) 
    AppendPolygon(e1, e2); 
  else 
    AppendPolygon(e2, e1);
}

References AddOutPt(), AppendPolygon(), ClipperLib::TEdge::OutIdx, ClipperLib::Unassigned, and ClipperLib::TEdge::WindDelta.

Referenced by DoMaxima(), IntersectEdges(), and ProcessHorizontal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddLocalMinPoly()

OutPt * ClipperLib::Clipper::AddLocalMinPoly	(	TEdge *	e1,
		TEdge *	e2,
		const IntPoint &	pt
	)

private

{
  OutPt* result;
  TEdge *e, *prevE;
  if (IsHorizontal(*e2) || ( e1->Dx > e2->Dx ))
  {
    result = AddOutPt(e1, Pt);
    e2->OutIdx = e1->OutIdx;
    e1->Side = esLeft;
    e2->Side = esRight;
    e = e1;
    if (e->PrevInAEL == e2)
      prevE = e2->PrevInAEL; 
    else
      prevE = e->PrevInAEL;
  } else
  {
    result = AddOutPt(e2, Pt);
    e1->OutIdx = e2->OutIdx;
    e1->Side = esRight;
    e2->Side = esLeft;
    e = e2;
    if (e->PrevInAEL == e1)
        prevE = e1->PrevInAEL;
    else
        prevE = e->PrevInAEL;
  }
 
  if (prevE && prevE->OutIdx >= 0 &&
      (TopX(*prevE, Pt.y()) == TopX(*e, Pt.y())) &&
      SlopesEqual(*e, *prevE, m_UseFullRange) &&
      (e->WindDelta != 0) && (prevE->WindDelta != 0))
  {
    OutPt* outPt = AddOutPt(prevE, Pt);
    m_Joins.emplace_back(Join(result, outPt, e->Top));
  }
  return result;
}

References AddOutPt(), ClipperLib::TEdge::Dx, ClipperLib::esLeft, ClipperLib::esRight, ClipperLib::IsHorizontal(), m_Joins, ClipperLib::ClipperBase::m_UseFullRange, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::PrevInAEL, ClipperLib::TEdge::Side, ClipperLib::SlopesEqual(), ClipperLib::TEdge::Top, ClipperLib::TopX(), and ClipperLib::TEdge::WindDelta.

Referenced by InsertLocalMinimaIntoAEL(), and IntersectEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddOutPt()

OutPt * ClipperLib::Clipper::AddOutPt	(	TEdge *	e,
		const IntPoint &	pt
	)

private

{
  if(  e->OutIdx < 0 )
  {
    OutRec *outRec = CreateOutRec();
    outRec->IsOpen = (e->WindDelta == 0);
    OutPt* newOp = this->AllocateOutPt();
    outRec->Pts = newOp;
    newOp->Idx = outRec->Idx;
    newOp->Pt = pt;
    newOp->Next = newOp;
    newOp->Prev = newOp;
    if (!outRec->IsOpen)
      SetHoleState(e, outRec);
    e->OutIdx = outRec->Idx;
    return newOp;
  } else
  {
    OutRec *outRec = &m_PolyOuts[e->OutIdx];
    //OutRec.Pts is the 'Left-most' point & OutRec.Pts.Prev is the 'Right-most'
    OutPt* op = outRec->Pts;
 
  bool ToFront = (e->Side == esLeft);
  if (ToFront && (pt == op->Pt)) return op;
    else if (!ToFront && (pt == op->Prev->Pt)) return op->Prev;
 
    OutPt* newOp = this->AllocateOutPt();
    newOp->Idx = outRec->Idx;
    newOp->Pt = pt;
    newOp->Next = op;
    newOp->Prev = op->Prev;
    newOp->Prev->Next = newOp;
    op->Prev = newOp;
    if (ToFront) outRec->Pts = newOp;
    return newOp;
  }
}

References AllocateOutPt(), CreateOutRec(), ClipperLib::esLeft, ClipperLib::OutPt::Idx, ClipperLib::OutRec::Idx, ClipperLib::OutRec::IsOpen, m_PolyOuts, ClipperLib::OutPt::Next, ClipperLib::TEdge::OutIdx, ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, ClipperLib::OutRec::Pts, SetHoleState(), ClipperLib::TEdge::Side, and ClipperLib::TEdge::WindDelta.

Referenced by AddLocalMaxPoly(), AddLocalMinPoly(), DoMaxima(), InsertLocalMinimaIntoAEL(), IntersectEdges(), ProcessEdgesAtTopOfScanbeam(), and ProcessHorizontal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddPath()

bool ClipperLib::ClipperBase::AddPath	(	const Path &	pg,
		PolyType	PolyTyp,
		bool	Closed
	)

inherited

{
  // Remove duplicate end point from a closed input path.
  // Remove duplicate points from the end of the input path.
  int highI = (int)pg.size() -1;
  if (Closed) 
    while (highI > 0 && (pg[highI] == pg[0])) 
      --highI;
  while (highI > 0 && (pg[highI] == pg[highI -1])) 
    --highI;
  if ((Closed && highI < 2) || (!Closed && highI < 1))
    return false;
 
  // Allocate a new edge array.
  Edges edges(highI + 1);
  // Fill in the edge array.
  bool result = AddPathInternal(pg, highI, PolyTyp, Closed, edges.data());
  if (result)
    // Success, remember the edge array.
    m_edges.emplace_back(std::move(edges));
  return result;
}

Referenced by ClipperLib::ClipperOffset::Execute(), ClipperLib::ClipperOffset::Execute(), Slic3r::fix_after_inner_offset(), Slic3r::fix_after_outer_offset(), and Slic3r::shrink_paths().

Here is the caller graph for this function:

◆ AddPathInternal()

bool ClipperLib::ClipperBase::AddPathInternal	(	const Path &	pg,
		int	highI,
		PolyType	PolyTyp,
		bool	Closed,
		TEdge *	edges
	)

protectedinherited

{
#ifdef use_lines
  if (!Closed && PolyTyp == ptClip)
    throw clipperException("AddPath: Open paths must be subject.");
#else
  if (!Closed)
    throw clipperException("AddPath: Open paths have been disabled.");
#endif
 
  assert(highI >= 0 && highI < pg.size());
 
  //1. Basic (first) edge initialization ...
  try
  {
    edges[1].Curr = pg[1];
#ifdef CLIPPERLIB_INT32
    RangeTest(pg[0]);
    RangeTest(pg[highI]);
#else
    RangeTest(pg[0], m_UseFullRange);
    RangeTest(pg[highI], m_UseFullRange);
#endif // CLIPPERLIB_INT32
    InitEdge(&edges[0], &edges[1], &edges[highI], pg[0]);
    InitEdge(&edges[highI], &edges[0], &edges[highI-1], pg[highI]);
    for (int i = highI - 1; i >= 1; --i)
    {
#ifdef CLIPPERLIB_INT32
      RangeTest(pg[i]);
#else
      RangeTest(pg[i], m_UseFullRange);
#endif // CLIPPERLIB_INT32
      InitEdge(&edges[i], &edges[i+1], &edges[i-1], pg[i]);
    }
  }
  catch(...)
  {
    throw; //range test fails
  }
  TEdge *eStart = &edges[0];
 
  //2. Remove duplicate vertices, and (when closed) collinear edges ...
  TEdge *E = eStart, *eLoopStop = eStart;
  for (;;)
  {
    //nb: allows matching start and end points when not Closed ...
    if (E->Curr == E->Next->Curr && (Closed || E->Next != eStart))
    {
      if (E == E->Next) break;
      if (E == eStart) eStart = E->Next;
      E = RemoveEdge(E);
      eLoopStop = E;
      continue;
    }
    if (E->Prev == E->Next) 
      break; //only two vertices
    else if (Closed &&
      SlopesEqual(E->Prev->Curr, E->Curr, E->Next->Curr, m_UseFullRange) && 
      (!m_PreserveCollinear ||
      !Pt2IsBetweenPt1AndPt3(E->Prev->Curr, E->Curr, E->Next->Curr)))
    {
      //Collinear edges are allowed for open paths but in closed paths
      //the default is to merge adjacent collinear edges into a single edge.
      //However, if the PreserveCollinear property is enabled, only overlapping
      //collinear edges (ie spikes) will be removed from closed paths.
      if (E == eStart) eStart = E->Next;
      E = RemoveEdge(E);
      E = E->Prev;
      eLoopStop = E;
      continue;
    }
    E = E->Next;
    if ((E == eLoopStop) || (!Closed && E->Next == eStart)) break;
  }
 
  if ((!Closed && (E == E->Next)) || (Closed && (E->Prev == E->Next)))
  {
    return false;
  }
 
  if (!Closed)
  { 
    m_HasOpenPaths = true;
    eStart->Prev->OutIdx = Skip;
  }
 
  //3. Do second stage of edge initialization ...
  // IsFlat means all vertices have the same Y coordinate.
  bool IsFlat = true;
  E = eStart;
  do
  {
    InitEdge2(*E, PolyTyp);
    E = E->Next;
    if (IsFlat && E->Curr.y() != eStart->Curr.y()) IsFlat = false;
  }
  while (E != eStart);
 
  //4. Finally, add edge bounds to LocalMinima list ...
 
  //Totally flat paths must be handled differently when adding them
  //to LocalMinima list to avoid endless loops etc ...
  if (IsFlat) 
  {
    if (Closed) 
    {
      return false;
    }
    E->Prev->OutIdx = Skip;
    LocalMinimum locMin;
    locMin.Y = E->Bot.y();
    locMin.LeftBound = 0;
    locMin.RightBound = E;
    locMin.RightBound->Side = esRight;
    locMin.RightBound->WindDelta = 0;
    for (;;)
    {
      if (E->Bot.x() != E->Prev->Top.x()) ReverseHorizontal(*E);
      if (E->Next->OutIdx == Skip) break;
      E->NextInLML = E->Next;
      E = E->Next;
    }
    m_MinimaList.emplace_back(locMin);
    return true;
  }
 
  bool leftBoundIsForward;
  TEdge* EMin = 0;
 
  //workaround to avoid an endless loop in the while loop below when
  //open paths have matching start and end points ...
  if (E->Prev->Bot == E->Prev->Top) E = E->Next;
 
  // Find local minima and store them into a Local Minima List.
  // Multiple Local Minima could be created for a single path.
  for (;;)
  {
    E = FindNextLocMin(E);
    if (E == EMin) break;
    else if (!EMin) EMin = E;
 
    //E and E.Prev now share a local minima (left aligned if horizontal).
    //Compare their slopes to find which starts which bound ...
    LocalMinimum locMin;
    locMin.Y = E->Bot.y();
    if (E->Dx < E->Prev->Dx) 
    {
      locMin.LeftBound = E->Prev;
      locMin.RightBound = E;
      leftBoundIsForward = false; //Q.nextInLML = Q.prev
    } else
    {
      locMin.LeftBound = E;
      locMin.RightBound = E->Prev;
      leftBoundIsForward = true; //Q.nextInLML = Q.next
    }
    locMin.LeftBound->Side = esLeft;
    locMin.RightBound->Side = esRight;
 
    if (!Closed) locMin.LeftBound->WindDelta = 0;
    else if (locMin.LeftBound->Next == locMin.RightBound)
      locMin.LeftBound->WindDelta = -1;
    else locMin.LeftBound->WindDelta = 1;
    locMin.RightBound->WindDelta = -locMin.LeftBound->WindDelta;
 
    E = ProcessBound(locMin.LeftBound, leftBoundIsForward);
    if (E->OutIdx == Skip) E = ProcessBound(E, leftBoundIsForward);
 
    TEdge* E2 = ProcessBound(locMin.RightBound, !leftBoundIsForward);
    if (E2->OutIdx == Skip) E2 = ProcessBound(E2, !leftBoundIsForward);
 
    if (locMin.LeftBound->OutIdx == Skip)
      locMin.LeftBound = 0;
    else if (locMin.RightBound->OutIdx == Skip)
      locMin.RightBound = 0;
    m_MinimaList.emplace_back(locMin);
    if (!leftBoundIsForward) E = E2;
  }
  return true;
}

References ClipperLib::TEdge::Curr, ClipperLib::esLeft, ClipperLib::esRight, ClipperLib::FindNextLocMin(), ClipperLib::InitEdge(), ClipperLib::InitEdge2(), ClipperLib::LocalMinimum::LeftBound, ClipperLib::TEdge::Next, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::Prev, ClipperLib::Pt2IsBetweenPt1AndPt3(), ClipperLib::ptClip, ClipperLib::RangeTest(), ClipperLib::RemoveEdge(), ClipperLib::ReverseHorizontal(), ClipperLib::LocalMinimum::RightBound, ClipperLib::TEdge::Side, ClipperLib::Skip, ClipperLib::SlopesEqual(), ClipperLib::TEdge::WindDelta, and ClipperLib::LocalMinimum::Y.

Here is the call graph for this function:

◆ AddPaths()

template<typename PathsProvider >

bool ClipperLib::ClipperBase::AddPaths	(	PathsProvider &&	paths_provider,
		PolyType	PolyTyp,
		bool	Closed
	)

inlineinherited

  {
    size_t num_paths = paths_provider.size();
    if (num_paths == 0)
        return false;
    if (num_paths == 1)
        return AddPath(*paths_provider.begin(), PolyTyp, Closed);
 
    std::vector<int, Allocator<int>> num_edges(num_paths, 0);
    int num_edges_total = 0;
    size_t i = 0;
    for (const Path &pg : paths_provider) {
      // Remove duplicate end point from a closed input path.
      // Remove duplicate points from the end of the input path.
      int highI = (int)pg.size() -1;
      if (Closed) 
        while (highI > 0 && (pg[highI] == pg[0])) 
          --highI;
      while (highI > 0 && (pg[highI] == pg[highI -1])) 
        --highI;
      if ((Closed && highI < 2) || (!Closed && highI < 1))
        highI = -1;
      num_edges[i ++] = highI + 1;
      num_edges_total += highI + 1;
    }
    if (num_edges_total == 0)
      return false;
 
    // Allocate a new edge array.
    std::vector<TEdge, Allocator<TEdge>> edges(num_edges_total);
    // Fill in the edge array.
    bool result = false;
    TEdge *p_edge = edges.data();
    i = 0;
    for (const Path &pg : paths_provider) {
      if (num_edges[i]) {
        bool res = AddPathInternal(pg, num_edges[i] - 1, PolyTyp, Closed, p_edge);
        if (res) {
          p_edge += num_edges[i];
          result = true;
        }
      }
      ++ i;
    }
    if (result)
      // At least some edges were generated. Remember the edge array.
      m_edges.emplace_back(std::move(edges));
    return result;
  }

Referenced by Slic3r::_clipper_pl_open(), Slic3r::clipper_do(), Slic3r::clipper_union(), ClipperLib::ClipperOffset::Execute(), ClipperLib::ClipperOffset::Execute(), Slic3r::expolygons_to_zpaths_shrunk(), Slic3r::shrink_paths(), Slic3r::top_level_islands(), Slic3r::variable_offset_inner(), Slic3r::variable_offset_inner_ex(), Slic3r::variable_offset_outer(), Slic3r::variable_offset_outer_ex(), and Slic3r::Algorithm::wavefront_clip().

Here is the caller graph for this function:

◆ AllocateOutPt()

OutPt * ClipperLib::Clipper::AllocateOutPt ( )

private

{
  OutPt *pt;
  if (m_OutPtsFree) {
    // Recycle some of the already released points.
    pt = m_OutPtsFree;
    m_OutPtsFree = pt->Next;
  } else if (m_OutPtsChunkLast < m_OutPtsChunkSize) {
    // Get a point from the last chunk.
    pt = &m_OutPts.back()[m_OutPtsChunkLast ++];
  } else {
    // The last chunk is full. Allocate a new one.
    m_OutPts.emplace_back();
    m_OutPtsChunkLast = 1;
    pt = &m_OutPts.back().front();
  }
  return pt;
}

References m_OutPts, m_OutPtsChunkLast, m_OutPtsChunkSize, m_OutPtsFree, and ClipperLib::OutPt::Next.

Referenced by AddOutPt(), and DupOutPt().

Here is the caller graph for this function:

◆ AppendPolygon()

void ClipperLib::Clipper::AppendPolygon	(	TEdge *	e1,
		TEdge *	e2
	)

private

{
  //get the start and ends of both output polygons ...
  OutRec *outRec1 = &m_PolyOuts[e1->OutIdx];
  OutRec *outRec2 = &m_PolyOuts[e2->OutIdx];
 
  OutRec *holeStateRec;
  if (Param1RightOfParam2(outRec1, outRec2)) 
    holeStateRec = outRec2;
  else if (Param1RightOfParam2(outRec2, outRec1)) 
    holeStateRec = outRec1;
  else 
    holeStateRec = GetLowermostRec(outRec1, outRec2);
 
  //get the start and ends of both output polygons and
  //join e2 poly onto e1 poly and delete pointers to e2 ...
 
  OutPt* p1_lft = outRec1->Pts;
  OutPt* p1_rt = p1_lft->Prev;
  OutPt* p2_lft = outRec2->Pts;
  OutPt* p2_rt = p2_lft->Prev;
 
  EdgeSide Side;
  //join e2 poly onto e1 poly and delete pointers to e2 ...
  if(  e1->Side == esLeft )
  {
    if(  e2->Side == esLeft )
    {
      //z y x a b c
      ReversePolyPtLinks(p2_lft);
      p2_lft->Next = p1_lft;
      p1_lft->Prev = p2_lft;
      p1_rt->Next = p2_rt;
      p2_rt->Prev = p1_rt;
      outRec1->Pts = p2_rt;
    } else
    {
      //x y z a b c
      p2_rt->Next = p1_lft;
      p1_lft->Prev = p2_rt;
      p2_lft->Prev = p1_rt;
      p1_rt->Next = p2_lft;
      outRec1->Pts = p2_lft;
    }
    Side = esLeft;
  } else
  {
    if(  e2->Side == esRight )
    {
      //a b c z y x
      ReversePolyPtLinks(p2_lft);
      p1_rt->Next = p2_rt;
      p2_rt->Prev = p1_rt;
      p2_lft->Next = p1_lft;
      p1_lft->Prev = p2_lft;
    } else
    {
      //a b c x y z
      p1_rt->Next = p2_lft;
      p2_lft->Prev = p1_rt;
      p1_lft->Prev = p2_rt;
      p2_rt->Next = p1_lft;
    }
    Side = esRight;
  }
 
  outRec1->BottomPt = 0;
  if (holeStateRec == outRec2)
  {
    if (outRec2->FirstLeft != outRec1)
      outRec1->FirstLeft = outRec2->FirstLeft;
    outRec1->IsHole = outRec2->IsHole;
  }
  outRec2->Pts = 0;
  outRec2->BottomPt = 0;
  outRec2->FirstLeft = outRec1;
 
  int OKIdx = e1->OutIdx;
  int ObsoleteIdx = e2->OutIdx;
 
  e1->OutIdx = Unassigned; //nb: safe because we only get here via AddLocalMaxPoly
  e2->OutIdx = Unassigned;
 
  TEdge* e = m_ActiveEdges;
  while( e )
  {
    if( e->OutIdx == ObsoleteIdx )
    {
      e->OutIdx = OKIdx;
      e->Side = Side;
      break;
    }
    e = e->NextInAEL;
  }
 
  outRec2->Idx = outRec1->Idx;
}

References ClipperLib::OutRec::BottomPt, ClipperLib::esLeft, ClipperLib::esRight, ClipperLib::OutRec::FirstLeft, ClipperLib::GetLowermostRec(), ClipperLib::OutRec::Idx, ClipperLib::OutRec::IsHole, m_ActiveEdges, m_PolyOuts, ClipperLib::OutPt::Next, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::OutIdx, ClipperLib::Param1RightOfParam2(), ClipperLib::OutPt::Prev, ClipperLib::OutRec::Pts, ClipperLib::ReversePolyPtLinks(), ClipperLib::TEdge::Side, and ClipperLib::Unassigned.

Referenced by AddLocalMaxPoly().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AscendToMax()

void ClipperLib::ClipperBase::AscendToMax	(	TEdge *&	E,
		bool	Appending,
		bool	IsClosed
	)

protectedinherited

◆ BuildIntersectList()

void ClipperLib::Clipper::BuildIntersectList ( const cInt topY )

private

{
  if ( !m_ActiveEdges ) return;
 
  //prepare for sorting ...
  TEdge* e = m_ActiveEdges;
  m_SortedEdges = e;
  while( e )
  {
    e->PrevInSEL = e->PrevInAEL;
    e->NextInSEL = e->NextInAEL;
    e->Curr.x() = TopX( *e, topY );
    e = e->NextInAEL;
  }
 
  //bubblesort ...
  bool isModified;
  do
  {
    isModified = false;
    e = m_SortedEdges;
    while( e->NextInSEL )
    {
      TEdge *eNext = e->NextInSEL;
      IntPoint Pt;
      if(e->Curr.x() > eNext->Curr.x())
      {
        IntersectPoint(*e, *eNext, Pt);
        m_IntersectList.emplace_back(IntersectNode(e, eNext, Pt));
        SwapPositionsInSEL(e, eNext);
        isModified = true;
      }
      else
        e = eNext;
    }
    if( e->PrevInSEL ) e->PrevInSEL->NextInSEL = 0;
    else break;
  }
  while ( isModified );
  m_SortedEdges = 0; //important
}

References ClipperLib::TEdge::Curr, ClipperLib::IntersectPoint(), m_ActiveEdges, m_IntersectList, m_SortedEdges, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::NextInSEL, ClipperLib::TEdge::PrevInAEL, ClipperLib::TEdge::PrevInSEL, SwapPositionsInSEL(), and ClipperLib::TopX().

Referenced by ProcessIntersections().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ BuildResult()

void ClipperLib::Clipper::BuildResult ( Paths & polys )

private

{
  polys.reserve(m_PolyOuts.size());
  for (OutRec &outRec : m_PolyOuts)
  {
    assert(! outRec.IsOpen);
    if (!outRec.Pts) continue;
    Path pg;
    OutPt* p = outRec.Pts->Prev;
    int cnt = PointCount(p);
    if (cnt < 2) continue;
    pg.reserve(cnt);
    for (int i = 0; i < cnt; ++i)
    {
      pg.emplace_back(p->Pt);
      p = p->Prev;
    }
    polys.emplace_back(std::move(pg));
  }
}

References m_PolyOuts, ClipperLib::PointCount(), ClipperLib::OutPt::Prev, and ClipperLib::OutPt::Pt.

Referenced by Execute().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ BuildResult2()

void ClipperLib::Clipper::BuildResult2 ( PolyTree & polytree )

private

{
    polytree.Clear();
    polytree.AllNodes.reserve(m_PolyOuts.size());
    //add each output polygon/contour to polytree ...
    for (OutRec &outRec : m_PolyOuts)
    {
        int cnt = PointCount(outRec.Pts);
        if ((outRec.IsOpen && cnt < 2) || (!outRec.IsOpen && cnt < 3))
          // Ignore an invalid output loop or a polyline.
          continue;
 
        //skip OutRecs that (a) contain outermost polygons or
        //(b) already have the correct owner/child linkage ...
        if (outRec.FirstLeft &&
            (outRec.IsHole == outRec.FirstLeft->IsHole || ! outRec.FirstLeft->Pts)) {
          OutRec* orfl = outRec.FirstLeft;
          while (orfl && ((orfl->IsHole == outRec.IsHole) || !orfl->Pts))
              orfl = orfl->FirstLeft;
          outRec.FirstLeft = orfl;
        }
 
        //nb: polytree takes ownership of all the PolyNodes
        polytree.AllNodes.emplace_back(PolyNode());
        PolyNode* pn = &polytree.AllNodes.back();
        outRec.PolyNd = pn;
        pn->Parent = 0;
        pn->Index = 0;
        pn->Contour.reserve(cnt);
        OutPt *op = outRec.Pts->Prev;
        for (int j = 0; j < cnt; j++)
        {
            pn->Contour.emplace_back(op->Pt);
            op = op->Prev;
        }
    }
 
    //fixup PolyNode links etc ...
    polytree.Childs.reserve(m_PolyOuts.size());
    for (OutRec &outRec : m_PolyOuts)
    {
        if (!outRec.PolyNd) continue;
        if (outRec.IsOpen) 
        {
          outRec.PolyNd->m_IsOpen = true;
          polytree.AddChild(*outRec.PolyNd);
        }
        else if (outRec.FirstLeft && outRec.FirstLeft->PolyNd) 
          outRec.FirstLeft->PolyNd->AddChild(*outRec.PolyNd);
        else
          polytree.AddChild(*outRec.PolyNd);
    }
}

References ClipperLib::PolyNode::AddChild(), ClipperLib::PolyTree::AllNodes, ClipperLib::PolyNode::Childs, ClipperLib::PolyTree::Clear(), ClipperLib::PolyNode::Contour, ClipperLib::OutRec::FirstLeft, ClipperLib::PolyNode::Index, ClipperLib::OutRec::IsHole, m_PolyOuts, ClipperLib::PolyNode::Parent, ClipperLib::PointCount(), ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, and ClipperLib::OutRec::Pts.

Referenced by Execute().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Clear()

void ClipperLib::Clipper::Clear ( )

inline

424{ ClipperBase::Clear(); DisposeAllOutRecs(); }

ClipperLib::ClipperBase::Clear

void Clear()

Definition clipper.cpp:959

ClipperLib::Clipper::DisposeAllOutRecs

void DisposeAllOutRecs()

Definition clipper.cpp:1187

Referenced by Slic3r::expolygons_to_zpaths_shrunk(), Slic3r::top_level_islands(), Slic3r::variable_offset_inner(), and Slic3r::variable_offset_outer().

Here is the caller graph for this function:

◆ CopyAELToSEL()

void ClipperLib::Clipper::CopyAELToSEL ( )

private

{
  TEdge* e = m_ActiveEdges;
  m_SortedEdges = e;
  while ( e )
  {
    e->PrevInSEL = e->PrevInAEL;
    e->NextInSEL = e->NextInAEL;
    e = e->NextInAEL;
  }
}

References m_ActiveEdges, m_SortedEdges, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::NextInSEL, ClipperLib::TEdge::PrevInAEL, and ClipperLib::TEdge::PrevInSEL.

Referenced by FixupIntersectionOrder().

Here is the caller graph for this function:

◆ CreateOutRec()

OutRec * ClipperLib::Clipper::CreateOutRec ( )

private

{
  m_PolyOuts.emplace_back();
  OutRec &result = m_PolyOuts.back();
  result.IsHole = false;
  result.IsOpen = false;
  result.FirstLeft = 0;
  result.Pts = 0;
  result.BottomPt = 0;
  result.PolyNd = 0;
  result.Idx = (int)m_PolyOuts.size()-1;
  return &result;
}

References ClipperLib::OutRec::BottomPt, ClipperLib::OutRec::FirstLeft, ClipperLib::OutRec::Idx, ClipperLib::OutRec::IsHole, ClipperLib::OutRec::IsOpen, m_PolyOuts, ClipperLib::OutRec::PolyNd, and ClipperLib::OutRec::Pts.

Referenced by AddOutPt(), DoSimplePolygons(), and JoinCommonEdges().

Here is the caller graph for this function:

◆ DeleteFromAEL()

void ClipperLib::Clipper::DeleteFromAEL ( TEdge * e )

private

{
  TEdge* AelPrev = e->PrevInAEL;
  TEdge* AelNext = e->NextInAEL;
  if(  !AelPrev &&  !AelNext && (e != m_ActiveEdges) ) return; //already deleted
  if( AelPrev ) AelPrev->NextInAEL = AelNext;
  else m_ActiveEdges = AelNext;
  if( AelNext ) AelNext->PrevInAEL = AelPrev;
  e->NextInAEL = 0;
  e->PrevInAEL = 0;
}

References m_ActiveEdges, ClipperLib::TEdge::NextInAEL, and ClipperLib::TEdge::PrevInAEL.

Referenced by DoMaxima(), and ProcessHorizontal().

Here is the caller graph for this function:

◆ DeleteFromSEL()

void ClipperLib::Clipper::DeleteFromSEL ( TEdge * e )

private

{
  TEdge* SelPrev = e->PrevInSEL;
  TEdge* SelNext = e->NextInSEL;
  if( !SelPrev &&  !SelNext && (e != m_SortedEdges) ) return; //already deleted
  if( SelPrev ) SelPrev->NextInSEL = SelNext;
  else m_SortedEdges = SelNext;
  if( SelNext ) SelNext->PrevInSEL = SelPrev;
  e->NextInSEL = 0;
  e->PrevInSEL = 0;
}

References m_SortedEdges, ClipperLib::TEdge::NextInSEL, and ClipperLib::TEdge::PrevInSEL.

Referenced by ProcessHorizontals().

Here is the caller graph for this function:

◆ DescendToMin()

TEdge * ClipperLib::ClipperBase::DescendToMin ( TEdge *& E )

protectedinherited

◆ DisposeAllOutRecs()

void ClipperLib::Clipper::DisposeAllOutRecs ( )

private

{
  m_OutPts.clear();
  m_OutPtsFree = nullptr;
  m_OutPtsChunkLast = m_OutPtsChunkSize;
  m_PolyOuts.clear();
}

References m_OutPts, m_OutPtsChunkLast, m_OutPtsChunkSize, m_OutPtsFree, and m_PolyOuts.

Referenced by Execute(), and Execute().

Here is the caller graph for this function:

◆ DisposeOutPt()

void ClipperLib::Clipper::DisposeOutPt ( OutPt * pt )

inlineprivate

513{ pt->Next = m_OutPtsFree; m_OutPtsFree = pt; }

References ClipperLib::OutPt::Next.

Referenced by FixupOutPolygon(), and FixupOutPolyline().

Here is the caller graph for this function:

◆ DisposeOutPts()

void ClipperLib::Clipper::DisposeOutPts ( OutPt *& pp )

inlineprivate

514{ if (pp != nullptr) { pp->Prev->Next = m_OutPtsFree; m_OutPtsFree = pp; } }

References ClipperLib::OutPt::Next, and ClipperLib::OutPt::Prev.

Referenced by FixupOutPolygon(), and FixupOutPolyline().

Here is the caller graph for this function:

◆ DoMaxima()

void ClipperLib::Clipper::DoMaxima ( TEdge * e )

private

{
  TEdge* eMaxPair = GetMaximaPair(e);
  if (!eMaxPair)
  {
    if (e->OutIdx >= 0)
      AddOutPt(e, e->Top);
    DeleteFromAEL(e);
    return;
  }
 
  TEdge* eNext = e->NextInAEL;
  while(eNext && eNext != eMaxPair)
  {
    IntersectEdges(e, eNext, e->Top);
    SwapPositionsInAEL(e, eNext);
    eNext = e->NextInAEL;
  }
 
  if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned)
  {
    DeleteFromAEL(e);
    DeleteFromAEL(eMaxPair);
  }
  else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 )
  {
    if (e->OutIdx >= 0) AddLocalMaxPoly(e, eMaxPair, e->Top);
    DeleteFromAEL(e);
    DeleteFromAEL(eMaxPair);
  }
#ifdef use_lines
  else if (e->WindDelta == 0)
  {
    if (e->OutIdx >= 0) 
    {
      AddOutPt(e, e->Top);
      e->OutIdx = Unassigned;
    }
    DeleteFromAEL(e);
 
    if (eMaxPair->OutIdx >= 0)
    {
      AddOutPt(eMaxPair, e->Top);
      eMaxPair->OutIdx = Unassigned;
    }
    DeleteFromAEL(eMaxPair);
  } 
#endif
  else throw clipperException("DoMaxima error");
}

References AddLocalMaxPoly(), AddOutPt(), DeleteFromAEL(), ClipperLib::GetMaximaPair(), IntersectEdges(), ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::OutIdx, SwapPositionsInAEL(), ClipperLib::TEdge::Top, ClipperLib::Unassigned, and ClipperLib::TEdge::WindDelta.

Referenced by ProcessEdgesAtTopOfScanbeam().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DoSimplePolygons()

void ClipperLib::Clipper::DoSimplePolygons ( )

private

{
  size_t i = 0;
  while (i < m_PolyOuts.size()) 
  {
    OutRec &outrec = m_PolyOuts[i++];
    OutPt* op = outrec.Pts;
    if (!op || outrec.IsOpen) continue;
    do //for each Pt in Polygon until duplicate found do ...
    {
      OutPt* op2 = op->Next;
      while (op2 != outrec.Pts) 
      {
        if ((op->Pt == op2->Pt) && op2->Next != op && op2->Prev != op) 
        {
          //split the polygon into two ...
          OutPt* op3 = op->Prev;
          OutPt* op4 = op2->Prev;
          op->Prev = op4;
          op4->Next = op;
          op2->Prev = op3;
          op3->Next = op2;
 
          outrec.Pts = op;
          OutRec* outrec2 = CreateOutRec();
          outrec2->Pts = op2;
          UpdateOutPtIdxs(*outrec2);
          if (Poly2ContainsPoly1(outrec2->Pts, outrec.Pts))
          {
            //OutRec2 is contained by OutRec1 ...
            outrec2->IsHole = !outrec.IsHole;
            outrec2->FirstLeft = &outrec;
            // For each m_PolyOuts, replace FirstLeft from outRec2 to outrec.
            if (m_UsingPolyTree) FixupFirstLefts2(outrec2, &outrec);
          }
          else
            if (Poly2ContainsPoly1(outrec.Pts, outrec2->Pts))
          {
            //OutRec1 is contained by OutRec2 ...
            outrec2->IsHole = outrec.IsHole;
            outrec.IsHole = !outrec2->IsHole;
            outrec2->FirstLeft = outrec.FirstLeft;
            outrec.FirstLeft = outrec2;
            // For each m_PolyOuts, replace FirstLeft from outrec to outrec2.
            if (m_UsingPolyTree) FixupFirstLefts2(&outrec, outrec2);
            }
            else
          {
            //the 2 polygons are separate ...
            outrec2->IsHole = outrec.IsHole;
            outrec2->FirstLeft = outrec.FirstLeft;
            // For each polygon of m_PolyOuts, replace FirstLeft from outrec to outrec2 if the polygon is inside outRec2.
            //FIXME This is potentially very expensive! O(n^3)!
            if (m_UsingPolyTree) FixupFirstLefts1(&outrec, outrec2);
          }
          op2 = op; //ie get ready for the Next iteration
        }
        op2 = op2->Next;
      }
      op = op->Next;
    }
    while (op != outrec.Pts);
  }
}

References CreateOutRec(), ClipperLib::OutRec::FirstLeft, FixupFirstLefts1(), FixupFirstLefts2(), ClipperLib::OutRec::IsHole, ClipperLib::OutRec::IsOpen, m_PolyOuts, m_UsingPolyTree, ClipperLib::OutPt::Next, ClipperLib::Poly2ContainsPoly1(), ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, ClipperLib::OutRec::Pts, and ClipperLib::UpdateOutPtIdxs().

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DupOutPt()

OutPt * ClipperLib::Clipper::DupOutPt	(	OutPt *	outPt,
		bool	InsertAfter
	)

private

{
  OutPt* result = this->AllocateOutPt();
  result->Pt = outPt->Pt;
  result->Idx = outPt->Idx;
  if (InsertAfter)
  {
    result->Next = outPt->Next;
    result->Prev = outPt;
    outPt->Next->Prev = result;
    outPt->Next = result;
  } 
  else
  {
    result->Prev = outPt->Prev;
    result->Next = outPt;
    outPt->Prev->Next = result;
    outPt->Prev = result;
  }
  return result;
}

References AllocateOutPt(), ClipperLib::OutPt::Idx, ClipperLib::OutPt::Next, ClipperLib::OutPt::Prev, and ClipperLib::OutPt::Pt.

Referenced by JoinHorz(), and JoinPoints().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Execute() [1/4]

bool ClipperLib::Clipper::Execute	(	ClipType	clipType,
		Paths &	solution,
		PolyFillType	fillType = `pftEvenOdd`
	)

inline

428 { return Execute(clipType, solution, fillType, fillType); }

ClipperLib::Clipper::Execute

bool Execute(ClipType clipType, Paths &solution, PolyFillType fillType=pftEvenOdd)

Definition clipper.hpp:425

Referenced by Slic3r::_clipper_pl_open(), Slic3r::clipper_do(), Slic3r::clipper_union(), ClipperLib::ClipperOffset::Execute(), ClipperLib::ClipperOffset::Execute(), Slic3r::expolygons_to_zpaths_shrunk(), Slic3r::fix_after_inner_offset(), Slic3r::fix_after_outer_offset(), Slic3r::shrink_paths(), Slic3r::top_level_islands(), Slic3r::variable_offset_inner(), Slic3r::variable_offset_inner_ex(), Slic3r::variable_offset_outer(), Slic3r::variable_offset_outer_ex(), and Slic3r::Algorithm::wavefront_clip().

Here is the caller graph for this function:

◆ Execute() [2/4]

bool ClipperLib::Clipper::Execute	(	ClipType	clipType,
		Paths &	solution,
		PolyFillType	subjFillType,
		PolyFillType	clipFillType
	)

{
  if (m_HasOpenPaths)
    throw clipperException("Error: PolyTree struct is needed for open path clipping.");
  solution.clear();
  m_SubjFillType = subjFillType;
  m_ClipFillType = clipFillType;
  m_ClipType = clipType;
  m_UsingPolyTree = false;
  bool succeeded = ExecuteInternal();
  if (succeeded) BuildResult(solution);
  DisposeAllOutRecs();
  return succeeded;
}

References BuildResult(), DisposeAllOutRecs(), ExecuteInternal(), m_ClipFillType, m_ClipType, ClipperLib::ClipperBase::m_HasOpenPaths, m_SubjFillType, and m_UsingPolyTree.

Here is the call graph for this function:

◆ Execute() [3/4]

bool ClipperLib::Clipper::Execute	(	ClipType	clipType,
		PolyTree &	polytree,
		PolyFillType	fillType = `pftEvenOdd`
	)

inline

436 { return Execute(clipType, polytree, fillType, fillType); }

◆ Execute() [4/4]

bool ClipperLib::Clipper::Execute	(	ClipType	clipType,
		PolyTree &	polytree,
		PolyFillType	subjFillType,
		PolyFillType	clipFillType
	)

{
  m_SubjFillType = subjFillType;
  m_ClipFillType = clipFillType;
  m_ClipType = clipType;
  m_UsingPolyTree = true;
  bool succeeded = ExecuteInternal();
  if (succeeded) BuildResult2(polytree);
  DisposeAllOutRecs();
  return succeeded;
}

References BuildResult2(), DisposeAllOutRecs(), ExecuteInternal(), m_ClipFillType, m_ClipType, m_SubjFillType, and m_UsingPolyTree.

Here is the call graph for this function:

◆ ExecuteInternal()

bool ClipperLib::Clipper::ExecuteInternal ( )

protectedvirtual

{
  bool succeeded = true;
  try {
    Reset();
    if (m_MinimaList.empty()) return true;
    cInt botY = m_Scanbeam.top();
    do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && botY == m_Scanbeam.top());
    do {
      InsertLocalMinimaIntoAEL(botY);
      ProcessHorizontals();
      m_GhostJoins.clear();
      if (m_Scanbeam.empty()) break;
      cInt topY = m_Scanbeam.top();
      do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && topY == m_Scanbeam.top());
      succeeded = ProcessIntersections(topY);
      if (!succeeded) break;
      ProcessEdgesAtTopOfScanbeam(topY);
      botY = topY;
    } while (!m_Scanbeam.empty() || !m_MinimaList.empty());
  }
  catch(...) 
  {
    succeeded = false;
  }
 
  if (succeeded)
  {
 
    //fix orientations ...
    //FIXME Vojtech: Does it not invalidate the loop hierarchy maintained as OutRec::FirstLeft pointers?
    //FIXME Vojtech: The area is calculated with floats, it may not be numerically stable!
    {
      for (OutRec &outRec : m_PolyOuts)
        if (outRec.Pts && !outRec.IsOpen && (outRec.IsHole ^ m_ReverseOutput) == (Area(outRec) > 0))
          ReversePolyPtLinks(outRec.Pts);
    }
 
    JoinCommonEdges();
 
    //unfortunately FixupOutPolygon() must be done after JoinCommonEdges()
    {
      for (OutRec &outRec : m_PolyOuts)
        if (outRec.Pts) {
          if (outRec.IsOpen)
            // Removes duplicate points.
            FixupOutPolyline(outRec);
          else
            // Removes duplicate points and simplifies consecutive parallel edges by removing the middle vertex.
            FixupOutPolygon(outRec);
        }
    }
    // For each polygon, search for exactly duplicate non-successive points.
    // If such a point is found, the loop is split into two pieces.
    // Search for the duplicate points is O(n^2)!
    // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/Clipper/Properties/StrictlySimple.htm
    if (m_StrictSimple) DoSimplePolygons();
  }
 
  m_Joins.clear();
  m_GhostJoins.clear();
  return succeeded;
}

References ClipperLib::Area(), DoSimplePolygons(), FixupOutPolygon(), FixupOutPolyline(), InsertLocalMinimaIntoAEL(), JoinCommonEdges(), m_GhostJoins, m_Joins, ClipperLib::ClipperBase::m_MinimaList, m_PolyOuts, m_ReverseOutput, m_Scanbeam, m_StrictSimple, ProcessEdgesAtTopOfScanbeam(), ProcessHorizontals(), ProcessIntersections(), Reset(), and ClipperLib::ReversePolyPtLinks().

Referenced by Execute(), and Execute().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FindOwnerFromSplitRecs()

bool ClipperLib::Clipper::FindOwnerFromSplitRecs	(	OutRec &	outRec,
		OutRec *&	currOrfl
	)

private

◆ FixHoleLinkage()

void ClipperLib::Clipper::FixHoleLinkage ( OutRec & outrec )

private

◆ FixupFirstLefts1()

void ClipperLib::Clipper::FixupFirstLefts1	(	OutRec *	OldOutRec,
		OutRec *	NewOutRec
	)

private

{ 
  //tests if NewOutRec contains the polygon before reassigning FirstLeft
  for (OutRec &outRec : m_PolyOuts)
  {
    if (!outRec.Pts || !outRec.FirstLeft) continue;
    OutRec* firstLeft = outRec.FirstLeft;
    // Skip empty polygons.
    while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;
    if (firstLeft == OldOutRec && Poly2ContainsPoly1(outRec.Pts, NewOutRec->Pts))
        outRec.FirstLeft = NewOutRec;
  }
}

References ClipperLib::OutRec::FirstLeft, m_PolyOuts, ClipperLib::Poly2ContainsPoly1(), and ClipperLib::OutRec::Pts.

Referenced by DoSimplePolygons(), and JoinCommonEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FixupFirstLefts2()

void ClipperLib::Clipper::FixupFirstLefts2	(	OutRec *	OldOutRec,
		OutRec *	NewOutRec
	)

private

{ 
  //reassigns FirstLeft WITHOUT testing if NewOutRec contains the polygon
  for (OutRec &outRec : m_PolyOuts)
    if (outRec.FirstLeft == OldOutRec) outRec.FirstLeft = NewOutRec;
}

References m_PolyOuts.

Referenced by DoSimplePolygons(), and JoinCommonEdges().

Here is the caller graph for this function:

◆ FixupIntersectionOrder()

bool ClipperLib::Clipper::FixupIntersectionOrder ( )

private

{
  //pre-condition: intersections are sorted Bottom-most first.
  //Now it's crucial that intersections are made only between adjacent edges,
  //so to ensure this the order of intersections may need adjusting ...
  CopyAELToSEL();
  std::sort(m_IntersectList.begin(), m_IntersectList.end(), [](const IntersectNode &node1, const IntersectNode &node2) { return node2.Pt.y() < node1.Pt.y(); });
 
  size_t cnt = m_IntersectList.size();
  for (size_t i = 0; i < cnt; ++i) 
  {
    if (!EdgesAdjacent(m_IntersectList[i]))
    {
      size_t j = i + 1;
      while (j < cnt && !EdgesAdjacent(m_IntersectList[j])) j++;
      if (j == cnt)  return false;
      std::swap(m_IntersectList[i], m_IntersectList[j]);
    }
    SwapPositionsInSEL(m_IntersectList[i].Edge1, m_IntersectList[i].Edge2);
  }
  return true;
}

References CopyAELToSEL(), ClipperLib::EdgesAdjacent(), m_IntersectList, and SwapPositionsInSEL().

Referenced by ProcessIntersections().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FixupOutPolygon()

void ClipperLib::Clipper::FixupOutPolygon ( OutRec & outrec )

private

{
    //FixupOutPolygon() - removes duplicate points and simplifies consecutive
    //parallel edges by removing the middle vertex.
    OutPt *lastOK = nullptr;
    outrec.BottomPt = nullptr;
    OutPt *pp = outrec.Pts;
    bool preserveCol = m_PreserveCollinear || m_StrictSimple;
 
    for (;;)
    {
        if (pp->Prev == pp || pp->Prev == pp->Next)
        {
            // Empty loop or a stick. Release the polygon.
            this->DisposeOutPts(pp);
            outrec.Pts = nullptr;
            return;
        }
 
        //test for duplicate points and collinear edges ...
        if ((pp->Pt == pp->Next->Pt) || (pp->Pt == pp->Prev->Pt) ||
            (SlopesEqual(pp->Prev->Pt, pp->Pt, pp->Next->Pt, m_UseFullRange) &&
            (!preserveCol || !Pt2IsBetweenPt1AndPt3(pp->Prev->Pt, pp->Pt, pp->Next->Pt))))
        {
            lastOK = nullptr;
            OutPt *tmp = pp;
            pp->Prev->Next = pp->Next;
            pp->Next->Prev = pp->Prev;
            pp = pp->Prev;
            this->DisposeOutPt(tmp);
        }
        else if (pp == lastOK) break;
        else
        {
            if (!lastOK) lastOK = pp;
            pp = pp->Next;
        }
    }
    outrec.Pts = pp;
}

References ClipperLib::OutRec::BottomPt, DisposeOutPt(), DisposeOutPts(), ClipperLib::ClipperBase::m_PreserveCollinear, m_StrictSimple, ClipperLib::ClipperBase::m_UseFullRange, ClipperLib::OutPt::Next, ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, ClipperLib::Pt2IsBetweenPt1AndPt3(), ClipperLib::OutRec::Pts, and ClipperLib::SlopesEqual().

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FixupOutPolyline()

void ClipperLib::Clipper::FixupOutPolyline ( OutRec & outrec )

private

{
  OutPt *pp = outrec.Pts;
  OutPt *lastPP = pp->Prev;
  while (pp != lastPP)
  {
    pp = pp->Next;
    if (pp->Pt == pp->Prev->Pt)
    {
      if (pp == lastPP) lastPP = pp->Prev;
      OutPt *tmpPP = pp->Prev;
      tmpPP->Next = pp->Next;
      pp->Next->Prev = tmpPP;
      this->DisposeOutPt(pp);
      pp = tmpPP;
    }
  }
 
  if (pp == pp->Prev)
  {
    this->DisposeOutPts(pp);
    outrec.Pts = 0;
    return;
  }
}

References DisposeOutPt(), DisposeOutPts(), ClipperLib::OutPt::Next, ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, and ClipperLib::OutRec::Pts.

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetBounds()

IntRect ClipperLib::ClipperBase::GetBounds ( )

inherited

{
  IntRect result;
  auto lm = m_MinimaList.begin();
  if (lm == m_MinimaList.end())
  {
    result.left = result.top = result.right = result.bottom = 0;
    return result;
  }
  result.left = lm->LeftBound->Bot.x();
  result.top = lm->LeftBound->Bot.y();
  result.right = lm->LeftBound->Bot.x();
  result.bottom = lm->LeftBound->Bot.y();
  while (lm != m_MinimaList.end())
  {
    result.bottom = std::max(result.bottom, lm->LeftBound->Bot.y());
    TEdge* e = lm->LeftBound;
    for (;;) {
      TEdge* bottomE = e;
      while (e->NextInLML)
      {
        if (e->Bot.x() < result.left) result.left = e->Bot.x();
        if (e->Bot.x() > result.right) result.right = e->Bot.x();
        e = e->NextInLML;
      }
      result.left = std::min(result.left, e->Bot.x());
      result.right = std::max(result.right, e->Bot.x());
      result.left = std::min(result.left, e->Top.x());
      result.right = std::max(result.right, e->Top.x());
      result.top = std::min(result.top, e->Top.y());
      if (bottomE == lm->LeftBound) e = lm->RightBound;
      else break;
    }
    ++lm;
  }
  return result;
}

References ClipperLib::TEdge::Bot, ClipperLib::IntRect::bottom, ClipperLib::IntRect::left, ClipperLib::TEdge::NextInLML, ClipperLib::IntRect::right, ClipperLib::IntRect::top, and ClipperLib::TEdge::Top.

Referenced by ClipperLib::ClipperOffset::Execute(), ClipperLib::ClipperOffset::Execute(), Slic3r::fix_after_inner_offset(), and Slic3r::shrink_paths().

Here is the caller graph for this function:

◆ GetLastOutPt()

OutPt * ClipperLib::Clipper::GetLastOutPt ( TEdge * e )

private

{
  OutRec *outRec = &m_PolyOuts[e->OutIdx];
  if (e->Side == esLeft)
    return outRec->Pts;
  else
    return outRec->Pts->Prev;
}

References ClipperLib::esLeft, m_PolyOuts, ClipperLib::TEdge::OutIdx, ClipperLib::OutPt::Prev, ClipperLib::OutRec::Pts, and ClipperLib::TEdge::Side.

Referenced by ProcessHorizontal().

Here is the caller graph for this function:

◆ GetOutRec()

OutRec * ClipperLib::Clipper::GetOutRec ( int idx )

private

{
  OutRec* outrec = &m_PolyOuts[Idx];
  while (outrec != &m_PolyOuts[outrec->Idx])
    outrec = &m_PolyOuts[outrec->Idx];
  return outrec;
}

References ClipperLib::OutRec::Idx, and m_PolyOuts.

Referenced by JoinCommonEdges().

Here is the caller graph for this function:

◆ InsertEdgeIntoAEL()

void ClipperLib::Clipper::InsertEdgeIntoAEL	(	TEdge *	edge,
		TEdge *	startEdge
	)

private

{
  if(!m_ActiveEdges)
  {
    edge->PrevInAEL = 0;
    edge->NextInAEL = 0;
    m_ActiveEdges = edge;
  }
  else if(!startEdge && E2InsertsBeforeE1(*m_ActiveEdges, *edge))
  {
      edge->PrevInAEL = 0;
      edge->NextInAEL = m_ActiveEdges;
      m_ActiveEdges->PrevInAEL = edge;
      m_ActiveEdges = edge;
  } 
  else
  {
    if(!startEdge) startEdge = m_ActiveEdges;
    while(startEdge->NextInAEL  && 
      !E2InsertsBeforeE1(*startEdge->NextInAEL , *edge))
        startEdge = startEdge->NextInAEL;
    edge->NextInAEL = startEdge->NextInAEL;
    if(startEdge->NextInAEL) startEdge->NextInAEL->PrevInAEL = edge;
    edge->PrevInAEL = startEdge;
    startEdge->NextInAEL = edge;
  }
}

References ClipperLib::E2InsertsBeforeE1(), m_ActiveEdges, ClipperLib::TEdge::NextInAEL, and ClipperLib::TEdge::PrevInAEL.

Referenced by InsertLocalMinimaIntoAEL().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ InsertLocalMinimaIntoAEL()

void ClipperLib::Clipper::InsertLocalMinimaIntoAEL ( const cInt botY )

private

{
  while (!m_MinimaList.empty() && m_MinimaList.back().Y == botY)
  {
    TEdge* lb = m_MinimaList.back().LeftBound;
    TEdge* rb = m_MinimaList.back().RightBound;
    m_MinimaList.pop_back();
 
    OutPt *Op1 = 0;
    if (!lb)
    {
      //nb: don't insert LB into either AEL or SEL
      InsertEdgeIntoAEL(rb, 0);
      SetWindingCount(*rb);
      if (IsContributing(*rb))
        Op1 = AddOutPt(rb, rb->Bot); 
    } 
    else if (!rb)
    {
      InsertEdgeIntoAEL(lb, 0);
      SetWindingCount(*lb);
      if (IsContributing(*lb))
        Op1 = AddOutPt(lb, lb->Bot);
      m_Scanbeam.push(lb->Top.y());
    }
    else
    {
      InsertEdgeIntoAEL(lb, 0);
      InsertEdgeIntoAEL(rb, lb);
      SetWindingCount( *lb );
      rb->WindCnt = lb->WindCnt;
      rb->WindCnt2 = lb->WindCnt2;
      if (IsContributing(*lb))
        Op1 = AddLocalMinPoly(lb, rb, lb->Bot);      
      m_Scanbeam.push(lb->Top.y());
    }
 
     if (rb)
     {
       if(IsHorizontal(*rb)) AddEdgeToSEL(rb);
       else m_Scanbeam.push(rb->Top.y());
     }
 
    if (!lb || !rb) continue;
 
    //if any output polygons share an edge, they'll need joining later ...
    if (Op1 && IsHorizontal(*rb) && 
      m_GhostJoins.size() > 0 && (rb->WindDelta != 0))
    {
      for (Join &jr : m_GhostJoins)
        //if the horizontal Rb and a 'ghost' horizontal overlap, then convert
        //the 'ghost' join to a real join ready for later ...
        if (HorzSegmentsOverlap(jr.OutPt1->Pt.x(), jr.OffPt.x(), rb->Bot.x(), rb->Top.x()))
          m_Joins.emplace_back(Join(jr.OutPt1, Op1, jr.OffPt));
    }
 
    if (lb->OutIdx >= 0 && lb->PrevInAEL && 
      lb->PrevInAEL->Curr.x() == lb->Bot.x() &&
      lb->PrevInAEL->OutIdx >= 0 &&
      SlopesEqual(*lb->PrevInAEL, *lb, m_UseFullRange) &&
      (lb->WindDelta != 0) && (lb->PrevInAEL->WindDelta != 0))
    {
        OutPt *Op2 = AddOutPt(lb->PrevInAEL, lb->Bot);
        m_Joins.emplace_back(Join(Op1, Op2, lb->Top));
    }
 
    if(lb->NextInAEL != rb)
    {
 
      if (rb->OutIdx >= 0 && rb->PrevInAEL->OutIdx >= 0 &&
        SlopesEqual(*rb->PrevInAEL, *rb, m_UseFullRange) &&
        (rb->WindDelta != 0) && (rb->PrevInAEL->WindDelta != 0))
      {
          OutPt *Op2 = AddOutPt(rb->PrevInAEL, rb->Bot);
          m_Joins.emplace_back(Join(Op1, Op2, rb->Top));
      }
 
      TEdge* e = lb->NextInAEL;
      if (e)
      {
        while( e != rb )
        {
          //nb: For calculating winding counts etc, IntersectEdges() assumes
          //that param1 will be to the Right of param2 ABOVE the intersection ...
          IntersectEdges(rb , e , lb->Curr); //order important here
          e = e->NextInAEL;
        }
      }
    }
    
  }
}

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IntersectEdges()

void ClipperLib::Clipper::IntersectEdges	(	TEdge *	e1,
		TEdge *	e2,
		IntPoint &	pt
	)

private

{
  bool e1Contributing = ( e1->OutIdx >= 0 );
  bool e2Contributing = ( e2->OutIdx >= 0 );
 
#ifdef CLIPPERLIB_USE_XYZ
        SetZ(Pt, *e1, *e2);
#endif
 
#ifdef use_lines
  //if either edge is on an OPEN path ...
  if (e1->WindDelta == 0 || e2->WindDelta == 0)
  {
    //ignore subject-subject open path intersections UNLESS they
    //are both open paths, AND they are both 'contributing maximas' ...
  if (e1->WindDelta == 0 && e2->WindDelta == 0) return;
 
    //if intersecting a subj line with a subj poly ...
    else if (e1->PolyTyp == e2->PolyTyp && 
      e1->WindDelta != e2->WindDelta && m_ClipType == ctUnion)
    {
      if (e1->WindDelta == 0)
      {
        if (e2Contributing)
        {
          AddOutPt(e1, Pt);
          if (e1Contributing) e1->OutIdx = Unassigned;
        }
      }
      else
      {
        if (e1Contributing)
        {
          AddOutPt(e2, Pt);
          if (e2Contributing) e2->OutIdx = Unassigned;
        }
      }
    }
    else if (e1->PolyTyp != e2->PolyTyp)
    {
      //toggle subj open path OutIdx on/off when Abs(clip.WndCnt) == 1 ...
      if ((e1->WindDelta == 0) && std::abs(e2->WindCnt) == 1 && 
        (m_ClipType != ctUnion || e2->WindCnt2 == 0))
      {
        AddOutPt(e1, Pt);
        if (e1Contributing) e1->OutIdx = Unassigned;
      }
      else if ((e2->WindDelta == 0) && (std::abs(e1->WindCnt) == 1) && 
        (m_ClipType != ctUnion || e1->WindCnt2 == 0))
      {
        AddOutPt(e2, Pt);
        if (e2Contributing) e2->OutIdx = Unassigned;
      }
    }
    return;
  }
#endif
 
  //update winding counts...
  //assumes that e1 will be to the Right of e2 ABOVE the intersection
  if ( e1->PolyTyp == e2->PolyTyp )
  {
    if ( IsEvenOddFillType( *e1) )
    {
      int oldE1WindCnt = e1->WindCnt;
      e1->WindCnt = e2->WindCnt;
      e2->WindCnt = oldE1WindCnt;
    } else
    {
      if (e1->WindCnt + e2->WindDelta == 0 ) e1->WindCnt = -e1->WindCnt;
      else e1->WindCnt += e2->WindDelta;
      if ( e2->WindCnt - e1->WindDelta == 0 ) e2->WindCnt = -e2->WindCnt;
      else e2->WindCnt -= e1->WindDelta;
    }
  } else
  {
    if (!IsEvenOddFillType(*e2)) e1->WindCnt2 += e2->WindDelta;
    else e1->WindCnt2 = ( e1->WindCnt2 == 0 ) ? 1 : 0;
    if (!IsEvenOddFillType(*e1)) e2->WindCnt2 -= e1->WindDelta;
    else e2->WindCnt2 = ( e2->WindCnt2 == 0 ) ? 1 : 0;
  }
 
  PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
  if (e1->PolyTyp == ptSubject)
  {
    e1FillType = m_SubjFillType;
    e1FillType2 = m_ClipFillType;
  } else
  {
    e1FillType = m_ClipFillType;
    e1FillType2 = m_SubjFillType;
  }
  if (e2->PolyTyp == ptSubject)
  {
    e2FillType = m_SubjFillType;
    e2FillType2 = m_ClipFillType;
  } else
  {
    e2FillType = m_ClipFillType;
    e2FillType2 = m_SubjFillType;
  }
 
  cInt e1Wc, e2Wc;
  switch (e1FillType)
  {
    case pftPositive: e1Wc = e1->WindCnt; break;
    case pftNegative: e1Wc = -e1->WindCnt; break;
    default: e1Wc = std::abs(e1->WindCnt);
  }
  switch(e2FillType)
  {
    case pftPositive: e2Wc = e2->WindCnt; break;
    case pftNegative: e2Wc = -e2->WindCnt; break;
    default: e2Wc = std::abs(e2->WindCnt);
  }
 
  if ( e1Contributing && e2Contributing )
  {
    if ((e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
      (e1->PolyTyp != e2->PolyTyp && m_ClipType != ctXor) )
    {
      AddLocalMaxPoly(e1, e2, Pt); 
    }
    else
    {
      AddOutPt(e1, Pt);
      AddOutPt(e2, Pt);
      std::swap(e1->Side, e2->Side);
      std::swap(e1->OutIdx, e2->OutIdx);
    }
  }
  else if ( e1Contributing )
  {
    if (e2Wc == 0 || e2Wc == 1) 
    {
      AddOutPt(e1, Pt);
      std::swap(e1->Side, e2->Side);
      std::swap(e1->OutIdx, e2->OutIdx);
    }
  }
  else if ( e2Contributing )
  {
    if (e1Wc == 0 || e1Wc == 1) 
    {
      AddOutPt(e2, Pt);
      std::swap(e1->Side, e2->Side);
      std::swap(e1->OutIdx, e2->OutIdx);
    }
  } 
  else if ( (e1Wc == 0 || e1Wc == 1) && (e2Wc == 0 || e2Wc == 1))
  {
    //neither edge is currently contributing ...
 
    cInt e1Wc2, e2Wc2;
    switch (e1FillType2)
    {
      case pftPositive: e1Wc2 = e1->WindCnt2; break;
      case pftNegative : e1Wc2 = -e1->WindCnt2; break;
      default: e1Wc2 = std::abs(e1->WindCnt2);
    }
    switch (e2FillType2)
    {
      case pftPositive: e2Wc2 = e2->WindCnt2; break;
      case pftNegative: e2Wc2 = -e2->WindCnt2; break;
      default: e2Wc2 = std::abs(e2->WindCnt2);
    }
 
    if (e1->PolyTyp != e2->PolyTyp)
    {
      AddLocalMinPoly(e1, e2, Pt);
    }
    else if (e1Wc == 1 && e2Wc == 1)
      switch( m_ClipType ) {
        case ctIntersection:
          if (e1Wc2 > 0 && e2Wc2 > 0)
            AddLocalMinPoly(e1, e2, Pt);
          break;
        case ctUnion:
          if ( e1Wc2 <= 0 && e2Wc2 <= 0 )
            AddLocalMinPoly(e1, e2, Pt);
          break;
        case ctDifference:
          if (((e1->PolyTyp == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
              ((e1->PolyTyp == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
                AddLocalMinPoly(e1, e2, Pt);
          break;
        case ctXor:
          AddLocalMinPoly(e1, e2, Pt);
      }
    else
      std::swap(e1->Side, e2->Side);
  }
}

References AddLocalMaxPoly(), AddLocalMinPoly(), AddOutPt(), ClipperLib::ctDifference, ClipperLib::ctIntersection, ClipperLib::ctUnion, ClipperLib::ctXor, IsEvenOddFillType(), m_ClipFillType, m_ClipType, m_SubjFillType, ClipperLib::TEdge::OutIdx, ClipperLib::pftNegative, ClipperLib::pftPositive, ClipperLib::TEdge::PolyTyp, ClipperLib::ptClip, ClipperLib::ptSubject, ClipperLib::TEdge::Side, ClipperLib::Unassigned, ClipperLib::TEdge::WindCnt, ClipperLib::TEdge::WindCnt2, and ClipperLib::TEdge::WindDelta.

Referenced by DoMaxima(), InsertLocalMinimaIntoAEL(), ProcessHorizontal(), and ProcessIntersections().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsContributing()

bool ClipperLib::Clipper::IsContributing ( const TEdge & edge ) const

private

{
  PolyFillType pft, pft2;
  if (edge.PolyTyp == ptSubject)
  {
    pft = m_SubjFillType;
    pft2 = m_ClipFillType;
  } else
  {
    pft = m_ClipFillType;
    pft2 = m_SubjFillType;
  }
 
  switch(pft)
  {
    case pftEvenOdd: 
      //return false if a subj line has been flagged as inside a subj polygon
      if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;
      break;
    case pftNonZero:
      if (std::abs(edge.WindCnt) != 1) return false;
      break;
    case pftPositive: 
      if (edge.WindCnt != 1) return false;
      break;
    default: //pftNegative
      if (edge.WindCnt != -1) return false;
  }
 
  switch(m_ClipType)
  {
    case ctIntersection:
      switch(pft2)
      {
        case pftEvenOdd: 
        case pftNonZero: 
          return (edge.WindCnt2 != 0);
        case pftPositive: 
          return (edge.WindCnt2 > 0);
        default: 
          return (edge.WindCnt2 < 0);
      }
      break;
    case ctUnion:
      switch(pft2)
      {
        case pftEvenOdd: 
        case pftNonZero: 
          return (edge.WindCnt2 == 0);
        case pftPositive: 
          return (edge.WindCnt2 <= 0);
        default: 
          return (edge.WindCnt2 >= 0);
      }
      break;
    case ctDifference:
      if (edge.PolyTyp == ptSubject)
        switch(pft2)
        {
          case pftEvenOdd: 
          case pftNonZero: 
            return (edge.WindCnt2 == 0);
          case pftPositive: 
            return (edge.WindCnt2 <= 0);
          default: 
            return (edge.WindCnt2 >= 0);
        }
      else
        switch(pft2)
        {
          case pftEvenOdd: 
          case pftNonZero: 
            return (edge.WindCnt2 != 0);
          case pftPositive: 
            return (edge.WindCnt2 > 0);
          default: 
            return (edge.WindCnt2 < 0);
        }
      break;
    case ctXor:
      if (edge.WindDelta == 0) //XOr always contributing unless open
        switch(pft2)
        {
          case pftEvenOdd: 
          case pftNonZero: 
            return (edge.WindCnt2 == 0);
          case pftPositive: 
            return (edge.WindCnt2 <= 0);
          default: 
            return (edge.WindCnt2 >= 0);
        }
      else 
        return true;
      break;
    default:
      return true;
  }
}

References ClipperLib::ctDifference, ClipperLib::ctIntersection, ClipperLib::ctUnion, ClipperLib::ctXor, m_ClipFillType, m_ClipType, m_SubjFillType, ClipperLib::pftEvenOdd, ClipperLib::pftNonZero, ClipperLib::pftPositive, ClipperLib::TEdge::PolyTyp, ClipperLib::ptSubject, ClipperLib::TEdge::WindCnt, ClipperLib::TEdge::WindCnt2, and ClipperLib::TEdge::WindDelta.

Referenced by InsertLocalMinimaIntoAEL().

Here is the caller graph for this function:

◆ IsEvenOddAltFillType()

bool ClipperLib::Clipper::IsEvenOddAltFillType ( const TEdge & edge ) const

inlineprivate

487 { return (edge.PolyTyp == ptSubject) ? m_ClipFillType == pftEvenOdd : m_SubjFillType == pftEvenOdd; }

References ClipperLib::pftEvenOdd, ClipperLib::TEdge::PolyTyp, and ClipperLib::ptSubject.

Referenced by SetWindingCount().

Here is the caller graph for this function:

◆ IsEvenOddFillType()

bool ClipperLib::Clipper::IsEvenOddFillType ( const TEdge & edge ) const

inlineprivate

485 { return (edge.PolyTyp == ptSubject) ? m_SubjFillType == pftEvenOdd : m_ClipFillType == pftEvenOdd; }

References ClipperLib::pftEvenOdd, ClipperLib::TEdge::PolyTyp, and ClipperLib::ptSubject.

Referenced by IntersectEdges(), and SetWindingCount().

Here is the caller graph for this function:

◆ IsTopHorz()

bool ClipperLib::Clipper::IsTopHorz ( const cInt XPos )

private

◆ JoinCommonEdges()

void ClipperLib::Clipper::JoinCommonEdges ( )

private

{
  for (Join &join : m_Joins)
  {
    OutRec *outRec1 = GetOutRec(join.OutPt1->Idx);
    OutRec *outRec2 = GetOutRec(join.OutPt2->Idx);
 
    if (!outRec1->Pts || !outRec2->Pts) continue;
    if (outRec1->IsOpen || outRec2->IsOpen) continue;
 
    //get the polygon fragment with the correct hole state (FirstLeft)
    //before calling JoinPoints() ...
    OutRec *holeStateRec;
    if (outRec1 == outRec2) holeStateRec = outRec1;
    else if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
    else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
    else holeStateRec = GetLowermostRec(outRec1, outRec2);
 
    if (!JoinPoints(&join, outRec1, outRec2)) continue;
 
    if (outRec1 == outRec2)
    {
      //instead of joining two polygons, we've just created a new one by
      //splitting one polygon into two.
      outRec1->Pts = join.OutPt1;
      outRec1->BottomPt = 0;
      outRec2 = CreateOutRec();
      outRec2->Pts = join.OutPt2;
 
      //update all OutRec2.Pts Idx's ...
      UpdateOutPtIdxs(*outRec2);
 
      //We now need to check every OutRec.FirstLeft pointer. If it points
      //to OutRec1 it may need to point to OutRec2 instead ...
      if (m_UsingPolyTree)
        for (size_t j = 0; j < m_PolyOuts.size() - 1; j++)
        {
          OutRec &oRec = m_PolyOuts[j];
          OutRec* firstLeft = oRec.FirstLeft;
          while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;
          if (!oRec.Pts || firstLeft != outRec1 ||
            oRec.IsHole == outRec1->IsHole) continue;
          if (Poly2ContainsPoly1(oRec.Pts, join.OutPt2))
            oRec.FirstLeft = outRec2;
        }
 
      if (Poly2ContainsPoly1(outRec2->Pts, outRec1->Pts))
      {
        //outRec2 is contained by outRec1 ...
        outRec2->IsHole = !outRec1->IsHole;
        outRec2->FirstLeft = outRec1;
 
        // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.
        if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
 
        if ((outRec2->IsHole ^ m_ReverseOutput) == (Area(*outRec2) > 0))
          ReversePolyPtLinks(outRec2->Pts);
            
      } else if (Poly2ContainsPoly1(outRec1->Pts, outRec2->Pts))
      {
        //outRec1 is contained by outRec2 ...
        outRec2->IsHole = outRec1->IsHole;
        outRec1->IsHole = !outRec2->IsHole;
        outRec2->FirstLeft = outRec1->FirstLeft;
        outRec1->FirstLeft = outRec2;
 
        // For each m_PolyOuts, replace FirstLeft from outRec1 to outRec2.
        if (m_UsingPolyTree) FixupFirstLefts2(outRec1, outRec2);
 
        if ((outRec1->IsHole ^ m_ReverseOutput) == (Area(*outRec1) > 0))
          ReversePolyPtLinks(outRec1->Pts);
      } 
      else
      {
        //the 2 polygons are completely separate ...
        outRec2->IsHole = outRec1->IsHole;
        outRec2->FirstLeft = outRec1->FirstLeft;
 
        //fixup FirstLeft pointers that may need reassigning to OutRec2
        // For each polygon of m_PolyOuts, replace FirstLeft from outRec1 to outRec2 if the polygon is inside outRec2.
        //FIXME This is potentially very expensive! O(n^3)!
        if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec2);
      }
     
    } else
    {
      //joined 2 polygons together ...
 
      outRec2->Pts = 0;
      outRec2->BottomPt = 0;
      outRec2->Idx = outRec1->Idx;
 
      outRec1->IsHole = holeStateRec->IsHole;
      if (holeStateRec == outRec2) 
        outRec1->FirstLeft = outRec2->FirstLeft;
      outRec2->FirstLeft = outRec1;
 
      // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.
      if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
    }
  }
}

References ClipperLib::Area(), ClipperLib::OutRec::BottomPt, CreateOutRec(), ClipperLib::OutRec::FirstLeft, FixupFirstLefts1(), FixupFirstLefts2(), ClipperLib::GetLowermostRec(), GetOutRec(), ClipperLib::OutRec::Idx, ClipperLib::OutRec::IsHole, ClipperLib::OutRec::IsOpen, JoinPoints(), m_Joins, m_PolyOuts, m_ReverseOutput, m_UsingPolyTree, ClipperLib::Param1RightOfParam2(), ClipperLib::Poly2ContainsPoly1(), ClipperLib::OutRec::Pts, ClipperLib::ReversePolyPtLinks(), and ClipperLib::UpdateOutPtIdxs().

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ JoinHorz()

bool ClipperLib::Clipper::JoinHorz	(	OutPt *	op1,
		OutPt *	op1b,
		OutPt *	op2,
		OutPt *	op2b,
		const IntPoint &	Pt,
		bool	DiscardLeft
	)

private

{
  Direction Dir1 = (op1->Pt.x() > op1b->Pt.x() ? dRightToLeft : dLeftToRight);
  Direction Dir2 = (op2->Pt.x() > op2b->Pt.x() ? dRightToLeft : dLeftToRight);
  if (Dir1 == Dir2) return false;
 
  //When DiscardLeft, we want Op1b to be on the Left of Op1, otherwise we
  //want Op1b to be on the Right. (And likewise with Op2 and Op2b.)
  //So, to facilitate this while inserting Op1b and Op2b ...
  //when DiscardLeft, make sure we're AT or RIGHT of Pt before adding Op1b,
  //otherwise make sure we're AT or LEFT of Pt. (Likewise with Op2b.)
  if (Dir1 == dLeftToRight) 
  {
    while (op1->Next->Pt.x() <= Pt.x() && 
      op1->Next->Pt.x() >= op1->Pt.x() && op1->Next->Pt.y() == Pt.y())  
        op1 = op1->Next;
    if (DiscardLeft && (op1->Pt.x() != Pt.x())) op1 = op1->Next;
    op1b = this->DupOutPt(op1, !DiscardLeft);
    if (op1b->Pt != Pt) 
    {
      op1 = op1b;
      op1->Pt = Pt;
      op1b = this->DupOutPt(op1, !DiscardLeft);
    }
  } 
  else
  {
    while (op1->Next->Pt.x() >= Pt.x() && 
      op1->Next->Pt.x() <= op1->Pt.x() && op1->Next->Pt.y() == Pt.y()) 
        op1 = op1->Next;
    if (!DiscardLeft && (op1->Pt.x() != Pt.x())) op1 = op1->Next;
    op1b = this->DupOutPt(op1, DiscardLeft);
    if (op1b->Pt != Pt)
    {
      op1 = op1b;
      op1->Pt = Pt;
      op1b = this->DupOutPt(op1, DiscardLeft);
    }
  }
 
  if (Dir2 == dLeftToRight)
  {
    while (op2->Next->Pt.x() <= Pt.x() && 
      op2->Next->Pt.x() >= op2->Pt.x() && op2->Next->Pt.y() == Pt.y())
        op2 = op2->Next;
    if (DiscardLeft && (op2->Pt.x() != Pt.x())) op2 = op2->Next;
    op2b = this->DupOutPt(op2, !DiscardLeft);
    if (op2b->Pt != Pt)
    {
      op2 = op2b;
      op2->Pt = Pt;
      op2b = this->DupOutPt(op2, !DiscardLeft);
    };
  } else
  {
    while (op2->Next->Pt.x() >= Pt.x() && 
      op2->Next->Pt.x() <= op2->Pt.x() && op2->Next->Pt.y() == Pt.y()) 
        op2 = op2->Next;
    if (!DiscardLeft && (op2->Pt.x() != Pt.x())) op2 = op2->Next;
    op2b = this->DupOutPt(op2, DiscardLeft);
    if (op2b->Pt != Pt)
    {
      op2 = op2b;
      op2->Pt = Pt;
      op2b = this->DupOutPt(op2, DiscardLeft);
    };
  };
 
  if ((Dir1 == dLeftToRight) == DiscardLeft)
  {
    op1->Prev = op2;
    op2->Next = op1;
    op1b->Next = op2b;
    op2b->Prev = op1b;
  }
  else
  {
    op1->Next = op2;
    op2->Prev = op1;
    op1b->Prev = op2b;
    op2b->Next = op1b;
  }
  return true;
}

References ClipperLib::dLeftToRight, ClipperLib::dRightToLeft, DupOutPt(), ClipperLib::OutPt::Next, ClipperLib::OutPt::Prev, and ClipperLib::OutPt::Pt.

Referenced by JoinPoints().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ JoinPoints()

bool ClipperLib::Clipper::JoinPoints	(	Join *	j,
		OutRec *	outRec1,
		OutRec *	outRec2
	)

private

{
  OutPt *op1 = j->OutPt1, *op1b;
  OutPt *op2 = j->OutPt2, *op2b;
 
  //There are 3 kinds of joins for output polygons ...
  //1. Horizontal joins where Join.OutPt1 & Join.OutPt2 are vertices anywhere
  //along (horizontal) collinear edges (& Join.OffPt is on the same horizontal).
  //2. Non-horizontal joins where Join.OutPt1 & Join.OutPt2 are at the same
  //location at the Bottom of the overlapping segment (& Join.OffPt is above).
  //3. StrictSimple joins where edges touch but are not collinear and where
  //Join.OutPt1, Join.OutPt2 & Join.OffPt all share the same point.
  bool isHorizontal = (j->OutPt1->Pt.y() == j->OffPt.y());
 
  if (isHorizontal  && (j->OffPt == j->OutPt1->Pt) &&
  (j->OffPt == j->OutPt2->Pt))
  {
    //Strictly Simple join ...
    if (outRec1 != outRec2) return false;
    op1b = j->OutPt1->Next;
    while (op1b != op1 && (op1b->Pt == j->OffPt)) 
      op1b = op1b->Next;
    bool reverse1 = (op1b->Pt.y() > j->OffPt.y());
    op2b = j->OutPt2->Next;
    while (op2b != op2 && (op2b->Pt == j->OffPt)) 
      op2b = op2b->Next;
    bool reverse2 = (op2b->Pt.y() > j->OffPt.y());
    if (reverse1 == reverse2) return false;
    if (reverse1)
    {
      op1b = this->DupOutPt(op1, false);
      op2b = this->DupOutPt(op2, true);
      op1->Prev = op2;
      op2->Next = op1;
      op1b->Next = op2b;
      op2b->Prev = op1b;
      j->OutPt1 = op1;
      j->OutPt2 = op1b;
      return true;
    } else
    {
      op1b = this->DupOutPt(op1, true);
      op2b = this->DupOutPt(op2, false);
      op1->Next = op2;
      op2->Prev = op1;
      op1b->Prev = op2b;
      op2b->Next = op1b;
      j->OutPt1 = op1;
      j->OutPt2 = op1b;
      return true;
    }
  } 
  else if (isHorizontal)
  {
    //treat horizontal joins differently to non-horizontal joins since with
    //them we're not yet sure where the overlapping is. OutPt1.Pt & OutPt2.Pt
    //may be anywhere along the horizontal edge.
    op1b = op1;
    while (op1->Prev->Pt.y() == op1->Pt.y() && op1->Prev != op1b && op1->Prev != op2)
      op1 = op1->Prev;
    while (op1b->Next->Pt.y() == op1b->Pt.y() && op1b->Next != op1 && op1b->Next != op2)
      op1b = op1b->Next;
    if (op1b->Next == op1 || op1b->Next == op2) return false; //a flat 'polygon'
 
    op2b = op2;
    while (op2->Prev->Pt.y() == op2->Pt.y() && op2->Prev != op2b && op2->Prev != op1b)
      op2 = op2->Prev;
    while (op2b->Next->Pt.y() == op2b->Pt.y() && op2b->Next != op2 && op2b->Next != op1)
      op2b = op2b->Next;
    if (op2b->Next == op2 || op2b->Next == op1) return false; //a flat 'polygon'
 
    cInt Left, Right;
    //Op1 --> Op1b & Op2 --> Op2b are the extremites of the horizontal edges
    if (!GetOverlap(op1->Pt.x(), op1b->Pt.x(), op2->Pt.x(), op2b->Pt.x(), Left, Right))
      return false;
 
    //DiscardLeftSide: when overlapping edges are joined, a spike will created
    //which needs to be cleaned up. However, we don't want Op1 or Op2 caught up
    //on the discard Side as either may still be needed for other joins ...
    IntPoint Pt;
    bool DiscardLeftSide;
    if (op1->Pt.x() >= Left && op1->Pt.x() <= Right) 
    {
      Pt = op1->Pt; DiscardLeftSide = (op1->Pt.x() > op1b->Pt.x());
    } 
    else if (op2->Pt.x() >= Left&& op2->Pt.x() <= Right) 
    {
      Pt = op2->Pt; DiscardLeftSide = (op2->Pt.x() > op2b->Pt.x());
    } 
    else if (op1b->Pt.x() >= Left && op1b->Pt.x() <= Right)
    {
      Pt = op1b->Pt; DiscardLeftSide = op1b->Pt.x() > op1->Pt.x();
    } 
    else
    {
      Pt = op2b->Pt; DiscardLeftSide = (op2b->Pt.x() > op2->Pt.x());
    }
    j->OutPt1 = op1; j->OutPt2 = op2;
    return JoinHorz(op1, op1b, op2, op2b, Pt, DiscardLeftSide);
  } else
  {
    //nb: For non-horizontal joins ...
    //    1. Jr.OutPt1.Pt.y() == Jr.OutPt2.Pt.y()
    //    2. Jr.OutPt1.Pt > Jr.OffPt.y()
 
    //make sure the polygons are correctly oriented ...
    op1b = op1->Next;
    while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Next;
    bool Reverse1 = ((op1b->Pt.y() > op1->Pt.y()) ||
      !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange));
    if (Reverse1)
    {
      op1b = op1->Prev;
      while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Prev;
      if ((op1b->Pt.y() > op1->Pt.y()) ||
        !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange)) return false;
    };
    op2b = op2->Next;
    while ((op2b->Pt == op2->Pt) && (op2b != op2))op2b = op2b->Next;
    bool Reverse2 = ((op2b->Pt.y() > op2->Pt.y()) ||
      !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange));
    if (Reverse2)
    {
      op2b = op2->Prev;
      while ((op2b->Pt == op2->Pt) && (op2b != op2)) op2b = op2b->Prev;
      if ((op2b->Pt.y() > op2->Pt.y()) ||
        !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange)) return false;
    }
 
    if ((op1b == op1) || (op2b == op2) || (op1b == op2b) ||
      ((outRec1 == outRec2) && (Reverse1 == Reverse2))) return false;
 
    if (Reverse1)
    {
      op1b = this->DupOutPt(op1, false);
      op2b = this->DupOutPt(op2, true);
      op1->Prev = op2;
      op2->Next = op1;
      op1b->Next = op2b;
      op2b->Prev = op1b;
      j->OutPt1 = op1;
      j->OutPt2 = op1b;
      return true;
    } else
    {
      op1b = this->DupOutPt(op1, true);
      op2b = this->DupOutPt(op2, false);
      op1->Next = op2;
      op2->Prev = op1;
      op1b->Prev = op2b;
      op2b->Next = op1b;
      j->OutPt1 = op1;
      j->OutPt2 = op1b;
      return true;
    }
  }
}

References DupOutPt(), ClipperLib::GetOverlap(), JoinHorz(), ClipperLib::ClipperBase::m_UseFullRange, ClipperLib::OutPt::Next, ClipperLib::Join::OffPt, ClipperLib::Join::OutPt1, ClipperLib::Join::OutPt2, ClipperLib::OutPt::Prev, ClipperLib::OutPt::Pt, and ClipperLib::SlopesEqual().

Referenced by JoinCommonEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PreserveCollinear() [1/2]

bool ClipperLib::ClipperBase::PreserveCollinear ( ) const

inlineinherited

388{return m_PreserveCollinear;};

◆ PreserveCollinear() [2/2]

void ClipperLib::ClipperBase::PreserveCollinear ( bool value )

inlineinherited

389{m_PreserveCollinear = value;};

◆ ProcessBound()

TEdge * ClipperLib::ClipperBase::ProcessBound	(	TEdge *	E,
		bool	IsClockwise
	)

protectedinherited

{
  TEdge *Result = E;
  TEdge *Horz = 0;
 
  if (E->OutIdx == Skip)
  {
    //if edges still remain in the current bound beyond the skip edge then
    //create another LocMin and call ProcessBound once more
    if (NextIsForward)
    {
      while (E->Top.y() == E->Next->Bot.y()) E = E->Next;
      //don't include top horizontals when parsing a bound a second time,
      //they will be contained in the opposite bound ...
      while (E != Result && IsHorizontal(*E)) E = E->Prev;
    }
    else
    {
      while (E->Top.y() == E->Prev->Bot.y()) E = E->Prev;
      while (E != Result && IsHorizontal(*E)) E = E->Next;
    }
 
    if (E == Result)
    {
      if (NextIsForward) Result = E->Next;
      else Result = E->Prev;
    }
    else
    {
      //there are more edges in the bound beyond result starting with E
      if (NextIsForward)
        E = Result->Next;
      else
        E = Result->Prev;
      LocalMinimum locMin;
      locMin.Y = E->Bot.y();
      locMin.LeftBound = 0;
      locMin.RightBound = E;
      E->WindDelta = 0;
      Result = ProcessBound(E, NextIsForward);
      m_MinimaList.emplace_back(locMin);
    }
    return Result;
  }
 
  TEdge *EStart;
 
  if (IsHorizontal(*E))
  {
    //We need to be careful with open paths because this may not be a
    //true local minima (ie E may be following a skip edge).
    //Also, consecutive horz. edges may start heading left before going right.
    if (NextIsForward) 
      EStart = E->Prev;
    else 
      EStart = E->Next;
    if (IsHorizontal(*EStart)) //ie an adjoining horizontal skip edge
      {
        if (EStart->Bot.x() != E->Bot.x() && EStart->Top.x() != E->Bot.x())
          ReverseHorizontal(*E);
      }
      else if (EStart->Bot.x() != E->Bot.x())
        ReverseHorizontal(*E);
  }
  
  EStart = E;
  if (NextIsForward)
  {
    while (Result->Top.y() == Result->Next->Bot.y() && Result->Next->OutIdx != Skip)
      Result = Result->Next;
    if (IsHorizontal(*Result) && Result->Next->OutIdx != Skip)
    {
      //nb: at the top of a bound, horizontals are added to the bound
      //only when the preceding edge attaches to the horizontal's left vertex
      //unless a Skip edge is encountered when that becomes the top divide
      Horz = Result;
      while (IsHorizontal(*Horz->Prev)) Horz = Horz->Prev;
      if (Horz->Prev->Top.x() > Result->Next->Top.x()) Result = Horz->Prev;
    }
    while (E != Result) 
    {
      E->NextInLML = E->Next;
      if (IsHorizontal(*E) && E != EStart &&
        E->Bot.x() != E->Prev->Top.x()) ReverseHorizontal(*E);
      E = E->Next;
    }
    if (IsHorizontal(*E) && E != EStart && E->Bot.x() != E->Prev->Top.x()) 
      ReverseHorizontal(*E);
    Result = Result->Next; //move to the edge just beyond current bound
  } else
  {
    while (Result->Top.y() == Result->Prev->Bot.y() && Result->Prev->OutIdx != Skip) 
      Result = Result->Prev;
    if (IsHorizontal(*Result) && Result->Prev->OutIdx != Skip)
    {
      Horz = Result;
      while (IsHorizontal(*Horz->Next)) Horz = Horz->Next;
      if (Horz->Next->Top.x() == Result->Prev->Top.x() ||
          Horz->Next->Top.x() > Result->Prev->Top.x()) Result = Horz->Next;
    }
 
    while (E != Result)
    {
      E->NextInLML = E->Prev;
      if (IsHorizontal(*E) && E != EStart && E->Bot.x() != E->Next->Top.x()) 
        ReverseHorizontal(*E);
      E = E->Prev;
    }
    if (IsHorizontal(*E) && E != EStart && E->Bot.x() != E->Next->Top.x()) 
      ReverseHorizontal(*E);
    Result = Result->Prev; //move to the edge just beyond current bound
  }
 
  return Result;
}

References ClipperLib::TEdge::Bot, ClipperLib::IsHorizontal(), ClipperLib::LocalMinimum::LeftBound, ClipperLib::TEdge::Next, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::Prev, ClipperLib::ReverseHorizontal(), ClipperLib::LocalMinimum::RightBound, ClipperLib::Skip, ClipperLib::TEdge::Top, and ClipperLib::LocalMinimum::Y.

Here is the call graph for this function:

◆ ProcessEdgesAtTopOfScanbeam()

void ClipperLib::Clipper::ProcessEdgesAtTopOfScanbeam ( const cInt topY )

private

{
  TEdge* e = m_ActiveEdges;
  while( e )
  {
    //1. process maxima, treating them as if they're 'bent' horizontal edges,
    //   but exclude maxima with horizontal edges. nb: e can't be a horizontal.
    bool IsMaximaEdge = IsMaxima(e, topY);
 
    if(IsMaximaEdge)
    {
      TEdge* eMaxPair = GetMaximaPair(e);
      IsMaximaEdge = (!eMaxPair || !IsHorizontal(*eMaxPair));
    }
 
    if(IsMaximaEdge)
    {
      if (m_StrictSimple) m_Maxima.emplace_back(e->Top.x());
      TEdge* ePrev = e->PrevInAEL;
      DoMaxima(e);
      if( !ePrev ) e = m_ActiveEdges;
      else e = ePrev->NextInAEL;
    }
    else
    {
      //2. promote horizontal edges, otherwise update Curr.x() and Curr.y() ...
      if (IsIntermediate(e, topY) && IsHorizontal(*e->NextInLML))
      {
        UpdateEdgeIntoAEL(e);
        if (e->OutIdx >= 0)
          AddOutPt(e, e->Bot);
        AddEdgeToSEL(e);
      } 
      else
      {
        e->Curr.x() = TopX( *e, topY );
        e->Curr.y() = topY;
#ifdef CLIPPERLIB_USE_XYZ
        e->Curr.z() = topY == e->Top.y() ? e->Top.z() : (topY == e->Bot.y() ? e->Bot.z() : 0);
#endif
      }
 
      //When StrictlySimple and 'e' is being touched by another edge, then
      //make sure both edges have a vertex here ...
      if (m_StrictSimple)
      {  
        TEdge* ePrev = e->PrevInAEL;
        if ((e->OutIdx >= 0) && (e->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) &&
          (ePrev->Curr.x() == e->Curr.x()) && (ePrev->WindDelta != 0))
        {
          IntPoint pt = e->Curr;
#ifdef CLIPPERLIB_USE_XYZ
          SetZ(pt, *ePrev, *e);
#endif
          OutPt* op = AddOutPt(ePrev, pt);
          OutPt* op2 = AddOutPt(e, pt);
          m_Joins.emplace_back(Join(op, op2, pt)); //StrictlySimple (type-3) join
        }
      }
 
      e = e->NextInAEL;
    }
  }
 
  //3. Process horizontals at the Top of the scanbeam ...
  std::sort(m_Maxima.begin(), m_Maxima.end());
  ProcessHorizontals();
  m_Maxima.clear();
 
  //4. Promote intermediate vertices ...
  e = m_ActiveEdges;
  while(e)
  {
    if(IsIntermediate(e, topY))
    {
      OutPt* op = 0;
      if( e->OutIdx >= 0 ) 
        op = AddOutPt(e, e->Top);
      UpdateEdgeIntoAEL(e);
 
      //if output polygons share an edge, they'll need joining later ...
      TEdge* ePrev = e->PrevInAEL;
      TEdge* eNext = e->NextInAEL;
      if (ePrev && ePrev->Curr.x() == e->Bot.x() &&
        ePrev->Curr.y() == e->Bot.y() && op &&
        ePrev->OutIdx >= 0 && ePrev->Curr.y() > ePrev->Top.y() &&
        SlopesEqual(*e, *ePrev, m_UseFullRange) &&
        (e->WindDelta != 0) && (ePrev->WindDelta != 0))
      {
        OutPt* op2 = AddOutPt(ePrev, e->Bot);
        m_Joins.emplace_back(Join(op, op2, e->Top));
      }
      else if (eNext && eNext->Curr.x() == e->Bot.x() &&
        eNext->Curr.y() == e->Bot.y() && op &&
        eNext->OutIdx >= 0 && eNext->Curr.y() > eNext->Top.y() &&
        SlopesEqual(*e, *eNext, m_UseFullRange) &&
        (e->WindDelta != 0) && (eNext->WindDelta != 0))
      {
        OutPt* op2 = AddOutPt(eNext, e->Bot);
        m_Joins.emplace_back(Join(op, op2, e->Top));
      }
    }
    e = e->NextInAEL;
  }
}

References AddEdgeToSEL(), AddOutPt(), ClipperLib::TEdge::Bot, ClipperLib::TEdge::Curr, DoMaxima(), ClipperLib::GetMaximaPair(), ClipperLib::IsHorizontal(), ClipperLib::IsIntermediate(), ClipperLib::IsMaxima(), m_ActiveEdges, m_Joins, m_Maxima, m_StrictSimple, ClipperLib::ClipperBase::m_UseFullRange, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::NextInLML, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::PrevInAEL, ProcessHorizontals(), ClipperLib::SlopesEqual(), ClipperLib::TEdge::Top, ClipperLib::TopX(), UpdateEdgeIntoAEL(), and ClipperLib::TEdge::WindDelta.

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ProcessHorizontal()

void ClipperLib::Clipper::ProcessHorizontal ( TEdge * horzEdge )

private

{
  Direction dir;
  cInt horzLeft, horzRight;
  bool IsOpen = (horzEdge->OutIdx >= 0 && m_PolyOuts[horzEdge->OutIdx].IsOpen);
 
  GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
 
  TEdge* eLastHorz = horzEdge, *eMaxPair = 0;
  while (eLastHorz->NextInLML && IsHorizontal(*eLastHorz->NextInLML)) 
    eLastHorz = eLastHorz->NextInLML;
  if (!eLastHorz->NextInLML)
    eMaxPair = GetMaximaPair(eLastHorz);
 
  cInts::const_iterator maxIt;
  cInts::const_reverse_iterator maxRit;
  if (!m_Maxima.empty())
  {
      //get the first maxima in range (X) ...
      if (dir == dLeftToRight)
      {
          maxIt = m_Maxima.begin();
          while (maxIt != m_Maxima.end() && *maxIt <= horzEdge->Bot.x()) ++maxIt;
          if (maxIt != m_Maxima.end() && *maxIt >= eLastHorz->Top.x())
              maxIt = m_Maxima.end();
      }
      else
      {
          maxRit = m_Maxima.rbegin();
          while (maxRit != m_Maxima.rend() && *maxRit > horzEdge->Bot.x()) ++maxRit;
          if (maxRit != m_Maxima.rend() && *maxRit <= eLastHorz->Top.x())
              maxRit = m_Maxima.rend();
      }
  }
 
  OutPt* op1 = 0;
 
  for (;;) //loop through consec. horizontal edges
  {
      
    bool IsLastHorz = (horzEdge == eLastHorz);
    TEdge* e = (dir == dLeftToRight) ? horzEdge->NextInAEL : horzEdge->PrevInAEL;
    while(e)
    {
 
        //this code block inserts extra coords into horizontal edges (in output
        //polygons) whereever maxima touch these horizontal edges. This helps
        //'simplifying' polygons (ie if the Simplify property is set).
        if (!m_Maxima.empty())
        {
            if (dir == dLeftToRight)
            {
                while (maxIt != m_Maxima.end() && *maxIt < e->Curr.x()) 
                {
                  if (horzEdge->OutIdx >= 0 && !IsOpen)
                    AddOutPt(horzEdge, IntPoint2d(*maxIt, horzEdge->Bot.y()));
                  ++maxIt;
                }
            }
            else
            {
                while (maxRit != m_Maxima.rend() && *maxRit > e->Curr.x())
                {
                  if (horzEdge->OutIdx >= 0 && !IsOpen)
                    AddOutPt(horzEdge, IntPoint2d(*maxRit, horzEdge->Bot.y()));
                  ++maxRit;
                }
            }
        };
 
        if ((dir == dLeftToRight && e->Curr.x() > horzRight) ||
      (dir == dRightToLeft && e->Curr.x() < horzLeft)) break;
 
    //Also break if we've got to the end of an intermediate horizontal edge ...
    //nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
    if (e->Curr.x() == horzEdge->Top.x() && horzEdge->NextInLML && 
      e->Dx < horzEdge->NextInLML->Dx) break;
 
    if (horzEdge->OutIdx >= 0 && !IsOpen)  //note: may be done multiple times
    {
#ifdef CLIPPERLIB_USE_XYZ
            if (dir == dLeftToRight)
                SetZ(e->Curr, *horzEdge, *e);
            else
                SetZ(e->Curr, *e, *horzEdge);
#endif
            op1 = AddOutPt(horzEdge, e->Curr);
      TEdge* eNextHorz = m_SortedEdges;
      while (eNextHorz)
      {
        if (eNextHorz->OutIdx >= 0 &&
          HorzSegmentsOverlap(horzEdge->Bot.x(),
          horzEdge->Top.x(), eNextHorz->Bot.x(), eNextHorz->Top.x()))
        {
                    OutPt* op2 = GetLastOutPt(eNextHorz);
                    m_Joins.emplace_back(Join(op2, op1, eNextHorz->Top));
        }
        eNextHorz = eNextHorz->NextInSEL;
      }
      m_GhostJoins.emplace_back(Join(op1, 0, horzEdge->Bot));
    }
    
    //OK, so far we're still in range of the horizontal Edge  but make sure
        //we're at the last of consec. horizontals when matching with eMaxPair
        if(e == eMaxPair && IsLastHorz)
        {
          if (horzEdge->OutIdx >= 0)
            AddLocalMaxPoly(horzEdge, eMaxPair, horzEdge->Top);
          DeleteFromAEL(horzEdge);
          DeleteFromAEL(eMaxPair);
          return;
        }
        
    if(dir == dLeftToRight)
        {
          IntPoint Pt = IntPoint2d(e->Curr.x(), horzEdge->Curr.y());
          IntersectEdges(horzEdge, e, Pt);
        }
        else
        {
          IntPoint Pt = IntPoint2d(e->Curr.x(), horzEdge->Curr.y());
          IntersectEdges( e, horzEdge, Pt);
        }
        TEdge* eNext = (dir == dLeftToRight) ? e->NextInAEL : e->PrevInAEL;
        SwapPositionsInAEL( horzEdge, e );
        e = eNext;
    } //end while(e)
 
  //Break out of loop if HorzEdge.NextInLML is not also horizontal ...
  if (!horzEdge->NextInLML || !IsHorizontal(*horzEdge->NextInLML)) break;
 
  UpdateEdgeIntoAEL(horzEdge);
    if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Bot);
    GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
 
  } //end for (;;)
 
  if (horzEdge->OutIdx >= 0 && !op1)
  {
      op1 = GetLastOutPt(horzEdge);
      TEdge* eNextHorz = m_SortedEdges;
      while (eNextHorz)
      {
          if (eNextHorz->OutIdx >= 0 &&
              HorzSegmentsOverlap(horzEdge->Bot.x(),
              horzEdge->Top.x(), eNextHorz->Bot.x(), eNextHorz->Top.x()))
          {
              OutPt* op2 = GetLastOutPt(eNextHorz);
              m_Joins.emplace_back(Join(op2, op1, eNextHorz->Top));
          }
          eNextHorz = eNextHorz->NextInSEL;
      }
      m_GhostJoins.emplace_back(Join(op1, 0, horzEdge->Top));
  }
 
  if (horzEdge->NextInLML)
  {
    if(horzEdge->OutIdx >= 0)
    {
      op1 = AddOutPt( horzEdge, horzEdge->Top);
      UpdateEdgeIntoAEL(horzEdge);
      if (horzEdge->WindDelta == 0) return;
      //nb: HorzEdge is no longer horizontal here
      TEdge* ePrev = horzEdge->PrevInAEL;
      TEdge* eNext = horzEdge->NextInAEL;
      if (ePrev && ePrev->Curr.x() == horzEdge->Bot.x() &&
        ePrev->Curr.y() == horzEdge->Bot.y() && ePrev->WindDelta != 0 &&
        (ePrev->OutIdx >= 0 && ePrev->Curr.y() > ePrev->Top.y() &&
        SlopesEqual(*horzEdge, *ePrev, m_UseFullRange)))
      {
        OutPt* op2 = AddOutPt(ePrev, horzEdge->Bot);
        m_Joins.emplace_back(Join(op1, op2, horzEdge->Top));
      }
      else if (eNext && eNext->Curr.x() == horzEdge->Bot.x() &&
        eNext->Curr.y() == horzEdge->Bot.y() && eNext->WindDelta != 0 &&
        eNext->OutIdx >= 0 && eNext->Curr.y() > eNext->Top.y() &&
        SlopesEqual(*horzEdge, *eNext, m_UseFullRange))
      {
        OutPt* op2 = AddOutPt(eNext, horzEdge->Bot);
        m_Joins.emplace_back(Join(op1, op2, horzEdge->Top));
      }
    }
    else
      UpdateEdgeIntoAEL(horzEdge); 
  }
  else
  {
    if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Top);
    DeleteFromAEL(horzEdge);
  }
}

References AddLocalMaxPoly(), AddOutPt(), ClipperLib::TEdge::Bot, ClipperLib::TEdge::Curr, DeleteFromAEL(), ClipperLib::dLeftToRight, ClipperLib::dRightToLeft, ClipperLib::TEdge::Dx, ClipperLib::GetHorzDirection(), GetLastOutPt(), ClipperLib::GetMaximaPair(), ClipperLib::HorzSegmentsOverlap(), IntersectEdges(), ClipperLib::IntPoint2d(), ClipperLib::IsHorizontal(), m_GhostJoins, m_Joins, m_Maxima, m_PolyOuts, m_SortedEdges, ClipperLib::ClipperBase::m_UseFullRange, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::NextInLML, ClipperLib::TEdge::NextInSEL, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::PrevInAEL, ClipperLib::SlopesEqual(), SwapPositionsInAEL(), ClipperLib::TEdge::Top, UpdateEdgeIntoAEL(), and ClipperLib::TEdge::WindDelta.

Referenced by ProcessHorizontals().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ProcessHorizontals()

void ClipperLib::Clipper::ProcessHorizontals ( )

private

{
  TEdge* horzEdge = m_SortedEdges;
  while(horzEdge)
  {
    DeleteFromSEL(horzEdge);
    ProcessHorizontal(horzEdge);
    horzEdge = m_SortedEdges;
  }
}

References DeleteFromSEL(), m_SortedEdges, and ProcessHorizontal().

Referenced by ExecuteInternal(), and ProcessEdgesAtTopOfScanbeam().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ProcessIntersections()

bool ClipperLib::Clipper::ProcessIntersections ( const cInt topY )

private

{
  if( !m_ActiveEdges ) return true;
  try {
    BuildIntersectList(topY);
    size_t IlSize = m_IntersectList.size();
    if (IlSize == 0) return true;
    if (IlSize == 1 || FixupIntersectionOrder()) {
      for (IntersectNode &iNode : m_IntersectList) {
        IntersectEdges( iNode.Edge1, iNode.Edge2, iNode.Pt);
        SwapPositionsInAEL( iNode.Edge1 , iNode.Edge2 );
      }
      m_IntersectList.clear();
    }
    else return false;
  }
  catch(...) 
  {
    m_SortedEdges = 0;
    m_IntersectList.clear();
    throw clipperException("ProcessIntersections error");
  }
  m_SortedEdges = 0;
  return true;
}

References BuildIntersectList(), FixupIntersectionOrder(), IntersectEdges(), m_ActiveEdges, m_IntersectList, m_SortedEdges, and SwapPositionsInAEL().

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Reset()

void ClipperLib::Clipper::Reset ( )

protected

{
  ClipperBase::Reset();
  m_Scanbeam = std::priority_queue<cInt, cInts>{};
  m_Maxima.clear();
  m_ActiveEdges = 0;
  m_SortedEdges = 0;
  for (auto lm = m_MinimaList.rbegin(); lm != m_MinimaList.rend(); ++lm)
    m_Scanbeam.push(lm->Y);
}

References m_ActiveEdges, m_Maxima, ClipperLib::ClipperBase::m_MinimaList, m_Scanbeam, m_SortedEdges, and ClipperLib::ClipperBase::Reset().

Referenced by ExecuteInternal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ReverseSolution() [1/2]

bool ClipperLib::Clipper::ReverseSolution ( ) const

inline

441{ return m_ReverseOutput; };

Referenced by ClipperLib::ClipperOffset::Execute(), ClipperLib::ClipperOffset::Execute(), Slic3r::fix_after_inner_offset(), Slic3r::fix_after_outer_offset(), and Slic3r::shrink_paths().

Here is the caller graph for this function:

◆ ReverseSolution() [2/2]

void ClipperLib::Clipper::ReverseSolution ( bool value )

inline

442{m_ReverseOutput = value;};

◆ SetHoleState()

void ClipperLib::Clipper::SetHoleState	(	TEdge *	e,
		OutRec *	outrec
	)

private

{
  bool IsHole = false;
  TEdge *e2 = e->PrevInAEL;
  while (e2)
  {
    if (e2->OutIdx >= 0 && e2->WindDelta != 0)
    {
      IsHole = !IsHole;
      if (! outrec->FirstLeft)
        outrec->FirstLeft = &m_PolyOuts[e2->OutIdx];
    }
    e2 = e2->PrevInAEL;
  }
  if (IsHole) outrec->IsHole = true;
}

References ClipperLib::OutRec::FirstLeft, ClipperLib::OutRec::IsHole, m_PolyOuts, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::PrevInAEL, and ClipperLib::TEdge::WindDelta.

Referenced by AddOutPt().

Here is the caller graph for this function:

◆ SetWindingCount()

void ClipperLib::Clipper::SetWindingCount ( TEdge & edge ) const

private

{
  TEdge *e = edge.PrevInAEL;
  //find the edge of the same polytype that immediately preceeds 'edge' in AEL
  while (e  && ((e->PolyTyp != edge.PolyTyp) || (e->WindDelta == 0))) e = e->PrevInAEL;
  if (!e)
  {
    edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
    edge.WindCnt2 = 0;
    e = m_ActiveEdges; //ie get ready to calc WindCnt2
  }   
  else if (edge.WindDelta == 0 && m_ClipType != ctUnion)
  {
    edge.WindCnt = 1;
    edge.WindCnt2 = e->WindCnt2;
    e = e->NextInAEL; //ie get ready to calc WindCnt2
  }
  else if (IsEvenOddFillType(edge))
  {
    //EvenOdd filling ...
    if (edge.WindDelta == 0)
    {
      //are we inside a subj polygon ...
      bool Inside = true;
      TEdge *e2 = e->PrevInAEL;
      while (e2)
      {
        if (e2->PolyTyp == e->PolyTyp && e2->WindDelta != 0) 
          Inside = !Inside;
        e2 = e2->PrevInAEL;
      }
      edge.WindCnt = (Inside ? 0 : 1);
    }
    else
    {
      edge.WindCnt = edge.WindDelta;
    }
    edge.WindCnt2 = e->WindCnt2;
    e = e->NextInAEL; //ie get ready to calc WindCnt2
  } 
  else
  {
    //nonZero, Positive or Negative filling ...
    if (e->WindCnt * e->WindDelta < 0)
    {
      //prev edge is 'decreasing' WindCount (WC) toward zero
      //so we're outside the previous polygon ...
      if (std::abs(e->WindCnt) > 1)
      {
        //outside prev poly but still inside another.
        //when reversing direction of prev poly use the same WC 
        if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
        //otherwise continue to 'decrease' WC ...
        else edge.WindCnt = e->WindCnt + edge.WindDelta;
      } 
      else
        //now outside all polys of same polytype so set own WC ...
        edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
    } else
    {
      //prev edge is 'increasing' WindCount (WC) away from zero
      //so we're inside the previous polygon ...
      if (edge.WindDelta == 0) 
        edge.WindCnt = (e->WindCnt < 0 ? e->WindCnt - 1 : e->WindCnt + 1);
      //if wind direction is reversing prev then use same WC
      else if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
      //otherwise add to WC ...
      else edge.WindCnt = e->WindCnt + edge.WindDelta;
    }
    edge.WindCnt2 = e->WindCnt2;
    e = e->NextInAEL; //ie get ready to calc WindCnt2
  }
 
  //update WindCnt2 ...
  if (IsEvenOddAltFillType(edge))
  {
    //EvenOdd filling ...
    while (e != &edge)
    {
      if (e->WindDelta != 0)
        edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);
      e = e->NextInAEL;
    }
  } else
  {
    //nonZero, Positive or Negative filling ...
    while ( e != &edge )
    {
      edge.WindCnt2 += e->WindDelta;
      e = e->NextInAEL;
    }
  }
}

References ClipperLib::ctUnion, IsEvenOddAltFillType(), IsEvenOddFillType(), m_ActiveEdges, m_ClipType, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::PolyTyp, ClipperLib::TEdge::PrevInAEL, ClipperLib::TEdge::WindCnt, ClipperLib::TEdge::WindCnt2, and ClipperLib::TEdge::WindDelta.

Referenced by InsertLocalMinimaIntoAEL().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ StrictlySimple() [1/2]

bool ClipperLib::Clipper::StrictlySimple ( ) const

inline

443{return m_StrictSimple;};

◆ StrictlySimple() [2/2]

void ClipperLib::Clipper::StrictlySimple ( bool value )

inline

444{m_StrictSimple = value;};

◆ SwapPositionsInAEL()

void ClipperLib::Clipper::SwapPositionsInAEL	(	TEdge *	edge1,
		TEdge *	edge2
	)

private

{
  //check that one or other edge hasn't already been removed from AEL ...
  if (Edge1->NextInAEL == Edge1->PrevInAEL || 
    Edge2->NextInAEL == Edge2->PrevInAEL) return;
 
  if(  Edge1->NextInAEL == Edge2 )
  {
    TEdge* Next = Edge2->NextInAEL;
    if( Next ) Next->PrevInAEL = Edge1;
    TEdge* Prev = Edge1->PrevInAEL;
    if( Prev ) Prev->NextInAEL = Edge2;
    Edge2->PrevInAEL = Prev;
    Edge2->NextInAEL = Edge1;
    Edge1->PrevInAEL = Edge2;
    Edge1->NextInAEL = Next;
  }
  else if(  Edge2->NextInAEL == Edge1 )
  {
    TEdge* Next = Edge1->NextInAEL;
    if( Next ) Next->PrevInAEL = Edge2;
    TEdge* Prev = Edge2->PrevInAEL;
    if( Prev ) Prev->NextInAEL = Edge1;
    Edge1->PrevInAEL = Prev;
    Edge1->NextInAEL = Edge2;
    Edge2->PrevInAEL = Edge1;
    Edge2->NextInAEL = Next;
  }
  else
  {
    TEdge* Next = Edge1->NextInAEL;
    TEdge* Prev = Edge1->PrevInAEL;
    Edge1->NextInAEL = Edge2->NextInAEL;
    if( Edge1->NextInAEL ) Edge1->NextInAEL->PrevInAEL = Edge1;
    Edge1->PrevInAEL = Edge2->PrevInAEL;
    if( Edge1->PrevInAEL ) Edge1->PrevInAEL->NextInAEL = Edge1;
    Edge2->NextInAEL = Next;
    if( Edge2->NextInAEL ) Edge2->NextInAEL->PrevInAEL = Edge2;
    Edge2->PrevInAEL = Prev;
    if( Edge2->PrevInAEL ) Edge2->PrevInAEL->NextInAEL = Edge2;
  }
 
  if( !Edge1->PrevInAEL ) m_ActiveEdges = Edge1;
  else if( !Edge2->PrevInAEL ) m_ActiveEdges = Edge2;
}

References m_ActiveEdges, ClipperLib::TEdge::NextInAEL, and ClipperLib::TEdge::PrevInAEL.

Referenced by DoMaxima(), ProcessHorizontal(), and ProcessIntersections().

Here is the caller graph for this function:

◆ SwapPositionsInSEL()

void ClipperLib::Clipper::SwapPositionsInSEL	(	TEdge *	edge1,
		TEdge *	edge2
	)

private

{
  if(  !( Edge1->NextInSEL ) &&  !( Edge1->PrevInSEL ) ) return;
  if(  !( Edge2->NextInSEL ) &&  !( Edge2->PrevInSEL ) ) return;
 
  if(  Edge1->NextInSEL == Edge2 )
  {
    TEdge* Next = Edge2->NextInSEL;
    if( Next ) Next->PrevInSEL = Edge1;
    TEdge* Prev = Edge1->PrevInSEL;
    if( Prev ) Prev->NextInSEL = Edge2;
    Edge2->PrevInSEL = Prev;
    Edge2->NextInSEL = Edge1;
    Edge1->PrevInSEL = Edge2;
    Edge1->NextInSEL = Next;
  }
  else if(  Edge2->NextInSEL == Edge1 )
  {
    TEdge* Next = Edge1->NextInSEL;
    if( Next ) Next->PrevInSEL = Edge2;
    TEdge* Prev = Edge2->PrevInSEL;
    if( Prev ) Prev->NextInSEL = Edge1;
    Edge1->PrevInSEL = Prev;
    Edge1->NextInSEL = Edge2;
    Edge2->PrevInSEL = Edge1;
    Edge2->NextInSEL = Next;
  }
  else
  {
    TEdge* Next = Edge1->NextInSEL;
    TEdge* Prev = Edge1->PrevInSEL;
    Edge1->NextInSEL = Edge2->NextInSEL;
    if( Edge1->NextInSEL ) Edge1->NextInSEL->PrevInSEL = Edge1;
    Edge1->PrevInSEL = Edge2->PrevInSEL;
    if( Edge1->PrevInSEL ) Edge1->PrevInSEL->NextInSEL = Edge1;
    Edge2->NextInSEL = Next;
    if( Edge2->NextInSEL ) Edge2->NextInSEL->PrevInSEL = Edge2;
    Edge2->PrevInSEL = Prev;
    if( Edge2->PrevInSEL ) Edge2->PrevInSEL->NextInSEL = Edge2;
  }
 
  if( !Edge1->PrevInSEL ) m_SortedEdges = Edge1;
  else if( !Edge2->PrevInSEL ) m_SortedEdges = Edge2;
}

References m_SortedEdges, ClipperLib::TEdge::NextInSEL, and ClipperLib::TEdge::PrevInSEL.

Referenced by BuildIntersectList(), and FixupIntersectionOrder().

Here is the caller graph for this function:

◆ UpdateEdgeIntoAEL()

void ClipperLib::Clipper::UpdateEdgeIntoAEL ( TEdge *& e )

private

{
  if( !e->NextInLML ) 
    throw clipperException("UpdateEdgeIntoAEL: invalid call");
 
  e->NextInLML->OutIdx = e->OutIdx;
  TEdge* AelPrev = e->PrevInAEL;
  TEdge* AelNext = e->NextInAEL;
  if (AelPrev) AelPrev->NextInAEL = e->NextInLML;
  else m_ActiveEdges = e->NextInLML;
  if (AelNext) AelNext->PrevInAEL = e->NextInLML;
  e->NextInLML->Side = e->Side;
  e->NextInLML->WindDelta = e->WindDelta;
  e->NextInLML->WindCnt = e->WindCnt;
  e->NextInLML->WindCnt2 = e->WindCnt2;
  e = e->NextInLML;
  e->Curr = e->Bot;
  e->PrevInAEL = AelPrev;
  e->NextInAEL = AelNext;
  if (!IsHorizontal(*e)) 
    m_Scanbeam.push(e->Top.y());
}

References ClipperLib::TEdge::Bot, ClipperLib::TEdge::Curr, ClipperLib::IsHorizontal(), m_ActiveEdges, m_Scanbeam, ClipperLib::TEdge::NextInAEL, ClipperLib::TEdge::NextInLML, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::PrevInAEL, ClipperLib::TEdge::Side, ClipperLib::TEdge::Top, ClipperLib::TEdge::WindCnt, ClipperLib::TEdge::WindCnt2, and ClipperLib::TEdge::WindDelta.

Referenced by ProcessEdgesAtTopOfScanbeam(), and ProcessHorizontal().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ m_ActiveEdges

TEdge* ClipperLib::Clipper::m_ActiveEdges

private

Referenced by AppendPolygon(), BuildIntersectList(), CopyAELToSEL(), DeleteFromAEL(), InsertEdgeIntoAEL(), ProcessEdgesAtTopOfScanbeam(), ProcessIntersections(), Reset(), SetWindingCount(), SwapPositionsInAEL(), and UpdateEdgeIntoAEL().

◆ m_ClipFillType

PolyFillType ClipperLib::Clipper::m_ClipFillType

private

Referenced by Execute(), Execute(), IntersectEdges(), and IsContributing().

◆ m_ClipType

ClipType ClipperLib::Clipper::m_ClipType

private

Referenced by Execute(), Execute(), IntersectEdges(), IsContributing(), and SetWindingCount().

◆ m_edges

std::vector<Edges, Allocator<Edges> > ClipperLib::ClipperBase::m_edges

protectedinherited

◆ m_GhostJoins

std::vector<Join, Allocator<Join> > ClipperLib::Clipper::m_GhostJoins

private

Referenced by ExecuteInternal(), InsertLocalMinimaIntoAEL(), and ProcessHorizontal().

◆ m_HasOpenPaths

bool ClipperLib::ClipperBase::m_HasOpenPaths

protectedinherited

Referenced by Clipper(), and Execute().

◆ m_IntersectList

std::vector<IntersectNode, Allocator<IntersectNode> > ClipperLib::Clipper::m_IntersectList

private

Referenced by BuildIntersectList(), FixupIntersectionOrder(), and ProcessIntersections().

◆ m_Joins

std::vector<Join, Allocator<Join> > ClipperLib::Clipper::m_Joins

private

Referenced by AddLocalMinPoly(), ExecuteInternal(), InsertLocalMinimaIntoAEL(), JoinCommonEdges(), ProcessEdgesAtTopOfScanbeam(), and ProcessHorizontal().

◆ m_Maxima

cInts ClipperLib::Clipper::m_Maxima

private

Referenced by ProcessEdgesAtTopOfScanbeam(), ProcessHorizontal(), and Reset().

◆ m_MinimaList

std::vector<LocalMinimum, Allocator<LocalMinimum> > ClipperLib::ClipperBase::m_MinimaList

protectedinherited

Referenced by ExecuteInternal(), InsertLocalMinimaIntoAEL(), and Reset().

◆ m_OutPts

std::deque<std::array<OutPt, m_OutPtsChunkSize>, Allocator<std::array<OutPt, m_OutPtsChunkSize> > > ClipperLib::Clipper::m_OutPts

private

Referenced by AllocateOutPt(), and DisposeAllOutRecs().

◆ m_OutPtsChunkLast

size_t ClipperLib::Clipper::m_OutPtsChunkLast

private

Referenced by AllocateOutPt(), and DisposeAllOutRecs().

◆ m_OutPtsChunkSize

constexpr const size_t ClipperLib::Clipper::m_OutPtsChunkSize = 32

staticconstexprprivate

Referenced by AllocateOutPt(), and DisposeAllOutRecs().

◆ m_OutPtsFree

OutPt* ClipperLib::Clipper::m_OutPtsFree

private

Referenced by AllocateOutPt(), and DisposeAllOutRecs().

◆ m_PolyOuts

std::deque<OutRec, Allocator<OutRec> > ClipperLib::Clipper::m_PolyOuts

private

Referenced by AddOutPt(), AppendPolygon(), BuildResult(), BuildResult2(), CreateOutRec(), DisposeAllOutRecs(), DoSimplePolygons(), ExecuteInternal(), FixupFirstLefts1(), FixupFirstLefts2(), GetLastOutPt(), GetOutRec(), JoinCommonEdges(), ProcessHorizontal(), and SetHoleState().

◆ m_PreserveCollinear

bool ClipperLib::ClipperBase::m_PreserveCollinear

protectedinherited

Referenced by Clipper(), and FixupOutPolygon().

◆ m_ReverseOutput

bool ClipperLib::Clipper::m_ReverseOutput

private

Referenced by Clipper(), ExecuteInternal(), and JoinCommonEdges().

◆ m_Scanbeam

std::priority_queue<cInt, cInts> ClipperLib::Clipper::m_Scanbeam

private

Referenced by ExecuteInternal(), InsertLocalMinimaIntoAEL(), Reset(), and UpdateEdgeIntoAEL().

◆ m_SortedEdges

TEdge* ClipperLib::Clipper::m_SortedEdges

private

Referenced by AddEdgeToSEL(), BuildIntersectList(), CopyAELToSEL(), DeleteFromSEL(), ProcessHorizontal(), ProcessHorizontals(), ProcessIntersections(), Reset(), and SwapPositionsInSEL().

◆ m_StrictSimple

bool ClipperLib::Clipper::m_StrictSimple

private

Referenced by Clipper(), ExecuteInternal(), FixupOutPolygon(), and ProcessEdgesAtTopOfScanbeam().

◆ m_SubjFillType

PolyFillType ClipperLib::Clipper::m_SubjFillType

private

Referenced by Execute(), Execute(), IntersectEdges(), and IsContributing().

◆ m_UseFullRange

constexpr const bool ClipperLib::ClipperBase::m_UseFullRange = false

staticconstexprprotectedinherited

Referenced by AddLocalMinPoly(), FixupOutPolygon(), InsertLocalMinimaIntoAEL(), JoinPoints(), ProcessEdgesAtTopOfScanbeam(), and ProcessHorizontal().

◆ m_UsingPolyTree

bool ClipperLib::Clipper::m_UsingPolyTree

private

Referenced by DoSimplePolygons(), Execute(), Execute(), and JoinCommonEdges().

The documentation for this class was generated from the following files:

src/clipper/clipper.hpp
src/clipper/clipper.cpp

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ cInts

◆ Edges

Constructor & Destructor Documentation

◆ Clipper()

◆ ~Clipper()

Member Function Documentation

◆ AddBoundsToLML()

◆ AddEdgeToSEL()

◆ AddLocalMaxPoly()

◆ AddLocalMinPoly()

◆ AddOutPt()

◆ AddPath()

◆ AddPathInternal()

◆ AddPaths()

◆ AllocateOutPt()

◆ AppendPolygon()

◆ AscendToMax()

◆ BuildIntersectList()

◆ BuildResult()

◆ BuildResult2()

◆ Clear()

◆ CopyAELToSEL()

◆ CreateOutRec()

◆ DeleteFromAEL()

◆ DeleteFromSEL()

◆ DescendToMin()

◆ DisposeAllOutRecs()

◆ DisposeOutPt()

◆ DisposeOutPts()

◆ DoMaxima()

◆ DoSimplePolygons()

◆ DupOutPt()

◆ Execute() [1/4]

◆ Execute() [2/4]

◆ Execute() [3/4]

◆ Execute() [4/4]

◆ ExecuteInternal()

◆ FindOwnerFromSplitRecs()

◆ FixHoleLinkage()

◆ FixupFirstLefts1()

◆ FixupFirstLefts2()

◆ FixupIntersectionOrder()

◆ FixupOutPolygon()

◆ FixupOutPolyline()

◆ GetBounds()

◆ GetLastOutPt()

◆ GetOutRec()

◆ InsertEdgeIntoAEL()

◆ InsertLocalMinimaIntoAEL()

◆ IntersectEdges()

◆ IsContributing()

◆ IsEvenOddAltFillType()

◆ IsEvenOddFillType()

◆ IsTopHorz()

◆ JoinCommonEdges()

◆ JoinHorz()

◆ JoinPoints()

◆ PreserveCollinear() [1/2]

◆ PreserveCollinear() [2/2]

◆ ProcessBound()

◆ ProcessEdgesAtTopOfScanbeam()

◆ ProcessHorizontal()

◆ ProcessHorizontals()

◆ ProcessIntersections()

◆ Reset()

◆ ReverseSolution() [1/2]

◆ ReverseSolution() [2/2]

◆ SetHoleState()

◆ SetWindingCount()