Detailed Description

Definition at line 27 of file EarClippingTriangulation.h.

#include <EarClippingTriangulation.h>

Public Member Functions
	EarClippingTriangulation (GeoLib::Polygon const &polygon, std::list< GeoLib::Triangle > &triangles, bool rot=true)

	~EarClippingTriangulation ()

Private Member Functions
void	copyPolygonPoints (GeoLib::Polygon const &polygon)

void	ensureCWOrientation ()

bool	isEar (std::size_t v0, std::size_t v1, std::size_t v2) const

void	initVertexList ()

void	initLists ()

void	clipEars ()

Private Attributes
std::vector< GeoLib::Point * >	_pnts

std::list< std::size_t >	_vertex_list

std::list< std::size_t >	_convex_vertex_list

std::list< std::size_t >	_ear_list

std::list< GeoLib::Triangle >	_triangles

GeoLib::Orientation	_original_orientation

Constructor & Destructor Documentation

◆ EarClippingTriangulation()

GeoLib::EarClippingTriangulation::EarClippingTriangulation	(	GeoLib::Polygon const &	polygon,
		std::list< GeoLib::Triangle > &	triangles,
		bool	rot = `true`
	)

Definition at line 27 of file EarClippingTriangulation.cpp.

 {
     copyPolygonPoints(polygon);
  
     if (rot)
     {
         rotatePointsToXY(_pnts);
         ensureCWOrientation();
     }
  
     initVertexList();
     initLists();
     clipEars();
  
     std::vector<GeoLib::Point*> const& ref_pnts_vec(polygon.getPointsVec());
     if (_original_orientation == GeoLib::CW)
     {
         for (auto const& t : _triangles)
         {
             const std::size_t i0(polygon.getPointID(t[0]));
             const std::size_t i1(polygon.getPointID(t[1]));
             const std::size_t i2(polygon.getPointID(t[2]));
             triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
         }
     }
     else
     {
         std::size_t n_pnts(_pnts.size() - 1);
         for (auto const& t : _triangles)
         {
             const std::size_t i0(polygon.getPointID(n_pnts - t[0]));
             const std::size_t i1(polygon.getPointID(n_pnts - t[1]));
             const std::size_t i2(polygon.getPointID(n_pnts - t[2]));
             triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
         }
     }
 }

References _original_orientation, _pnts, _triangles, clipEars(), copyPolygonPoints(), GeoLib::CW, ensureCWOrientation(), GeoLib::Polyline::getPointID(), GeoLib::Polyline::getPointsVec(), initLists(), initVertexList(), and GeoLib::rotatePointsToXY().

◆ ~EarClippingTriangulation()

GeoLib::EarClippingTriangulation::~EarClippingTriangulation ( )

Definition at line 67 of file EarClippingTriangulation.cpp.

 {
     for (auto p : _pnts)
     {
         delete p;
     }
 }

References _pnts.

Member Function Documentation

◆ clipEars()

void GeoLib::EarClippingTriangulation::clipEars ( )

inlineprivate

