ClipperLib::ClipperBase Class Reference

#include <src/clipper/clipper.hpp>

Inheritance diagram for ClipperLib::ClipperBase:

Collaboration diagram for ClipperLib::ClipperBase:

Public Member Functions
	ClipperBase ()
	~ClipperBase ()
bool	AddPath (const Path &pg, PolyType PolyTyp, bool Closed)
template<typename PathsProvider >
bool	AddPaths (PathsProvider &&paths_provider, PolyType PolyTyp, bool Closed)
void	Clear ()
IntRect	GetBounds ()
bool	PreserveCollinear () const
void	PreserveCollinear (bool value)

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

Protected Member Functions
bool	AddPathInternal (const Path &pg, int highI, PolyType PolyTyp, bool Closed, TEdge *edges)
TEdge *	AddBoundsToLML (TEdge *e, bool IsClosed)
void	Reset ()
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

Detailed Description

Member Typedef Documentation

Edges

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

protected

Constructor & Destructor Documentation

ClipperBase()

ClipperLib::ClipperBase::ClipperBase ( )

inline

                : 
#ifndef CLIPPERLIB_INT32
    m_UseFullRange(false), 
#endif // CLIPPERLIB_INT32
    m_HasOpenPaths(false) {}

~ClipperBase()

ClipperLib::ClipperBase::~ClipperBase ( )

inline

{ Clear(); }

Member Function Documentation

AddBoundsToLML()

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

protected

AddPath()

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

{
  // 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  )

protected

{
#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  )

inline

  {
    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:

AscendToMax()

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

protected

Clear()

void ClipperLib::ClipperBase::Clear

(

)

{
  m_MinimaList.clear();
  m_edges.clear();
#ifndef CLIPPERLIB_INT32
  m_UseFullRange = false;
#endif // CLIPPERLIB_INT32
  m_HasOpenPaths = false;
}

DescendToMin()

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

protected

GetBounds()

IntRect ClipperLib::ClipperBase::GetBounds

(

)

{
  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:

PreserveCollinear() [1/2]

bool ClipperLib::ClipperBase::PreserveCollinear ( ) const

inline

{return m_PreserveCollinear;};

PreserveCollinear() [2/2]

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

inline

{m_PreserveCollinear = value;};

ProcessBound()

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

protected

{
  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:

Reset()

void ClipperLib::ClipperBase::Reset ( )

protected

{
  if (m_MinimaList.empty()) return; //ie nothing to process
  std::sort(m_MinimaList.begin(), m_MinimaList.end(), [](const LocalMinimum& lm1, const LocalMinimum& lm2){ return lm1.Y < lm2.Y; });
 
  //reset all edges ...
  for (LocalMinimum &lm : m_MinimaList) {
    TEdge* e = lm.LeftBound;
    if (e)
    {
      e->Curr = e->Bot;
      e->Side = esLeft;
      e->OutIdx = Unassigned;
    }
 
    e = lm.RightBound;
    if (e)
    {
      e->Curr = e->Bot;
      e->Side = esRight;
      e->OutIdx = Unassigned;
    }
  }
}

References ClipperLib::TEdge::Bot, ClipperLib::TEdge::Curr, ClipperLib::esLeft, ClipperLib::esRight, ClipperLib::TEdge::OutIdx, ClipperLib::TEdge::Side, and ClipperLib::Unassigned.

Referenced by ClipperLib::Clipper::Reset().

Here is the caller graph for this function:

Member Data Documentation

m_edges

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

protected

m_HasOpenPaths

bool ClipperLib::ClipperBase::m_HasOpenPaths

protected

Referenced by ClipperLib::Clipper::Clipper(), and ClipperLib::Clipper::Execute().

m_MinimaList

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

protected

Referenced by ClipperLib::Clipper::ExecuteInternal(), ClipperLib::Clipper::InsertLocalMinimaIntoAEL(), and ClipperLib::Clipper::Reset().

m_PreserveCollinear

bool ClipperLib::ClipperBase::m_PreserveCollinear

protected

Referenced by ClipperLib::Clipper::Clipper(), and ClipperLib::Clipper::FixupOutPolygon().

m_UseFullRange

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

staticconstexprprotected

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

---

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

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