Merge ~sethh/kicad:tesselation into ~kicad-product-committers/kicad:master

[Seth Hillbrand]

Merge new tesselation code for triangulation in OpenGL as well as 3d-viewer.

This commit removes the previous poly2tri code and clears the associated limitations allowing more robust triangulation, including overlapping holes, degenerate vertices and others.

[Wayne Stambaugh (stambaughw)]

I just tested this and I didn't run into any issues. As for any performance improvements, I really didn't notice any significant difference one way or the other but I don't have any really complex boards to test so my testing may not be accurate. Visually, I didn't notice any differences. If someone has some really complex boards, please test this and give your feedback. I do like the idea that we are replacing the Poly2Tri. I'm going to tentatively approve this assuming additional testing by other developers.

review: Approve

[jean-pierre charras (jp-charras)]

I made a few tests (one with a complex board) and did not notice any issue or difference.
I also did not see performance improvements: roughly 3D viewer takes the same time to build the 3D scene.
(W7/32 bits)

[Seth Hillbrand (sethh)]

Jeff, would you mind giving this a test-run to ensure there's no funny business on the Mac-side?

[Seth Hillbrand (sethh)]

@jp/wayne- Thanks for the tests. Speed is not expected to be noticeably different unless the board has overlapping holes. Then poly2tri cannot cache the polygon and we triangulate using whatever routine the user's OpenGL driver implements. Since the OpenGL routine runs on a single processor and re-runs each time the zone is highlighted, the speed difference is primarily visible there. This is related to
https://bugs.launchpad.net/kicad/+bug/1745050
and
https://bugs.launchpad.net/kicad/+bug/1780130

[Jeff Young (jeyjey)]

Nothing looks out of place on my boards or a few customer boards I checked.

review: Approve