Definition at line 207 of file EarClippingTriangulation.cpp.

 {
     std::list<std::size_t>::iterator it, prev, next;
     // *** clip an ear
     while (_vertex_list.size() > 3)
     {
         // pop ear from list
         std::size_t ear = _ear_list.front();
         _ear_list.pop_front();
         // remove ear tip from _convex_vertex_list
         _convex_vertex_list.remove(ear);
  
         // remove ear from vertex_list, apply changes to _ear_list,
         // _convex_vertex_list
         bool nfound(true);
         it = _vertex_list.begin();
         prev = _vertex_list.end();
         --prev;
         while (nfound && it != _vertex_list.end())
         {
             if (*it == ear)
             {
                 nfound = false;
                 it = _vertex_list.erase(it);  // remove ear tip
                 next = it;
                 if (next == _vertex_list.end())
                 {
                     next = _vertex_list.begin();
                     prev = _vertex_list.end();
                     --prev;
                 }
                 // add triangle
                 _triangles.emplace_back(_pnts, *prev, *next, ear);
  
                 // check the orientation of prevprev, prev, next
                 std::list<std::size_t>::iterator prevprev;
                 if (prev == _vertex_list.begin())
                 {
                     prevprev = _vertex_list.end();
                 }
                 else
                 {
                     prevprev = prev;
                 }
                 --prevprev;
  
                 // apply changes to _convex_vertex_list and _ear_list looking
                 // "backward"
                 GeoLib::Orientation orientation = GeoLib::getOrientation(
                     *_pnts[*prevprev], *_pnts[*prev], *_pnts[*next]);
                 if (orientation == GeoLib::CW)
                 {
                     BaseLib::uniquePushBack(_convex_vertex_list, *prev);
                     // prev is convex
                     if (isEar(*prevprev, *prev, *next))
                     {
                         // prev is an ear tip
                         BaseLib::uniquePushBack(_ear_list, *prev);
                     }
                     else
                     {
                         // if necessary remove prev
                         _ear_list.remove(*prev);
                     }
                 }
                 else
                 {
                     // prev is not convex => reflex or collinear
                     _convex_vertex_list.remove(*prev);
                     _ear_list.remove(*prev);
                     if (orientation == GeoLib::COLLINEAR)
                     {
                         prev = _vertex_list.erase(prev);
                         if (prev == _vertex_list.begin())
                         {
                             prev = _vertex_list.end();
                             --prev;
                         }
                         else
                         {
                             --prev;
                         }
                     }
                 }
  
                 // check the orientation of prev, next, nextnext
                 std::list<std::size_t>::iterator nextnext,
                     help_it(_vertex_list.end());
                 --help_it;
                 if (next == help_it)
                 {
                     nextnext = _vertex_list.begin();
                 }
                 else
                 {
                     nextnext = next;
                     ++nextnext;
                 }
  
                 // apply changes to _convex_vertex_list and _ear_list looking
                 // "forward"
                 orientation = getOrientation(*_pnts[*prev], *_pnts[*next],
                                              *_pnts[*nextnext]);
                 if (orientation == GeoLib::CW)
                 {
                     BaseLib::uniquePushBack(_convex_vertex_list, *next);
                     // next is convex
                     if (isEar(*prev, *next, *nextnext))
                     {
                         // next is an ear tip
                         BaseLib::uniquePushBack(_ear_list, *next);
                     }
                     else
                     {
                         // if necessary remove *next
                         _ear_list.remove(*next);
                     }
                 }
                 else
                 {
                     // next is not convex => reflex or collinear
                     _convex_vertex_list.remove(*next);
                     _ear_list.remove(*next);
                     if (orientation == GeoLib::COLLINEAR)
                     {
                         next = _vertex_list.erase(next);
                         if (next == _vertex_list.end())
                             next = _vertex_list.begin();
                     }
                 }
             }
             else
             {
                 prev = it;
                 ++it;
             }
         }
     }
  
     // add last triangle
     next = _vertex_list.begin();
     prev = next;
     ++next;
     if (next == _vertex_list.end())
     {
         return;
     }
     it = next;
     ++next;
     if (next == _vertex_list.end())
     {
         return;
     }
  
     if (getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]) ==
         GeoLib::CCW)
     {
         _triangles.emplace_back(_pnts, *prev, *it, *next);
     }
     else
     {
         _triangles.emplace_back(_pnts, *prev, *next, *it);
     }
 }

References _convex_vertex_list, _ear_list, _pnts, _triangles, _vertex_list, GeoLib::CCW, GeoLib::COLLINEAR, GeoLib::CW, GeoLib::getOrientation(), isEar(), and BaseLib::uniquePushBack().

Referenced by EarClippingTriangulation().

◆ copyPolygonPoints()

void GeoLib::EarClippingTriangulation::copyPolygonPoints ( GeoLib::Polygon const & polygon )

inlineprivate

copies the points of the polygon to the vector _pnts

Definition at line 75 of file EarClippingTriangulation.cpp.

 {
     // copy points - last point is identical to the first
     std::size_t n_pnts(polygon.getNumberOfPoints() - 1);
     for (std::size_t k(0); k < n_pnts; k++)
     {
         _pnts.push_back(new GeoLib::Point(*(polygon.getPoint(k))));
     }
 }

References _pnts, GeoLib::Polyline::getNumberOfPoints(), and GeoLib::Polyline::getPoint().

Referenced by EarClippingTriangulation().

◆ ensureCWOrientation()

void GeoLib::EarClippingTriangulation::ensureCWOrientation ( )

inlineprivate

