Added secondary files

7 files changed, 2962 insertions, 0 deletions

diff --git a/common/geometry/hetriang.cpp b/common/geometry/hetriang.cpp
new file mode 100644
index 0000000..e5cf26c
--- /dev/null
+++ b/common/geometry/hetriang.cpp
@@ -0,0 +1,739 @@
+/*
+ * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
+ * Applied Mathematics, Norway.
+ * Copyright (C) 2013 CERN
+ * @author Maciej Suminski <maciej.suminski@cern.ch>
+ *
+ * Contact information: E-mail: tor.dokken@sintef.no
+ * SINTEF ICT, Department of Applied Mathematics,
+ * P.O. Box 124 Blindern,
+ * 0314 Oslo, Norway.
+ *
+ * This file is part of TTL.
+ *
+ * TTL is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * TTL 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 Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public
+ * License along with TTL. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * In accordance with Section 7(b) of the GNU Affero General Public
+ * License, a covered work must retain the producer line in every data
+ * file that is created or manipulated using TTL.
+ *
+ * Other Usage
+ * You can be released from the requirements of the license by purchasing
+ * a commercial license. Buying such a license is mandatory as soon as you
+ * develop commercial activities involving the TTL library without
+ * disclosing the source code of your own applications.
+ *
+ * This file may be used in accordance with the terms contained in a
+ * written agreement between you and SINTEF ICT.
+ */
+
+#include <ttl/halfedge/hetriang.h>
+#include <ttl/halfedge/hetraits.h>
+#include <ttl/ttl.h>
+#include <algorithm>
+#include <fstream>
+#include <limits>
+#include <boost/foreach.hpp>
+#include <boost/make_shared.hpp>
+#include <class_board_connected_item.h>
+
+using namespace hed;
+
+#ifdef TTL_USE_NODE_ID
+  int NODE::id_count = 0;
+#endif
+
+
+void NODE::updateLayers()
+{
+    assert( m_layers.none() );
+
+    BOOST_FOREACH( const BOARD_CONNECTED_ITEM* item, m_parents )
+        m_layers |= item->GetLayerSet();
+}
+
+
+//#define DEBUG_HE
+#ifdef DEBUG_HE
+#include <iostream>
+static void errorAndExit( char* aMessage )
+{
+    cout << "\n!!! ERROR: "<< aMessage << " !!!\n" << endl;
+    exit( -1 );
+}
+#endif
+
+
+static EDGE_PTR getLeadingEdgeInTriangle( const EDGE_PTR& aEdge )
+{
+    EDGE_PTR edge = aEdge;
+
+    // Code: 3EF (assumes triangle)
+    if( !edge->IsLeadingEdge() )
+    {
+        edge = edge->GetNextEdgeInFace();
+
+        if( !edge->IsLeadingEdge() )
+            edge = edge->GetNextEdgeInFace();
+    }
+
+    if( !edge->IsLeadingEdge() )
+    {
+        return EDGE_PTR();
+    }
+
+    return edge;
+}
+
+
+static void getLimits( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast,
+                       int& aXmin, int& aYmin, int& aXmax, int& aYmax)
+{
+    aXmin = aYmin = std::numeric_limits<int>::min();
+    aXmax = aYmax = std::numeric_limits<int>::max();
+
+    NODES_CONTAINER::iterator it;
+
+    for( it = aFirst; it != aLast; ++it )
+    {
+        aXmin = std::min( aXmin, ( *it )->GetX() );
+        aYmin = std::min( aYmin, ( *it )->GetY() );
+        aXmax = std::max( aXmax, ( *it )->GetX() );
+        aYmax = std::max( aYmax, ( *it )->GetY() );
+    }
+}
+
+
+EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
+                                                  NODES_CONTAINER::iterator aLast)
+{
+    int xmin, ymin, xmax, ymax;
+    getLimits( aFirst, aLast, xmin, ymin, xmax, ymax );
+
+    // Add 10% of range:
+    double fac = 10.0;
+    double dx = ( xmax - xmin ) / fac;
+    double dy = ( ymax - ymin ) / fac;
+
+    NODE_PTR n1 = boost::make_shared<NODE>( xmin - dx, ymin - dy );
+    NODE_PTR n2 = boost::make_shared<NODE>( xmax + dx, ymin - dy );
+    NODE_PTR n3 = boost::make_shared<NODE>( xmax + dx, ymax + dy );
+    NODE_PTR n4 = boost::make_shared<NODE>( xmin - dx, ymax + dy );
+
+    // diagonal
+    EDGE_PTR e1d = boost::make_shared<EDGE>();
+    EDGE_PTR e2d = boost::make_shared<EDGE>();
+
+    // lower triangle
+    EDGE_PTR e11 = boost::make_shared<EDGE>();
+    EDGE_PTR e12 = boost::make_shared<EDGE>();
+
+    // upper triangle
+    EDGE_PTR e21 = boost::make_shared<EDGE>();
+    EDGE_PTR e22 = boost::make_shared<EDGE>();
+
+    // lower triangle
+    e1d->SetSourceNode( n3 );
+    e1d->SetNextEdgeInFace( e11 );
+    e1d->SetTwinEdge( e2d );
+    addLeadingEdge( e1d );
+
+    e11->SetSourceNode( n1 );
+    e11->SetNextEdgeInFace( e12 );
+
+    e12->SetSourceNode( n2 );
+    e12->SetNextEdgeInFace( e1d );
+
+    // upper triangle
+    e2d->SetSourceNode( n1 );
+    e2d->SetNextEdgeInFace( e21 );
+    e2d->SetTwinEdge( e1d );
+    addLeadingEdge( e2d );
+
+    e21->SetSourceNode( n3 );
+    e21->SetNextEdgeInFace( e22 );
+
+    e22->SetSourceNode( n4 );
+    e22->SetNextEdgeInFace( e2d );
+
+    return e11;
+}
+
+
+TRIANGULATION::TRIANGULATION()
+{
+    m_helper = new ttl::TRIANGULATION_HELPER( *this );
+}
+
+
+TRIANGULATION::TRIANGULATION( const TRIANGULATION& aTriangulation )
+{
+    m_helper = 0;   // make coverity and static analysers quiet.
+    // Triangulation: Copy constructor not present
+    assert( false );
+}
+
+
+TRIANGULATION::~TRIANGULATION()
+{
+    cleanAll();
+    delete m_helper;
+}
+
+
+void TRIANGULATION::CreateDelaunay( NODES_CONTAINER::iterator aFirst,
+                                    NODES_CONTAINER::iterator aLast )
+{
+    cleanAll();
+
+    EDGE_PTR bedge = InitTwoEnclosingTriangles( aFirst, aLast );
+    DART dc( bedge );
+
+    DART d_iter = dc;
+
+    NODES_CONTAINER::iterator it;
+    for( it = aFirst; it != aLast; ++it )
+    {
+        m_helper->InsertNode<TTLtraits>( d_iter, *it );
+    }
+
+    // In general (e.g. for the triangle based data structure), the initial dart
+    // may have been changed.
+    // It is the users responsibility to get a valid boundary dart here.
+    // The half-edge data structure preserves the initial dart.
+    // (A dart at the boundary can also be found by trying to locate a
+    // triangle "outside" the triangulation.)
+
+    // Assumes rectangular domain
+    m_helper->RemoveRectangularBoundary<TTLtraits>( dc );
+}
+
+
+void TRIANGULATION::RemoveTriangle( EDGE_PTR& aEdge )
+{
+  EDGE_PTR e1 = getLeadingEdgeInTriangle( aEdge );
+
+#ifdef DEBUG_HE
+    if( !e1 )
+    errorAndExit( "Triangulation::removeTriangle: could not find leading aEdge" );
+#endif
+
+    removeLeadingEdgeFromList( e1 );
+    // cout << "No leading edges = " << leadingEdges_.size() << endl;
+    // Remove the triangle
+    EDGE_PTR e2( e1->GetNextEdgeInFace() );
+    EDGE_PTR e3( e2->GetNextEdgeInFace() );
+
+    e1->Clear();
+    e2->Clear();
+    e3->Clear();
+}
+
+
+void TRIANGULATION::ReverseSplitTriangle( EDGE_PTR& aEdge )
+{
+    // Reverse operation of splitTriangle
+    EDGE_PTR e1( aEdge->GetNextEdgeInFace() );
+    EDGE_PTR le( getLeadingEdgeInTriangle( e1 ) );
+#ifdef DEBUG_HE
+    if (!le)
+    errorAndExit("Triangulation::removeTriangle: could not find leading edge");
+#endif
+    removeLeadingEdgeFromList( le );
+
+    EDGE_PTR e2( e1->GetNextEdgeInFace()->GetTwinEdge()->GetNextEdgeInFace() );
+    le = getLeadingEdgeInTriangle( e2 );
+#ifdef DEBUG_HE
+    if (!le)
+    errorAndExit("Triangulation::removeTriangle: could not find leading edge");
+#endif
+    removeLeadingEdgeFromList( le );
+
+    EDGE_PTR e3( aEdge->GetTwinEdge()->GetNextEdgeInFace()->GetNextEdgeInFace() );
+    le = getLeadingEdgeInTriangle( e3 );
+#ifdef DEBUG_HE
+    if (!le)
+    errorAndExit("Triangulation::removeTriangle: could not find leading edge");
+#endif
+    removeLeadingEdgeFromList( le );
+
+    // The three triangles at the node have now been removed
+    // from the triangulation, but the arcs have not been deleted.
+    // Next delete the 6 half edges radiating from the node
+    // The node is maintained by handle and need not be deleted explicitly
+    EDGE_PTR estar = aEdge;
+    EDGE_PTR enext = estar->GetTwinEdge()->GetNextEdgeInFace();
+    estar->GetTwinEdge()->Clear();
+    estar->Clear();
+
+    estar = enext;
+    enext = estar->GetTwinEdge()->GetNextEdgeInFace();
+    estar->GetTwinEdge()->Clear();
+    estar->Clear();
+
+    enext->GetTwinEdge()->Clear();
+    enext->Clear();
+
+    // Create the new triangle
+    e1->SetNextEdgeInFace( e2 );
+    e2->SetNextEdgeInFace( e3 );
+    e3->SetNextEdgeInFace( e1 );
+    addLeadingEdge( e1 );
+}
+
+
+DART TRIANGULATION::CreateDart()
+{
+  // Return an arbitrary CCW dart
+    return DART( *m_leadingEdges.begin() );
+}
+
+
+bool TRIANGULATION::removeLeadingEdgeFromList( EDGE_PTR& aLeadingEdge )
+{
+    // Remove the edge from the list of leading edges,
+    // but don't delete it.
+    // Also set flag for leading edge to false.
+    // Must search from start of list. Since edges are added to the
+    // start of the list during triangulation, this operation will
+    // normally be fast (when used in the triangulation algorithm)
+    std::list<EDGE_PTR>::iterator it;
+    for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        if( edge == aLeadingEdge )
+        {
+            edge->SetAsLeadingEdge( false );
+            it = m_leadingEdges.erase( it );
+
+            return true;
+        }
+    }
+
+    return false;
+}
+
+
+void TRIANGULATION::cleanAll()
+{
+    BOOST_FOREACH( EDGE_PTR& edge, m_leadingEdges )
+        edge->SetNextEdgeInFace( EDGE_PTR() );
+}
+
+
+void TRIANGULATION::swapEdge( DART& aDart )
+{
+    SwapEdge( aDart.GetEdge() );
+}
+
+
+void TRIANGULATION::splitTriangle( DART& aDart, const NODE_PTR& aPoint )
+{
+    EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
+    aDart.Init( edge );
+}
+
+
+void TRIANGULATION::reverseSplitTriangle( DART& aDart )
+{
+    ReverseSplitTriangle( aDart.GetEdge() );
+}
+
+
+void TRIANGULATION::removeBoundaryTriangle( DART& aDart )
+{
+    RemoveTriangle( aDart.GetEdge() );
+}
+
+
+#ifdef TTL_USE_NODE_FLAG
+void TRIANGULATION::FlagNodes( bool aFlag ) const
+{
+    std::list<EDGE_PTR>::const_iterator it;
+    for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        for( int i = 0; i < 3; ++i )
+        {
+            edge->GetSourceNode()->SetFlag( aFlag );
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+}
+
+
+std::list<NODE_PTR>* TRIANGULATION::GetNodes() const
+{
+    FlagNodes( false );
+    std::list<NODE_PTR>* nodeList = new std::list<NODE_PTR>;
+    std::list<EDGE_PTR>::const_iterator it;
+
+    for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        for( int i = 0; i < 3; ++i )
+        {
+            const NODE_PTR& node = edge->GetSourceNode();
+
+            if( node->GetFlag() == false )
+            {
+                nodeList->push_back( node );
+                node->SetFlag( true );
+            }
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+    return nodeList;
+}
+#endif
+
+
+std::list<EDGE_PTR>* TRIANGULATION::GetEdges( bool aSkipBoundaryEdges ) const
+{
+    // collect all arcs (one half edge for each arc)
+    // (boundary edges are also collected).
+    std::list<EDGE_PTR>::const_iterator it;
+    std::list<EDGE_PTR>* elist = new std::list<EDGE_PTR>;
+
+    for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+        for( int i = 0; i < 3; ++i )
+        {
+            EDGE_PTR twinedge = edge->GetTwinEdge();
+            // only one of the half-edges
+
+            if( ( !twinedge && !aSkipBoundaryEdges )
+                    || ( twinedge && ( (size_t) edge.get() > (size_t) twinedge.get() ) ) )
+                elist->push_front( edge );
+
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+
+    return elist;
+}
+
+
+EDGE_PTR TRIANGULATION::SplitTriangle( EDGE_PTR& aEdge, const NODE_PTR& aPoint )
+{
+    // Add a node by just splitting a triangle into three triangles
+    // Assumes the half aEdge is located in the triangle
+    // Returns a half aEdge with source node as the new node
+
+    // e#_n are new edges
+    // e# are existing edges
+    // e#_n and e##_n are new twin edges
+    // e##_n are edges incident to the new node
+
+    // Add the node to the structure
+    //NODE_PTR new_node(new Node(x,y,z));
+
+    NODE_PTR n1( aEdge->GetSourceNode() );
+    EDGE_PTR e1( aEdge );
+
+    EDGE_PTR e2( aEdge->GetNextEdgeInFace() );
+    NODE_PTR n2( e2->GetSourceNode() );
+
+    EDGE_PTR e3( e2->GetNextEdgeInFace() );
+    NODE_PTR n3( e3->GetSourceNode() );
+
+    EDGE_PTR e1_n = boost::make_shared<EDGE>();
+    EDGE_PTR e11_n = boost::make_shared<EDGE>();
+    EDGE_PTR e2_n = boost::make_shared<EDGE>();
+    EDGE_PTR e22_n = boost::make_shared<EDGE>();
+    EDGE_PTR e3_n = boost::make_shared<EDGE>();
+    EDGE_PTR e33_n = boost::make_shared<EDGE>();
+
+    e1_n->SetSourceNode( n1 );
+    e11_n->SetSourceNode( aPoint );
+    e2_n->SetSourceNode( n2 );
+    e22_n->SetSourceNode( aPoint );
+    e3_n->SetSourceNode( n3 );
+    e33_n->SetSourceNode( aPoint );
+
+    e1_n->SetTwinEdge( e11_n );
+    e11_n->SetTwinEdge( e1_n );
+    e2_n->SetTwinEdge( e22_n );
+    e22_n->SetTwinEdge( e2_n );
+    e3_n->SetTwinEdge( e33_n );
+    e33_n->SetTwinEdge( e3_n );
+
+    e1_n->SetNextEdgeInFace( e33_n );
+    e2_n->SetNextEdgeInFace( e11_n );
+    e3_n->SetNextEdgeInFace( e22_n );
+
+    e11_n->SetNextEdgeInFace( e1 );
+    e22_n->SetNextEdgeInFace( e2 );
+    e33_n->SetNextEdgeInFace( e3 );
+
+    // and update old's next aEdge
+    e1->SetNextEdgeInFace( e2_n );
+    e2->SetNextEdgeInFace( e3_n );
+    e3->SetNextEdgeInFace( e1_n );
+
+    // add the three new leading edges,
+    // Must remove the old leading aEdge from the list.
+    // Use the field telling if an aEdge is a leading aEdge
+    // NOTE: Must search in the list!!!
+
+    if( e1->IsLeadingEdge() )
+        removeLeadingEdgeFromList( e1 );
+    else if( e2->IsLeadingEdge() )
+        removeLeadingEdgeFromList( e2 );
+    else if( e3->IsLeadingEdge() )
+        removeLeadingEdgeFromList( e3 );
+    else
+        assert( false );        // one of the edges should be leading
+
+    addLeadingEdge( e1_n );
+    addLeadingEdge( e2_n );
+    addLeadingEdge( e3_n );
+
+    // Return a half aEdge incident to the new node (with the new node as source node)
+
+    return e11_n;
+}
+
+
+void TRIANGULATION::SwapEdge( EDGE_PTR& aDiagonal )
+{
+    // Note that diagonal is both input and output and it is always
+    // kept in counterclockwise direction (this is not required by all
+    // functions in TriangulationHelper now)
+
+    // Swap by rotating counterclockwise
+    // Use the same objects - no deletion or new objects
+    EDGE_PTR eL( aDiagonal );
+    EDGE_PTR eR( eL->GetTwinEdge() );
+    EDGE_PTR eL_1( eL->GetNextEdgeInFace() );
+    EDGE_PTR eL_2( eL_1->GetNextEdgeInFace() );
+    EDGE_PTR eR_1( eR->GetNextEdgeInFace() );
+    EDGE_PTR eR_2( eR_1->GetNextEdgeInFace() );
+
+    // avoid node to be dereferenced to zero and deleted
+    NODE_PTR nR( eR_2->GetSourceNode() );
+    NODE_PTR nL( eL_2->GetSourceNode() );
+
+    eL->SetSourceNode( nR );
+    eR->SetSourceNode( nL );
+
+    // and now 6 1-sewings
+    eL->SetNextEdgeInFace( eL_2 );
+    eL_2->SetNextEdgeInFace( eR_1 );
+    eR_1->SetNextEdgeInFace( eL );
+
+    eR->SetNextEdgeInFace( eR_2 );
+    eR_2->SetNextEdgeInFace( eL_1 );
+    eL_1->SetNextEdgeInFace( eR );
+
+    if( eL->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eL );
+    else if( eL_1->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eL_1 );
+    else if( eL_2->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eL_2 );
+
+    if( eR->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eR );
+    else if( eR_1->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eR_1 );
+    else if( eR_2->IsLeadingEdge() )
+        removeLeadingEdgeFromList( eR_2 );
+
+    addLeadingEdge( eL );
+    addLeadingEdge( eR );
+}
+
+
+bool TRIANGULATION::CheckDelaunay() const
+{
+    // ???? outputs !!!!
+    // ofstream os("qweND.dat");
+    const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
+
+    std::list<EDGE_PTR>::const_iterator it;
+    bool ok = true;
+    int noNotDelaunay = 0;
+
+    for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        for( int i = 0; i < 3; ++i )
+        {
+            EDGE_PTR twinedge = edge->GetTwinEdge();
+
+            // only one of the half-edges
+            if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
+            {
+                DART dart( edge );
+                if( m_helper->SwapTestDelaunay<TTLtraits>( dart ) )
+                {
+                    noNotDelaunay++;
+
+                    //printEdge(dart,os); os << "\n";
+                    ok = false;
+                    //cout << "............. not Delaunay .... " << endl;
+                }
+            }
+
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+
+#ifdef DEBUG_HE
+    cout << "!!! Triangulation is NOT Delaunay: " << noNotDelaunay << " edges\n" << endl;
+#endif
+
+    return ok;
+}
+
+
+void TRIANGULATION::OptimizeDelaunay()
+{
+    // This function is also present in ttl where it is implemented
+    // generically.
+    // The implementation below is tailored for the half-edge data structure,
+    // and is thus more efficient
+
+    // Collect all interior edges (one half edge for each arc)
+    bool skip_boundary_edges = true;
+    std::list<EDGE_PTR>* elist = GetEdges( skip_boundary_edges );
+
+    // Assumes that elist has only one half-edge for each arc.
+    bool cycling_check = true;
+    bool optimal = false;
+    std::list<EDGE_PTR>::const_iterator it;
+
+    while( !optimal )
+    {
+        optimal = true;
+
+        for( it = elist->begin(); it != elist->end(); ++it )
+        {
+            EDGE_PTR edge = *it;
+
+            DART dart( edge );
+            // Constrained edges should not be swapped
+            if( m_helper->SwapTestDelaunay<TTLtraits>( dart, cycling_check ) )
+            {
+                optimal = false;
+                SwapEdge( edge );
+            }
+        }
+    }
+
+    delete elist;
+}
+
+
+EDGE_PTR TRIANGULATION::GetInteriorNode() const
+{
+    const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
+    std::list<EDGE_PTR>::const_iterator it;
+
+    for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        // multiple checks, but only until found
+        for( int i = 0; i < 3; ++i )
+        {
+            if( edge->GetTwinEdge() )
+            {
+                if( !m_helper->IsBoundaryNode( DART( edge ) ) )
+                    return edge;
+            }
+
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+
+    return EDGE_PTR(); // no boundary nodes
+}
+
+
+EDGE_PTR TRIANGULATION::GetBoundaryEdgeInTriangle( const EDGE_PTR& aEdge ) const
+{
+    EDGE_PTR edge = aEdge;
+
+    if( m_helper->IsBoundaryEdge( DART( edge ) ) )
+        return edge;
+
+    edge = edge->GetNextEdgeInFace();
+    if( m_helper->IsBoundaryEdge( DART( edge ) ) )
+        return edge;
+
+    edge = edge->GetNextEdgeInFace();
+    if( m_helper->IsBoundaryEdge( DART( edge ) ) )
+        return edge;
+
+    return EDGE_PTR();
+}
+
+
+EDGE_PTR TRIANGULATION::GetBoundaryEdge() const
+{
+    // Get an arbitrary (CCW) boundary edge
+    // If the triangulation is closed, NULL is returned
+    const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
+    std::list<EDGE_PTR>::const_iterator it;
+    EDGE_PTR edge;
+
+    for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
+    {
+        edge = GetBoundaryEdgeInTriangle( *it );
+
+        if( edge )
+            return edge;
+    }
+    return EDGE_PTR();
+}
+
+
+void TRIANGULATION::PrintEdges( std::ofstream& aOutput ) const
+{
+    // Print source node and target node for each edge face by face,
+    // but only one of the half-edges.
+    const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
+    std::list<EDGE_PTR>::const_iterator it;
+
+    for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
+    {
+        EDGE_PTR edge = *it;
+
+        for( int i = 0; i < 3; ++i )
+        {
+            EDGE_PTR twinedge = edge->GetTwinEdge();
+
+            // Print only one edge (the highest value of the pointer)
+            if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
+            {
+                // Print source node and target node
+                NODE_PTR node = edge->GetSourceNode();
+                aOutput << node->GetX() << " " << node->GetY() << std::endl;
+                node = edge->GetTargetNode();
+                aOutput << node->GetX() << " " << node->GetY() << std::endl;
+                aOutput << '\n'; // blank line
+            }
+
+            edge = edge->GetNextEdgeInFace();
+        }
+    }
+}
diff --git a/common/geometry/seg.cpp b/common/geometry/seg.cpp
new file mode 100644
index 0000000..f1796b6
--- /dev/null
+++ b/common/geometry/seg.cpp
@@ -0,0 +1,158 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2013 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * 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
+ */
+
+#include <geometry/seg.h>
+
+template <typename T>
+int sgn( T aVal )
+{
+    return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
+}
+
+
+bool SEG::PointCloserThan( const VECTOR2I& aP, int aDist ) const
+{
+    VECTOR2I d = B - A;
+    ecoord dist_sq = (ecoord) aDist * aDist;
+
+    SEG::ecoord l_squared = d.Dot( d );
+    SEG::ecoord t = d.Dot( aP - A );
+
+    if( t <= 0 || !l_squared )
+        return ( aP - A ).SquaredEuclideanNorm() < dist_sq;
+    else if( t >= l_squared )
+        return ( aP - B ).SquaredEuclideanNorm() < dist_sq;
+
+    int dxdy = abs( d.x ) - abs( d.y );
+
+    if( ( dxdy >= -1 && dxdy <= 1 ) || abs( d.x ) <= 1 || abs( d.y ) <= 1 )
+    {
+        int ca = -sgn( d.y );
+        int cb = sgn( d.x );
+        int cc = -ca * A.x - cb * A.y;
+
+        ecoord num = (ecoord) ca * aP.x + (ecoord) cb * aP.y + cc;
+        num *= num;
+
+        if( ca && cb )
+            num >>= 1;
+
+        if( num > ( dist_sq + 100 ) )
+            return false;
+
+        else if( num < ( dist_sq - 100 ) )
+            return true;
+    }
+
+    VECTOR2I nearest;
+    nearest.x = A.x + rescale( t, (ecoord) d.x, l_squared );
+    nearest.y = A.y + rescale( t, (ecoord) d.y, l_squared );
+
+    return ( nearest - aP ).SquaredEuclideanNorm() <= dist_sq;
+}
+
+
+SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
+{
+    // fixme: rather inefficient....
+    if( Intersect( aSeg ) )
+        return 0;
+
+    const VECTOR2I pts[4] =
+    {
+        aSeg.NearestPoint( A ) - A,
+        aSeg.NearestPoint( B ) - B,
+        NearestPoint( aSeg.A ) - aSeg.A,
+        NearestPoint( aSeg.B ) - aSeg.B
+    };
+
+    ecoord m = VECTOR2I::ECOORD_MAX;
+
+    for( int i = 0; i < 4; i++ )
+        m = std::min( m, pts[i].SquaredEuclideanNorm() );
+
+    return m;
+}
+
+
+OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
+{
+    const VECTOR2I  e( B - A );
+    const VECTOR2I  f( aSeg.B - aSeg.A );
+    const VECTOR2I  ac( aSeg.A - A );
+
+    ecoord d = f.Cross( e );
+    ecoord p = f.Cross( ac );
+    ecoord q = e.Cross( ac );
+
+    if( d == 0 )
+        return OPT_VECTOR2I();
+
+    if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
+        return OPT_VECTOR2I();
+
+    if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
+        return OPT_VECTOR2I();
+
+    if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
+        return OPT_VECTOR2I();
+
+    VECTOR2I ip( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
+                 aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
+
+     return ip;
+}
+
+
+bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
+{
+    return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
+}
+
+
+bool SEG::Collide( const SEG& aSeg, int aClearance ) const
+{
+    // check for intersection
+    // fixme: move to a method
+    if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
+            ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
+        return true;
+
+#define CHK( _seg, _pt ) \
+    if( (_seg).PointCloserThan( _pt, aClearance ) ) return true;
+
+    CHK( *this, aSeg.A );
+    CHK( *this, aSeg.B );
+    CHK( aSeg, A );
+    CHK( aSeg, B );
+#undef CHK
+
+    return false;
+}
+
+
+bool SEG::Contains( const VECTOR2I& aP ) const
+{
+    return PointCloserThan( aP, 1 );
+}
diff --git a/common/geometry/shape.cpp b/common/geometry/shape.cpp
new file mode 100644
index 0000000..0e312c5
--- /dev/null
+++ b/common/geometry/shape.cpp
@@ -0,0 +1,38 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2015 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * 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
+ */
+
+
+#include <geometry/shape.h>
+
+bool SHAPE::Parse( std::stringstream& aStream )
+{
+    assert ( false );
+    return false;
+};
+
+const std::string SHAPE::Format( ) const
+{
+    assert ( false );
+    return std::string("");
+};
diff --git a/common/geometry/shape_collisions.cpp b/common/geometry/shape_collisions.cpp
new file mode 100644
index 0000000..773dcc9
--- /dev/null
+++ b/common/geometry/shape_collisions.cpp
@@ -0,0 +1,496 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2013 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * 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
+ */
+
+#include <math/vector2d.h>
+#include <math.h>
+
+#include <geometry/shape.h>
+#include <geometry/shape_line_chain.h>
+#include <geometry/shape_circle.h>
+#include <geometry/shape_rect.h>
+#include <geometry/shape_segment.h>
+#include <geometry/shape_convex.h>
+
+typedef VECTOR2I::extended_type ecoord;
+
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CIRCLE& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
+    ecoord min_dist_sq = min_dist * min_dist;
+
+    const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
+
+    ecoord dist_sq = delta.SquaredEuclideanNorm();
+
+    if( dist_sq >= min_dist_sq )
+        return false;
+
+    if( aNeedMTV )
+        aMTV = delta.Resize( min_dist - sqrt( dist_sq ) + 3 );  // fixme: apparent rounding error
+
+    return true;
+}
+
+
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CIRCLE& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    const VECTOR2I c = aB.GetCenter();
+    const VECTOR2I p0 = aA.GetPosition();
+    const VECTOR2I size = aA.GetSize();
+    const int r = aB.GetRadius();
+    const int min_dist = aClearance + r;
+
+    const VECTOR2I vts[] =
+    {
+        VECTOR2I( p0.x,          p0.y ),
+        VECTOR2I( p0.x,          p0.y + size.y ),
+        VECTOR2I( p0.x + size.x, p0.y + size.y ),
+        VECTOR2I( p0.x + size.x, p0.y ),
+        VECTOR2I( p0.x,          p0.y )
+    };
+
+    int nearest_seg_dist = INT_MAX;
+    VECTOR2I nearest;
+
+    bool inside = c.x >= p0.x && c.x <= ( p0.x + size.x )
+                  && c.y >= p0.y && c.y <= ( p0.y + size.y );
+
+
+    if( !aNeedMTV && inside )
+        return true;
+
+    for( int i = 0; i < 4; i++ )
+    {
+        const SEG seg( vts[i], vts[i + 1] );
+
+        VECTOR2I pn = seg.NearestPoint( c );
+
+        int d = ( pn - c ).EuclideanNorm();
+
+        if( ( d < min_dist ) && !aNeedMTV )
+            return true;
+
+        if( d < nearest_seg_dist )
+        {
+            nearest = pn;
+            nearest_seg_dist = d;
+        }
+    }
+
+    if( nearest_seg_dist >= min_dist && !inside )
+        return false;
+
+    VECTOR2I delta = c - nearest;
+
+    if( !aNeedMTV )
+        return true;
+
+
+    if( inside )
+        aMTV = -delta.Resize( abs( min_dist + 1 + nearest_seg_dist ) + 1 );
+    else
+        aMTV = delta.Resize( abs( min_dist + 1 - nearest_seg_dist ) + 1 );
+
+
+    return true;
+}
+
+
+static VECTOR2I pushoutForce( const SHAPE_CIRCLE& aA, const SEG& aB, int aClearance )
+{
+    VECTOR2I f( 0, 0 );
+
+    const VECTOR2I c = aA.GetCenter();
+    const VECTOR2I nearest = aB.NearestPoint( c );
+
+    const int r = aA.GetRadius();
+
+    int dist = ( nearest - c ).EuclideanNorm();
+    int min_dist = aClearance + r;
+
+    if( dist < min_dist )
+    {
+        for( int corr = 0; corr < 5; corr++ )
+        {
+            f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
+
+            if( aB.Distance( c + f ) >= min_dist )
+                break;
+        }
+    }
+
+    return f;
+}
+
+
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    bool found = false;
+
+    for( int s = 0; s < aB.SegmentCount(); s++ )
+    {
+        if( aA.Collide( aB.CSegment( s ), aClearance ) )
+        {
+            found = true;
+            break;
+        }
+    }
+
+    if( !aNeedMTV || !found )
+        return found;
+
+    SHAPE_CIRCLE cmoved( aA );
+    VECTOR2I f_total( 0, 0 );
+
+    for( int s = 0; s < aB.SegmentCount(); s++ )
+    {
+        VECTOR2I f = pushoutForce( cmoved, aB.CSegment( s ), aClearance );
+        cmoved.SetCenter( cmoved.GetCenter() + f );
+        f_total += f;
+    }
+
+    aMTV = f_total;
+    return found;
+}
+
+
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CONVEX& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    bool found;
+    const SHAPE_LINE_CHAIN& lc( aB.Vertices() );
+
+    found = lc.Distance( aA.GetCenter() ) <= aClearance + aA.GetRadius();
+
+    if( !aNeedMTV || !found )
+        return found;
+
+    SHAPE_CIRCLE cmoved( aA );
+    VECTOR2I f_total( 0, 0 );
+
+    for( int s = 0; s < lc.SegmentCount(); s++ )
+    {
+        VECTOR2I f = pushoutForce( cmoved, lc.CSegment( s ), aClearance );
+        cmoved.SetCenter( cmoved.GetCenter() + f );
+        f_total += f;
+    }
+
+    aMTV = f_total;
+    return found;
+}
+
+
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    bool col = aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
+
+    if( col && aNeedMTV )
+    {
+        aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
+    }
+    return col;
+}
+
+
+static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    for( int i = 0; i < aB.SegmentCount(); i++ )
+        if( aA.Collide( aB.CSegment( i ), aClearance ) )
+            return true;
+
+    return false;
+}
+
+
+static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_CONVEX& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
+static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_CONVEX& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide( aA.Vertices(), aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    for( int s = 0; s < aB.SegmentCount(); s++ )
+    {
+        SEG seg = aB.CSegment( s );
+
+        if( aA.Collide( seg, aClearance ) )
+            return true;
+    }
+
+    return false;
+}
+
+
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CONVEX& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2 );
+}
+
+
+static inline bool Collide( const SHAPE_SEGMENT& aA, const SHAPE_SEGMENT& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2 );
+}
+
+
+static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_SEGMENT& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2 ) )
+        return true;
+
+    return false;
+}
+
+
+static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_SEGMENT& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide( aA.Vertices(), aB, aClearance, aNeedMTV, aMTV );
+}
+
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_RECT& aB, int aClearance,
+                            bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide( aA.Outline(), aB.Outline(), aClearance, aNeedMTV, aMTV );
+}
+
+
+template<class ShapeAType, class ShapeBType>
+inline bool CollCase( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeedMTV, VECTOR2I& aMTV )
+{
+    return Collide (*static_cast<const ShapeAType*>( aA ),
+                    *static_cast<const ShapeBType*>( aB ),
+                    aClearance, aNeedMTV, aMTV);
+}
+
+template<class ShapeAType, class ShapeBType>
+inline bool CollCaseReversed ( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeedMTV, VECTOR2I& aMTV )
+{
+    bool rv = Collide (*static_cast<const ShapeBType*>( aB ),
+                       *static_cast<const ShapeAType*>( aA ),
+                        aClearance, aNeedMTV, aMTV);
+    if(rv && aNeedMTV)
+        aMTV = -aMTV;
+    return rv;
+}
+
+
+bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeedMTV, VECTOR2I& aMTV )
+{
+    switch( aA->Type() )
+    {
+        case SH_RECT:
+            switch( aB->Type() )
+            {
+                case SH_RECT:
+                    return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CIRCLE:
+                    return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_LINE_CHAIN:
+                    return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_SEGMENT:
+                    return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CONVEX:
+                    return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                default:
+                    break;
+            }
+            break;
+
+        case SH_CIRCLE:
+            switch( aB->Type() )
+            {
+                case SH_RECT:
+                    return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CIRCLE:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_LINE_CHAIN:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_SEGMENT:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CONVEX:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                default:
+                    break;
+            }
+            break;
+
+        case SH_LINE_CHAIN:
+            switch( aB->Type() )
+            {
+                case SH_RECT:
+                    return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_CIRCLE:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_LINE_CHAIN:
+                    return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_SEGMENT:
+                    return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CONVEX:
+                    return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                default:
+                    break;
+            }
+            break;
+
+        case SH_SEGMENT:
+            switch( aB->Type() )
+            {
+                case SH_RECT:
+                    return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_CIRCLE:
+                    return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_LINE_CHAIN:
+                    return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_SEGMENT:
+                    return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CONVEX:
+                    return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                default:
+                    break;
+            }
+            break;
+
+        case SH_CONVEX:
+            switch( aB->Type() )
+            {
+                case SH_RECT:
+                    return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_CIRCLE:
+                    return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_LINE_CHAIN:
+                    return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+                case SH_SEGMENT:
+                    return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                case SH_CONVEX:
+                    return CollCase<SHAPE_CONVEX, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+                default:
+                    break;
+            }
+            break;
+
+        default:
+            break;
+    }
+
+    bool unsupported_collision = true;
+    (void) unsupported_collision;   // make gcc quiet
+
+    assert( unsupported_collision == false );
+
+    return false;
+}
+
+
+bool SHAPE::Collide( const SHAPE* aShape, int aClerance, VECTOR2I& aMTV ) const
+{
+    return CollideShapes( this, aShape, aClerance, true, aMTV );
+}
+
+
+bool SHAPE::Collide( const SHAPE* aShape, int aClerance ) const
+{
+    VECTOR2I dummy;
+
+    return CollideShapes( this, aShape, aClerance, false, dummy );
+}
+
+bool SHAPE_RECT::Collide( const SEG& aSeg, int aClearance ) const
+    {
+        //VECTOR2I pmin = VECTOR2I( std::min( aSeg.a.x, aSeg.b.x ), std::min( aSeg.a.y, aSeg.b.y ) );
+        //VECTOR2I pmax = VECTOR2I( std::max( aSeg.a.x, aSeg.b.x ), std::max( aSeg.a.y, aSeg.b.y ));
+        //BOX2I r( pmin, VECTOR2I( pmax.x - pmin.x, pmax.y - pmin.y ) );
+
+        //if( BBox( 0 ).SquaredDistance( r ) > aClearance * aClearance )
+        //    return false;
+
+        if( BBox( 0 ).Contains( aSeg.A ) || BBox( 0 ).Contains( aSeg.B ) )
+            return true;
+
+        VECTOR2I vts[] = { VECTOR2I( m_p0.x, m_p0.y ),
+                           VECTOR2I( m_p0.x, m_p0.y + m_h ),
+                           VECTOR2I( m_p0.x + m_w, m_p0.y + m_h ),
+                           VECTOR2I( m_p0.x + m_w, m_p0.y ),
+                           VECTOR2I( m_p0.x, m_p0.y ) };
+
+        for( int i = 0; i < 4; i++ )
+        {
+            SEG s( vts[i], vts[i + 1], i );
+
+            if( s.Distance( aSeg ) < aClearance )
+                return true;
+        }
+
+        return false;
+    }
diff --git a/common/geometry/shape_file_io.cpp b/common/geometry/shape_file_io.cpp
new file mode 100644
index 0000000..a87fd74
--- /dev/null
+++ b/common/geometry/shape_file_io.cpp
@@ -0,0 +1,146 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2013 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * 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
+ */
+
+#include <string>
+#include <cassert>
+
+#include <geometry/shape.h>
+#include <geometry/shape_file_io.h>
+
+SHAPE_FILE_IO::SHAPE_FILE_IO( const std::string& aFilename, SHAPE_FILE_IO::IO_MODE aMode )
+{
+    m_groupActive = false;
+
+    if( aFilename.length() )
+    {
+        switch( aMode )
+        {
+            case IOM_READ: m_file = fopen( aFilename.c_str(), "rb" ); break;
+            case IOM_WRITE: m_file = fopen( aFilename.c_str(), "wb" ); break;
+            case IOM_APPEND: m_file = fopen( aFilename.c_str(), "ab" ); break;
+            default:
+                return;
+        }
+    }
+    else
+    {
+        m_file = NULL;
+    }
+
+    m_mode = aMode;
+    // fixme: exceptions
+}
+
+
+SHAPE_FILE_IO::~SHAPE_FILE_IO()
+{
+    if( !m_file )
+        return;
+
+    if( m_groupActive && m_mode != IOM_READ )
+        fprintf( m_file, "endgroup\n" );
+
+    fclose( m_file );
+}
+
+
+SHAPE* SHAPE_FILE_IO::Read()
+{
+ /*   char tmp[1024];
+
+    do {
+
+        if (fscanf(m_file, "%s", tmp) != 1)
+            return NULL;
+
+        if( !strcmp( tmp, "shape" )
+            break;
+    }
+
+    int type;
+
+    SHAPE *rv = NULL;
+
+    fscanf(m_file,"%d %s", &type, tmp);
+
+    printf("create shape %d\n", type);
+
+    switch(type)
+    {
+        case SHAPE::LINE_CHAIN:
+            rv = new SHAPE_LINE_CHAIN;
+            break;
+    }
+
+    if(!rv)
+        return NULL;
+
+    rv.Parse ( )
+
+    fprintf(m_file,"shape %d %s %s\n", aShape->Type(), aName.c_str(), sh.c_str() );
+*/
+    assert( false );
+    return NULL;
+}
+
+
+void SHAPE_FILE_IO::BeginGroup( const std::string aName )
+{
+    assert( m_mode != IOM_READ );
+
+    if( !m_file )
+        return;
+
+    fprintf( m_file, "group %s\n", aName.c_str() );
+    m_groupActive = true;
+}
+
+
+void SHAPE_FILE_IO::EndGroup()
+{
+    assert( m_mode != IOM_READ );
+
+    if( !m_file || !m_groupActive )
+        return;
+
+    fprintf( m_file, "endgroup\n" );
+    m_groupActive = false;
+}
+
+
+void SHAPE_FILE_IO::Write( const SHAPE* aShape, const std::string aName )
+{
+    assert( m_mode != IOM_READ );
+
+    if( !m_file )
+        return;
+
+    if( !m_groupActive )
+        fprintf( m_file,"group default\n" );
+
+    std::string sh = aShape->Format();
+
+    fprintf( m_file, "shape %d %s %s\n", aShape->Type(), aName.c_str(), sh.c_str() );
+    fflush( m_file );
+}
\ No newline at end of file
diff --git a/common/geometry/shape_line_chain.cpp b/common/geometry/shape_line_chain.cpp
new file mode 100644
index 0000000..a097b0b
--- /dev/null
+++ b/common/geometry/shape_line_chain.cpp
@@ -0,0 +1,580 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2013 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * 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
+ */
+
+#include <geometry/shape_line_chain.h>
+#include <geometry/shape_circle.h>
+
+using boost::optional;
+
+bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance ) const
+{
+    // fixme: ugly!
+    SEG s( aP, aP );
+    return this->Collide( s, aClearance );
+}
+
+
+bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance ) const
+{
+    BOX2I box_a( aSeg.A, aSeg.B - aSeg.A );
+    BOX2I::ecoord_type dist_sq = (BOX2I::ecoord_type) aClearance * aClearance;
+
+    for( int i = 0; i < SegmentCount(); i++ )
+    {
+        const SEG& s = CSegment( i );
+        BOX2I box_b( s.A, s.B - s.A );
+
+        BOX2I::ecoord_type d = box_a.SquaredDistance( box_b );
+
+        if( d < dist_sq )
+        {
+            if( s.Collide( aSeg, aClearance ) )
+                return true;
+        }
+    }
+
+    return false;
+}
+
+
+const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Reverse() const
+{
+    SHAPE_LINE_CHAIN a( *this );
+
+    reverse( a.m_points.begin(), a.m_points.end() );
+    a.m_closed = m_closed;
+
+    return a;
+}
+
+
+int SHAPE_LINE_CHAIN::Length() const
+{
+    int l = 0;
+
+    for( int i = 0; i < SegmentCount(); i++ )
+        l += CSegment( i ).Length();
+
+    return l;
+}
+
+
+void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
+{
+    if( aEndIndex < 0 )
+        aEndIndex += PointCount();
+
+    if( aStartIndex < 0 )
+        aStartIndex += PointCount();
+
+    if( aStartIndex == aEndIndex )
+        m_points[aStartIndex] = aP;
+    else
+    {
+        m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
+        m_points[aStartIndex] = aP;
+    }
+}
+
+
+void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
+{
+    if( aEndIndex < 0 )
+        aEndIndex += PointCount();
+
+    if( aStartIndex < 0 )
+        aStartIndex += PointCount();
+
+    m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
+    m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
+}
+
+
+void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
+{
+    if( aEndIndex < 0 )
+        aEndIndex += PointCount();
+
+    if( aStartIndex < 0 )
+        aStartIndex += PointCount();
+
+    m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
+}
+
+
+int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP ) const
+{
+    int d = INT_MAX;
+
+    if( IsClosed() && PointInside( aP ) )
+        return 0;
+
+    for( int s = 0; s < SegmentCount(); s++ )
+        d = std::min( d, CSegment( s ).Distance( aP ) );
+
+    return d;
+}
+
+
+int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP )
+{
+    int ii = -1;
+    int min_dist = 2;
+
+    int found_index = Find( aP );
+
+    for( int s = 0; s < SegmentCount(); s++ )
+    {
+        const SEG seg = CSegment( s );
+        int dist = seg.Distance( aP );
+
+        // make sure we are not producing a 'slightly concave' primitive. This might happen
+        // if aP lies very close to one of already existing points.
+        if( dist < min_dist && seg.A != aP && seg.B != aP )
+        {
+            min_dist = dist;
+            if( found_index < 0 )
+                ii = s;
+            else if( s < found_index )
+                ii = s;
+        }
+    }
+
+    if( ii < 0 )
+        ii = found_index;
+
+    if( ii >= 0 )
+    {
+        m_points.insert( m_points.begin() + ii + 1, aP );
+
+        return ii + 1;
+    }
+
+    return -1;
+}
+
+
+int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
+{
+    for( int s = 0; s < PointCount(); s++ )
+        if( CPoint( s ) == aP )
+            return s;
+
+    return -1;
+}
+
+
+int SHAPE_LINE_CHAIN::FindSegment( const VECTOR2I& aP ) const
+{
+    for( int s = 0; s < SegmentCount(); s++ )
+        if( CSegment( s ).Distance( aP ) <= 1 )
+            return s;
+
+    return -1;
+}
+
+
+const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
+{
+    SHAPE_LINE_CHAIN rv;
+
+    if( aEndIndex < 0 )
+        aEndIndex += PointCount();
+
+    if( aStartIndex < 0 )
+        aStartIndex += PointCount();
+
+    for( int i = aStartIndex; i <= aEndIndex; i++ )
+        rv.Append( m_points[i] );
+
+    return rv;
+}
+
+
+struct compareOriginDistance
+{
+    compareOriginDistance( VECTOR2I& aOrigin ) :
+        m_origin( aOrigin ) {};
+
+    bool operator()( const SHAPE_LINE_CHAIN::INTERSECTION& aA,
+                     const SHAPE_LINE_CHAIN::INTERSECTION& aB )
+    {
+        return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
+    }
+
+    VECTOR2I m_origin;
+};
+
+
+int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
+{
+    for( int s = 0; s < SegmentCount(); s++ )
+    {
+        OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
+
+        if( p )
+        {
+            INTERSECTION is;
+            is.our = CSegment( s );
+            is.their = aSeg;
+            is.p = *p;
+            aIp.push_back( is );
+        }
+    }
+
+    compareOriginDistance comp( aSeg.A );
+    sort( aIp.begin(), aIp.end(), comp );
+
+    return aIp.size();
+}
+
+
+int SHAPE_LINE_CHAIN::Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const
+{
+    BOX2I bb_other = aChain.BBox();
+
+    for( int s1 = 0; s1 < SegmentCount(); s1++ )
+    {
+        const SEG& a = CSegment( s1 );
+        const BOX2I bb_cur( a.A, a.B - a.A );
+
+        if( !bb_other.Intersects( bb_cur ) )
+            continue;
+
+        for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
+        {
+            const SEG& b = aChain.CSegment( s2 );
+            INTERSECTION is;
+
+            if( a.Collinear( b ) )
+            {
+                is.our = a;
+                is.their = b;
+
+                if( a.Contains( b.A ) ) { is.p = b.A; aIp.push_back( is ); }
+                if( a.Contains( b.B ) ) { is.p = b.B; aIp.push_back( is ); }
+                if( b.Contains( a.A ) ) { is.p = a.A; aIp.push_back( is ); }
+                if( b.Contains( a.B ) ) { is.p = a.B; aIp.push_back( is ); }
+            }
+            else
+            {
+                OPT_VECTOR2I p = a.Intersect( b );
+
+                if( p )
+                {
+                    is.p = *p;
+                    is.our = a;
+                    is.their = b;
+                    aIp.push_back( is );
+                }
+            }
+        }
+    }
+
+    return aIp.size();
+}
+
+
+int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP ) const
+{
+    int sum = 0;
+
+    for( int i = 0; i < SegmentCount(); i++ )
+    {
+        const SEG seg = CSegment( i );
+        int d = seg.Distance( aP );
+
+        if( d <= 1 )
+        {
+            sum += ( aP - seg.A ).EuclideanNorm();
+            return sum;
+        }
+        else
+            sum += seg.Length();
+    }
+
+    return -1;
+}
+
+
+bool SHAPE_LINE_CHAIN::PointInside( const VECTOR2I& aP ) const
+{
+    if( !m_closed || SegmentCount() < 3 )
+        return false;
+
+    int cur = CSegment( 0 ).Side( aP );
+
+    if( cur == 0 )
+        return false;
+
+    for( int i = 1; i < SegmentCount(); i++ )
+    {
+        const SEG s = CSegment( i );
+
+        if( aP == s.A || aP == s.B ) // edge does not belong to the interior!
+            return false;
+
+        if( s.Side( aP ) != cur )
+            return false;
+    }
+
+    return true;
+}
+
+
+bool SHAPE_LINE_CHAIN::PointOnEdge( const VECTOR2I& aP ) const
+{
+	if( !PointCount() )
+		return false;
+
+	else if( PointCount() == 1 )
+        return m_points[0] == aP;
+
+    for( int i = 0; i < SegmentCount(); i++ )
+    {
+        const SEG s = CSegment( i );
+
+        if( s.A == aP || s.B == aP )
+            return true;
+
+        if( s.Distance( aP ) <= 1 )
+            return true;
+    }
+
+    return false;
+}
+
+
+const optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
+{
+    for( int s1 = 0; s1 < SegmentCount(); s1++ )
+    {
+        for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
+        {
+            const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
+
+            if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
+            {
+                INTERSECTION is;
+                is.our = CSegment( s1 );
+                is.their = CSegment( s2 );
+                is.p = s2a;
+                return is;
+            }
+            else if( CSegment( s1 ).Contains( s2b ) )
+            {
+                INTERSECTION is;
+                is.our = CSegment( s1 );
+                is.their = CSegment( s2 );
+                is.p = s2b;
+                return is;
+            }
+            else
+            {
+                OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
+
+                if( p )
+                {
+                    INTERSECTION is;
+                    is.our = CSegment( s1 );
+                    is.their = CSegment( s2 );
+                    is.p = *p;
+                    return is;
+                }
+            }
+        }
+    }
+
+    return optional<INTERSECTION>();
+}
+
+
+SHAPE_LINE_CHAIN& SHAPE_LINE_CHAIN::Simplify()
+{
+    std::vector<VECTOR2I> pts_unique;
+
+    if( PointCount() < 2 )
+    {
+        return *this;
+    }
+    else if( PointCount() == 2 )
+    {
+        if( m_points[0] == m_points[1] )
+            m_points.pop_back();
+
+        return *this;
+    }
+
+    int i = 0;
+    int np = PointCount();
+
+    // stage 1: eliminate duplicate vertices
+    while( i < np )
+    {
+        int j = i + 1;
+
+        while( j < np && CPoint( i ) == CPoint( j ) )
+            j++;
+
+        pts_unique.push_back( CPoint( i ) );
+        i = j;
+    }
+
+    m_points.clear();
+    np = pts_unique.size();
+
+    i = 0;
+
+    // stage 1: eliminate collinear segments
+    while( i < np - 2 )
+    {
+        const VECTOR2I p0 = pts_unique[i];
+        const VECTOR2I p1 = pts_unique[i + 1];
+        int n = i;
+
+        while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
+            n++;
+
+        m_points.push_back( p0 );
+
+        if( n > i )
+            i = n;
+
+        if( n == np )
+        {
+            m_points.push_back( pts_unique[n - 1] );
+            return *this;
+        }
+
+        i++;
+    }
+
+    if( np > 1 )
+        m_points.push_back( pts_unique[np - 2] );
+
+    m_points.push_back( pts_unique[np - 1] );
+
+    return *this;
+}
+
+
+const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const VECTOR2I& aP ) const
+{
+    int min_d = INT_MAX;
+    int nearest = 0;
+
+    for( int i = 0; i < SegmentCount(); i++ )
+    {
+        int d = CSegment( i ).Distance( aP );
+
+        if( d < min_d )
+        {
+            min_d = d;
+            nearest = i;
+        }
+    }
+
+    return CSegment( nearest ).NearestPoint( aP );
+}
+
+
+const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
+{
+    int nearest = 0;
+
+    dist = INT_MAX;
+    for( int i = 0; i < PointCount(); i++ )
+    {
+        int d = aSeg.LineDistance( CPoint( i ) );
+
+        if( d < dist )
+        {
+            dist = d;
+            nearest = i;
+        }
+    }
+
+    return CPoint( nearest );
+}
+
+
+const std::string SHAPE_LINE_CHAIN::Format() const
+{
+    std::stringstream ss;
+
+    ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
+
+    for( int i = 0; i < PointCount(); i++ )
+        ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
+
+    return ss.str();
+}
+
+
+bool SHAPE_LINE_CHAIN::CompareGeometry ( const SHAPE_LINE_CHAIN & aOther ) const
+{
+    SHAPE_LINE_CHAIN a(*this), b( aOther );
+    a.Simplify();
+    b.Simplify();
+
+    if( a.m_points.size() != b.m_points.size() )
+        return false;
+
+    for( int i = 0; i < a.PointCount(); i++)
+        if( a.CPoint( i ) != b.CPoint( i ) )
+            return false;
+    return true;
+}
+
+
+bool SHAPE_LINE_CHAIN::Intersects( const SHAPE_LINE_CHAIN& aChain ) const
+{
+    INTERSECTIONS dummy;
+    return Intersect( aChain, dummy ) != 0;
+}
+
+
+SHAPE* SHAPE_LINE_CHAIN::Clone() const
+{
+    return new SHAPE_LINE_CHAIN( *this );
+}
+
+bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
+{
+    int n_pts;
+
+    m_points.clear();
+    aStream >> n_pts;
+    aStream >> m_closed;
+
+    for( int i = 0; i < n_pts; i++ )
+    {
+        int x, y;
+        aStream >> x;
+        aStream >> y;
+        m_points.push_back( VECTOR2I( x, y ) );
+    }
+
+    return true;
+}
\ No newline at end of file
diff --git a/common/geometry/shape_poly_set.cpp b/common/geometry/shape_poly_set.cpp
new file mode 100644
index 0000000..ce28926
--- /dev/null
+++ b/common/geometry/shape_poly_set.cpp
@@ -0,0 +1,805 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2015 CERN
+ * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
+ *
+ * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
+ * subject to Clipper library license.
+ *
+ * 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
+ */
+
+
+#include <vector>
+#include <cstdio>
+#include <set>
+#include <list>
+#include <algorithm>
+
+#include <boost/foreach.hpp>
+
+#include <geometry/shape.h>
+#include <geometry/shape_line_chain.h>
+#include <geometry/shape_poly_set.h>
+
+using namespace ClipperLib;
+
+SHAPE_POLY_SET::SHAPE_POLY_SET() :
+    SHAPE( SH_POLY_SET )
+{
+
+}
+
+
+SHAPE_POLY_SET::~SHAPE_POLY_SET()
+{
+}
+
+
+int SHAPE_POLY_SET::NewOutline()
+{
+    SHAPE_LINE_CHAIN empty_path;
+    POLYGON poly;
+    poly.push_back( empty_path );
+    m_polys.push_back( poly );
+    return m_polys.size() - 1;
+}
+
+
+int SHAPE_POLY_SET::NewHole( int aOutline )
+{
+    m_polys.back().push_back( SHAPE_LINE_CHAIN() );
+
+    return m_polys.back().size() - 2;
+}
+
+
+int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole )
+{
+    if( aOutline < 0 )
+        aOutline += m_polys.size();
+
+    int idx;
+
+    if( aHole < 0 )
+        idx = 0;
+    else
+        idx = aHole + 1;
+
+    assert( aOutline < (int)m_polys.size() );
+    assert( idx < (int)m_polys[aOutline].size() );
+
+    m_polys[aOutline][idx].Append( x, y );
+
+    return m_polys[aOutline][idx].PointCount();
+}
+
+
+int SHAPE_POLY_SET::VertexCount( int aOutline , int aHole  ) const
+{
+    if( aOutline < 0 )
+        aOutline += m_polys.size();
+
+    int idx;
+
+    if( aHole < 0 )
+        idx = 0;
+    else
+        idx = aHole + 1;
+
+    assert ( aOutline < (int)m_polys.size() );
+    assert ( idx < (int)m_polys[aOutline].size() );
+
+    return m_polys[aOutline][idx].PointCount();
+}
+
+
+const VECTOR2I& SHAPE_POLY_SET::CVertex( int index, int aOutline , int aHole ) const
+{
+    if( aOutline < 0 )
+        aOutline += m_polys.size();
+
+    int idx;
+
+    if( aHole < 0 )
+        idx = 0;
+    else
+        idx = aHole + 1;
+
+    assert( aOutline < (int)m_polys.size() );
+    assert( idx < (int)m_polys[aOutline].size() );
+
+    return m_polys[aOutline][idx].CPoint( index );
+}
+
+
+VECTOR2I& SHAPE_POLY_SET::Vertex( int index, int aOutline , int aHole )
+{
+    if( aOutline < 0 )
+        aOutline += m_polys.size();
+
+    int idx;
+
+    if( aHole < 0 )
+        idx = 0;
+    else
+        idx = aHole + 1;
+
+    assert( aOutline < (int)m_polys.size() );
+    assert( idx < (int)m_polys[aOutline].size() );
+
+    return m_polys[aOutline][idx].Point( index );
+}
+
+
+int SHAPE_POLY_SET::AddOutline( const SHAPE_LINE_CHAIN& aOutline )
+{
+    assert( aOutline.IsClosed() );
+
+    POLYGON poly;
+
+    poly.push_back( aOutline );
+
+    m_polys.push_back( poly );
+
+    return m_polys.size() - 1;
+}
+
+
+int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
+{
+    assert ( m_polys.size() );
+
+    if( aOutline < 0 )
+        aOutline += m_polys.size();
+
+    POLYGON& poly = m_polys[aOutline];
+
+    assert( poly.size() );
+
+    poly.push_back( aHole );
+
+    return poly.size() - 1;
+}
+
+
+const Path SHAPE_POLY_SET::convertToClipper( const SHAPE_LINE_CHAIN& aPath, bool aRequiredOrientation )
+{
+    Path c_path;
+
+    for( int i = 0; i < aPath.PointCount(); i++ )
+    {
+        const VECTOR2I& vertex = aPath.CPoint( i );
+        c_path.push_back( IntPoint( vertex.x, vertex.y ) );
+    }
+
+    if( Orientation( c_path ) != aRequiredOrientation )
+        ReversePath( c_path );
+
+    return c_path;
+}
+
+
+const SHAPE_LINE_CHAIN SHAPE_POLY_SET::convertFromClipper( const Path& aPath )
+{
+    SHAPE_LINE_CHAIN lc;
+
+    for( unsigned int i = 0; i < aPath.size(); i++ )
+        lc.Append( aPath[i].X, aPath[i].Y );
+
+    return lc;
+}
+
+void SHAPE_POLY_SET::booleanOp( ClipType aType, const SHAPE_POLY_SET& aOtherShape,
+                                bool aFastMode )
+{
+    Clipper c;
+
+    if( !aFastMode )
+        c.StrictlySimple( true );
+
+    BOOST_FOREACH( const POLYGON& poly, m_polys )
+    {
+        for( unsigned int i = 0; i < poly.size(); i++ )
+            c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
+    }
+
+    BOOST_FOREACH( const POLYGON& poly, aOtherShape.m_polys )
+    {
+        for( unsigned int i = 0; i < poly.size(); i++ )
+            c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
+    }
+
+    PolyTree solution;
+
+    c.Execute( aType, solution, pftNonZero, pftNonZero );
+
+    importTree( &solution );
+}
+
+
+void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
+                                const SHAPE_POLY_SET& aShape,
+                                const SHAPE_POLY_SET& aOtherShape,
+                                bool aFastMode )
+{
+    Clipper c;
+
+    if( !aFastMode )
+        c.StrictlySimple( true );
+
+    BOOST_FOREACH( const POLYGON& poly, aShape.m_polys )
+    {
+        for( unsigned int i = 0; i < poly.size(); i++ )
+            c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
+    }
+
+    BOOST_FOREACH( const POLYGON& poly, aOtherShape.m_polys )
+    {
+        for( unsigned int i = 0; i < poly.size(); i++ )
+            c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
+    }
+
+    PolyTree solution;
+
+    c.Execute( aType, solution, pftNonZero, pftNonZero );
+
+    importTree( &solution );
+}
+
+
+void SHAPE_POLY_SET::BooleanAdd( const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctUnion, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::BooleanSubtract( const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctDifference, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::BooleanIntersection( const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctIntersection, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctUnion, a, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctDifference, a, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode )
+{
+    booleanOp( ctIntersection, a, b, aFastMode );
+}
+
+
+void SHAPE_POLY_SET::Inflate( int aFactor, int aCircleSegmentsCount )
+{
+    ClipperOffset c;
+
+    BOOST_FOREACH( const POLYGON& poly, m_polys )
+    {
+        for( unsigned int i = 0; i < poly.size(); i++ )
+            c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), jtRound, etClosedPolygon );
+    }
+
+    PolyTree solution;
+
+    c.ArcTolerance = fabs( (double) aFactor ) / M_PI / aCircleSegmentsCount;
+
+    c.Execute( solution, aFactor );
+
+    importTree( &solution );
+}
+
+
+void SHAPE_POLY_SET::importTree( PolyTree* tree)
+{
+    m_polys.clear();
+
+    for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
+    {
+        if( !n->IsHole() )
+        {
+            POLYGON paths;
+            paths.push_back( convertFromClipper( n->Contour ) );
+
+            for( unsigned int i = 0; i < n->Childs.size(); i++ )
+                paths.push_back( convertFromClipper( n->Childs[i]->Contour ) );
+
+            m_polys.push_back(paths);
+        }
+    }
+}
+
+// Polygon fracturing code. Work in progress.
+
+struct FractureEdge
+{
+    FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
+        m_connected( connected ),
+        m_next( NULL )
+    {
+        m_p1 = owner->CPoint( index );
+        m_p2 = owner->CPoint( index + 1 );
+    }
+
+    FractureEdge( int y = 0 ) :
+        m_connected( false ),
+        m_next( NULL )
+    {
+        m_p1.x = m_p2.y = y;
+    }
+
+    FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
+        m_connected( connected ),
+        m_p1( p1 ),
+        m_p2( p2 ),
+        m_next( NULL )
+    {
+    }
+
+    bool matches( int y ) const
+    {
+        int y_min = std::min( m_p1.y, m_p2.y );
+        int y_max = std::max( m_p1.y, m_p2.y );
+
+        return ( y >= y_min ) && ( y <= y_max );
+    }
+
+    bool m_connected;
+    VECTOR2I m_p1, m_p2;
+    FractureEdge* m_next;
+};
+
+
+typedef std::vector<FractureEdge*> FractureEdgeSet;
+
+static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
+{
+    int x = edge->m_p1.x;
+    int y = edge->m_p1.y;
+    int min_dist = std::numeric_limits<int>::max();
+    int x_nearest = 0;
+
+    FractureEdge* e_nearest = NULL;
+
+    for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
+    {
+        if( !(*i)->matches( y ) )
+            continue;
+
+        int x_intersect;
+
+        if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
+            x_intersect = std::max ( (*i)->m_p1.x, (*i)->m_p2.x );
+        else
+            x_intersect = (*i)->m_p1.x + rescale((*i)->m_p2.x - (*i)->m_p1.x,   y - (*i)->m_p1.y,   (*i)->m_p2.y - (*i)->m_p1.y );
+
+        int dist = ( x - x_intersect );
+
+        if( dist >= 0 && dist < min_dist && (*i)->m_connected )
+        {
+            min_dist = dist;
+            x_nearest = x_intersect;
+            e_nearest = (*i);
+        }
+    }
+
+    if( e_nearest && e_nearest->m_connected )
+    {
+        int count = 0;
+
+		FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
+        FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
+        FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
+
+        edges.push_back( split_2 );
+        edges.push_back( lead1 );
+        edges.push_back( lead2 );
+
+        FractureEdge* link = e_nearest->m_next;
+
+        e_nearest->m_p2 = VECTOR2I( x_nearest, y );
+        e_nearest->m_next = lead1;
+        lead1->m_next = edge;
+
+        FractureEdge*last;
+        for( last = edge; last->m_next != edge; last = last->m_next )
+        {
+            last->m_connected = true;
+            count++;
+        }
+
+        last->m_connected = true;
+        last->m_next = lead2;
+        lead2->m_next = split_2;
+        split_2->m_next = link;
+
+        return count + 1;
+    }
+
+    return 0;
+}
+
+void SHAPE_POLY_SET::fractureSingle( POLYGON& paths )
+{
+    FractureEdgeSet edges;
+    FractureEdgeSet border_edges;
+    FractureEdge* root = NULL;
+
+    bool first = true;
+
+    if( paths.size() == 1 )
+        return;
+
+    int num_unconnected = 0;
+
+    BOOST_FOREACH( SHAPE_LINE_CHAIN& path, paths )
+    {
+        int index = 0;
+
+        FractureEdge *prev = NULL, *first_edge = NULL;
+
+        int x_min = std::numeric_limits<int>::max();
+
+        for( int i = 0; i < path.PointCount(); i++ )
+        {
+            const VECTOR2I& p = path.CPoint( i );
+
+            if( p.x < x_min )
+                x_min = p.x;
+        }
+
+        for( int i = 0; i < path.PointCount(); i++ )
+        {
+            FractureEdge* fe = new FractureEdge( first, &path, index++ );
+
+            if( !root )
+                root = fe;
+
+            if( !first_edge )
+                first_edge = fe;
+
+            if( prev )
+                prev->m_next = fe;
+
+            if( i == path.PointCount() - 1 )
+                fe->m_next = first_edge;
+
+            prev = fe;
+            edges.push_back( fe );
+
+            if( !first )
+            {
+                if( fe->m_p1.x == x_min )
+                    border_edges.push_back( fe );
+            }
+
+            if( !fe->m_connected )
+                num_unconnected++;
+        }
+        first = false; // first path is always the outline
+    }
+
+    // keep connecting holes to the main outline, until there's no holes left...
+    while( num_unconnected > 0 )
+    {
+        int x_min = std::numeric_limits<int>::max();
+
+        FractureEdge* smallestX = NULL;
+
+        // find the left-most hole edge and merge with the outline
+        for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
+        {
+            int xt = (*i)->m_p1.x;
+
+            if( ( xt < x_min ) && ! (*i)->m_connected )
+            {
+                x_min = xt;
+                smallestX = *i;
+            }
+        }
+
+        num_unconnected -= processEdge( edges, smallestX );
+    }
+
+    paths.clear();
+    SHAPE_LINE_CHAIN newPath;
+
+    newPath.SetClosed( true );
+
+    FractureEdge* e;
+
+    for( e = root; e->m_next != root; e = e->m_next )
+        newPath.Append( e->m_p1 );
+
+    newPath.Append( e->m_p1 );
+
+    for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
+        delete *i;
+
+    paths.push_back( newPath );
+}
+
+
+void SHAPE_POLY_SET::Fracture( bool aFastMode )
+{
+    Simplify( aFastMode ); // remove overlapping holes/degeneracy
+
+    BOOST_FOREACH( POLYGON& paths, m_polys )
+    {
+        fractureSingle( paths );
+    }
+}
+
+
+void SHAPE_POLY_SET::Simplify( bool aFastMode )
+{
+    SHAPE_POLY_SET empty;
+
+    booleanOp( ctUnion, empty, aFastMode );
+}
+
+
+const std::string SHAPE_POLY_SET::Format() const
+{
+    std::stringstream ss;
+
+    ss << "polyset " << m_polys.size() << "\n";
+
+    for( unsigned i = 0; i < m_polys.size(); i++ )
+    {
+        ss << "poly " << m_polys[i].size() << "\n";
+        for( unsigned j = 0; j < m_polys[i].size(); j++)
+        {
+            ss << m_polys[i][j].PointCount() << "\n";
+            for( int v = 0; v < m_polys[i][j].PointCount(); v++)
+                ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
+        }
+        ss << "\n";
+    }
+
+    return ss.str();
+}
+
+
+bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
+{
+    std::string tmp;
+
+    aStream >> tmp;
+
+    if( tmp != "polyset" )
+        return false;
+
+    aStream >> tmp;
+
+    int n_polys = atoi( tmp.c_str() );
+
+    if( n_polys < 0 )
+        return false;
+
+    for( int i = 0; i < n_polys; i++ )
+    {
+        POLYGON paths;
+
+        aStream >> tmp;
+
+        if( tmp != "poly" )
+            return false;
+
+        aStream >> tmp;
+        int n_outlines = atoi( tmp.c_str() );
+
+        if( n_outlines < 0 )
+            return false;
+
+        for( int j = 0; j < n_outlines; j++ )
+        {
+            SHAPE_LINE_CHAIN outline;
+
+            outline.SetClosed( true );
+
+            aStream >> tmp;
+            int n_vertices = atoi( tmp.c_str() );
+            for( int v = 0; v < n_vertices; v++ )
+            {
+                VECTOR2I p;
+
+                aStream >> tmp; p.x = atoi( tmp.c_str() );
+                aStream >> tmp; p.y = atoi( tmp.c_str() );
+                outline.Append( p );
+            }
+
+            paths.push_back( outline );
+        }
+
+        m_polys.push_back( paths );
+    }
+    return true;
+}
+
+
+const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
+{
+    BOX2I bb;
+
+    for( unsigned i = 0; i < m_polys.size(); i++ )
+    {
+        if( i == 0 )
+            bb = m_polys[i][0].BBox();
+        else
+            bb.Merge( m_polys[i][0].BBox() );
+    }
+
+    bb.Inflate( aClearance );
+    return bb;
+}
+
+
+void SHAPE_POLY_SET::RemoveAllContours()
+{
+    m_polys.clear();
+}
+
+
+void SHAPE_POLY_SET::DeletePolygon( int aIdx )
+{
+    m_polys.erase( m_polys.begin() + aIdx );
+}
+
+
+void SHAPE_POLY_SET::Append( const SHAPE_POLY_SET& aSet )
+{
+    m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
+}
+
+
+void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
+{
+    Append( aP.x, aP.y, aOutline, aHole );
+}
+
+
+bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex ) const
+{
+    // fixme: support holes!
+
+    if( m_polys.size() == 0 ) // empty set?
+        return false;
+
+    if( aSubpolyIndex >= 0 )
+        return pointInPolygon( aP, m_polys[aSubpolyIndex][0] );
+
+    BOOST_FOREACH ( const POLYGON& polys, m_polys )
+    {
+        if( polys.size() == 0 )
+            continue;
+
+        if( pointInPolygon( aP, polys[0] ) )
+            return true;
+    }
+
+    return false;
+}
+
+
+bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
+{
+    int result = 0;
+    int cnt = aPath.PointCount();
+
+    if ( !aPath.BBox().Contains( aP ) ) // test with bounding box first
+        return false;
+
+    if( cnt < 3 )
+        return false;
+
+    VECTOR2I ip = aPath.CPoint( 0 );
+
+    for( int i = 1; i <= cnt; ++i )
+    {
+        VECTOR2I ipNext = ( i == cnt ? aPath.CPoint( 0 ) : aPath.CPoint( i ) );
+
+        if( ipNext.y == aP.y )
+        {
+            if( ( ipNext.x == aP.x ) || ( ip.y == aP.y &&
+                ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
+                return true;
+        }
+
+        if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
+        {
+            if( ip.x >= aP.x )
+            {
+                if( ipNext.x > aP.x )
+                    result = 1 - result;
+                else
+                {
+                    int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
+                                (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
+
+                    if( !d )
+                        return true;
+
+                    if( ( d > 0 ) == ( ipNext.y > ip.y ) )
+                        result = 1 - result;
+                }
+            }
+            else
+            {
+                if( ipNext.x > aP.x )
+                {
+                    int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
+                                (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
+
+                if( !d )
+                    return true;
+
+                if( ( d > 0 ) == ( ipNext.y > ip.y ) )
+                    result = 1 - result;
+                }
+            }
+        }
+
+        ip = ipNext;
+    }
+
+    return result ? true : false;
+}
+
+
+void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
+{
+    BOOST_FOREACH( POLYGON &poly, m_polys )
+    {
+        BOOST_FOREACH( SHAPE_LINE_CHAIN &path, poly )
+        {
+            path.Move( aVector );
+        }
+    }
+}
+
+
+int SHAPE_POLY_SET::TotalVertices() const
+{
+    int c = 0;
+
+    BOOST_FOREACH( const POLYGON& poly, m_polys )
+    {
+        BOOST_FOREACH ( const SHAPE_LINE_CHAIN& path, poly )
+        {
+            c += path.PointCount();
+        }
+    }
+
+    return c;
+}