diff --git a/3d-viewer/3d_canvas/create_3Dgraphic_brd_items.cpp b/3d-viewer/3d_canvas/create_3Dgraphic_brd_items.cpp
index b7914e8..90b7590 100644
--- a/3d-viewer/3d_canvas/create_3Dgraphic_brd_items.cpp
+++ b/3d-viewer/3d_canvas/create_3Dgraphic_brd_items.cpp
@@ -506,10 +506,6 @@ void CINFO3D_VISU::createNewPadWithClearance( const D_PAD* aPad,
         if( aClearanceValue.x )
             polyList.Inflate( aClearanceValue.x, 32 );
 
-        // This convert the poly in outline and holes
-        polyList.Simplify( SHAPE_POLY_SET::PM_FAST );
-        polyList.Simplify( SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
-
         // Add the PAD polygon
         Convert_shape_line_polygon_to_triangles( polyList, *aDstContainer, m_biuTo3Dunits, *aPad );
 
@@ -830,11 +826,6 @@ void CINFO3D_VISU::AddShapeWithClearanceToContainer( const DRAWSEGMENT* aDrawSeg
 
         aDrawSegment->TransformShapeWithClearanceToPolygon( polyList, aClearanceValue,
                                                         segcountforcircle, correctionFactor );
-        // This convert the poly in outline and holes
-        // Note: This two sequencial calls are need in order to get
-        // the triangulation function to work properly.
-        polyList.Simplify( SHAPE_POLY_SET::PM_FAST );
-        polyList.Simplify( SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
 
         if( polyList.IsEmpty() ) // Just for caution
             break;
@@ -861,15 +852,6 @@ void CINFO3D_VISU::AddSolidAreasShapesToContainer( const ZONE_CONTAINER* aZoneCo
     SHAPE_POLY_SET polyList = SHAPE_POLY_SET(aZoneContainer->GetFilledPolysList());
 
     // This convert the poly in outline and holes
-
-    // Note: This two sequencial calls are need in order to get
-    // the triangulation function to work properly.
-    polyList.Simplify( SHAPE_POLY_SET::PM_FAST );
-    polyList.Simplify( SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
-
-    if( polyList.IsEmpty() )
-        return;
-
     Convert_shape_line_polygon_to_triangles( polyList,
                                              *aDstContainer,
                                              m_biuTo3Dunits,
diff --git a/3d-viewer/3d_rendering/3d_render_ogl_legacy/c3d_render_createscene_ogl_legacy.cpp b/3d-viewer/3d_rendering/3d_render_ogl_legacy/c3d_render_createscene_ogl_legacy.cpp
index 9412318..bcd099b 100644
--- a/3d-viewer/3d_rendering/3d_render_ogl_legacy/c3d_render_createscene_ogl_legacy.cpp
+++ b/3d-viewer/3d_rendering/3d_render_ogl_legacy/c3d_render_createscene_ogl_legacy.cpp
@@ -369,7 +369,8 @@ void C3D_RENDER_OGL_LEGACY::reload( REPORTER *aStatusTextReporter )
     // /////////////////////////////////////////////////////////////////////////
 
     CCONTAINER2D boardContainer;
-    Convert_shape_line_polygon_to_triangles( m_settings.GetBoardPoly(),
+    SHAPE_POLY_SET tmpBoard = m_settings.GetBoardPoly();
+    Convert_shape_line_polygon_to_triangles( tmpBoard,
                                              boardContainer,
                                              m_settings.BiuTo3Dunits(),
                                              (const BOARD_ITEM &)*m_settings.GetBoard() );
diff --git a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.cpp b/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.cpp
index 0ed9d61..45d0cca 100644
--- a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.cpp
+++ b/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.cpp
@@ -35,9 +35,9 @@
 
 #include <wx/glcanvas.h>    // CALLBACK definition, needed on Windows
                             // alse needed on OSX to define __DARWIN__
-
+#include <geometry/polygon_triangulation.h>
 #include "../../../3d_fastmath.h"
-#include <poly2tri/poly2tri.h>
+
 
 
 CTRIANGLE2D::CTRIANGLE2D ( const SFVEC2F &aV1,
@@ -126,172 +126,28 @@ bool CTRIANGLE2D::IsPointInside( const SFVEC2F &aPoint ) const
     const float c = 1.0f - a - b;
 
     return 0.0f <= c && c <= 1.0f;
-/*
-    return 0.0f <= a && a <= 1.0f &&
-           0.0f <= b && b <= 1.0f &&
-           0.0f <= c && c <= 1.0f;*/
-}
-
-
-template <class C> void FreeClear( C & cntr )
-{
-    for( typename C::iterator it = cntr.begin();
-         it != cntr.end();
-         ++it )
-    {
-        delete * it;
-    }
-
-    cntr.clear();
 }
 
-// Note: Please check edgeshrink.cpp in order to learn the EdgeShrink propose
 
-#define APPLY_EDGE_SHRINK
-
-#ifdef APPLY_EDGE_SHRINK
-extern void EdgeShrink( std::vector<SFVEC2I64> &aPath );
-
-#define POLY_SCALE_FACT 256
-#define POLY_SCALE_FACT_INVERSE (1.0 / (double)(POLY_SCALE_FACT))
-#endif
-
-void Convert_shape_line_polygon_to_triangles( const SHAPE_POLY_SET &aPolyList,
+void Convert_shape_line_polygon_to_triangles( SHAPE_POLY_SET &aPolyList,
                                               CGENERICCONTAINER2D &aDstContainer,
                                               float aBiuTo3DunitsScale ,
                                               const BOARD_ITEM &aBoardItem )
 {
-    unsigned int nOutlines = aPolyList.OutlineCount();
 
+    aPolyList.CacheTriangulation();
+    const double conver_d = (double)aBiuTo3DunitsScale;
 
-    for( unsigned int idx = 0; idx < nOutlines; ++idx )
+    for( unsigned int i = 0; i < aPolyList.TriangulatedPolyCount(); i++ )
     {
-        const SHAPE_LINE_CHAIN &outlinePath = aPolyList.COutline( idx );
-
-        wxASSERT( outlinePath.PointCount() >= 3 );
-
-        std::vector<SFVEC2I64> scaledOutline;
-        scaledOutline.resize( outlinePath.PointCount() );
-
-        // printf("\nidx: %u\n", idx);
-
-        // Apply a scale to the points
-        for( unsigned int i = 0;
-             i < (unsigned int)outlinePath.PointCount();
-             ++i )
-        {
-            const VECTOR2I& a = outlinePath.CPoint( i );
-
-#ifdef APPLY_EDGE_SHRINK
-            scaledOutline[i] = SFVEC2I64( (glm::int64)a.x * POLY_SCALE_FACT,
-                                          (glm::int64)a.y * POLY_SCALE_FACT );
-#else
-            scaledOutline[i] = SFVEC2I64( (glm::int64)a.x,
-                                          (glm::int64)a.y );
-#endif
-        }
-
-#ifdef APPLY_EDGE_SHRINK
-        // Apply a modification to the points
-        EdgeShrink( scaledOutline );
-#endif
-        // Copy to a array of pointers
-        std::vector<p2t::Point*> polyline;
-        polyline.resize( outlinePath.PointCount() );
-
-        for( unsigned int i = 0;
-             i < (unsigned int)scaledOutline.size();
-             ++i )
-        {
-            const SFVEC2I64 &a = scaledOutline[i];
-
-            //printf("%lu %lu\n", a.x, a.y);
-
-            polyline[i] = new p2t::Point( (double)a.x,
-                                          (double)a.y );
-        }
-
-        // Start creating the structured to be triangulated
-        p2t::CDT* cdt = new p2t::CDT( polyline );
-
-        // Add holes for this outline
-        unsigned int nHoles = aPolyList.HoleCount( idx );
-
-        std::vector< std::vector<p2t::Point*> > polylineHoles;
-
-        polylineHoles.resize( nHoles );
-
-        for( unsigned int idxHole = 0; idxHole < nHoles; ++idxHole )
-        {
-            const SHAPE_LINE_CHAIN &outlineHoles = aPolyList.CHole( idx,
-                                                                    idxHole );
-
-            wxASSERT( outlineHoles.PointCount() >= 3 );
-
-            std::vector<SFVEC2I64> scaledHole;
-            scaledHole.resize( outlineHoles.PointCount() );
-
-            // Apply a scale to the points
-            for( unsigned int i = 0;
-                 i < (unsigned int)outlineHoles.PointCount();
-                 ++i )
-            {
-                const VECTOR2I &h = outlineHoles.CPoint( i );
-#ifdef APPLY_EDGE_SHRINK
-                scaledHole[i] = SFVEC2I64( (glm::int64)h.x * POLY_SCALE_FACT,
-                                           (glm::int64)h.y * POLY_SCALE_FACT );
-#else
-                scaledHole[i] = SFVEC2I64( (glm::int64)h.x,
-                                           (glm::int64)h.y );
-#endif
-            }
-
-#ifdef APPLY_EDGE_SHRINK
-            // Apply a modification to the points
-            EdgeShrink( scaledHole );
-#endif
-
-            // Resize and reserve space
-            polylineHoles[idxHole].resize( outlineHoles.PointCount() );
-
-            for( unsigned int i = 0;
-                 i < (unsigned int)outlineHoles.PointCount();
-                 ++i )
-            {
-                const SFVEC2I64 &h = scaledHole[i];
-
-                polylineHoles[idxHole][i] = new p2t::Point( h.x, h.y );
-            }
-
-            cdt->AddHole( polylineHoles[idxHole] );
-        }
-
-        // Triangulate
-        cdt->Triangulate();
-
-        // Hint: if you find any crashes on the triangulation poly2tri library,
-        // you can use the following site to debug the points and it will mark
-        // the errors in the polygon:
-        // http://r3mi.github.io/poly2tri.js/
-
-
-        // Get and add triangles
-        std::vector<p2t::Triangle*> triangles;
-        triangles = cdt->GetTriangles();
+        auto triPoly = aPolyList.TriangulatedPolygon( i );
 
-#ifdef APPLY_EDGE_SHRINK
-        const double conver_d = (double)aBiuTo3DunitsScale *
-                                POLY_SCALE_FACT_INVERSE;
-#else
-        const double conver_d = (double)aBiuTo3DunitsScale;
-#endif
-        for( unsigned int i = 0; i < triangles.size(); ++i )
+        for( size_t i = 0; i < triPoly->GetTriangleCount(); i++ )
         {
-            p2t::Triangle& t = *triangles[i];
-
-            p2t::Point& a = *t.GetPoint( 0 );
-            p2t::Point& b = *t.GetPoint( 1 );
-            p2t::Point& c = *t.GetPoint( 2 );
+            VECTOR2I a;
+            VECTOR2I b;
+            VECTOR2I c;
+            triPoly->GetTriangle( i, a, b, c );
 
             aDstContainer.Add( new CTRIANGLE2D( SFVEC2F( a.x * conver_d,
                                                         -a.y * conver_d ),
@@ -302,15 +158,5 @@ void Convert_shape_line_polygon_to_triangles( const SHAPE_POLY_SET &aPolyList,
                                                 aBoardItem ) );
         }
 
-        // Delete created data
-        delete cdt;
-
-        // Free points
-        FreeClear(polyline);
-
-        for( unsigned int idxHole = 0; idxHole < nHoles; ++idxHole )
-        {
-            FreeClear( polylineHoles[idxHole] );
-        }
     }
 }
diff --git a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.h b/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.h
index e43f2b8..c4b6689 100644
--- a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.h
+++ b/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/ctriangle2d.h
@@ -68,7 +68,7 @@ public:
 };
 
 
-void Convert_shape_line_polygon_to_triangles(  const SHAPE_POLY_SET &aPolyList,
+void Convert_shape_line_polygon_to_triangles(  SHAPE_POLY_SET &aPolyList,
                                                CGENERICCONTAINER2D &aDstContainer,
                                                float aBiuTo3DunitsScale,
                                                const BOARD_ITEM &aBoardItem );
diff --git a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/edgeshrink.cpp b/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/edgeshrink.cpp
deleted file mode 100644
index 1027ec3..0000000
--- a/3d-viewer/3d_rendering/3d_render_raytracing/shapes2D/edgeshrink.cpp
+++ /dev/null
@@ -1,89 +0,0 @@
-/*
- * This program source code file is part of KiCad, a free EDA CAD application.
- *
- * Copyright (C) 2016 Mario Luzeiro <[e-mail]>
- * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, you may find one here:
- * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
- * or you may search the http://www.gnu.org website for the version 2 license,
- * or you may write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
- */
-
-/**
- * @file  edgeshrink.cpp
- * @brief The edgeShrink function was found in the project clip2tri by the:
- *        Bitfighter project (http://bitfighter.org)
- * https://github.com/raptor/clip2tri
- * https://github.com/raptor/clip2tri/blob/f62a734d22733814b8a970ed8a68a4d94c24fa5f/clip2tri/clip2tri.cpp#L150
- */
-
-#include <plugins/3dapi/xv3d_types.h>
-#include <vector>
-
-// clip2tri is Licenced under:
-
-// The MIT License (MIT)
-
-// Copyright (c) 2014 Bitfighter developers
-
-// Permission is hereby granted, free of charge, to any person obtaining a copy
-// of this software and associated documentation files (the "Software"), to deal
-// in the Software without restriction, including without limitation the rights
-// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-// copies of the Software, and to permit persons to whom the Software is
-// furnished to do so, subject to the following conditions:
-
-// The above copyright notice and this permission notice shall be included in all
-// copies or substantial portions of the Software.
-
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-// SOFTWARE.
-
-
-// Shrink large polygons by reducing each coordinate by 1 in the
-// general direction of the last point as we wind around
-//
-// This normally wouldn't work in every case, but our upscaled-by-1000 polygons
-// have little chance to create new duplicate points with this method.
-//
-// For information on why this was needed, see:
-//
-//    https://github.com/greenm01/poly2tri/issues/90
-//
-
-#define S_INC 1
-
-void EdgeShrink( std::vector<SFVEC2I64> &aPath )
-{
-   unsigned int prev = aPath.size() - 1;
-
-   for( unsigned int i = 0; i < aPath.size(); i++ )
-   {
-      // Adjust coordinate by 1 depending on the direction
-      (aPath[i].x - aPath[prev].x) > 0 ? aPath[i].x -= S_INC :
-                                         aPath[i].x += S_INC;
-
-      (aPath[i].y - aPath[prev].y) > 0 ? aPath[i].y -= S_INC :
-                                         aPath[i].y += S_INC;
-
-      prev = i;
-   }
-}
diff --git a/3d-viewer/CMakeLists.txt b/3d-viewer/CMakeLists.txt
index 76ce150..6cea78a 100644
--- a/3d-viewer/CMakeLists.txt
+++ b/3d-viewer/CMakeLists.txt
@@ -37,11 +37,6 @@ set(3D-VIEWER_SRCS
     ${DIR_DLG}/dlg_select_3dmodel.cpp
     ${DIR_DLG}/panel_prev_3d_base.cpp
     ${DIR_DLG}/panel_prev_model.cpp
-    ../polygon/poly2tri/common/shapes.cc
-    ../polygon/poly2tri/sweep/advancing_front.cc
-    ../polygon/poly2tri/sweep/cdt.cc
-    ../polygon/poly2tri/sweep/sweep.cc
-    ../polygon/poly2tri/sweep/sweep_context.cc
     3d_canvas/cinfo3d_visu.cpp
     3d_canvas/create_layer_items.cpp
     3d_canvas/create_3Dgraphic_brd_items.cpp
@@ -76,7 +71,6 @@ set(3D-VIEWER_SRCS
     ${DIR_RAY_2D}/cring2d.cpp
     ${DIR_RAY_2D}/croundsegment2d.cpp
     ${DIR_RAY_2D}/ctriangle2d.cpp
-    ${DIR_RAY_2D}/edgeshrink.cpp
     ${DIR_RAY_3D}/cbbox.cpp
     ${DIR_RAY_3D}/cbbox_ray.cpp
     ${DIR_RAY_3D}/ccylinder.cpp
diff --git a/common/gal/opengl/opengl_gal.cpp b/common/gal/opengl/opengl_gal.cpp
index 291b3a4..41de80c 100644
--- a/common/gal/opengl/opengl_gal.cpp
+++ b/common/gal/opengl/opengl_gal.cpp
@@ -907,10 +907,10 @@ void OPENGL_GAL::drawTriangulatedPolyset( const SHAPE_POLY_SET& aPolySet )
         {
             auto triPoly = aPolySet.TriangulatedPolygon( j );
 
-            for( int i = 0; i < triPoly->GetTriangleCount(); i++ )
+            for( size_t i = 0; i < triPoly->GetTriangleCount(); i++ )
             {
                 VECTOR2I a, b, c;
-                triPoly->GetTriangle( i ,a,b,c);
+                triPoly->GetTriangle( i, a, b, c );
                 currentManager->Vertex( a.x, a.y, layerDepth );
                 currentManager->Vertex( b.x, b.y, layerDepth );
                 currentManager->Vertex( c.x, c.y, layerDepth );
diff --git a/common/geometry/shape_poly_set.cpp b/common/geometry/shape_poly_set.cpp
index 9cba55d..637c93e 100644
--- a/common/geometry/shape_poly_set.cpp
+++ b/common/geometry/shape_poly_set.cpp
@@ -42,8 +42,7 @@
 #include <geometry/shape.h>
 #include <geometry/shape_line_chain.h>
 #include <geometry/shape_poly_set.h>
-
-#include "poly2tri/poly2tri.h"
+#include <geometry/polygon_triangulation.h>
 
 using namespace ClipperLib;
 
@@ -1862,164 +1861,6 @@ SHAPE_POLY_SET &SHAPE_POLY_SET::operator=( const SHAPE_POLY_SET& aOther )
     return *this;
 }
 
-
-class SHAPE_POLY_SET::TRIANGULATION_CONTEXT
-{
-public:
-
-    TRIANGULATION_CONTEXT( TRIANGULATED_POLYGON* aResultPoly ) :
-    m_triPoly( aResultPoly )
-    {
-    }
-
-    void AddOutline( const SHAPE_LINE_CHAIN& outl, bool aIsHole = false )
-    {
-        m_points.reserve( outl.PointCount() );
-        m_points.clear();
-
-        for( int i = 0; i < outl.PointCount(); i++ )
-        {
-            m_points.push_back( addPoint( outl.CPoint( i ) ) );
-        }
-
-        if ( aIsHole )
-            m_cdt->AddHole( m_points );
-        else
-            m_cdt.reset( new p2t::CDT( m_points ) );
-    }
-
-    void Triangulate()
-    {
-        m_cdt->Triangulate();
-
-        m_triPoly->AllocateTriangles( m_cdt->GetTriangles().size() );
-
-        int i = 0;
-
-        for( auto tri : m_cdt->GetTriangles() )
-        {
-            TRIANGULATED_POLYGON::TRI t;
-
-            t.a = tri->GetPoint( 0 )->id;
-            t.b = tri->GetPoint( 1 )->id;
-            t.c = tri->GetPoint( 2 )->id;
-
-            m_triPoly->SetTriangle(i, t);
-            i++;
-        }
-
-        for( auto p : m_uniquePoints )
-            delete p;
-    }
-
-private:
-
-    class comparePoints
-    {
-    public:
-        bool operator()( p2t::Point* a, p2t::Point* b ) const
-        {
-        if (a->x < b->x)
-            return true;
-
-        if( a->x == b->x )
-            return ( a->y > b->y );
-
-        return false;
-        }
-    };
-
-
-    p2t::Point* addPoint( const VECTOR2I& aP )
-    {
-        p2t::Point check( aP.x, aP.y );
-        auto it = m_uniquePoints.find( &check );
-
-        if( it != m_uniquePoints.end() )
-        {
-            return *it;
-        }
-        else
-        {
-            auto lastId = m_triPoly->GetVertexCount();
-            auto p = new p2t::Point( aP.x, aP.y, lastId );
-            m_triPoly->AddVertex( aP );
-            m_uniquePoints.insert ( p );
-            return p;
-        }
-    }
-
-    typedef std::set<p2t::Point*, comparePoints>  P2T_SET;
-    typedef std::vector<p2t::Point*>    P2T_VEC;
-
-    P2T_VEC m_points;
-    P2T_SET m_uniquePoints;
-    TRIANGULATED_POLYGON *m_triPoly;
-    std::unique_ptr<p2t::CDT> m_cdt;
-};
-
-SHAPE_POLY_SET::TRIANGULATED_POLYGON::~TRIANGULATED_POLYGON()
-{
-    Clear();
-}
-
-
-void SHAPE_POLY_SET::TRIANGULATED_POLYGON::Clear()
-{
-    if( m_vertices )
-        delete[] m_vertices;
-
-    if( m_triangles )
-        delete[] m_triangles;
-}
-
-
-void SHAPE_POLY_SET::TRIANGULATED_POLYGON::AllocateVertices( int aSize )
-{
-    m_vertices = new VECTOR2I[aSize];
-}
-
-
-void SHAPE_POLY_SET::TRIANGULATED_POLYGON::AllocateTriangles( int aSize )
-{
-    m_triangles = new TRI[aSize];
-    m_triangleCount = aSize;
-}
-
-
-static int totalVertexCount( const SHAPE_POLY_SET::POLYGON& aPoly )
-{
-    int cnt = 0;
-
-    for( const auto& outl : aPoly )
-    {
-        cnt += outl.PointCount();
-    }
-
-    return cnt;
-}
-
-
-void SHAPE_POLY_SET::triangulateSingle( const POLYGON& aPoly,
-        SHAPE_POLY_SET::TRIANGULATED_POLYGON& aResult )
-{
-    if( aPoly.size() == 0 )
-        return;
-
-    TRIANGULATION_CONTEXT ctx ( &aResult );
-
-    aResult.AllocateVertices( totalVertexCount( aPoly ) );
-    ctx.AddOutline( aPoly[0], false );
-
-    for( unsigned i = 1; i < aPoly.size(); i++ )
-    {
-        ctx.AddOutline( aPoly[i], true ); // add holes
-    }
-
-    ctx.Triangulate();
-}
-
-
 MD5_HASH SHAPE_POLY_SET::GetHash() const
 {
     if( !m_hash.IsValid() )
@@ -2067,22 +1908,17 @@ void SHAPE_POLY_SET::CacheTriangulation()
 
     SHAPE_POLY_SET tmpSet = *this;
 
-    if( !tmpSet.HasHoles() )
-        tmpSet.Unfracture( PM_FAST );
+    if( tmpSet.HasHoles() )
+        tmpSet.Fracture( PM_FAST );
 
     m_triangulatedPolys.clear();
 
-    if( tmpSet.HasTouchingHoles() )
-    {
-        // temporary workaround for overlapping hole vertices that poly2tri doesn't handle
-        m_triangulationValid = false;
-        return;
-    }
-
     for( int i = 0; i < tmpSet.OutlineCount(); i++ )
     {
         m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
-        triangulateSingle( tmpSet.Polygon( i ), *m_triangulatedPolys.back() );
+        PolygonTriangulation tess( *m_triangulatedPolys.back() );
+
+        tess.TesselatePolygon( tmpSet.Polygon( i ).front() );
     }
 
     m_triangulationValid = true;
diff --git a/include/geometry/polygon_triangulation.h b/include/geometry/polygon_triangulation.h
new file mode 100644
index 0000000..58f3fc5
--- /dev/null
+++ b/include/geometry/polygon_triangulation.h
@@ -0,0 +1,608 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Modifications Copyright (C) 2018 KiCad Developers
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ *
+ * Based on Uniform Plane Subdivision algorithm from Lamot, Marko, and Borut Žalik.
+ * "A fast polygon triangulation algorithm based on uniform plane subdivision."
+ * Computers & graphics 27, no. 2 (2003): 239-253.
+ *
+ * Code derived from:
+ * K-3D which is Copyright (c) 2005-2006, Romain Behar, GPL-2, license above
+ * earcut which is Copyright (c) 2016, Mapbox, ISC
+ *
+ * ISC License:
+ * Permission to use, copy, modify, and/or distribute this software for any purpose
+ * with or without fee is hereby granted, provided that the above copyright notice
+ * and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+ * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+ * THIS SOFTWARE.
+ *
+ */
+
+#ifndef __POLYGON_TRIANGULATION_H
+#define __POLYGON_TRIANGULATION_H
+
+#include <algorithm>
+#include <cmath>
+#include <vector>
+#include <math/box2.h>
+
+class PolygonTriangulation
+{
+
+public:
+
+    PolygonTriangulation( SHAPE_POLY_SET::TRIANGULATED_POLYGON& aResult ) :
+        m_result( aResult )
+    {};
+
+private:
+    struct Vertex
+    {
+        Vertex( size_t aIndex, double aX, double aY, PolygonTriangulation* aParent ) :
+                i( aIndex ), x( aX ), y( aY ), parent( aParent )
+        {
+        }
+        Vertex& operator=( const Vertex& ) = delete;
+        Vertex& operator=( Vertex&& ) = delete;
+
+        bool operator==( const Vertex& rhs ) const
+        {
+            return this->x == rhs.x && this->y == rhs.y;
+        }
+        bool operator!=( const Vertex& rhs ) const { return !( *this == rhs ); }
+
+
+        /**
+         * Function split
+         * Splits the referenced polygon between the reference point and
+         * vertex b, assuming they are in the same polygon.  Notes that while we
+         * create a new vertex pointer for the linked list, we maintain the same
+         * vertex index value from the original polygon.  In this way, we have
+         * two polygons that both share the same vertices.
+         *
+         * Returns the pointer to the newly created vertex in the polygon that
+         * does not include the reference vertex.
+         */
+        Vertex* split( Vertex* b )
+        {
+            parent->m_vertices.emplace_back( i, x, y, parent );
+            Vertex* a2 = &parent->m_vertices.back();
+            parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
+            Vertex* b2 = &parent->m_vertices.back();
+            Vertex* an = next;
+            Vertex* bp = b->prev;
+
+            next = b;
+            b->prev = this;
+
+            a2->next = an;
+            an->prev = a2;
+
+            b2->next = a2;
+            a2->prev = b2;
+
+            bp->next = b2;
+            b2->prev = bp;
+
+            return b2;
+        }
+
+        /**
+         * Function remove
+         * Removes the node from the linked list and z-ordered linked list.
+         */
+        void remove()
+        {
+            next->prev = prev;
+            prev->next = next;
+
+            if( prevZ )
+                prevZ->nextZ = nextZ;
+            if( nextZ )
+                nextZ->prevZ = prevZ;
+            next = NULL;
+            prev = NULL;
+            nextZ = NULL;
+            prevZ = NULL;
+        }
+
+
+        void updateOrder()
+        {
+            if( !z )
+                z = parent->zOrder( x, y );
+        }
+
+        /**
+         * Function updateList
+         * After inserting or changing nodes, this function should be called to
+         * remove duplicate vertices and ensure z-ordering is correct
+         */
+        void updateList()
+        {
+            Vertex* p = next;
+
+            while( p != this )
+            {
+                /**
+                 * Remove duplicates
+                 */
+                if( *p == *p->next )
+                {
+                    p = p->prev;
+                    p->next->remove();
+
+                    if( p == p->next )
+                        break;
+                }
+
+                p->updateOrder();
+                p = p->next;
+            };
+
+            updateOrder();
+            zSort();
+        }
+
+        /**
+         * Sort all vertices in this vertex's list by their Morton code
+         */
+        void zSort()
+        {
+            std::deque<Vertex*> queue;
+
+            queue.push_back( this );
+
+            for( auto p = next; p && p != this; p = p->next )
+                queue.push_back( p );
+
+            std::sort( queue.begin(), queue.end(), []( const Vertex* a, const Vertex* b)
+            {
+                return a->z < b->z;
+            } );
+
+            Vertex* prev_elem = nullptr;
+            for( auto elem : queue )
+            {
+                if( prev_elem )
+                    prev_elem->nextZ = elem;
+
+                elem->prevZ = prev_elem;
+                prev_elem = elem;
+            }
+
+            prev_elem->nextZ = nullptr;
+        }
+
+
+        /**
+         * Check to see if triangle surrounds our current vertex
+         */
+        bool inTriangle( const Vertex& a, const Vertex& b, const Vertex& c )
+        {
+            return     ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
+                    && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
+                    && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
+        }
+
+        const size_t i;
+        const double x;
+        const double y;
+        PolygonTriangulation* parent;
+
+        // previous and next vertices nodes in a polygon ring
+        Vertex* prev = nullptr;
+        Vertex* next = nullptr;
+
+        // z-order curve value
+        int32_t z = 0;
+
+        // previous and next nodes in z-order
+        Vertex* prevZ = nullptr;
+        Vertex* nextZ = nullptr;
+    };
+
+    BOX2I m_bbox;
+    std::deque<Vertex> m_vertices;
+    SHAPE_POLY_SET::TRIANGULATED_POLYGON& m_result;
+
+    /**
+     * Calculate the Morton code of the Vertex
+     * http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
+     *
+     */
+    int32_t zOrder( const double aX, const double aY ) const
+    {
+        int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
+        int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
+
+        x = ( x | ( x << 8 ) ) & 0x00FF00FF;
+        x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
+        x = ( x | ( x << 2 ) ) & 0x33333333;
+        x = ( x | ( x << 1 ) ) & 0x55555555;
+
+        y = ( y | ( y << 8 ) ) & 0x00FF00FF;
+        y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
+        y = ( y | ( y << 2 ) ) & 0x33333333;
+        y = ( y | ( y << 1 ) ) & 0x55555555;
+
+        return x | ( y << 1 );
+    }
+
+    /**
+     * Function removeNullTriangles
+     * Iterates through the list to remove NULL triangles if they exist.
+     * This should only be called as a last resort when tesselation fails
+     * as the NULL triangles are inserted as Steiner points to improve the
+     * triangulation regularity of polygons
+     */
+    bool removeNullTriangles( Vertex* aStart )
+    {
+        bool retval = false;
+        Vertex* p = aStart->next;
+
+        while( p != aStart )
+        {
+            if( area( p->prev, p, p->next ) == 0.0 )
+            {
+                p = p->prev;
+                p->next->remove();
+                retval = true;
+
+                if( p == p->next )
+                    break;
+            }
+            p = p->next;
+        };
+
+        // We needed an end point above that wouldn't be removed, so
+        // here we do the final check for this as a Steiner point
+        if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
+        {
+            p->remove();
+            retval = true;
+        }
+
+        return retval;
+    }
+
+    /**
+     * Function createList
+     * Takes the SHAPE_LINE_CHAIN and links each point into a
+     * circular, doubly-linked list
+     */
+    Vertex* createList( const SHAPE_LINE_CHAIN& points )
+    {
+        Vertex* tail = nullptr;
+
+        for( int i = 0; i < points.PointCount(); i++ )
+            tail = insertVertex( points.CPoint( i ), tail );
+
+        if( tail && ( *tail == *tail->next ) )
+        {
+            tail->next->remove();
+        }
+
+        return tail;
+    }
+
+    /**
+     * Function: earcutList
+     * Walks through a circular linked list starting at aPoint.  For each point,
+     * test to see if the adjacent points form a triangle that is completely enclosed
+     * by the remaining polygon (an "ear" sticking off the polygon).  If the three points
+     * form an ear, we log the ear's location and remove the center point from the linked list.
+     *
+     * This function can be called recursively in the case of difficult polygons.  In cases where
+     * there is an intersection (not technically allowed by KiCad, but could exist in an edited file),
+     * we create a single triangle and remove both vertices before attempting to
+     */
+    void earcutList( Vertex* aPoint, int pass = 0 )
+    {
+        if( !aPoint )
+            return;
+
+        Vertex* stop = aPoint;
+        Vertex* prev;
+        Vertex* next;
+
+        while( aPoint->prev != aPoint->next )
+        {
+            prev = aPoint->prev;
+            next = aPoint->next;
+
+            if( isEar( aPoint ) )
+            {
+                m_result.AddTriangle( prev->i, aPoint->i, next->i );
+                aPoint->remove();
+
+                // Skip one vertex as the triangle will account for the prev node
+                aPoint = next->next;
+                stop = next->next;
+
+                continue;
+            }
+
+            Vertex* nextNext = next->next;
+
+            if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
+                    locallyInside( prev, nextNext ) &&
+                    locallyInside( nextNext, prev ) )
+            {
+                m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
+
+                // remove two nodes involved
+                next->remove();
+                aPoint->remove();
+
+                aPoint = nextNext;
+
+                continue;
+            }
+
+            aPoint = next;
+
+            /**
+             * We've searched the entire polygon for available ears and there are still un-sliced nodes
+             * remaining
+             */
+            if( aPoint == stop )
+            {
+                // First, try to remove the remaining steiner points
+                if( removeNullTriangles( aPoint ) )
+                    continue;
+
+                // If we don't have any NULL triangles left, cut the polygon in two and try again
+                splitPolygon( aPoint );
+                break;
+            }
+        }
+
+        /**
+         * At this point, our polygon should be fully tesselated.
+         */
+        assert( aPoint->prev == aPoint->next );
+    }
+
+    /**
+     * Function isEar
+     * Checks whether the given vertex is in the middle of an ear.
+     * This works by walking forward and backward in zOrder to the limits
+     * of the minimal bounding box formed around the triangle, checking whether
+     * any points are located inside the given triangle.
+     *
+     * Returns true if aEar is the apex point of a ear in the polygon
+     */
+    bool isEar( Vertex* aEar ) const
+    {
+        const Vertex* a = aEar->prev;
+        const Vertex* b = aEar;
+        const Vertex* c = aEar->next;
+
+        // If the area >=0, then the three points for a concave sequence
+        // with b as the reflex point
+        if( area( a, b, c ) >= 0 )
+            return false;
+
+        // triangle bbox
+        const double minTX = std::min( a->x, std::min( b->x, c->x ) );
+        const double minTY = std::min( a->y, std::min( b->y, c->y ) );
+        const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
+        const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
+
+        // z-order range for the current triangle bounding box
+        const int32_t minZ = zOrder( minTX, minTY );
+        const int32_t maxZ = zOrder( maxTX, maxTY );
+
+        // first look for points inside the triangle in increasing z-order
+        Vertex* p = aEar->nextZ;
+
+        while( p && p->z <= maxZ )
+        {
+            if( p != a && p != c
+                    && p->inTriangle( *a, *b, *c )
+                    && area( p->prev, p, p->next ) >= 0 )
+                return false;
+            p = p->nextZ;
+        }
+
+        // then look for points in decreasing z-order
+        p = aEar->prevZ;
+
+        while( p && p->z >= minZ )
+        {
+            if( p != a && p != c
+                    && p->inTriangle( *a, *b, *c )
+                    && area( p->prev, p, p->next ) >= 0 )
+                return false;
+            p = p->prevZ;
+        }
+
+        return true;
+    }
+
+    /**
+     * Function splitPolygon
+     * If we cannot find an ear to slice in the current polygon list, we
+     * use this to split the polygon into two separate lists and slice them each
+     * independently.  This is assured to generate at least one new ear if the
+     * split is successful
+     */
+    void splitPolygon( Vertex* start )
+    {
+        Vertex* origPoly = start;
+        do
+        {
+            Vertex* marker = origPoly->next->next;
+            while( marker != origPoly->prev )
+            {
+                // Find a diagonal line that is wholly enclosed by the polygon interior
+                if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
+                {
+                    Vertex* newPoly = origPoly->split( marker );
+
+                    origPoly->updateList();
+                    newPoly->updateList();
+
+                    earcutList( origPoly );
+                    earcutList( newPoly );
+                    return;
+                }
+                marker = marker->next;
+            }
+            origPoly = origPoly->next;
+        } while( origPoly != start );
+    }
+
+    /**
+     * Check if a segment joining two vertices lies fully inside the polygon.
+     * To do this, we first ensure that the line isn't along the polygon edge.
+     * Next, we know that if the line doesn't intersect the polygon, then it is
+     * either fully inside or fully outside the polygon.  Finally, by checking whether
+     * the segment is enclosed by the local triangles, we distinguish between
+     * these two cases and no further checks are needed.
+     */
+    bool goodSplit( const Vertex* a, const Vertex* b ) const
+    {
+        return a->next->i != b->i &&
+               a->prev->i != b->i &&
+               !intersectsPolygon( a, b ) &&
+               locallyInside( a, b );
+    }
+
+    /**
+     * Function area
+     * Returns the twice the signed area of the triangle formed by vertices
+     * p, q, r.
+     */
+    double area( const Vertex* p, const Vertex* q, const Vertex* r ) const
+    {
+        return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
+    }
+
+    /**
+     * Function intersects
+     * Checks for intersection between two segments, end points included.
+     * Returns true if p1-p2 intersects q1-q2
+     */
+    bool intersects( const Vertex* p1, const Vertex* q1, const Vertex* p2, const Vertex* q2 ) const
+    {
+        if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
+            return true;
+
+        return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
+                && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
+    }
+
+    /**
+     * Function intersectsPolygon
+     * Checks whether the segment from vertex a -> vertex b crosses any of the segments
+     * of the polygon of which vertex a is a member.
+     * Return true if the segment intersects the edge of the polygon
+     */
+    bool intersectsPolygon( const Vertex* a, const Vertex* b ) const
+    {
+        const Vertex* p = a->next;
+        do
+        {
+            if( p->i != a->i &&
+                p->next->i != a->i &&
+                p->i != b->i &&
+                p->next->i != b->i && intersects( p, p->next, a, b ) )
+                return true;
+
+            p = p->next;
+        } while( p != a );
+
+        return false;
+    }
+
+    /**
+     * Function locallyInside
+     * Checks whether the segment from vertex a -> vertex b is inside the polygon
+     * around the immediate area of vertex a.  We don't define the exact area
+     * over which the segment is inside but it is guaranteed to be inside the polygon
+     * immediately adjacent to vertex a.
+     * Returns true if the segment from a->b is inside a's polygon next to vertex a
+     */
+    bool locallyInside( const Vertex* a, const Vertex* b ) const
+    {
+        if( area( a->prev, a, a->next ) < 0 )
+            return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
+        else
+            return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
+    }
+
+    /**
+     * Function insertVertex
+     * Creates an entry in the vertices lookup and optionally inserts the newly
+     * created vertex into an existing linked list.
+     * Returns a pointer to the newly created vertex
+     */
+    Vertex* insertVertex( const VECTOR2I& pt, Vertex* last )
+    {
+        m_result.AddVertex( pt );
+        m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
+
+        Vertex* p = &m_vertices.back();
+        if( !last )
+        {
+            p->prev = p;
+            p->next = p;
+        }
+        else
+        {
+            p->next = last->next;
+            p->prev = last;
+            last->next->prev = p;
+            last->next = p;
+        }
+        return p;
+    }
+
+public:
+
+    void TesselatePolygon( const SHAPE_LINE_CHAIN& aPoly )
+    {
+        m_bbox = aPoly.BBox();
+
+        if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
+            return;
+
+        Vertex* outerNode = createList( aPoly );
+        if( !outerNode )
+            return;
+
+        outerNode->updateList();
+        earcutList( outerNode );
+
+        m_vertices.clear();
+    }
+};
+
+#endif //__POLYGON_TRIANGULATION_H
diff --git a/include/geometry/shape_poly_set.h b/include/geometry/shape_poly_set.h
index 8714c5d..2d29e00 100644
--- a/include/geometry/shape_poly_set.h
+++ b/include/geometry/shape_poly_set.h
@@ -58,64 +58,60 @@ class SHAPE_POLY_SET : public SHAPE
     public:
         ///> represents a single polygon outline with holes. The first entry is the outline,
         ///> the remaining (if any), are the holes
+        ///> N.B. SWIG only supports typedef, so avoid c++ 'using' keyword
         typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
 
-        class TRIANGULATION_CONTEXT;
-
         class TRIANGULATED_POLYGON
         {
         public:
             struct TRI
             {
-                TRI() : a(0), b(0), c(0)
+                TRI( int _a = 0, int _b = 0, int _c = 0 ) : a( _a ), b( _b ), c( _c )
                 {
                 }
 
                 int a, b, c;
             };
 
-            ~TRIANGULATED_POLYGON();
-
             void Clear();
 
-            void AllocateVertices( int aSize );
-            void AllocateTriangles ( int aSize );
-
             void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
             {
-                auto tri = &m_triangles[ index ];
-                a = m_vertices[ tri->a ];
-                b = m_vertices[ tri->b ];
-                c = m_vertices[ tri->c ];
+                auto tri = m_triangles[ index ];
+                a = m_vertices[ tri.a ];
+                b = m_vertices[ tri.b ];
+                c = m_vertices[ tri.c ];
+            }
+
+            void AddTriangle( const TRI& aTri )
+            {
+                m_triangles.push_back( aTri );
             }
 
-            void SetTriangle( int aIndex, const TRI& aTri )
+            void AddTriangle( int a, int b, int c )
             {
-                m_triangles[aIndex] = aTri;
+                m_triangles.emplace_back( a, b, c );
             }
 
-            int AddVertex( const VECTOR2I& aP )
+            void AddVertex( const VECTOR2I& aP )
             {
-                m_vertices[ m_vertexCount ] = aP;
-                return (m_vertexCount++);
+                m_vertices.push_back( aP );
             }
 
-            int GetTriangleCount() const
+            size_t GetTriangleCount() const
             {
-                return m_triangleCount;
+                return m_triangles.size();
             }
 
-            int GetVertexCount() const
+            size_t GetVertexCount() const
             {
-                return m_vertexCount;
+                return m_vertices.size();
             }
 
         private:
 
-            TRI* m_triangles = nullptr;
-            VECTOR2I* m_vertices = nullptr;
-            int m_vertexCount = 0;
-            int m_triangleCount = 0;
+            std::deque<TRI> m_triangles;
+            std::deque<VECTOR2I> m_vertices;
         };
 
         /**
@@ -1184,7 +1180,6 @@ class SHAPE_POLY_SET : public SHAPE
         MD5_HASH GetHash() const;
 
     private:
-        void triangulateSingle( const POLYGON& aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON& aResult );
 
         MD5_HASH checksum() const;
 
diff --git a/polygon/CMakeLists.txt b/polygon/CMakeLists.txt
index 6205d07..cd5959e 100644
--- a/polygon/CMakeLists.txt
+++ b/polygon/CMakeLists.txt
@@ -13,11 +13,6 @@ set(POLYGON_SRCS
     PolyLine.cpp
     polygon_test_point_inside.cpp
     clipper.cpp
-    ./poly2tri/sweep/sweep.cc
-    ./poly2tri/sweep/sweep_context.cc
-    ./poly2tri/sweep/cdt.cc
-    ./poly2tri/sweep/advancing_front.cc
-    ./poly2tri/common/shapes.cc
 )
 
 add_library(polygon STATIC ${POLYGON_SRCS})
diff --git a/polygon/poly2tri/common/shapes.cc b/polygon/poly2tri/common/shapes.cc
deleted file mode 100644
index 5ad7fab..0000000
--- a/polygon/poly2tri/common/shapes.cc
+++ /dev/null
@@ -1,375 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "shapes.h"
-#include <iostream>
-#include <stdexcept>
-
-namespace p2t {
-
-Triangle::Triangle(Point& a, Point& b, Point& c)
-{
-  points_[0] = &a; points_[1] = &b; points_[2] = &c;
-  neighbors_[0] = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL;
-  constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false;
-  delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
-  interior_ = false;
-}
-
-// Update neighbor pointers
-void Triangle::MarkNeighbor(Point* p1, Point* p2, Triangle* t)
-{
-  if ((p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2]))
-    neighbors_[0] = t;
-  else if ((p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0]))
-    neighbors_[1] = t;
-  else if ((p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0]))
-    neighbors_[2] = t;
-  else
-    throw std::runtime_error("Polygon contains overlapping hole vertices.");
-}
-
-// Exhaustive search to update neighbor pointers
-void Triangle::MarkNeighbor(Triangle& t)
-{
-  if (t.Contains(points_[1], points_[2])) {
-    neighbors_[0] = &t;
-    t.MarkNeighbor(points_[1], points_[2], this);
-  } else if (t.Contains(points_[0], points_[2])) {
-    neighbors_[1] = &t;
-    t.MarkNeighbor(points_[0], points_[2], this);
-  } else if (t.Contains(points_[0], points_[1])) {
-    neighbors_[2] = &t;
-    t.MarkNeighbor(points_[0], points_[1], this);
-  }
-}
-
-/**
- * Clears all references to all other triangles and points
- */
-void Triangle::Clear()
-{
-    Triangle *t;
-    for( int i=0; i<3; i++ )
-    {
-        t = neighbors_[i];
-        if( t != NULL )
-        {
-            t->ClearNeighbor( this );
-        }
-    }
-    ClearNeighbors();
-    points_[0]=points_[1]=points_[2] = NULL;
-}
-
-void Triangle::ClearNeighbor(Triangle *triangle )
-{
-    if( neighbors_[0] == triangle )
-    {
-        neighbors_[0] = NULL;
-    }
-    else if( neighbors_[1] == triangle )
-    {
-        neighbors_[1] = NULL;
-    }
-    else
-    {
-        neighbors_[2] = NULL;
-    }
-}
-
-void Triangle::ClearNeighbors()
-{
-  neighbors_[0] = NULL;
-  neighbors_[1] = NULL;
-  neighbors_[2] = NULL;
-}
-
-void Triangle::ClearDelunayEdges()
-{
-  delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
-}
-
-Point* Triangle::OppositePoint(Triangle& t, Point& p)
-{
-    Point*  cw  = t.PointCW( p );
-
-    /*
-    double  x   = cw->x;
-    double  y   = cw->y;
-
-    x   = p.x;
-    y   = p.y;
-    */
-
-    return PointCW( *cw );
-}
-
-// Legalized triangle by rotating clockwise around point(0)
-void Triangle::Legalize(Point& point)
-{
-  points_[1] = points_[0];
-  points_[0] = points_[2];
-  points_[2] = &point;
-}
-
-// Legalize triagnle by rotating clockwise around oPoint
-void Triangle::Legalize(Point& opoint, Point& npoint)
-{
-  if (&opoint == points_[0]) {
-    points_[1] = points_[0];
-    points_[0] = points_[2];
-    points_[2] = &npoint;
-  } else if (&opoint == points_[1]) {
-    points_[2] = points_[1];
-    points_[1] = points_[0];
-    points_[0] = &npoint;
-  } else if (&opoint == points_[2]) {
-    points_[0] = points_[2];
-    points_[2] = points_[1];
-    points_[1] = &npoint;
-  } else {
-      throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  }
-}
-
-int Triangle::Index(const Point* p)
-{
-  if (p == points_[0]) {
-    return 0;
-  } else if (p == points_[1]) {
-    return 1;
-  } else if (p == points_[2]) {
-    return 2;
-  }
-  throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  return 0;
-}
-
-int Triangle::EdgeIndex(const Point* p1, const Point* p2)
-{
-  if (points_[0] == p1) {
-    if (points_[1] == p2) {
-      return 2;
-    } else if (points_[2] == p2) {
-      return 1;
-    }
-  } else if (points_[1] == p1) {
-    if (points_[2] == p2) {
-      return 0;
-    } else if (points_[0] == p2) {
-      return 2;
-    }
-  } else if (points_[2] == p1) {
-    if (points_[0] == p2) {
-      return 1;
-    } else if (points_[1] == p2) {
-      return 0;
-    }
-  }
-  return -1;
-}
-
-void Triangle::MarkConstrainedEdge(const int index)
-{
-  constrained_edge[index] = true;
-}
-
-void Triangle::MarkConstrainedEdge(Edge& edge)
-{
-  MarkConstrainedEdge(edge.p, edge.q);
-}
-
-// Mark edge as constrained
-void Triangle::MarkConstrainedEdge(Point* p, Point* q)
-{
-  if ((q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0])) {
-    constrained_edge[2] = true;
-  } else if ((q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0])) {
-    constrained_edge[1] = true;
-  } else if ((q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1])) {
-    constrained_edge[0] = true;
-  }
-}
-
-// The point counter-clockwise to given point
-Point* Triangle::PointCW(Point& point)
-{
-  if (&point == points_[0]) {
-    return points_[2];
-  } else if (&point == points_[1]) {
-    return points_[0];
-  } else if (&point == points_[2]) {
-    return points_[1];
-  }
-  throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  return NULL;
-}
-
-// The point counter-clockwise to given point
-Point* Triangle::PointCCW(Point& point)
-{
-  if (&point == points_[0]) {
-    return points_[1];
-  } else if (&point == points_[1]) {
-    return points_[2];
-  } else if (&point == points_[2]) {
-    return points_[0];
-  }
-  throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  return NULL;
-}
-
-// The neighbor clockwise to given point
-Triangle* Triangle::NeighborCW(Point& point)
-{
-  if (&point == points_[0]) {
-    return neighbors_[1];
-  } else if (&point == points_[1]) {
-    return neighbors_[2];
-  }
-  return neighbors_[0];
-}
-
-// The neighbor counter-clockwise to given point
-Triangle* Triangle::NeighborCCW(Point& point)
-{
-  if (&point == points_[0]) {
-    return neighbors_[2];
-  } else if (&point == points_[1]) {
-    return neighbors_[0];
-  }
-  return neighbors_[1];
-}
-
-bool Triangle::GetConstrainedEdgeCCW(Point& p)
-{
-  if (&p == points_[0]) {
-    return constrained_edge[2];
-  } else if (&p == points_[1]) {
-    return constrained_edge[0];
-  }
-  return constrained_edge[1];
-}
-
-bool Triangle::GetConstrainedEdgeCW(Point& p)
-{
-  if (&p == points_[0]) {
-    return constrained_edge[1];
-  } else if (&p == points_[1]) {
-    return constrained_edge[2];
-  }
-  return constrained_edge[0];
-}
-
-void Triangle::SetConstrainedEdgeCCW(Point& p, bool ce)
-{
-  if (&p == points_[0]) {
-    constrained_edge[2] = ce;
-  } else if (&p == points_[1]) {
-    constrained_edge[0] = ce;
-  } else {
-    constrained_edge[1] = ce;
-  }
-}
-
-void Triangle::SetConstrainedEdgeCW(Point& p, bool ce)
-{
-  if (&p == points_[0]) {
-    constrained_edge[1] = ce;
-  } else if (&p == points_[1]) {
-    constrained_edge[2] = ce;
-  } else {
-    constrained_edge[0] = ce;
-  }
-}
-
-bool Triangle::GetDelunayEdgeCCW(Point& p)
-{
-  if (&p == points_[0]) {
-    return delaunay_edge[2];
-  } else if (&p == points_[1]) {
-    return delaunay_edge[0];
-  }
-  return delaunay_edge[1];
-}
-
-bool Triangle::GetDelunayEdgeCW(Point& p)
-{
-  if (&p == points_[0]) {
-    return delaunay_edge[1];
-  } else if (&p == points_[1]) {
-    return delaunay_edge[2];
-  }
-  return delaunay_edge[0];
-}
-
-void Triangle::SetDelunayEdgeCCW(Point& p, bool e)
-{
-  if (&p == points_[0]) {
-    delaunay_edge[2] = e;
-  } else if (&p == points_[1]) {
-    delaunay_edge[0] = e;
-  } else {
-    delaunay_edge[1] = e;
-  }
-}
-
-void Triangle::SetDelunayEdgeCW(Point& p, bool e)
-{
-  if (&p == points_[0]) {
-    delaunay_edge[1] = e;
-  } else if (&p == points_[1]) {
-    delaunay_edge[2] = e;
-  } else {
-    delaunay_edge[0] = e;
-  }
-}
-
-// The neighbor across to given point
-Triangle* Triangle::NeighborAcross(Point& opoint)
-{
-  if (&opoint == points_[0]) {
-    return neighbors_[0];
-  } else if (&opoint == points_[1]) {
-    return neighbors_[1];
-  }
-  return neighbors_[2];
-}
-
-void Triangle::DebugPrint()
-{
-  using namespace std;
-  cout << points_[0]->x << "," << points_[0]->y << " ";
-  cout << points_[1]->x << "," << points_[1]->y << " ";
-  cout << points_[2]->x << "," << points_[2]->y << endl;
-}
-
-}
diff --git a/polygon/poly2tri/common/shapes.h b/polygon/poly2tri/common/shapes.h
deleted file mode 100644
index 3ec2f98..0000000
--- a/polygon/poly2tri/common/shapes.h
+++ /dev/null
@@ -1,325 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-// Include guard
-#ifndef SHAPES_H
-#define SHAPES_H
-
-#include <vector>
-#include <cstddef>
-#include <assert.h>
-#include <cmath>
-
-namespace p2t {
-
-struct Edge;
-
-struct Point {
-
-  double x, y;
-  int id;
-
-  /// Default constructor does nothing (for performance).
-  Point()
-  {
-    x = 0.0;
-    y = 0.0;
-    id = 0;
-  }
-
-  /// The edges this point constitutes an upper ending point
-  std::vector<Edge*> edge_list;
-
-  /// Construct using coordinates.
-  Point(double ax, double ay, int aid = 0) : x(ax), y(ay), id(aid) {}
-
-  /// Set this point to all zeros.
-  void set_zero()
-  {
-    x = 0.0;
-    y = 0.0;
-  }
-
-  /// Set this point to some specified coordinates.
-  void set(double x_, double y_)
-  {
-    x = x_;
-    y = y_;
-  }
-
-  /// Negate this point.
-  Point operator -() const
-  {
-    Point v;
-    v.set(-x, -y);
-    return v;
-  }
-
-  /// Add a point to this point.
-  void operator +=(const Point& v)
-  {
-    x += v.x;
-    y += v.y;
-  }
-
-  /// Subtract a point from this point.
-  void operator -=(const Point& v)
-  {
-    x -= v.x;
-    y -= v.y;
-  }
-
-  /// Multiply this point by a scalar.
-  void operator *=(double a)
-  {
-    x *= a;
-    y *= a;
-  }
-
-  /// Get the length of this point (the norm).
-  double Length() const
-  {
-    return sqrt(x * x + y * y);
-  }
-
-  /// Convert this point into a unit point. Returns the Length.
-  double Normalize()
-  {
-    double len = Length();
-    x /= len;
-    y /= len;
-    return len;
-  }
-
-};
-
-// Represents a simple polygon's edge
-struct Edge {
-
-  Point* p, *q;
-
-  /// Constructor
-  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
-  {
-    if (p1.y > p2.y) {
-      q = &p1;
-      p = &p2;
-    } else if (p1.y == p2.y) {
-      if (p1.x > p2.x) {
-        q = &p1;
-        p = &p2;
-      } else if (p1.x == p2.x) {
-        // Repeat points
-        assert(false);
-      }
-    }
-
-    q->edge_list.push_back(this);
-  }
-};
-
-// Triangle-based data structures are know to have better performance than quad-edge structures
-// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
-//      "Triangulations in CGAL"
-class Triangle {
-public:
-
-/// Constructor
-Triangle(Point& a, Point& b, Point& c);
-
-/// Flags to determine if an edge is a Constrained edge
-bool constrained_edge[3];
-/// Flags to determine if an edge is a Delauney edge
-bool delaunay_edge[3];
-
-Point* GetPoint(const int& index);
-Point* PointCW(Point& point);
-Point* PointCCW(Point& point);
-Point* OppositePoint(Triangle& t, Point& p);
-
-Triangle* GetNeighbor(const int& index);
-void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
-void MarkNeighbor(Triangle& t);
-
-void MarkConstrainedEdge(const int index);
-void MarkConstrainedEdge(Edge& edge);
-void MarkConstrainedEdge(Point* p, Point* q);
-
-int Index(const Point* p);
-int EdgeIndex(const Point* p1, const Point* p2);
-
-Triangle* NeighborCW(Point& point);
-Triangle* NeighborCCW(Point& point);
-bool GetConstrainedEdgeCCW(Point& p);
-bool GetConstrainedEdgeCW(Point& p);
-void SetConstrainedEdgeCCW(Point& p, bool ce);
-void SetConstrainedEdgeCW(Point& p, bool ce);
-bool GetDelunayEdgeCCW(Point& p);
-bool GetDelunayEdgeCW(Point& p);
-void SetDelunayEdgeCCW(Point& p, bool e);
-void SetDelunayEdgeCW(Point& p, bool e);
-
-bool Contains(Point* p);
-bool Contains(const Edge& e);
-bool Contains(Point* p, Point* q);
-void Legalize(Point& point);
-void Legalize(Point& opoint, Point& npoint);
-/**
- * Clears all references to all other triangles and points
- */
-void Clear();
-void ClearNeighbor(Triangle *triangle );
-void ClearNeighbors();
-void ClearDelunayEdges();
-
-inline bool IsInterior();
-inline void IsInterior(bool b);
-
-Triangle* NeighborAcross(Point& opoint);
-
-void DebugPrint();
-
-private:
-
-/// Triangle points
-Point* points_[3];
-/// Neighbor list
-Triangle* neighbors_[3];
-
-/// Has this triangle been marked as an interior triangle?
-bool interior_;
-};
-
-inline bool cmp(const Point* a, const Point* b)
-{
-  if (a->y < b->y) {
-    return true;
-  } else if (a->y == b->y) {
-    // Make sure q is point with greater x value
-    if (a->x < b->x) {
-      return true;
-    }
-  }
-  return false;
-}
-
-/// Add two points_ component-wise.
-inline Point operator +(const Point& a, const Point& b)
-{
-  return Point(a.x + b.x, a.y + b.y);
-}
-
-/// Subtract two points_ component-wise.
-inline Point operator -(const Point& a, const Point& b)
-{
-  return Point(a.x - b.x, a.y - b.y);
-}
-
-/// Multiply point by scalar
-inline Point operator *(double s, const Point& a)
-{
-  return Point(s * a.x, s * a.y);
-}
-
-inline bool operator ==(const Point& a, const Point& b)
-{
-  return a.x == b.x && a.y == b.y;
-}
-
-inline bool operator !=(const Point& a, const Point& b)
-{
-  return !(a.x == b.x) && !(a.y == b.y);
-}
-
-/// Peform the dot product on two vectors.
-inline double Dot(const Point& a, const Point& b)
-{
-  return a.x * b.x + a.y * b.y;
-}
-
-/// Perform the cross product on two vectors. In 2D this produces a scalar.
-inline double Cross(const Point& a, const Point& b)
-{
-  return a.x * b.y - a.y * b.x;
-}
-
-/// Perform the cross product on a point and a scalar. In 2D this produces
-/// a point.
-inline Point Cross(const Point& a, double s)
-{
-  return Point(s * a.y, -s * a.x);
-}
-
-/// Perform the cross product on a scalar and a point. In 2D this produces
-/// a point.
-inline Point Cross(const double s, const Point& a)
-{
-  return Point(-s * a.y, s * a.x);
-}
-
-inline Point* Triangle::GetPoint(const int& index)
-{
-  return points_[index];
-}
-
-inline Triangle* Triangle::GetNeighbor(const int& index)
-{
-  return neighbors_[index];
-}
-
-inline bool Triangle::Contains(Point* p)
-{
-  return p == points_[0] || p == points_[1] || p == points_[2];
-}
-
-inline bool Triangle::Contains(const Edge& e)
-{
-  return Contains(e.p) && Contains(e.q);
-}
-
-inline bool Triangle::Contains(Point* p, Point* q)
-{
-  return Contains(p) && Contains(q);
-}
-
-inline bool Triangle::IsInterior()
-{
-  return interior_;
-}
-
-inline void Triangle::IsInterior(bool b)
-{
-  interior_ = b;
-}
-
-}
-
-#endif
diff --git a/polygon/poly2tri/common/utils.h b/polygon/poly2tri/common/utils.h
deleted file mode 100644
index 78416f2..0000000
--- a/polygon/poly2tri/common/utils.h
+++ /dev/null
@@ -1,123 +0,0 @@
-/* 
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
- 
-#ifndef UTILS_H
-#define UTILS_H
-
-// Otherwise #defines like M_PI are undeclared under Visual Studio
-#define _USE_MATH_DEFINES
-
-#include <exception>
-#include <math.h>
-
-namespace p2t {
-
-const double PI_3div4 = 3 * M_PI / 4;
-const double PI_div2 = 1.57079632679489661923;
-const double EPSILON = 1e-12;
-
-enum Orientation { CW, CCW, COLLINEAR };
-
-/**
- * Forumla to calculate signed area<br>
- * Positive if CCW<br>
- * Negative if CW<br>
- * 0 if collinear<br>
- * <pre>
- * A[P1,P2,P3]  =  (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
- *              =  (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
- * </pre>
- */
-Orientation Orient2d(Point& pa, Point& pb, Point& pc)
-{
-  double detleft = (pa.x - pc.x) * (pb.y - pc.y);
-  double detright = (pa.y - pc.y) * (pb.x - pc.x);
-  double val = detleft - detright;
-  if (val > -EPSILON && val < EPSILON) {
-    return COLLINEAR;
-  } else if (val > 0) {
-    return CCW;
-  }
-  return CW;
-}
-
-/*
-bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd)
-{
-  double pdx = pd.x;
-  double pdy = pd.y;
-  double adx = pa.x - pdx;
-  double ady = pa.y - pdy;
-  double bdx = pb.x - pdx;
-  double bdy = pb.y - pdy;
-
-  double adxbdy = adx * bdy;
-  double bdxady = bdx * ady;
-  double oabd = adxbdy - bdxady;
-
-  if (oabd <= EPSILON) {
-    return false;
-  }
-
-  double cdx = pc.x - pdx;
-  double cdy = pc.y - pdy;
-
-  double cdxady = cdx * ady;
-  double adxcdy = adx * cdy;
-  double ocad = cdxady - adxcdy;
-
-  if (ocad <= EPSILON) {
-    return false;
-  }
-
-  return true;
-}
-
-*/
-
-bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd)
-{
-  double oadb = (pa.x - pb.x)*(pd.y - pb.y) - (pd.x - pb.x)*(pa.y - pb.y);
-  if (oadb >= -EPSILON) {
-    return false;
-  }
-
-  double oadc = (pa.x - pc.x)*(pd.y - pc.y) - (pd.x - pc.x)*(pa.y - pc.y);
-  if (oadc <= EPSILON) {
-    return false;
-  }
-  return true;
-}
-
-}
-
-#endif
-
diff --git a/polygon/poly2tri/poly2tri.h b/polygon/poly2tri/poly2tri.h
deleted file mode 100644
index 487755e..0000000
--- a/polygon/poly2tri/poly2tri.h
+++ /dev/null
@@ -1,39 +0,0 @@
-/* 
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef POLY2TRI_H
-#define POLY2TRI_H
-
-#include "common/shapes.h"
-#include "sweep/cdt.h"
-
-#endif
-
diff --git a/polygon/poly2tri/sweep/advancing_front.cc b/polygon/poly2tri/sweep/advancing_front.cc
deleted file mode 100644
index 019df4a..0000000
--- a/polygon/poly2tri/sweep/advancing_front.cc
+++ /dev/null
@@ -1,109 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "advancing_front.h"
-
-namespace p2t {
-
-AdvancingFront::AdvancingFront(Node& head, Node& tail)
-{
-  head_ = &head;
-  tail_ = &tail;
-  search_node_ = &head;
-}
-
-Node* AdvancingFront::LocateNode(const double& x)
-{
-  Node* node = search_node_;
-
-  if (x < node->value) {
-    while ((node = node->prev) != NULL) {
-      if (x >= node->value) {
-        search_node_ = node;
-        return node;
-      }
-    }
-  } else {
-    while ((node = node->next) != NULL) {
-      if (x < node->value) {
-        search_node_ = node->prev;
-        return node->prev;
-      }
-    }
-  }
-  return NULL;
-}
-
-Node* AdvancingFront::FindSearchNode(const double& x)
-{
-  (void)x; // suppress compiler warnings "unused parameter 'x'"
-  // TODO: implement BST index
-  return search_node_;
-}
-
-Node* AdvancingFront::LocatePoint(const Point* point)
-{
-  const double px = point->x;
-  Node* node = FindSearchNode(px);
-  const double nx = node->point->x;
-
-  if (px == nx) {
-    if (point != node->point) {
-      // We might have two nodes with same x value for a short time
-      if (point == node->prev->point) {
-        node = node->prev;
-      } else if (point == node->next->point) {
-        node = node->next;
-      } else {
-        assert(0);
-      }
-    }
-  } else if (px < nx) {
-    while ((node = node->prev) != NULL) {
-      if (point == node->point) {
-        break;
-      }
-    }
-  } else {
-    while ((node = node->next) != NULL) {
-      if (point == node->point)
-        break;
-    }
-  }
-  if(node) search_node_ = node;
-  return node;
-}
-
-AdvancingFront::~AdvancingFront()
-{
-}
-
-}
-
diff --git a/polygon/poly2tri/sweep/advancing_front.h b/polygon/poly2tri/sweep/advancing_front.h
deleted file mode 100644
index bab73d4..0000000
--- a/polygon/poly2tri/sweep/advancing_front.h
+++ /dev/null
@@ -1,118 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef ADVANCED_FRONT_H
-#define ADVANCED_FRONT_H
-
-#include "../common/shapes.h"
-
-namespace p2t {
-
-struct Node;
-
-// Advancing front node
-struct Node {
-  Point* point;
-  Triangle* triangle;
-
-  Node* next;
-  Node* prev;
-
-  double value;
-
-  Node(Point& p) : point(&p), triangle(NULL), next(NULL), prev(NULL), value(p.x)
-  {
-  }
-
-  Node(Point& p, Triangle& t) : point(&p), triangle(&t), next(NULL), prev(NULL), value(p.x)
-  {
-  }
-
-};
-
-// Advancing front
-class AdvancingFront {
-public:
-
-AdvancingFront(Node& head, Node& tail);
-// Destructor
-~AdvancingFront();
-
-Node* head();
-void set_head(Node* node);
-Node* tail();
-void set_tail(Node* node);
-Node* search();
-void set_search(Node* node);
-
-/// Locate insertion point along advancing front
-Node* LocateNode(const double& x);
-
-Node* LocatePoint(const Point* point);
-
-private:
-
-Node* head_, *tail_, *search_node_;
-
-Node* FindSearchNode(const double& x);
-};
-
-inline Node* AdvancingFront::head()
-{
-  return head_;
-}
-inline void AdvancingFront::set_head(Node* node)
-{
-  head_ = node;
-}
-
-inline Node* AdvancingFront::tail()
-{
-  return tail_;
-}
-inline void AdvancingFront::set_tail(Node* node)
-{
-  tail_ = node;
-}
-
-inline Node* AdvancingFront::search()
-{
-  return search_node_;
-}
-
-inline void AdvancingFront::set_search(Node* node)
-{
-  search_node_ = node;
-}
-
-}
-
-#endif
diff --git a/polygon/poly2tri/sweep/cdt.cc b/polygon/poly2tri/sweep/cdt.cc
deleted file mode 100644
index cae6157..0000000
--- a/polygon/poly2tri/sweep/cdt.cc
+++ /dev/null
@@ -1,74 +0,0 @@
-/* 
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "cdt.h"
-
-#include <utility>
-
-namespace p2t {
-
-CDT::CDT(std::vector<Point*> polyline)
-{
-  sweep_context_ = new SweepContext( std::move( polyline ) );
-  sweep_ = new Sweep;
-}
-
-void CDT::AddHole(std::vector<Point*> polyline)
-{
-  sweep_context_->AddHole(polyline);
-}
-
-void CDT::AddPoint(Point* point) {
-  sweep_context_->AddPoint(point);
-}
-
-void CDT::Triangulate()
-{
-  sweep_->Triangulate(*sweep_context_);
-}
-
-std::vector<p2t::Triangle*> CDT::GetTriangles()
-{
-  return sweep_context_->GetTriangles();
-}
-
-std::list<p2t::Triangle*> CDT::GetMap()
-{
-  return sweep_context_->GetMap();
-}
-
-CDT::~CDT()
-{
-  delete sweep_context_;
-  delete sweep_;
-}
-
-}
-
diff --git a/polygon/poly2tri/sweep/cdt.h b/polygon/poly2tri/sweep/cdt.h
deleted file mode 100644
index 3e6f024..0000000
--- a/polygon/poly2tri/sweep/cdt.h
+++ /dev/null
@@ -1,105 +0,0 @@
-/* 
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
- 
-#ifndef CDT_H
-#define CDT_H
-
-#include "advancing_front.h"
-#include "sweep_context.h"
-#include "sweep.h"
-
-/**
- * 
- * @author Mason Green <[e-mail]>
- *
- */
- 
-namespace p2t {
-
-class CDT
-{
-public:
-
-  /**
-   * Constructor - add polyline with non repeating points
-   * 
-   * @param polyline
-   */
-  CDT(std::vector<Point*> polyline);
-  
-   /**
-   * Destructor - clean up memory
-   */
-  ~CDT();
-  
-  /**
-   * Add a hole
-   * 
-   * @param polyline
-   */
-  void AddHole(std::vector<Point*> polyline);
-  
-  /**
-   * Add a steiner point
-   * 
-   * @param point
-   */
-  void AddPoint(Point* point);
-  
-  /**
-   * Triangulate - do this AFTER you've added the polyline, holes, and Steiner points
-   */
-  void Triangulate();
-  
-  /**
-   * Get CDT triangles
-   */
-  std::vector<Triangle*> GetTriangles();
-  
-  /**
-   * Get triangle map
-   */
-  std::list<Triangle*> GetMap();
-
-  private:
-
-  /**
-   * Internals
-   */
-   
-  SweepContext* sweep_context_;
-  Sweep* sweep_;
-
-};
-
-}
-
-#endif
diff --git a/polygon/poly2tri/sweep/sweep.cc b/polygon/poly2tri/sweep/sweep.cc
deleted file mode 100644
index dcd815f..0000000
--- a/polygon/poly2tri/sweep/sweep.cc
+++ /dev/null
@@ -1,811 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "sweep.h"
-#include "sweep_context.h"
-#include "advancing_front.h"
-#include "../common/utils.h"
-#include <stdexcept>
-
-namespace p2t {
-
-// Triangulate simple polygon with holes
-void Sweep::Triangulate(SweepContext& tcx)
-{
-  tcx.InitTriangulation();
-  tcx.CreateAdvancingFront(nodes_);
-  // Sweep points; build mesh
-  SweepPoints(tcx);
-  // Clean up
-  FinalizationPolygon(tcx);
-}
-
-void Sweep::SweepPoints(SweepContext& tcx)
-{
-  for (int i = 1; i < tcx.point_count(); i++) {
-    Point& point = *tcx.GetPoint(i);
-    Node* node = &PointEvent(tcx, point);
-    for (unsigned int j = 0; j < point.edge_list.size(); j++) {
-      EdgeEvent(tcx, point.edge_list[j], node);
-    }
-  }
-}
-
-void Sweep::FinalizationPolygon(SweepContext& tcx)
-{
-  // Get an Internal triangle to start with
-  Triangle* t = tcx.front()->head()->next->triangle;
-  Point* p = tcx.front()->head()->next->point;
-  while (!t->GetConstrainedEdgeCW(*p)) {
-    t = t->NeighborCCW(*p);
-  }
-
-  // Collect interior triangles constrained by edges
-  tcx.MeshClean(*t);
-}
-
-Node& Sweep::PointEvent(SweepContext& tcx, Point& point)
-{
-  Node& node = tcx.LocateNode(point);
-  Node& new_node = NewFrontTriangle(tcx, point, node);
-
-  // Only need to check +epsilon since point never have smaller
-  // x value than node due to how we fetch nodes from the front
-  if (point.x <= node.point->x + EPSILON) {
-    Fill(tcx, node);
-  }
-
-  //tcx.AddNode(new_node);
-
-  FillAdvancingFront(tcx, new_node);
-  return new_node;
-}
-
-void Sweep::EdgeEvent(SweepContext& tcx, Edge* edge, Node* node)
-{
-  tcx.edge_event.constrained_edge = edge;
-  tcx.edge_event.right = (edge->p->x > edge->q->x);
-
-  if (IsEdgeSideOfTriangle(*node->triangle, *edge->p, *edge->q)) {
-    return;
-  }
-
-  // For now we will do all needed filling
-  // TODO: integrate with flip process might give some better performance
-  //       but for now this avoid the issue with cases that needs both flips and fills
-  FillEdgeEvent(tcx, edge, node);
-  EdgeEvent(tcx, *edge->p, *edge->q, node->triangle, *edge->q);
-}
-
-void Sweep::EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point)
-{
-  if (IsEdgeSideOfTriangle(*triangle, ep, eq)) {
-    return;
-  }
-
-  Point* p1 = triangle->PointCCW(point);
-  Orientation o1 = Orient2d(eq, *p1, ep);
-  if (o1 == COLLINEAR) {
-    if( triangle->Contains(&eq, p1)) {
-      triangle->MarkConstrainedEdge(&eq, p1 );
-      // We are modifying the constraint maybe it would be better to
-      // not change the given constraint and just keep a variable for the new constraint
-      tcx.edge_event.constrained_edge->q = p1;
-      triangle = triangle->NeighborAcross(point);
-      EdgeEvent( tcx, ep, *p1, triangle, *p1 );
-    } else {
-      std::runtime_error("EdgeEvent - collinear points not supported");
-    }
-    return;
-  }
-
-  Point* p2 = triangle->PointCW(point);
-  Orientation o2 = Orient2d(eq, *p2, ep);
-  if (o2 == COLLINEAR) {
-    if( triangle->Contains(&eq, p2)) {
-      triangle->MarkConstrainedEdge(&eq, p2 );
-      // We are modifying the constraint maybe it would be better to
-      // not change the given constraint and just keep a variable for the new constraint
-      tcx.edge_event.constrained_edge->q = p2;
-      triangle = triangle->NeighborAcross(point);
-      EdgeEvent( tcx, ep, *p2, triangle, *p2 );
-    } else {
-      std::runtime_error("EdgeEvent - collinear points not supported");
-    }
-    return;
-  }
-
-  if (o1 == o2) {
-    // Need to decide if we are rotating CW or CCW to get to a triangle
-    // that will cross edge
-    if (o1 == CW) {
-      triangle = triangle->NeighborCCW(point);
-    }       else{
-      triangle = triangle->NeighborCW(point);
-    }
-    EdgeEvent(tcx, ep, eq, triangle, point);
-  } else {
-    // This triangle crosses constraint so lets flippin start!
-    FlipEdgeEvent(tcx, ep, eq, triangle, point);
-  }
-}
-
-bool Sweep::IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq)
-{
-  int index = triangle.EdgeIndex(&ep, &eq);
-
-  if (index != -1) {
-    triangle.MarkConstrainedEdge(index);
-    Triangle* t = triangle.GetNeighbor(index);
-    if (t) {
-      t->MarkConstrainedEdge(&ep, &eq);
-    }
-    return true;
-  }
-  return false;
-}
-
-Node& Sweep::NewFrontTriangle(SweepContext& tcx, Point& point, Node& node)
-{
-  Triangle* triangle = new Triangle(point, *node.point, *node.next->point);
-
-  triangle->MarkNeighbor(*node.triangle);
-  tcx.AddToMap(triangle);
-
-  Node* new_node = new Node(point);
-  nodes_.push_back(new_node);
-
-  new_node->next = node.next;
-  new_node->prev = &node;
-  node.next->prev = new_node;
-  node.next = new_node;
-
-  if (!Legalize(tcx, *triangle)) {
-    tcx.MapTriangleToNodes(*triangle);
-  }
-
-  return *new_node;
-}
-
-void Sweep::Fill(SweepContext& tcx, Node& node)
-{
-  Triangle* triangle = new Triangle(*node.prev->point, *node.point, *node.next->point);
-
-  // TODO: should copy the constrained_edge value from neighbor triangles
-  //       for now constrained_edge values are copied during the legalize
-  triangle->MarkNeighbor(*node.prev->triangle);
-  triangle->MarkNeighbor(*node.triangle);
-
-  tcx.AddToMap(triangle);
-
-  // Update the advancing front
-  node.prev->next = node.next;
-  node.next->prev = node.prev;
-
-  // If it was legalized the triangle has already been mapped
-  if (!Legalize(tcx, *triangle)) {
-    tcx.MapTriangleToNodes(*triangle);
-  }
-
-}
-
-void Sweep::FillAdvancingFront(SweepContext& tcx, Node& n)
-{
-
-  // Fill right holes
-  Node* node = n.next;
-
-  while (node->next) {
-    // if HoleAngle exceeds 90 degrees then break.
-    if (LargeHole_DontFill(node)) break;
-    Fill(tcx, *node);
-    node = node->next;
-  }
-
-  // Fill left holes
-  node = n.prev;
-
-  while (node->prev) {
-    // if HoleAngle exceeds 90 degrees then break.
-    if (LargeHole_DontFill(node)) break;
-    Fill(tcx, *node);
-    node = node->prev;
-  }
-
-  // Fill right basins
-  if (n.next && n.next->next) {
-    double angle = BasinAngle(n);
-    if (angle < PI_3div4) {
-      FillBasin(tcx, n);
-    }
-  }
-}
-
-// True if HoleAngle exceeds 90 degrees.
-bool Sweep::LargeHole_DontFill(Node* node) {
-
-  Node* nextNode = node->next;
-  Node* prevNode = node->prev;
-  if (!AngleExceeds90Degrees(node->point, nextNode->point, prevNode->point))
-          return false;
-
-  // Check additional points on front.
-  Node* next2Node = nextNode->next;
-  // "..Plus.." because only want angles on same side as point being added.
-  if ((next2Node != NULL) && !AngleExceedsPlus90DegreesOrIsNegative(node->point, next2Node->point, prevNode->point))
-          return false;
-
-  Node* prev2Node = prevNode->prev;
-  // "..Plus.." because only want angles on same side as point being added.
-  if ((prev2Node != NULL) && !AngleExceedsPlus90DegreesOrIsNegative(node->point, nextNode->point, prev2Node->point))
-          return false;
-
-  return true;
-}
-
-bool Sweep::AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb) {
-  double angle = Angle(*origin, *pa, *pb);
-  bool exceeds90Degrees = ((angle > PI_div2) || (angle < -PI_div2));
-  return exceeds90Degrees;
-}
-
-bool Sweep::AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb) {
-  double angle = Angle(*origin, *pa, *pb);
-  bool exceedsPlus90DegreesOrIsNegative = (angle > PI_div2) || (angle < 0);
-  return exceedsPlus90DegreesOrIsNegative;
-}
-
-double Sweep::Angle(Point& origin, Point& pa, Point& pb) {
-  /* Complex plane
-   * ab = cosA +i*sinA
-   * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx)
-   * atan2(y,x) computes the principal value of the argument function
-   * applied to the complex number x+iy
-   * Where x = ax*bx + ay*by
-   *       y = ax*by - ay*bx
-   */
-  double px = origin.x;
-  double py = origin.y;
-  double ax = pa.x- px;
-  double ay = pa.y - py;
-  double bx = pb.x - px;
-  double by = pb.y - py;
-  double x = ax * by - ay * bx;
-  double y = ax * bx + ay * by;
-  double angle = atan2(x, y);
-  return angle;
-}
-
-double Sweep::BasinAngle(Node& node)
-{
-  double ax = node.point->x - node.next->next->point->x;
-  double ay = node.point->y - node.next->next->point->y;
-  return atan2(ay, ax);
-}
-
-double Sweep::HoleAngle(Node& node)
-{
-  /* Complex plane
-   * ab = cosA +i*sinA
-   * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx)
-   * atan2(y,x) computes the principal value of the argument function
-   * applied to the complex number x+iy
-   * Where x = ax*bx + ay*by
-   *       y = ax*by - ay*bx
-   */
-  double ax = node.next->point->x - node.point->x;
-  double ay = node.next->point->y - node.point->y;
-  double bx = node.prev->point->x - node.point->x;
-  double by = node.prev->point->y - node.point->y;
-  return atan2(ax * by - ay * bx, ax * bx + ay * by);
-}
-
-bool Sweep::Legalize(SweepContext& tcx, Triangle& t)
-{
-  // To legalize a triangle we start by finding if any of the three edges
-  // violate the Delaunay condition
-  for (int i = 0; i < 3; i++) {
-    if (t.delaunay_edge[i])
-      continue;
-
-    Triangle* ot = t.GetNeighbor(i);
-
-    if (ot) {
-      Point* p = t.GetPoint(i);
-      Point* op = ot->OppositePoint(t, *p);
-      int oi = ot->Index(op);
-
-      // If this is a Constrained Edge or a Delaunay Edge(only during recursive legalization)
-      // then we should not try to legalize
-      if (ot->constrained_edge[oi] || ot->delaunay_edge[oi]) {
-        t.constrained_edge[i] = ot->constrained_edge[oi];
-        continue;
-      }
-
-      bool inside = Incircle(*p, *t.PointCCW(*p), *t.PointCW(*p), *op);
-
-      if (inside) {
-        // Lets mark this shared edge as Delaunay
-        t.delaunay_edge[i] = true;
-        ot->delaunay_edge[oi] = true;
-
-        // Lets rotate shared edge one vertex CW to legalize it
-        RotateTrianglePair(t, *p, *ot, *op);
-
-        // We now got one valid Delaunay Edge shared by two triangles
-        // This gives us 4 new edges to check for Delaunay
-
-        // Make sure that triangle to node mapping is done only one time for a specific triangle
-        bool not_legalized = !Legalize(tcx, t);
-        if (not_legalized) {
-          tcx.MapTriangleToNodes(t);
-        }
-
-        not_legalized = !Legalize(tcx, *ot);
-        if (not_legalized)
-          tcx.MapTriangleToNodes(*ot);
-
-        // Reset the Delaunay edges, since they only are valid Delaunay edges
-        // until we add a new triangle or point.
-        // XXX: need to think about this. Can these edges be tried after we
-        //      return to previous recursive level?
-        t.delaunay_edge[i] = false;
-        ot->delaunay_edge[oi] = false;
-
-        // If triangle have been legalized no need to check the other edges since
-        // the recursive legalization will handles those so we can end here.
-        return true;
-      }
-    }
-  }
-  return false;
-}
-
-bool Sweep::Incircle(Point& pa, Point& pb, Point& pc, Point& pd)
-{
-  double adx = pa.x - pd.x;
-  double ady = pa.y - pd.y;
-  double bdx = pb.x - pd.x;
-  double bdy = pb.y - pd.y;
-
-  double adxbdy = adx * bdy;
-  double bdxady = bdx * ady;
-  double oabd = adxbdy - bdxady;
-
-  if (oabd <= 0)
-    return false;
-
-  double cdx = pc.x - pd.x;
-  double cdy = pc.y - pd.y;
-
-  double cdxady = cdx * ady;
-  double adxcdy = adx * cdy;
-  double ocad = cdxady - adxcdy;
-
-  if (ocad <= 0)
-    return false;
-
-  double bdxcdy = bdx * cdy;
-  double cdxbdy = cdx * bdy;
-
-  double alift = adx * adx + ady * ady;
-  double blift = bdx * bdx + bdy * bdy;
-  double clift = cdx * cdx + cdy * cdy;
-
-  double det = alift * (bdxcdy - cdxbdy) + blift * ocad + clift * oabd;
-
-  return det > 0;
-}
-
-void Sweep::RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op)
-{
-  Triangle* n1, *n2, *n3, *n4;
-  n1 = t.NeighborCCW(p);
-  n2 = t.NeighborCW(p);
-  n3 = ot.NeighborCCW(op);
-  n4 = ot.NeighborCW(op);
-
-  bool ce1, ce2, ce3, ce4;
-  ce1 = t.GetConstrainedEdgeCCW(p);
-  ce2 = t.GetConstrainedEdgeCW(p);
-  ce3 = ot.GetConstrainedEdgeCCW(op);
-  ce4 = ot.GetConstrainedEdgeCW(op);
-
-  bool de1, de2, de3, de4;
-  de1 = t.GetDelunayEdgeCCW(p);
-  de2 = t.GetDelunayEdgeCW(p);
-  de3 = ot.GetDelunayEdgeCCW(op);
-  de4 = ot.GetDelunayEdgeCW(op);
-
-  t.Legalize(p, op);
-  ot.Legalize(op, p);
-
-  // Remap delaunay_edge
-  ot.SetDelunayEdgeCCW(p, de1);
-  t.SetDelunayEdgeCW(p, de2);
-  t.SetDelunayEdgeCCW(op, de3);
-  ot.SetDelunayEdgeCW(op, de4);
-
-  // Remap constrained_edge
-  ot.SetConstrainedEdgeCCW(p, ce1);
-  t.SetConstrainedEdgeCW(p, ce2);
-  t.SetConstrainedEdgeCCW(op, ce3);
-  ot.SetConstrainedEdgeCW(op, ce4);
-
-  // Remap neighbors
-  // XXX: might optimize the markNeighbor by keeping track of
-  //      what side should be assigned to what neighbor after the
-  //      rotation. Now mark neighbor does lots of testing to find
-  //      the right side.
-  t.ClearNeighbors();
-  ot.ClearNeighbors();
-  if (n1) ot.MarkNeighbor(*n1);
-  if (n2) t.MarkNeighbor(*n2);
-  if (n3) t.MarkNeighbor(*n3);
-  if (n4) ot.MarkNeighbor(*n4);
-  t.MarkNeighbor(ot);
-}
-
-void Sweep::FillBasin(SweepContext& tcx, Node& node)
-{
-  if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) {
-    tcx.basin.left_node = node.next->next;
-  } else {
-    tcx.basin.left_node = node.next;
-  }
-
-  // Find the bottom and right node
-  tcx.basin.bottom_node = tcx.basin.left_node;
-  while (tcx.basin.bottom_node->next
-         && tcx.basin.bottom_node->point->y >= tcx.basin.bottom_node->next->point->y) {
-    tcx.basin.bottom_node = tcx.basin.bottom_node->next;
-  }
-  if (tcx.basin.bottom_node == tcx.basin.left_node) {
-    // No valid basin
-    return;
-  }
-
-  tcx.basin.right_node = tcx.basin.bottom_node;
-  while (tcx.basin.right_node->next
-         && tcx.basin.right_node->point->y < tcx.basin.right_node->next->point->y) {
-    tcx.basin.right_node = tcx.basin.right_node->next;
-  }
-  if (tcx.basin.right_node == tcx.basin.bottom_node) {
-    // No valid basins
-    return;
-  }
-
-  tcx.basin.width = tcx.basin.right_node->point->x - tcx.basin.left_node->point->x;
-  tcx.basin.left_highest = tcx.basin.left_node->point->y > tcx.basin.right_node->point->y;
-
-  FillBasinReq(tcx, tcx.basin.bottom_node);
-}
-
-void Sweep::FillBasinReq(SweepContext& tcx, Node* node)
-{
-  // if shallow stop filling
-  if (IsShallow(tcx, *node)) {
-    return;
-  }
-
-  Fill(tcx, *node);
-
-  if (node->prev == tcx.basin.left_node && node->next == tcx.basin.right_node) {
-    return;
-  } else if (node->prev == tcx.basin.left_node) {
-    Orientation o = Orient2d(*node->point, *node->next->point, *node->next->next->point);
-    if (o == CW) {
-      return;
-    }
-    node = node->next;
-  } else if (node->next == tcx.basin.right_node) {
-    Orientation o = Orient2d(*node->point, *node->prev->point, *node->prev->prev->point);
-    if (o == CCW) {
-      return;
-    }
-    node = node->prev;
-  } else {
-    // Continue with the neighbor node with lowest Y value
-    if (node->prev->point->y < node->next->point->y) {
-      node = node->prev;
-    } else {
-      node = node->next;
-    }
-  }
-
-  FillBasinReq(tcx, node);
-}
-
-bool Sweep::IsShallow(SweepContext& tcx, Node& node)
-{
-  double height;
-
-  if (tcx.basin.left_highest) {
-    height = tcx.basin.left_node->point->y - node.point->y;
-  } else {
-    height = tcx.basin.right_node->point->y - node.point->y;
-  }
-
-  // if shallow stop filling
-  if (tcx.basin.width > height) {
-    return true;
-  }
-  return false;
-}
-
-void Sweep::FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node)
-{
-  if (tcx.edge_event.right) {
-    FillRightAboveEdgeEvent(tcx, edge, node);
-  } else {
-    FillLeftAboveEdgeEvent(tcx, edge, node);
-  }
-}
-
-void Sweep::FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node)
-{
-  while (node->next->point->x < edge->p->x) {
-    // Check if next node is below the edge
-    if (Orient2d(*edge->q, *node->next->point, *edge->p) == CCW) {
-      FillRightBelowEdgeEvent(tcx, edge, *node);
-    } else {
-      node = node->next;
-    }
-  }
-}
-
-void Sweep::FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  if (node.point->x < edge->p->x) {
-    if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) {
-      // Concave
-      FillRightConcaveEdgeEvent(tcx, edge, node);
-    } else{
-      // Convex
-      FillRightConvexEdgeEvent(tcx, edge, node);
-      // Retry this one
-      FillRightBelowEdgeEvent(tcx, edge, node);
-    }
-  }
-}
-
-void Sweep::FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  Fill(tcx, *node.next);
-  if (node.next->point != edge->p) {
-    // Next above or below edge?
-    if (Orient2d(*edge->q, *node.next->point, *edge->p) == CCW) {
-      // Below
-      if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) {
-        // Next is concave
-        FillRightConcaveEdgeEvent(tcx, edge, node);
-      } else {
-        // Next is convex
-      }
-    }
-  }
-
-}
-
-void Sweep::FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  // Next concave or convex?
-  if (Orient2d(*node.next->point, *node.next->next->point, *node.next->next->next->point) == CCW) {
-    // Concave
-    FillRightConcaveEdgeEvent(tcx, edge, *node.next);
-  } else{
-    // Convex
-    // Next above or below edge?
-    if (Orient2d(*edge->q, *node.next->next->point, *edge->p) == CCW) {
-      // Below
-      FillRightConvexEdgeEvent(tcx, edge, *node.next);
-    } else{
-      // Above
-    }
-  }
-}
-
-void Sweep::FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node)
-{
-  while (node->prev->point->x > edge->p->x) {
-    // Check if next node is below the edge
-    if (Orient2d(*edge->q, *node->prev->point, *edge->p) == CW) {
-      FillLeftBelowEdgeEvent(tcx, edge, *node);
-    } else {
-      node = node->prev;
-    }
-  }
-}
-
-void Sweep::FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  if (node.point->x > edge->p->x) {
-    if (Orient2d(*node.point, *node.prev->point, *node.prev->prev->point) == CW) {
-      // Concave
-      FillLeftConcaveEdgeEvent(tcx, edge, node);
-    } else {
-      // Convex
-      FillLeftConvexEdgeEvent(tcx, edge, node);
-      // Retry this one
-      FillLeftBelowEdgeEvent(tcx, edge, node);
-    }
-  }
-}
-
-void Sweep::FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  // Next concave or convex?
-  if (Orient2d(*node.prev->point, *node.prev->prev->point, *node.prev->prev->prev->point) == CW) {
-    // Concave
-    FillLeftConcaveEdgeEvent(tcx, edge, *node.prev);
-  } else{
-    // Convex
-    // Next above or below edge?
-    if (Orient2d(*edge->q, *node.prev->prev->point, *edge->p) == CW) {
-      // Below
-      FillLeftConvexEdgeEvent(tcx, edge, *node.prev);
-    } else{
-      // Above
-    }
-  }
-}
-
-void Sweep::FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node)
-{
-  Fill(tcx, *node.prev);
-  if (node.prev->point != edge->p) {
-    // Next above or below edge?
-    if (Orient2d(*edge->q, *node.prev->point, *edge->p) == CW) {
-      // Below
-      if (Orient2d(*node.point, *node.prev->point, *node.prev->prev->point) == CW) {
-        // Next is concave
-        FillLeftConcaveEdgeEvent(tcx, edge, node);
-      } else{
-        // Next is convex
-      }
-    }
-  }
-
-}
-
-void Sweep::FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p)
-{
-  Triangle* ot = t->NeighborAcross(p);
-  Point& op = *ot->OppositePoint(*t, p);
-
-  if (ot == nullptr) {
-    throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  }
-
-  if (InScanArea(p, *t->PointCCW(p), *t->PointCW(p), op)) {
-    // Lets rotate shared edge one vertex CW
-    RotateTrianglePair(*t, p, *ot, op);
-    tcx.MapTriangleToNodes(*t);
-    tcx.MapTriangleToNodes(*ot);
-
-    if (p == eq && op == ep) {
-      if (eq == *tcx.edge_event.constrained_edge->q && ep == *tcx.edge_event.constrained_edge->p) {
-        t->MarkConstrainedEdge(&ep, &eq);
-        ot->MarkConstrainedEdge(&ep, &eq);
-        Legalize(tcx, *t);
-        Legalize(tcx, *ot);
-      } else {
-        // XXX: I think one of the triangles should be legalized here?
-      }
-    } else {
-      Orientation o = Orient2d(eq, op, ep);
-      t = &NextFlipTriangle(tcx, (int)o, *t, *ot, p, op);
-      FlipEdgeEvent(tcx, ep, eq, t, p);
-    }
-  } else {
-    Point& newP = NextFlipPoint(ep, eq, *ot, op);
-    FlipScanEdgeEvent(tcx, ep, eq, *t, *ot, newP);
-    EdgeEvent(tcx, ep, eq, t, p);
-  }
-}
-
-Triangle& Sweep::NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op)
-{
-  if (o == CCW) {
-    // ot is not crossing edge after flip
-    int edge_index = ot.EdgeIndex(&p, &op);
-
-    if(edge_index < 0)
-      throw std::runtime_error("Edge not found in the triangle");
-
-    ot.delaunay_edge[edge_index] = true;
-    Legalize(tcx, ot);
-    ot.ClearDelunayEdges();
-    return t;
-  }
-
-  // t is not crossing edge after flip
-  int edge_index = t.EdgeIndex(&p, &op);
-
-  if(edge_index < 0)
-    throw std::runtime_error("Edge not found in the triangle");
-
-  t.delaunay_edge[edge_index] = true;
-  Legalize(tcx, t);
-  t.ClearDelunayEdges();
-  return ot;
-}
-
-Point& Sweep::NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op)
-{
-  Orientation o2d = Orient2d(eq, op, ep);
-  if (o2d == CW) {
-    // Right
-    return *ot.PointCCW(op);
-  } else if (o2d == CCW) {
-    // Left
-    return *ot.PointCW(op);
-  } else{
-    throw std::runtime_error("Polygon contains overlapping hole vertices.");
-    return ep;     // Arbitrary return val -- fixes warning
-  }
-}
-
-void Sweep::FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle,
-                              Triangle& t, Point& p)
-{
-  Triangle* ot = t.NeighborAcross(p);
-  Point& op = *ot->OppositePoint(t, p);
-
-  if (ot == NULL) {
-      throw std::runtime_error("Polygon contains overlapping hole vertices.");
-  }
-
-  if (InScanArea(eq, *flip_triangle.PointCCW(eq), *flip_triangle.PointCW(eq), op)) {
-    // flip with new edge op->eq
-    FlipEdgeEvent(tcx, eq, op, ot, op);
-    // TODO: Actually I just figured out that it should be possible to
-    //       improve this by getting the next ot and op before the the above
-    //       flip and continue the flipScanEdgeEvent here
-    // set new ot and op here and loop back to inScanArea test
-    // also need to set a new flip_triangle first
-    // Turns out at first glance that this is somewhat complicated
-    // so it will have to wait.
-  } else{
-    Point& newP = NextFlipPoint(ep, eq, *ot, op);
-    FlipScanEdgeEvent(tcx, ep, eq, flip_triangle, *ot, newP);
-  }
-}
-
-Sweep::~Sweep() {
-
-    // Clean up memory
-    for(unsigned i = 0; i < nodes_.size(); i++) {
-        delete nodes_[i];
-    }
-
-}
-
-}
diff --git a/polygon/poly2tri/sweep/sweep.h b/polygon/poly2tri/sweep/sweep.h
deleted file mode 100644
index f62c4cc..0000000
--- a/polygon/poly2tri/sweep/sweep.h
+++ /dev/null
@@ -1,285 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-/**
- * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and
- * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation',
- * International Journal of Geographical Information Science
- *
- * "FlipScan" Constrained Edge Algorithm invented by Thomas �hl�n, [e-mail]
- */
-
-#ifndef SWEEP_H
-#define SWEEP_H
-
-#include <vector>
-
-namespace p2t {
-
-class SweepContext;
-struct Node;
-struct Point;
-struct Edge;
-class Triangle;
-
-class Sweep 
-{
-public:
-
-  /**
-   * Triangulate
-   * 
-   * @param tcx
-   */
-  void Triangulate(SweepContext& tcx);
-  
-  /**
-   * Destructor - clean up memory
-   */
-  ~Sweep();
-
-private:
-
-  /**
-   * Start sweeping the Y-sorted point set from bottom to top
-   * 
-   * @param tcx
-   */
-  void SweepPoints(SweepContext& tcx);
-
-  /**
-   * Find closes node to the left of the new point and
-   * create a new triangle. If needed new holes and basins
-   * will be filled to.
-   *
-   * @param tcx
-   * @param point
-   * @return
-   */
-  Node& PointEvent(SweepContext& tcx, Point& point);
-
-   /**
-     * 
-     * 
-     * @param tcx
-     * @param edge
-     * @param node
-     */
-  void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
-
-  void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point);
-
-  /**
-   * Creates a new front triangle and legalize it
-   * 
-   * @param tcx
-   * @param point
-   * @param node
-   * @return
-   */
-  Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node);
-
-  /**
-   * Adds a triangle to the advancing front to fill a hole.
-   * @param tcx
-   * @param node - middle node, that is the bottom of the hole
-   */
-  void Fill(SweepContext& tcx, Node& node);
-
-  /**
-   * Returns true if triangle was legalized
-   */
-  bool Legalize(SweepContext& tcx, Triangle& t);
-
-  /**
-   * <b>Requirement</b>:<br>
-   * 1. a,b and c form a triangle.<br>
-   * 2. a and d is know to be on opposite side of bc<br>
-   * <pre>
-   *                a
-   *                +
-   *               / \
-   *              /   \
-   *            b/     \c
-   *            +-------+
-   *           /    d    \
-   *          /           \
-   * </pre>
-   * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
-   *  a,b and c<br>
-   *  d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
-   *  This preknowledge gives us a way to optimize the incircle test
-   * @param a - triangle point, opposite d
-   * @param b - triangle point
-   * @param c - triangle point
-   * @param d - point opposite a
-   * @return true if d is inside circle, false if on circle edge
-   */
-  bool Incircle(Point& pa, Point& pb, Point& pc, Point& pd);
-
-  /**
-   * Rotates a triangle pair one vertex CW
-   *<pre>
-   *       n2                    n2
-   *  P +-----+             P +-----+
-   *    | t  /|               |\  t |
-   *    |   / |               | \   |
-   *  n1|  /  |n3           n1|  \  |n3
-   *    | /   |    after CW   |   \ |
-   *    |/ oT |               | oT \|
-   *    +-----+ oP            +-----+
-   *       n4                    n4
-   * </pre>
-   */
-  void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op);
-
-  /**
-   * Fills holes in the Advancing Front
-   *
-   *
-   * @param tcx
-   * @param n
-   */
-  void FillAdvancingFront(SweepContext& tcx, Node& n);
-  
-  // Decision-making about when to Fill hole. 
-  // Contributed by ToolmakerSteve2
-  bool LargeHole_DontFill(Node* node);
-  bool AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb);
-  bool AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb);
-  double Angle(Point& origin, Point& pa, Point& pb);
-
-  /**
-   *
-   * @param node - middle node
-   * @return the angle between 3 front nodes
-   */
-  double HoleAngle(Node& node);
-
-  /**
-   * The basin angle is decided against the horizontal line [1,0]
-   */
-  double BasinAngle(Node& node);
-
-  /**
-   * Fills a basin that has formed on the Advancing Front to the right
-   * of given node.<br>
-   * First we decide a left,bottom and right node that forms the
-   * boundaries of the basin. Then we do a reqursive fill.
-   *
-   * @param tcx
-   * @param node - starting node, this or next node will be left node
-   */
-  void FillBasin(SweepContext& tcx, Node& node);
-
-  /**
-   * Recursive algorithm to fill a Basin with triangles
-   *
-   * @param tcx
-   * @param node - bottom_node
-   * @param cnt - counter used to alternate on even and odd numbers
-   */
-  void FillBasinReq(SweepContext& tcx, Node* node);
-
-  bool IsShallow(SweepContext& tcx, Node& node);
-
-  bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq);
-
-  void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
-
-  void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
-
-  void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
-
-  void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
-
-  void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p);
-
-  /**
-   * After a flip we have two triangles and know that only one will still be
-   * intersecting the edge. So decide which to contiune with and legalize the other
-   * 
-   * @param tcx
-   * @param o - should be the result of an orient2d( eq, op, ep )
-   * @param t - triangle 1
-   * @param ot - triangle 2
-   * @param p - a point shared by both triangles 
-   * @param op - another point shared by both triangles
-   * @return returns the triangle still intersecting the edge
-   */
-  Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle&  t, Triangle& ot, Point& p, Point& op);
-
-   /**
-     * When we need to traverse from one triangle to the next we need 
-     * the point in current triangle that is the opposite point to the next
-     * triangle. 
-     * 
-     * @param ep
-     * @param eq
-     * @param ot
-     * @param op
-     * @return
-     */
-  Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op);
-
-   /**
-     * Scan part of the FlipScan algorithm<br>
-     * When a triangle pair isn't flippable we will scan for the next 
-     * point that is inside the flip triangle scan area. When found 
-     * we generate a new flipEdgeEvent
-     * 
-     * @param tcx
-     * @param ep - last point on the edge we are traversing
-     * @param eq - first point on the edge we are traversing
-     * @param flipTriangle - the current triangle sharing the point eq with edge
-     * @param t
-     * @param p
-     */
-  void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p);
-
-  void FinalizationPolygon(SweepContext& tcx);
-
-  std::vector<Node*> nodes_;
-
-};
-
-}
-
-#endif
diff --git a/polygon/poly2tri/sweep/sweep_context.cc b/polygon/poly2tri/sweep/sweep_context.cc
deleted file mode 100644
index fe5f06b..0000000
--- a/polygon/poly2tri/sweep/sweep_context.cc
+++ /dev/null
@@ -1,217 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "sweep_context.h"
-#include <algorithm>
-#include <utility>
-#include "advancing_front.h"
-
-namespace p2t {
-
-SweepContext::SweepContext(std::vector<Point*> polyline) :
-  front_(0),
-  head_(0),
-  tail_(0),
-  af_head_(0),
-  af_middle_(0),
-  af_tail_(0)
-{
-  basin = Basin();
-  edge_event = EdgeEvent();
-
-  points_ = std::move( polyline );
-
-  InitEdges(points_);
-}
-
-void SweepContext::AddHole(std::vector<Point*> polyline)
-{
-  InitEdges(polyline);
-  for(unsigned int i = 0; i < polyline.size(); i++) {
-    points_.push_back(polyline[i]);
-  }
-}
-
-void SweepContext::AddPoint(Point* point) {
-  points_.push_back(point);
-}
-
-std::vector<Triangle*> SweepContext::GetTriangles()
-{
-  return triangles_;
-}
-
-std::list<Triangle*> SweepContext::GetMap()
-{
-  return map_;
-}
-
-void SweepContext::InitTriangulation()
-{
-  double xmax(points_[0]->x), xmin(points_[0]->x);
-  double ymax(points_[0]->y), ymin(points_[0]->y);
-
-  // Calculate bounds.
-  for (unsigned int i = 0; i < points_.size(); i++) {
-    Point& p = *points_[i];
-    if (p.x > xmax)
-      xmax = p.x;
-    if (p.x < xmin)
-      xmin = p.x;
-    if (p.y > ymax)
-      ymax = p.y;
-    if (p.y < ymin)
-      ymin = p.y;
-  }
-
-  double dx = kAlpha * (xmax - xmin);
-  double dy = kAlpha * (ymax - ymin);
-  head_ = new Point(xmax + dx, ymin - dy);
-  tail_ = new Point(xmin - dx, ymin - dy);
-
-  // Sort points along y-axis
-  std::sort(points_.begin(), points_.end(), cmp);
-
-}
-
-void SweepContext::InitEdges(std::vector<Point*> polyline)
-{
-  int num_points = polyline.size();
-  for (int i = 0; i < num_points; i++) {
-    int j = i < num_points - 1 ? i + 1 : 0;
-    edge_list.push_back(new Edge(*polyline[i], *polyline[j]));
-  }
-}
-
-Point* SweepContext::GetPoint(const int& index)
-{
-  return points_[index];
-}
-
-void SweepContext::AddToMap(Triangle* triangle)
-{
-  map_.push_back(triangle);
-}
-
-Node& SweepContext::LocateNode(Point& point)
-{
-  // TODO implement search tree
-  return *front_->LocateNode(point.x);
-}
-
-void SweepContext::CreateAdvancingFront(std::vector<Node*> nodes)
-{
-
-  (void) nodes;
-  // Initial triangle
-  Triangle* triangle = new Triangle(*points_[0], *tail_, *head_);
-
-  map_.push_back(triangle);
-
-  af_head_ = new Node(*triangle->GetPoint(1), *triangle);
-  af_middle_ = new Node(*triangle->GetPoint(0), *triangle);
-  af_tail_ = new Node(*triangle->GetPoint(2));
-  front_ = new AdvancingFront(*af_head_, *af_tail_);
-
-  // TODO: More intuitive if head is middles next and not previous?
-  //       so swap head and tail
-  af_head_->next = af_middle_;
-  af_middle_->next = af_tail_;
-  af_middle_->prev = af_head_;
-  af_tail_->prev = af_middle_;
-}
-
-void SweepContext::RemoveNode(Node* node)
-{
-  delete node;
-}
-
-void SweepContext::MapTriangleToNodes(Triangle& t)
-{
-  for (int i = 0; i < 3; i++) {
-    if (!t.GetNeighbor(i)) {
-      Node* n = front_->LocatePoint(t.PointCW(*t.GetPoint(i)));
-      if (n)
-        n->triangle = &t;
-    }
-  }
-}
-
-void SweepContext::RemoveFromMap(Triangle* triangle)
-{
-  map_.remove(triangle);
-}
-
-void SweepContext::MeshClean(Triangle& triangle)
-{
-  std::vector<Triangle *> triangles;
-  triangles.push_back(&triangle);
-
-  while(!triangles.empty()){
-	Triangle *t = triangles.back();
-	triangles.pop_back();
-
-    if (t != NULL && !t->IsInterior()) {
-      t->IsInterior(true);
-      triangles_.push_back(t);
-      for (int i = 0; i < 3; i++) {
-        if (!t->constrained_edge[i])
-          triangles.push_back(t->GetNeighbor(i));
-      }
-    }
-  }
-}
-
-SweepContext::~SweepContext()
-{
-
-    // Clean up memory
-
-    delete head_;
-    delete tail_;
-    delete front_;
-    delete af_head_;
-    delete af_middle_;
-    delete af_tail_;
-
-    typedef std::list<Triangle*> type_list;
-
-    for(type_list::iterator iter = map_.begin(); iter != map_.end(); ++iter) {
-        Triangle* ptr = *iter;
-        delete ptr;
-    }
-
-     for(unsigned int i = 0; i < edge_list.size(); i++) {
-        delete edge_list[i];
-    }
-
-}
-
-}
diff --git a/polygon/poly2tri/sweep/sweep_context.h b/polygon/poly2tri/sweep/sweep_context.h
deleted file mode 100644
index 1010c0e..0000000
--- a/polygon/poly2tri/sweep/sweep_context.h
+++ /dev/null
@@ -1,186 +0,0 @@
-/*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification,
- * are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright notice,
- *   this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright notice,
- *   this list of conditions and the following disclaimer in the documentation
- *   and/or other materials provided with the distribution.
- * * Neither the name of Poly2Tri nor the names of its contributors may be
- *   used to endorse or promote products derived from this software without specific
- *   prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef SWEEP_CONTEXT_H
-#define SWEEP_CONTEXT_H
-
-#include <list>
-#include <vector>
-#include <cstddef>
-
-namespace p2t {
-
-// Inital triangle factor, seed triangle will extend 30% of
-// PointSet width to both left and right.
-const double kAlpha = 0.3;
-
-struct Point;
-class Triangle;
-struct Node;
-struct Edge;
-class AdvancingFront;
-
-class SweepContext {
-public:
-
-/// Constructor
-SweepContext(std::vector<Point*> polyline);
-/// Destructor
-~SweepContext();
-
-void set_head(Point* p1);
-
-Point* head();
-
-void set_tail(Point* p1);
-
-Point* tail();
-
-int point_count();
-
-Node& LocateNode(Point& point);
-
-void RemoveNode(Node* node);
-
-void CreateAdvancingFront(std::vector<Node*> nodes);
-
-/// Try to map a node to all sides of this triangle that don't have a neighbor
-void MapTriangleToNodes(Triangle& t);
-
-void AddToMap(Triangle* triangle);
-
-Point* GetPoint(const int& index);
-
-Point* GetPoints();
-
-void RemoveFromMap(Triangle* triangle);
-
-void AddHole(std::vector<Point*> polyline);
-
-void AddPoint(Point* point);
-
-AdvancingFront* front();
-
-void MeshClean(Triangle& triangle);
-
-std::vector<Triangle*> GetTriangles();
-std::list<Triangle*> GetMap();
-
-std::vector<Edge*> edge_list;
-
-struct Basin {
-  Node* left_node;
-  Node* bottom_node;
-  Node* right_node;
-  double width;
-  bool left_highest;
-
-  Basin() : left_node(NULL), bottom_node(NULL), right_node(NULL), width(0.0), left_highest(false)
-  {
-  }
-
-  void Clear()
-  {
-    left_node = NULL;
-    bottom_node = NULL;
-    right_node = NULL;
-    width = 0.0;
-    left_highest = false;
-  }
-};
-
-struct EdgeEvent {
-  Edge* constrained_edge;
-  bool right;
-
-  EdgeEvent() : constrained_edge(NULL), right(false)
-  {
-  }
-};
-
-Basin basin;
-EdgeEvent edge_event;
-
-private:
-
-friend class Sweep;
-
-std::vector<Triangle*> triangles_;
-std::list<Triangle*> map_;
-std::vector<Point*> points_;
-
-// Advancing front
-AdvancingFront* front_;
-// head point used with advancing front
-Point* head_;
-// tail point used with advancing front
-Point* tail_;
-
-Node *af_head_, *af_middle_, *af_tail_;
-
-void InitTriangulation();
-void InitEdges(std::vector<Point*> polyline);
-
-};
-
-inline AdvancingFront* SweepContext::front()
-{
-  return front_;
-}
-
-inline int SweepContext::point_count()
-{
-  return points_.size();
-}
-
-inline void SweepContext::set_head(Point* p1)
-{
-  head_ = p1;
-}
-
-inline Point* SweepContext::head()
-{
-  return head_;
-}
-
-inline void SweepContext::set_tail(Point* p1)
-{
-  tail_ = p1;
-}
-
-inline Point* SweepContext::tail()
-{
-  return tail_;
-}
-
-}
-
-#endif