Definition at line 85 of file EarClippingTriangulation.cpp.

 {
     std::size_t n_pnts(_pnts.size());
     // get the left most upper point
     std::size_t min_x_max_y_idx(0);  // for orientation check
     for (std::size_t k(0); k < n_pnts; k++)
     {
         if ((*(_pnts[k]))[0] <= (*(_pnts[min_x_max_y_idx]))[0])
         {
             if ((*(_pnts[k]))[0] < (*(_pnts[min_x_max_y_idx]))[0])
             {
                 min_x_max_y_idx = k;
             }
             else
             {
                 if ((*(_pnts[k]))[1] > (*(_pnts[min_x_max_y_idx]))[1])
                 {
                     min_x_max_y_idx = k;
                 }
             }
         }
     }
     // determine orientation
     if (0 < min_x_max_y_idx && min_x_max_y_idx < n_pnts - 1)
     {
         _original_orientation =
             GeoLib::getOrientation(*_pnts[min_x_max_y_idx - 1],
                                    *_pnts[min_x_max_y_idx],
                                    *_pnts[min_x_max_y_idx + 1]);
     }
     else
     {
         if (0 == min_x_max_y_idx)
         {
             _original_orientation = GeoLib::getOrientation(
                 *_pnts[n_pnts - 1], *_pnts[0], *_pnts[1]);
         }
         else
         {
             _original_orientation = GeoLib::getOrientation(
                 *_pnts[n_pnts - 2], *_pnts[n_pnts - 1], *_pnts[0]);
         }
     }
     if (_original_orientation == GeoLib::CCW)
     {
         // switch orientation
         for (std::size_t k(0); k < n_pnts / 2; k++)
         {
             std::swap(_pnts[k], _pnts[n_pnts - 1 - k]);
         }
     }
 }

References _original_orientation, _pnts, GeoLib::CCW, and GeoLib::getOrientation().

Referenced by EarClippingTriangulation().

◆ initLists()

void GeoLib::EarClippingTriangulation::initLists ( )

inlineprivate

Definition at line 161 of file EarClippingTriangulation.cpp.

 {
     // go through points checking ccw, cw or collinear order and identifying
     // ears
     std::list<std::size_t>::iterator it(_vertex_list.begin()),
         prev(_vertex_list.end()), next;
     --prev;
     next = it;
     ++next;
     GeoLib::Orientation orientation;
     bool first_run(
         true);  // saves special handling of the last case with identical code
     while (_vertex_list.size() >= 3 && first_run)
     {
         if (next == _vertex_list.end())
         {
             first_run = false;
             next = _vertex_list.begin();
         }
         orientation = getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]);
         if (orientation == GeoLib::COLLINEAR)
         {
             WARN(
                 "EarClippingTriangulation::initLists(): collinear points "
                 "({:f}, {:f}, {:f}), ({:f}, {:f}, {:f}), ({:f}, {:f}, {:f})",
                 (*_pnts[*prev])[0], (*_pnts[*prev])[1], (*_pnts[*prev])[2],
                 (*_pnts[*it])[0], (*_pnts[*it])[1], (*_pnts[*it])[2],
                 (*_pnts[*next])[0], (*_pnts[*next])[1], (*_pnts[*next])[2]);
             it = _vertex_list.erase(it);
             ++next;
         }
         else
         {
             if (orientation == GeoLib::CW)
             {
                 _convex_vertex_list.push_back(*it);
                 if (isEar(*prev, *it, *next))
                     _ear_list.push_back(*it);
             }
             prev = it;
             it = next;
             ++next;
         }
     }
 }

References _convex_vertex_list, _ear_list, _pnts, _vertex_list, GeoLib::COLLINEAR, GeoLib::CW, GeoLib::getOrientation(), isEar(), and WARN().

Referenced by EarClippingTriangulation().

◆ initVertexList()

void GeoLib::EarClippingTriangulation::initVertexList ( )

inlineprivate

Definition at line 155 of file EarClippingTriangulation.cpp.

 {
     _vertex_list.resize(_pnts.size());
     std::iota(begin(_vertex_list), end(_vertex_list), 0);
 }

References _pnts, and _vertex_list.

Referenced by EarClippingTriangulation().

◆ isEar()

bool GeoLib::EarClippingTriangulation::isEar	(	std::size_t	v0,
		std::size_t	v1,
		std::size_t	v2
	)		const

inlineprivate

Definition at line 138 of file EarClippingTriangulation.cpp.

 {
     for (auto const& v : _vertex_list)
     {
         if (v != v0 && v != v1 && v != v2)
         {
             if (MathLib::isPointInTriangle(*_pnts[v], *_pnts[v0], *_pnts[v1],
                                            *_pnts[v2]))
             {
                 return false;
             }
         }
     }
     return true;
 }