# HG changeset patch
# User Alexis Jeandet <alexis.jeandet@member.fsf.org>
# Date 2015-06-21 22:02:06
# Node ID 4df93d51b13ecef3df32973314200b47ce1dde7d
# Parent  72560b13551af2ecaa74dc1811c46f43e75a3011

Improved Polygon rendering by splittig them into lower complexity polygons.

diff --git a/test/PCBView/PCBView.pro b/test/PCBView/PCBView.pro
--- a/test/PCBView/PCBView.pro
+++ b/test/PCBView/PCBView.pro
@@ -30,7 +30,8 @@ SOURCES += main.cpp\
     pcbcontext.cpp \
     pcbvia.cpp \
     pcbpad.cpp \
-    pcbzone.cpp
+    pcbzone.cpp \
+    polypartition/src/polypartition.cpp
 
 HEADERS  += mainwindow.h \
     pcbgraphicview.h \
@@ -39,6 +40,7 @@ HEADERS  += mainwindow.h \
     pcbcontext.h \
     pcbvia.h \
     pcbpad.h \
-    pcbzone.h
+    pcbzone.h \
+    polypartition/src/polypartition.h
 
 FORMS    += mainwindow.ui
diff --git a/test/PCBView/pcbgraphicview.cpp b/test/PCBView/pcbgraphicview.cpp
--- a/test/PCBView/pcbgraphicview.cpp
+++ b/test/PCBView/pcbgraphicview.cpp
@@ -110,8 +110,8 @@ void PCBGraphicView::drawBackground(QPai
 
     // Shadow
     QRectF sceneRect = this->sceneRect();
-    QRectF rightShadow(sceneRect.right(), sceneRect.top() + 20, 20, sceneRect.height());
-    QRectF bottomShadow(sceneRect.left() + 20, sceneRect.bottom(), sceneRect.width(), 20);
+    QRectF rightShadow(sceneRect.right(), sceneRect.top() + 2, 2, sceneRect.height());
+    QRectF bottomShadow(sceneRect.left() + 2, sceneRect.bottom(), sceneRect.width(), 2);
     if (rightShadow.intersects(rect) || rightShadow.contains(rect))
         painter->fillRect(rightShadow, Qt::darkGray);
     if (bottomShadow.intersects(rect) || bottomShadow.contains(rect))
diff --git a/test/PCBView/pcbpad.cpp b/test/PCBView/pcbpad.cpp
--- a/test/PCBView/pcbpad.cpp
+++ b/test/PCBView/pcbpad.cpp
@@ -60,8 +60,10 @@ void PCBPad::init( QPointF offset)
             this->addToGroup(rect);
         }
         QGraphicsTextItem* text=new QGraphicsTextItem(QString::number(padNode->padNumber()));
+        text->setScale(0.01);
         text->setPos(rec.center());
-        text->setScale(0.01);
+//        text->setTransformOriginPoint(rec.center());
+//        text->setRotation(padNode->angle());
         text->setZValue(1);
         this->addToGroup(text);
 
diff --git a/test/PCBView/pcbzone.cpp b/test/PCBView/pcbzone.cpp
--- a/test/PCBView/pcbzone.cpp
+++ b/test/PCBView/pcbzone.cpp
@@ -22,41 +22,119 @@
 #include "pcbzone.h"
 #include <QPen>
 #include <QPixmapCache>
+#include "polypartition/src/polypartition.h"
+
 
 PCBZone::PCBZone(QIlib::QIcadPcbZone *zoneNode, PCBContext *context)
     :QGraphicsItemGroup(),zoneNode(zoneNode),context(context)
 {
-    this->init();
+    this->initQtClipping();
 }
 
-void PCBZone::init()
+void PCBZone::initTriangPolypartition()
+{
+    TPPLPartition pp;
+    this->setFlags(ItemIsMovable|ItemIsSelectable|ItemIsFocusable);
+    TPPLPoly test;
+    std::list<TPPLPoly> triangles;
+    test.Init(this->zoneNode->filledPolygon.points.points.count());
+    for(int i=0;i<this->zoneNode->filledPolygon.points.points.count();i++)
+    {
+        test[i].x =this->zoneNode->filledPolygon.points.points.at(i)->pos().x();
+        test[i].y =this->zoneNode->filledPolygon.points.points.at(i)->pos().y();
+    }
+    pp.Triangulate_OPT(&test,&triangles);
+    for(std::list<TPPLPoly>::iterator iter = triangles.begin();iter != triangles.end(); iter++)
+    {
+        QPolygonF poly;
+        TPPLPoly t = *iter;
+        for(int i=0;i<t.GetNumPoints();i++)
+        {
+            poly.append(QPointF(t[i].x,t[i].y));
+        }
+        QGraphicsPolygonItem* triangleItem = new QGraphicsPolygonItem();
+        QPen pen = triangleItem->pen();
+        pen.setWidthF(0.05);
+
+        triangleItem->setPen(pen);
+        QBrush brush = triangleItem->brush();
+        brush.setStyle(Qt::SolidPattern);
+        brush.setColor(context->layerColor(this->zoneNode->layer.value()));
+        triangleItem->setBrush(brush);
+        triangleItem->setZValue(-context->layer(this->zoneNode->layer.value()));
+        triangleItem->setPolygon(poly);
+        triangleItem->setCacheMode(QGraphicsItem::DeviceCoordinateCache);
+
+        this->addToGroup(triangleItem);
+    }
+
+    this->setCacheMode(QGraphicsItem::DeviceCoordinateCache);
+    setOpacity(0.6);
+}
+
+void PCBZone::initQtClipping()
 {
     this->setFlags(ItemIsMovable|ItemIsSelectable|ItemIsFocusable);
     QPolygonF poly;
     for(int i=0;i<this->zoneNode->filledPolygon.points.points.count();i++)
     {
-        poly.append(this->zoneNode->filledPolygon.points.points.at(i)->pos());
+        QPointF p;
+        p.setX(this->zoneNode->filledPolygon.points.points.at(i)->pos().x());
+        p.setY(this->zoneNode->filledPolygon.points.points.at(i)->pos().y());
+        poly.append(p);
     }
-    QGraphicsPixmapItem* test=new QGraphicsPixmapItem();
-    QPixmap pix;
-    QPainter painter;
-    QGraphicsPolygonItem* polygonItem = new QGraphicsPolygonItem();
-    QPen pen = polygonItem->pen();
-    pen.setWidthF(0.01);
+    QList<QPolygonF> clippedPolygons = splitPolygons(poly,100);
+    for(int i=0;i<clippedPolygons.count();i++)
+    {
+        QGraphicsPolygonItem* polygonItem = new QGraphicsPolygonItem();
+//        QPen pen = polygonItem->pen();
+//        pen.setWidthF(0.01);
 
-    polygonItem->setPen(pen);
-    QBrush brush = polygonItem->brush();
-    brush.setStyle(Qt::SolidPattern);
-    brush.setColor(context->layerColor(this->zoneNode->layer.value()));
-    polygonItem->setBrush(brush);
-    polygonItem->setZValue(-context->layer(this->zoneNode->layer.value()));
-    polygonItem->setPolygon(poly);
-    polygonItem->setCacheMode(QGraphicsItem::DeviceCoordinateCache);
-//    test->setPixmap(polygonItem->);
-    //voir doc/qt/...
-//    polygonItem->paint();
-    this->addToGroup(polygonItem);
+        polygonItem->setPen(Qt::NoPen);
+//        polygonItem->setPen(pen);
+        QBrush brush = polygonItem->brush();
+        brush.setStyle(Qt::SolidPattern);
+        brush.setColor(context->layerColor(this->zoneNode->layer.value()));
+        polygonItem->setBrush(brush);
+        polygonItem->setZValue(-context->layer(this->zoneNode->layer.value()));
+        polygonItem->setPolygon(clippedPolygons.at(i));
+//        polygonItem->setCacheMode(QGraphicsItem::DeviceCoordinateCache);
+
+        this->addToGroup(polygonItem);
+    }
+
 
     this->setCacheMode(QGraphicsItem::DeviceCoordinateCache);
     setOpacity(0.6);
 }
+
+QPolygonF intersect(QPointF topLeft,QPointF bottomRight,QPolygonF poly)
+{
+    QPolygonF rect;
+    rect.append(topLeft);
+    rect.append(QPointF(bottomRight.x(),topLeft.y()));
+    rect.append(bottomRight);
+    rect.append(QPointF(topLeft.x(),bottomRight.y()));
+    return poly.intersected(rect);
+}
+
+QList<QPolygonF> PCBZone::splitPolygons(QPolygonF polygon, int maxPoints)
+{
+    QList<QPolygonF> result;
+    if(polygon.size()>maxPoints)
+    {
+        QRectF brect =  polygon.boundingRect();
+        QPointF center = brect.center();
+        QPointF centerLeft = QPointF(brect.x(),brect.center().y());
+        QPointF centerRight = QPointF(brect.topRight().x(),brect.center().y());
+        QPointF topCenter = QPointF(center.x(),brect.topLeft().y());
+        QPointF bottomCenter = QPointF(center.x(),brect.bottomLeft().y());
+        result.append(splitPolygons(intersect(brect.topLeft(),center,polygon),maxPoints));
+        result.append(splitPolygons(intersect(topCenter,centerRight,polygon),maxPoints));
+        result.append(splitPolygons(intersect(center,brect.bottomRight(),polygon),maxPoints));
+        result.append(splitPolygons(intersect(centerLeft,bottomCenter,polygon),maxPoints));
+    }
+    else
+        result.append(polygon);
+    return result;
+}
diff --git a/test/PCBView/pcbzone.h b/test/PCBView/pcbzone.h
--- a/test/PCBView/pcbzone.h
+++ b/test/PCBView/pcbzone.h
@@ -34,7 +34,9 @@ class PCBZone: public QGraphicsItemGroup
 public:
     PCBZone(QIlib::QIcadPcbZone* zoneNode,PCBContext* context);
 private:
-    void init();
+    void initTriangPolypartition();
+    void initQtClipping();
+    QList<QPolygonF> splitPolygons(QPolygonF polygon,int maxPoints);
     QIlib::QIcadPcbZone* zoneNode;
     int layer;
     PCBContext* context;
diff --git a/test/PCBView/polypartition/README.md b/test/PCBView/polypartition/README.md
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/README.md
@@ -0,0 +1,81 @@
+####PolyPartition
+
+PolyPartition is a lightweight C++ library for polygon partition and triangulation. PolyPartition implements multiple algorithms for both convex partitioning and triangulation. Different algorithms produce different quality of results (and their complexity varies accordingly). The implemented methods/algorithms with their advantages and disadvantages are outlined below.
+
+For input parameters and return values see method declarations in `polypartition.h`. All methods require that the input polygons are not self-intersecting, and are defined in the correct vertex order (conter-clockwise for non-holes, clockwise for holes). Polygon vertices can easily be ordered correctly by calling `TPPLPoly::SetOrientation` method.
+
+####Triangulation by ear clipping
+
+Method: `TPPLPartition::Triangulate_EC`
+
+Time/Space complexity: `O(n^2)/O(n)`
+
+Supports holes: Yes, by calling `TPPLPartition::RemoveHoles`
+
+Quality of solution: Satisfactory in most cases
+
+Example:
+
+![http://polypartition.googlecode.com/svn/trunk/images/tri_ec.png](https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/tri_ec.png)
+
+
+####Optimal triangulation in terms of edge length using dynamic programming algorithm
+
+Method: `TPPLPartition::Triangulate_OPT`
+
+Time/Space complexity: `O(n^3)/O(n^2)`
+
+Supports holes: No. You could call `TPPLPartition::RemoveHoles` prior to calling `TPPLPartition::Triangulate_OPT`, but the solution would no longer be optimal, thus defeating the purpose
+
+Quality of solution: Optimal in terms of minimal edge length
+
+Example:
+
+![https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/tri_opt.png](https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/tri_opt.png)
+
+
+####Triangulation by partition into monotone polygons
+
+Method: `TPPLPartition::Triangulate_MONO`
+
+Time/Space complexity: `O(n*log(n))/O(n)`
+
+Supports holes: Yes, by design
+
+Quality of solution: Poor. Many thin triangles are created in most cases
+
+Example:
+
+![https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/tri_mono.png](https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/tri_mono.png)
+
+
+####Convex partition using Hertel-Mehlhorn algorithm
+
+Method: `TPPLPartition::ConvexPartition_HM`
+
+Time/Space complexity: `O(n^2)/O(n)`
+
+Supports holes: Yes, by calling `TPPLPartition::RemoveHoles`
+
+Quality of solution: At most four times the minimum number of convex polygons is created. However, in practice it works much better than that and often gives optimal partition.
+
+Example:
+
+![https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/conv_hm.png](https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/conv_hm.png)
+
+
+####Optimal convex partition using dynamic programming algorithm by Keil and Snoeyink
+
+Method: `TPPLPartition::ConvexPartition_OPT`
+
+Time/Space complexity: `O(n^3)/O(n^3)`
+
+Supports holes: No. You could call `TPPLPartition::RemoveHoles` prior to calling `TPPLPartition::Triangulate_OPT`, but the solution would no longer be optimal, thus defeating the purpose
+
+Quality of solution: Optimal. A minimum number of convex polygons is produced
+
+Example:
+
+![https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/conv_opt.png](https://raw.githubusercontent.com/ivanfratric/polypartition/master/images/conv_opt.png)
+
+
diff --git a/test/PCBView/polypartition/images/conv_hm.png b/test/PCBView/polypartition/images/conv_hm.png
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..e389517dd989104690743a6c5f4eeeea64a8bb72
GIT binary patch
literal 4969
zc$`g^c|6qL_s6Y;>{1xnmp;h8)F+H3WM2oB>^s>aVR%~y*|%(Ev{_4%U70k=Iw;v?
zD8?GY#27Q)^W*dV=Xd`(_nv$1dA{!B+{b;KbSn!ZHWmRE8X6il<C`~ZPV58?4Xq{<
z-N|fP$V2ADF!<=2>(bD?%Q;7JW2B+s5i!1@YxmIk&y$~z=hRt~=ZL^sc$-CYwp<4N
zFei=Q7R>VcAp|bw6<h`Y$4C2?)Moly?C{+w=pUWO^i)sY?an`+h(G7#o9WZpRe^L|
z<hnL>i*^1(?OZ`@^bI7yNjp0HlObNYX4xmL47I6+WWRQn6@JF(+lpQp3Rz^X^|4CI
zg}v*=5^krB*9D$@PpQd%+NxVGw2FL`k<M~PtlcRywOa;*CB7AoT~M<A$DkA;-7Dn?
z_2YJ#y}{0HO8!vBwSN()!|IOuhTDudF@@FNx$-ojuM`?!S$qTwG~ZGANDKd2XKxv$
zT?{RHcF01$bsSbnB7d!9f^&$Osu8wBZPaEcFsBaxu4OkkPs2tdss7<YP3s&5rg^ub
z&E~<l7i7F!0{)jo6un*%%2M|_0Q3$tdTiU`eM=wUt`!IXm+SK+?fy7Uj@gRAf-%_4
zKfYmg4_>e1cI4_7%251s-<D5y$IS`S#CLm%835OtriM}IwTY(Wx=TX>8${@vqN0oQ
ztH`a3^j=d=txA6)Kg_1u&)vbIR9asQ+#>B-?N3tt982>IT7D0HR0B@EGZa5CGPg<l
z@jWwg_Nyp?BQmrj2ZNlmNsoAI{1*Vhdc;eIHd~DZFNka$So>g>;^(aBtqCbYQP2Id
zbni*pEt59KG_aQiv{v6<TM1t!#JA~8Y-g$<kU@qH7;H{G1(D4PmmxKsYyGR~fjO`{
z%MuRmI`|M);{sXss%LRs-{cqij4#?<>S~)t0x6TVt)-uYfkKv8Igrr^b5QZj`l(6v
zQwvQh%bvsgS4~K0*r9lFc(hgjD(-&vCx64IimtO==^sIDd&f*;$<((vH6v}jlDtw(
zAUJZ}eZFv~%T8s-`AmrvhSGuT-`shq3?|NrN@hMoFSl3TgskQ;I>-`QqJ{Slh|fN|
zciSDZ{2cuI^*iLD&r`hM!0KphS!d5@dLHJRa$0|@Ns!wTJTF6XZO%7u-3{)pc)E(*
z8T;PKe$+bzAL-mYQ~dtmAE#d--@Bk38mw`bwzdl_1}sJY!S-LxY*AjG4A8jxq?tti
zSo_R&J4;OX3T%L+nR0mFsV8Zu8_%`IH~DT$aq!YdwzqTvgtR#P>bJb}qc7w!*g%Fi
z-ktnmXZ@#Ahvz6yi&NThj`)|&*%m>1gS$Rj+z5FN#@qU_Gt1_KJV&_B90B!f=NC1W
zo(WQ^uCsMjfhtaC?z523SJ9Od2N1FBjOXw^T2`_4CeO_tpz1Fhi}CxEcusFv<qiu^
z3txsD@roS!7g3ql3KVGN84H)HhYvxu<<H&DJwA)~BvtTl_W1j`K7}+|zS)9Yc?pe$
zW!k-Ls}%^rmkS-T+Mb0=^p!IdRlX)c<Sr6J*NITLnHBS(75K@B;Vp|4>%+f0rX^CH
zX1zX4inPJp)?#HIm)AhX(09DfODyW<&6j~HelDfweqg0XucsHmC$@a}1JI+w``NS1
zHwJu7FBW~nLz~L!WR{YbJl?Lyb4NNFGvuQa6S4mK58J+ePp$diV~(EQ+mM0vFxZ9V
zlC`biKT}Sd@%qPBV-)_i=FW~u(rQT%pYr)b5=6*hau%I@#s+uu63>-z@LE+D$F79x
z6$|I?tBLIT4ojmNWr8$lGFD5rJL(ahI02{RtPd1t_-qa3sUT4|8L+xi*lndB7!$E_
zuI`crOV5b!U$Jbm><2l{rPD(R;|^rayok<t+?y*}<rMkJ;`{eNI(x6U$_U{8=w|)$
z%7;nzfpb3kAR_zx^46Z=_=35Jqy2sO*$I5p-YYdEu;aK}1U2_+;hwjO54;Lmi3IQA
zczA6$!#IiIutSJYLZ;Vy4_%_}t-K&?%Qp(fIaieWJF|!0%w6-1vGGCfD0bzRfkn$N
z(kf);qL<i~vza<xU_?Syvx_MFxl~H1l*Ia3lFeald-76ES$1G0$@a?U($smEqXNSN
zEah59UUJ^h_1J~tW>0gyY^y}nRBFi+nPWS?pl?Uk^u||z40Gm||C{oDW}Zj;qEvYe
z6_n=3d+ujG=~pLpexA4v1)gNf#=UG>MN+1_sC=n3H~bI1iWYZD`Ql!dQH*f{afMP*
zO$dViC4Pq5*FRmfyWzr&qypBIX^8#J{fcplXuy6z)j~({Jp-}+DSwa>$R<wOXEpu6
zB9^h&QiqRpDx=)w-NqhzD6G6^LcKORqdgkQ-G@HfD68TfQrH`4y>D3=i7^cn{1@%u
z2O^{(3>|$7wbnw}OUv+dJ&M+dTb#s1ly*2Y4qNqD!eYT;*|bJoz8xsW<zSQ3uUKhz
z$!Y_HvkiN1%+^Ha24R{x{pJqvuxBw_t2up7auEGJ{UJ}18ucEU<{?x2cO|>DaT9oA
zL3U;CU&dSN)LapmL|If&yUJ*Y<uH~I>U%e7?qcKE7R43P9%zHkZdU0hXR!pO!u+&q
zE_E+nF*na{bAyfeLPq_5Rz`I0XlNK^sxiQ$LtM<*;wQ|niT8%x$xU{vGQgj89!yi1
z>>cg*`;+iv$f(_t&v4-{nfRSpE`B#4yfH_@leiS-BM%L#zIq`NeCi$d)PAi=al)<<
zzx+AfqSmJI`WegLJNq{Fw_Xn>p}AhzVIr0XBo$V{kEp_&xl&RppMXuBV(W*mRhc2(
zXJl1FpQON5>hu$LJPpqbgy&1tt>^E!Oz=T>cxr((EA5d@Q^FQ^52+mGimnZNl`Zd|
z5ADGqzkIEfz_{do+g2vuTbp@wT(wCU&5G7@B^0}M)-K0EHVC5(I!)~)Q|I`1a4gCY
zZL>nwx{Gm<vHJQ8gZ$PQLOO{dqC(Qr5;4MV&U(IB6mwOV={7N34G7}nrYlD=jGIdm
z=d4iFQkt6=G=PC~ijQ~5Q@)OMa8z|Y$&_)>@dHUk;DS6hSpOKj$j)WmND?15W%@(b
z=n0P;IId{Gjk4+gKS4w&56!?YoI(`s*S%P(0Gnyi&MB-`hd)CDFhqY|A>XUPQa_7|
zv8V&dQOwU`sZu4|@*UXm2}+0CO{PGQ+f1Wq{uJgzCvt0^BB}7nv3tkmg<I|3DNKR)
zvd1oN)Yq{cj$+#<yIj3-qX(Cxs36+BgJl^1DM^g!EQ4yWGACeM64$Hp|AU#)NMw|w
zmKphmh{pk{a<J}G*eg0OxdjS8+qvSMwr6qFbE#>Urzu=G$>f9Ma@WqT<v2?R!YV>k
zw2@@0_|q=z6ozDu_Y5Tzf1vRobpu(5SA(Z8lwD<JZ#ndZ+tS{#`i~u8iIa=59Qye~
z@>n;(V-{IFzq9TS&MQhVr~}MZ<tE#wFcsQdxgaqAqO06VJN2#6j&uquW+{C4kl>>#
z=hTfw933kNiamEF7?l)r&Ju$Y*SGUe>xzURl0V@Tdcti7{)0);<o9A+_UJNK$e^0Q
zV;Srz%qBtkLNJ(#NE!OCt||IA&If`_1a3VtXs-D4ZWyXMKp#A~^F3+mZN~xRo-CNX
zAJ|%*^Z|oAimREA)NT1RzT1fL+Z~=)*S~}h9KweBz+x=$an61LU<gsKC`bR-Ui9ry
zpPlG#ew80Vci)+hpqAV(MBnf9i?~|Fo>^&j9e*}%s|Mg?zs?}d=5Az-OFEPV4bz^C
zVUUSYe%a%F`VvHZiEciV+CylzTT1N6%@zu2)tNbLVK{_xP1<5%bLs9gU;)`ex{r2P
z(qPe!@6U^JZ|2u7L%r6}+k6-KuQJg6;h1`-`W0|NXfZtQFuTB&fqzf_j#pI!O%Q<?
zb54^V9bw|gr5%Ar&@<HU5j%(Y=U`WKn20ZXU<J1cs(?>l^6TOD`Esc2uju0yYw2s$
z=C=o7g{awcC3jJcME+t;s{4aaW9TmnZ=v1?iVRb~cYa>0)}odqh1f_F+ekm26G8&P
zuM59Y`5OcsVqY-DQRZV46Eb#-*T7?19-RgJP3PT{=ltpH{+$E%ro~=q?c_7>71vED
zKVM(Vk6*o=*SCPD#1Pl{#6^uJC{b`ggpc|7ez8G?eom-@(hyz)ew;s@AZ>h&v<;;b
zr}7Fb8qS=AX$v6=#T#c|tcBt&hXp8XQ<~=$g`T=wwuqS~Njt$!gJQ~|<q^Db$BJJ9
zE;nK{Z9mcgY2|5%ws-v*P-VI2OKeLjsz6ODI*Xmr_f;PIKgqs^5n^CW1js4O#kMZ#
zNLQGLiFY|pRzqiwQ?h=lT=^~`G!^$kr%ps5lD_WKcS-_#qB7DedpVmkAlQ}J%KMG{
z4-FvFyOX%e&fstkch<}G8-G(LWoco_q#()jwlbv~rg^PFwe$tI1~6q|GAU&oHX~fY
z?@*Vkyz<W=azL$sFVv{Ss$`?%zU}P-zFnglKXAl*uuamEDUKS(s{VqOH<6e0{>W<r
z`%v0!MY|z);x@T?BTq=8Y=y-0udLaACnPG&R<FR3?n22+LBPKH^-*MZ&0g}QhDpSm
zXigEENlGk)uNC4Z8X!|&!ElcCZ7&inZqz>@piRHFuU{pz+W(tLDGSF5{0saen|D4!
zA~gAGu5!xxU!$wp3MMh<O9dT@4%oIc!dRIQaCu<8Tm*toAwSnC5p0s7bi}4}gtx;9
z&#rd^kp@ePMs*x3ZztKEfUNg143Uei6s7E|?w3SWUIQcRz5`r)_cz+pkZyYEgwcDi
z#K*Xl(Zs1I*<S@k>nx!%mV2c8<!guXS+%diC{j5sTJ;s0p*~mfx)i0kGPh$d3)=#z
z-C98&*>Lev=yyg<K?fGh{;SV-dW$qSyKf<^g?ofMs-LBY(M~H~?jju+Ep({4NdYfo
z7s<jdy&JVRa+<Szx67AQa?wE}E}f|1Xat6X5xoINxTW{d>wN7(OBP_I^9n;aE;F<8
zDNem=CRi#Tm~$J)G3$Hg&#2%8iqJ@ZTx66T$vE6@>3yGBbATJ@9c*BbBQd(=_MX#h
z(Nb;0O9&RmtU4=UyNcO6`CXdKeuO<J_!FTs(O;)&FMF`0Fr-`m`z5Ga<?jy@+6*tp
z7keQmg3`e#$BD%{%}LtGMTMd3^;3GsN=^O`P9idg2*qAcCVV?UrFMV#iKFBjg?W`?
zB021>){yADsq?5bfZ#xzI4_hu#$>xxp$fD+7!=6_*+rSDzZrCSbW6$y{Y6IhWSOJ^
zNOj3Pg3Z_Lm1z2dW)EQJ>)WkYl%mcLBK`GXLIt)(y)ycCQ6X>3p!4;eCcGMTn(ek2
z;ceL6SC1etq4`=I2eGcfrZ-E5WBW%mr8g$ItF)$YTFls8`58%N2Ie5AYn1<G*_z<f
zRNvs3k}borW+w>L_1Hz}B-!WH23oJs#@@+9xkl>nWb{kmZsso{PSs8nafeG7hg6?Z
zH%yrS&6oI(IzeYrA*7u&P*rqzuJ!A(2bWSX7qZ9GfD_2Cl`uBjmXm($C}B)@dy0}^
z_(rs#QrwvCsD%~CtBPNkDBLyN<qz>W&8SwWsRcjtpLTyXNlOkSZDbt@{qeT`z&P6H
z)6++bImpz}`0Gsx`E41aG_%vE*(83iFR8@GsR5PNvI7sJ4_PZ+Fv7k+Oq5Rq(XUO>
zQBtC4Z?`6As%EkFUGWD)-rC#b)8sAvPqvAPkcc+@uc>hGQ0b60jf?De6Wbp$Ho8IS
zZKo+~d7Rmt&3g8uKdAF!vLNr|)c<lvD|3q|3;wNF1(YttTfDjK!RqNA`d=aT3t9Ee
z<hFk}f&KjbA@eDBi(V#pUj5}yNNsPfLolSV8adSuxqQN>>DCAEK}sFR+Hf4I{xE(t
zC(pT~iPP)Ic<{Nq>!Qk_V>K|Z(`0K?H^7qZQpb?J(L5z@<#%aljPS4TvjPZFsSBZR
zNcv8<@1PaGd=YCn>9qs;r-WaUC*#@MFD+z2$I@mzk^<%oAFN9^Wz1xh#DE=^Ei)d$
z^cSu&ZCA&5xk^iy#-oP%)^-(QwPFpF-fcgJoK=n+nci_zdz4no>^*Db14m@Jg=Kyv
zr(+kZUaSsduaDqMN!I1i`FmFUsPmjJQHSDPstG`_;0$wn(P&;RW!V9~apNn}|8qCs
zqseQ~N|;3;pno35QU|%@nnbh!N&<YnWnO_~IAwAbZP~ZcOTm=X?O^#mFU}O^qoTz3
zk7bP-`<qlL*VvuwpV=NaslQK%YekB1(}CWW--$b{^BI9zD+=D3-M|Xdg<DUMP<%X$
z|01rqZs}K)*zpJ5-T@a+Vk~t;r=$Oj7Nxgsf%sOiN6fT&_ab~%yS(C8F?=(E+nW@n
z*Z;}IzV9TkvbA5`8VsBJLw3k^%}ddvydut0{`6rzs_8-YZ~A3qacqyY^zhx4`}^Y;
z#-IRoU}$q@_1YK(LuggWx#SCe6>4#>pvPb}gRc{&6R0$qG`<F*vM+wnoD5?FiyIAk
Hu8IE#T2Cig

diff --git a/test/PCBView/polypartition/images/conv_opt.png b/test/PCBView/polypartition/images/conv_opt.png
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..3a0b9f1df63206e4349d161cefcaba37058484e5
GIT binary patch
literal 5110
zc${sQX*?8A_s5Yfq3nB>iNcsMhHTZ?mt-fDHCwhU*-AAk`wX%sOOou_liiezoylHy
zW6N$v7-swH`M-HyJon8x_s#u&e!p`*_nsSXW}?r=BFI8RL&Iihpkr|sCunGBZ!puH
zWxp=F%A5syPfcS@8k*YV3nUi?8XB%jLmf@4aL1k8nbei*>^kjK>PYBusf}f2s(~2v
z{43z#ST|!;y!M;&S~3bwB_HRXTCxmUEFw_<AM@?vW&Nf1pC4zk6n)cSNI=D7Z8oRj
zFBk>EA@Ca0<5IGx#9~Hs%<GZCbUYN9fFi0oWeU@r6Qwn1$u+_qhq-AtPW@aQa0%nJ
zCy@<sX#HQ@fXC5F(UJ*VA{F3nS^l`iV2I!Yy9Cr8>P6QV*S6v-?ktyA)HP2v^PF9-
z2FXK|iYJ(>ok(RA_NO`puOAFYJ3k7o{sh=>!mn3uOupc;E16Plry(|37dc{|f#5Ql
zJAlvir$rjL<3vqP0=tAI&p~jml`bz_K))&*)Ql9`EoVWXkVHMDIV^ZN^hw_BX~Pn^
zJ46G*AM&v{^l~kO^(YS<Pz*qn3D$r9KxMMvxl8KP2V5x4uKoPstw#BD0*Yg7q|0i^
z)^cd?+JA42aaX4x2a##iOO>frNBOzlb{Z2%cZLa~sjT}N?Gz=AjMkWj{DTQqAN}<9
zsUU`R1uH_Jq8F|G(D^YL9OhQgVf*_y<p*lnS?K&VCnm!R*XhnL{=gxx(go^@8ZW%&
z6X(YK>p#>JVzqGUJ(nWEB(Dob9aJl*97XXWlEV{lum{&98D3H0$25Bd-3=Mdt-mp$
z;osW2d(M&0x)~74x-b`4o`6D?<GIuT`vogMOl(Jel2r#R<+#Tv%hki!i?^<yKe04E
zC~L?$Rw;W`{vbTzkSv>SqBL}#gsZSBb;XOS1Z5txBzns_c&G(XC0D?nhF&Px+P*&f
zMvz(W;{#P$`5ZGo)-1eW$1$phB@I%rvcKB4)_YF0kQ3U2-BSbT8K1PB)#We0b3*U|
zQ+_XTA>4z+^r$sm{#EGf8Mf5)Kr*mNNZ_vb%oc7>JG!sN?1-Z?bL>Kn<F~Zn&YKGP
zu<)Et=iee%IprZCHu>0U*_1(N7ADJ7LCJ`6whDn+_^;8?%tzx0<sa$M2aF{LlhVQu
z8pkGK7pFpA_<ueuO2f;#^@9~6YaC;oBX;Op^LXK~v`rZX({a348Ov~wVV7tCLl}tI
zC41>1FMlZis)pZO#kc!y=#B$S;eD;PuPuu3LXN))=b`lK-aVchjf7VAfscani<&Mk
zZwrDp2nSVBRs9a<DnHmNK1snx+B*4FKT2^pM>Gz<cSL<I?|0Yc3x|x5E6Wyli~?`+
zyO6DILEyLiu!08`x7+N4VD9PkDPP9eM&%lO<ln(upX=3EInpvZ72)A@n=6+5u@4mM
z{ohf@TXF8hC+PWeU|E5e;EZIAug<~BlVwUoy#b5-TNQ~`Mt<6U$V6rDMF6YcKJz2+
z=tD0>S&G_^hOMT*M9h5g$mm0lRZO_fwp}9axuh5B(G`U=X3wH%IJR}~0p+fHS{4(h
z;t*gQi%m^Mq3+4!!-tTszqsMW4cOE=!a;|W=RB%A&%4ttYvhRZMCi+}`@XY8%qxU!
zt>mJ7)#sP(BJDk^09&8v?Y7mBomR%T3YB}X3!wSg%&a%%3RgcAR&+GyH_tP+9yz?m
zVl+!^h8m7Ue>zMR`9vN}IoQn4&PB3YbZ60t$bF$k?oNXYG^Q3;Hqrph%q=W%Tc02r
z;XTxKSzDMPfhco}lDxGtkf=X+Ax<?PWk8=V)|$6lCM8zEz-I%=j06camBj!qjrBOa
z<`FwC<69<14etc+aJ8fd>(sYGGimJ=+HagZfXrokkBL6+ybTjJ9G=brPq>==0s@<!
z(H1RMBR-g&?s|A*q=Gm?jc%G&Z(UN@A6nllqcgNg$-QYjH5!NRHo&OVUxoBx{pXgl
zcFD?ds9hFe<&vr1P?4QXNXAV4n+!g9Xxa13`R`ZS5OQo0Ghc4JTFUCBw9Z)vFnC5h
zqeq+$Hf){Rx+Dl}8f}txhv|Wo7aqp(1WzvZXg&U1U;}|`Sc}FfmF&k?L};B#7)Rft
z8F<ZzxL(0v)8LjOeY8O2db904c?@<sQXj%+f!bQS-JbA;UBB08Kkzyah&2#DkM;93
z8`X4apJO|9e!7#i%?($&fXG6NmO13az!t7FwQ-JzuI+`m8b)Q(*CxwJIo#omm`aUU
z^G(=GQv1-UcBSQ4&$kP2p>K<1I>MG_5wL+?+Z?N~KwKEi#E}mm<q|&+OHAZpS6ZII
z)KQ0x()^{jDH-W32PrNbcoty}g35xXv$PZJo>CE#dM|z4P^LIr*q#xrg^P{DY$drp
z-+$M{{6vHk7nbYMQ50DzCT$VttTE6yfmbV)0yV*HmXi4#jOGR8I^=J;;?`fkw3&U2
z@sblRk%U&q)Hojzmq{#3KG+a};5plv{ux$pYP-C`2;`wc@4_MG!m;4XvO5!_MTMF!
z4K3}LmpM|v&`t~aAJ6+sf5Z0xOvUU?!6CvN^*QN^{0`7daQY`O{Uq*+rCo>dNYD;;
zmA1!=r@4NoF8nI<AE+DEW$R}ZqR7-w(MYdy=v#&>ArEeUBr9}pqGhYbPYmc0LK)^O
zFyk^Bl*h*`pc*@s?zX()ce!>#Xs2D(m`&gcn3z9U%+PkHf+|=9t%a>iQdK&OK?N(%
zT2B+hsRCg4_^wnj5W^3ob!A@QTB`Co#m}jKUG5txSzZjw1*vNzc27~?2jVFaat1*i
zl9~#vYa1W%4MnNfIN)t{P8=5TvKt03bXKh)v<R49`@;pYi4Bf#=u%oW!F3$5Kj*I%
zLe&c>>^CQsr6c1lkNuIu*+61m71mT+?@l@vtmk=S;00Itv8ai5n<tL1S~ab9*Xe(r
zb4Wof>SYuXETsjwN_H3c^OWq4)E&;=HDuN`v=eeTJd-SCwFk?M3CCc;j*q2W=TOL}
zBOU)(;B0XzCtOb{-%{&B)Fzqld!md!uEat?%47}&QS+(W4r@t(u?axT6HxqlI3Uru
zbRMq4hI@~8YFoS0-2xXl{P_I%jOC=LeWwGPY!2=WL!F->f?o+)Ct*#C-0tMIz+HnU
z-G1){^S}ia9(?46L)4b-j&jV}sR4r6n+R0+&^u%ZRbf+?xO>JzJ&ehEh88V!jN1FB
z-HBegTo|2yyDv*6gxdY*b6?%Uh73i~txHFm@*udoep|WVDRoJ)D}on}%Z3VUQQXH7
zM|1yJBdm~<gfrWj7yfBSF+Z|WO@L*jLIO7_i6eGt?x-<ql2>nByafsU2kH6ypNT)b
z;*Nn7tdgg~Bzd5eZ>RMi>!ZK}JP#cCl%wN6+Bs%RgSg=`lCIcsvQS~Y)WD093c}bM
z4z3~sVnhH__s_)Gu}gb)B(%@4+h^iibMSQ7Kb9`EYekmAe<<<n_@8!(CiB&66sz0a
zU1daNJx}Aze?=`32T0w<@fAYfyZ<xsVu|>CJpnP5+h=<WE_D2|_m73}i0iW<K{j;>
zyZ^N7o;45-y->yc==b#9<2}Q959aqPev?yEqrYQO15bZ>+;3B8G`3t1X_SNO#~Oi=
zVbck)33X%P^~LSXuRNYdR*wsfYd@GTUH=WA`wslVEL0RagY4AH^kkwS^F>bhTpG1p
zOBB?)nNGzhsVHVSp%#J=Tq0Khlpo8xx0_u{&oTXLi#D5QQdMFcPrP_J-hBaSM#3Kp
zR4FWa=quCpIOV{CE+3)KZOsG(ryL(M)x(@l`xZDun{Q>K>@3}yt|sT^A^8WQPg=Jx
z`sUFCdf$ZIml+FTb=d);7ZzH5{{kg((Ir)cA3Wjtt8p9HL-Ntel;iTyRWJLAGUefN
zqW>kh6aKuNKwxvS&nzOT>xCiZk!f2fo59CE^IJ(h#6`)8+u?XdY070D*FP@L)Gr=k
zF#}DLl#S09r)f28zo9|q0mP$D`GLbDClbx}z~G~J<E;&fABh_9k-rB`K*Uz#mQK_P
zXz(o=taGie1Ar9a&Rd$iHwf{uKgBbLf+Z<}u1QxGm26g~w{}rH{!3U)s0sYO2(z9R
zym>1>;k`Ad1XeWPo!}!YR834D3PY;qaLb={`L#JijT^^kQ59%+rTSVGZ5kOH(Z};{
zx{lfs$x^haT^UFX^_*2&%<vw(1&qLzWETRG+*^2s^!u5{qC^)f;BmkjD$v)?*MQO@
z-NNWbThc0-g4VOX$aPg6&MP8!9jSN3XRRUGE&Iz6TE@EJNIGN)HeXfPT|Yw6+xu{W
zG*+{+Vavcok1RKhfN$vgIgsd)!5oK&PNasesC6cFL46;jzamsh#3l1BtTi;$=<O>v
z+tGH1@|#U_qmoJeO@vk(3x(^3Z)Q%nQ+6_CKG_GR;@2&P+<ndU`OWw@8-i?X-`47i
z78v8gcr0(pJ<-_nmj$qxiD#w2svRAPF`=Di`z>|I$@?W!^A@kWJf2XZ`dPHwF?yG0
zd49SBX$SbPh`=3-+Kx<HO0iLLHvZooBLEto>~P0&&cA%4;@b+^j;`419ov&=1!+Ni
zUIb>n%8O8IH8J)@tT&rHC74o-)Jf%LrfZ@xXtw9X#g@H(;$@R!6lm@JIdJg8!=Hcf
z%_QS|dOMo6q$dI{bc1#KOk13L%%!u0KS|Z1!`FOCtcL}p)$H$c@X>O0-zJ7%wf8xl
z-@Jn9aeU(opiK{Hrjeut!5i6i+A08rxM>nCl*S%uk?Nu05{cN{iuJudLcV}tCS`W7
zSV+&uEz4nisM*;#p4$*O6{6Mj%%NK=-l4!=w*?7ym+z=bn(j_J0a(|x&d5b$9~5jC
zP0RVqiqF;VR`qCbGO%miJ{vQ$zdQ7bBr*sMz3&IiNjhL=;m@d<%)CPJ>C<AFb#mA9
zw)~G`_t!``u2GBCgh{y$pP$A(`hSWIPAO@@^Xw9anwv%~Oo}QtMP5YH(NI9#m0O0%
zUC)D)A4g~Z$S+?nQ7I>IMiRsdXL7Gib&?X_vtSbCJO6liimSXtRo|7In`cbX;SB<?
zDpfg6=tO!nV*OnSNh2M~*Swku=S+q}_)`tVLb^`vr_+NSNaE0E8IB5!pW*~=;k#i;
zsF{i`_5R1Kq6`bG5^E7KiT%K~Wuh1TW7jq-whF9#`<=hm4b=&+4LQhUar=8*{%m)A
zn&0ZsF6l%vPOV*h7!Kv5%mXPJSHd^GclFI0h}=qt;fIV8-m{9A3+u6*lzeGS^E&p&
zt&2>gJ;$w^S%fU|kBF>RIrkeB2r_-P{6lHI#&Cg2y;DIlEQ-P0n0~T^@Vdxo#g_Cg
z1_$Dj5?*tc2{Z=Wxiq1|Kjg6sBXH5D<)lbAgQW~`v7`n-aY#@k0Z()GYsMxs?OoNv
zO}(`UTBIo;W>osq_6BXyb-8pQBB(c&*8G0?U`p%XRNL@Qs2IfaE@LVb%7*Xlf&vp@
zD@)kaaJi=hZwD+l94(qWTg{AiGBWFX`PdM6d5>jj`_!QOyO9Ew>`CRB27#&vK5`&A
zl?IU<R;Tp1sonlx^&@vAhY|vjoQB=vBPE2i-YiLjvl;L_<(ojp5M5`R8c++jY<Ac<
zNU85F=XBpt;Vno&ZN;^ghp=VF=-EEAxi+t1S1ErNz`gKTS?dnqq&_$r%N8Y}GmDyw
zX@z~am0;GjyU7i2k2&v1s$`!rCZiX?=D^tax4zm*KQqH2ascfL;!w<$+v;((?_%CT
zv^2m*pB6J%xo!-QXTs@XylUz1cT42!Koh(ap}b?K@~hgx0R9|t$*oMBIpe3S?i5_=
zBxPA?kpJaMH4zb2zP?2IZORFLcRT$ic6PHbSzFdbg7OHH>j16<3F$<<9hNK};Lof$
ztJT1+E$O*wZwS($ua1l3zNmDuPe6cY*|8Inz9#fU1WecRH(20@1vk7V_=3s{HTXAy
zry;bne3240Iu?U8<epvF2U?4|Z%d#z3EW)#`8MfoBnHJj9v@wzrJjcAH?*udZr$1!
zLd0T}<@LZ$#h4n8zoag57{!hMC+X^?@UxjA{z<cyNI11~0<PNGQMCr^${Kn6S1bWV
z76($EK|TKB-A`G4^f0Eg@coEYXn<Br6y%jiqP0gG906P2-}aE#t0}Dgip5+TpZ-s7
z4yJ|o9AGz+Ym*Sa|9q`2pFDhZC=8jk5vU}6k8;U#b=<;3T7vFis`&1pfA3|$b_CT&
zgJ;5RL<0nFb`~w4drAjF@y?txoI>nkp$6{$P)DMsyFb@t#o4tA8kfXZla)agVHemd
zyFioIGeI{Ux<T>tfF9hsRzNO2sQoMC>y}p|eb>9ee39=3GBll)yAQ_49x_%y@?n5i
zh0&2b_TwWTOVBaCFa|g;{kbn<MfL;j6`oTXqyD^<7Uu3=@sZ$oF~6HX#!b4Mguct`
zW`2kT*A;kv8gC}}i1ACaz~)FC@Bgw+s*1o(nHjfIMaAkm@84Y39qwI_dxaZ)bIxS<
z1(X1zIvVWfe<HO5Y)M{yO@CC4=G#aPmvSZFgl<0h*uJT1J~K{gmryY;yz!G+R`oDf
z);E-5LciXBMfh2&S?v2UYlldbcJan-$t68&Jx)V)QeHi*KaZ#{`5fJMWAeP{5`&I(
tfQ%W5hZV|mjp9-6)Qmtqa4x2!(&|ps?z~}+7N9v>hPoy?Ra(xk{ty2)KH~rY

diff --git a/test/PCBView/polypartition/images/tri_ec.png b/test/PCBView/polypartition/images/tri_ec.png
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..a63a7f36c9ece261960fcbba5c9af20217503d69
GIT binary patch
literal 5984
zc$@)X7oX^fP)<h;3K|Lk000e1NJLTq007kh00BG*0ssI2*dAjl00004XF*Lt006O%
z3;baP000*kNkl<ZcwX(DZJXY<3WR(9|Bvq3&9im9vL%LL^k$P!xl%wd+(ME!ZU6W0
zzyJP|zfyr&3ViXGzfyr&3j8x`;aoQr_&$46g;Zdo0?FS*@pI{%e|`oUH+6row|nIL
zg9tb?cYHCpdKP9-=yw|>fA{?_hTLKF`E!JsS_H)RJvNY(FOkEXULbk5a+$$jB63k?
z^7kW1n=O3oH84s9Z*DB_+;-(ItRJaC@@|=n%+ZJSE9c+$j~{DI<v>B^92fav@a6aC
zDtyG)JFo*ONd!y&R6m0T8?b`e6#^G|$f#@I2v-mR%%KM!zm6Wsj&$`8th|%iEqvx$
zLFUf!C4!p?OAJ(PElL*i_ldrRtfdft1a4dey~iuq^)0kIdK%BRBY#Kec$Q%EXtQ&M
zjh)?zIsEla7btgBHMa|YMGH6LuXg`a9XB8c8!7ggg>=Gt{<vEd*q9z>$0gysr^k#s
z?T4No;@}x_2#Wc;O@hm8jG6~$=iiK3y1mNEqSfy7M9wn)+SjHPI(p4vHRd+D2-Z;Z
zp2Zse+Tau0Vhpdh!*8`e93zEy6;;Ot{F!)}2HxUT_6sI<zIQH|-l4pin`!U~72*#Z
zwqPnMs_-~VC3Y2asq~1u0fGn5AFd8=iK8R2Tp_XZz$1Dr(SZnpOXoVN(Vu_d%h%pY
zM9p#+R~0>0clAb|KqR0`x`wfP{vktkmwoIKG19HGZ)4!?q8l+&YS{Sr;~K_!srucB
zGdMBt)*YOlOK>i?tCxd6Zb@RVxP*up(-pZE#RuMl=U?sN4DsjPxVz}so4=>(7Mv+(
zS#18|O^Qcw%^TdfQ)2YM+hyMd`TLal5#QiX(jiF@oGRQ>o>*|;y^6mNd^Uf_ZjSs0
zXJVwKia*uB+l#*l4`<(B9|wvr1ri!mZI&dXEl@k~_Tn$zjw=}G_h)?Vt{uYDxV5A=
zMyG+d3xBGfCV%dK-&rL+vUBL|fdr4(s6;UM>-Wrw6fg9}8$4#<Z886D->pPbZpAO>
z0p6in2C8(43QZTJI@Mk`leroo=@DUrE~<tO<xet7gTlEQJZ0eJ{JXgi1$W`$9*iT0
zueK#74!rgGQ+2Zj!+ZH#Vc;cy9r;`E2tKYd3(n?c<@#)rpkfo|Up(nfNANNE7W_?*
zlIfUdXvXmu<fce8m^ZCm`*|)8O9wn|pQ{N~U=T^K;d}o*R=8Ls6y4Oe<02`Y-#v?@
zbk<EcN0Pr1$hrM4Ufgq&0S}5ul5YO!BlvcuNa~$NAYEWEpX;}tjl|(nZF}ke)5or_
zzQJ||-8n&tMURKh`X5{xuU$^A`TWfqHV7!3rby(Yk+mgyFO4S&jtnm0<j-gXC#%`r
z>rvad-J8)y8fZ5R$saegw5bmhU5j9wJWkkQQZ&*dR5D#!e;>|t2IqF;N-<K_##%(B
zx6w@Uww8iW$#hBnen2vnYHt;gynTlsm$|8`@%MpEf7gS~8*T7(B+{!rY-^blOROV;
zH+jT9`TNyhL^AVX`$+hR`G<&^{FStrs^LfNE)U)#PvfnM{g02qXg}N79Peg7Tq?Vw
znYnc`XuRUN{5h{q)zRbGRRw5l|NCHIAn;}9iZ-|bjg7?3JW!K~W%ipLV53L#M_eOj
zwdbQ?guIQ4MN$Qka_u@Le_(!~*(~gek#M|l>EEnSh?xV}6wnNz8NL5GVqy1FyarRX
z-Uf84$JC@F^e(N459X;g`$h|?Q@<)kDw11Q8?f-}$UOdph|sm7+u(STpe1OQ{29H*
zb*x=_yb;F3ho5h_C0;c&|G<UuRl$H$no$fhFo)VR#ia?jmfQ?a60t;V{+<tDF-TCv
z=6MHG`+@Az1nh;@%#|TxjMyZ9P!mll;|5S3J&nu~ya$3WAXpj_6tVFZ1E$x>tWi;W
z?Cmn<d$i0I6TSZ-H#XP8NWe~1;bCtp0?DhrNbuDMSjt=G4u}_NhBghZYY{GZ!g0%M
zdftS+_VJuu5xnV{_NGCR-pu*8{s=s)=^A@moWEXHkbZe%I`}h}_pWUQbZzAx#-EBf
z^433p<^5s;y4u!WfLMNU1S8}v&R>sa5iw=+k63%14t+Qq{L8iT<;FewMZ}!X-^dYI
zBkZ=jgqr6#$Jt#&$CXU-_oG0qE0JzRd~4|3b{FqrB&Fii_J$h3r8lMPzEXY4@Xf!*
ztm;vciA$$e$!m!OJU^v_n@aL3*AAd1_%n~-PMm3v-D2#OAG*5zl{2q6!Obw4zZxr&
zs=QK~1ClV{3NgJ*10vP7OXE2eS?jhCx;pp#>&G8mLqtu<lmasc&4lGNF30pL59IGt
z()9Ka3AE2#)g_%~<u-w!+VlClWrb+oN1emb+e=|rIQqGgIWI}E1$kU1S1&HkPxraP
zR7srU1otIZ2=^q6Y?Vm2A~l}(IahTtFCszy`f?@3`Mb98Rv<1tua}DnmvQX|=FKo@
zf8FP2dR!I7TYs*Fd4I&uU-J&(QbgDrGn6VZRU9+nYqL!8+cB5m53I_y`x|={QJJ&B
zIf$IOE*-c+8eT<>wUR+8z-V9<<oql615>{poV9BN9uq7z0zr>tdc?fe=o(jGO2SDo
zl)rX)E~O&Oxh~G~vG?ot)9r^MpH+yX7C~?c{?6r@Nh4h(#EMX8=G>mvk)_8VNT0K2
zvyRA!hQ@6&q9d3Gm?f<jQ38?@VnZyA9Fg&`jpV_)kO*L?*4;ExD#9P0B2sW9TYT!6
z13;CA>n4CN>b>XGBAXKdZ*Fx7ysE~=H4{Zv8OEQgJxEcYO}vq=-34Z4-XP;?^Y4%I
z4Oen?8-qog^0=UQYYR)&(q<gfz)b8D!5imRnJ)Zs=a*TJX<+t#*oZYVxo<}JIgChz
z*jy1jdo9f$QQmo!wmU}$Z|qlYw{V1+UOfsl=b4#R(V&I+`}FltZ43GEs}k54p&2b8
z?uc8~Zv4U>8$Ex|{6z}G?-SfAw_aQ*A#K7_7_SAltfjXif5ED7{#=%|lU=A_4;;N>
zy6j!X4Fn~H3+CT30)vIQ+;QWpCGIPcm<xg@iCg0L>_*O?t?OO17Er_A5j~Qbw<OU1
zY!*q6!-)1Gssq;oBi~;BXx~Bn9XpIjw1-OpAK0Nq%uGQ{1J(Vq-@X;kzv5}>%3H4H
z*6^8UB`25b_N+Z>?>EDMy$({y30m_y{v2F=fDYUeW`W+Yh|a@A>p1@kUCfdYUGM|t
z6OE4PZE8RJ+Y%ymwSCPtX)7Ja-}!3TThjpthqevvXoXx6_-cD{mSUs%YrK?IvJT$C
zV?aD#CxR<pX$~qM$!8jW*Ozi!g;|?8(g567wXc@C8BgY~IFt{7@;3t%z|rq#xdeaa
zw+6ia_z=a{8fhtfPAw(TLi|bExs<q)iq0>F=T(>dsUYbU=geI4*Gpwp+=q2Y`{hL?
zvM^50KcSf7P}jZmu-)~2wGeAIJKSSBB>zM|yEFIeCx0vUrM8P6v%CKO7-B{F135jQ
zLyZz1P+ig6oPPn>JGiz9Oa3}YE)BVLhs@+n1F4oHg5~@hp)#@t!WLqKthJ6!^0!1U
zK(IiwB}&4QNd7RLdRpOB;g&t~RmM*Klxh;OTu8Z$iDbsRB!A;I|GT1>C$Ig?+OV~g
zKTM|%Rs>9hONYdjA(KC)nqaIij5v}wFEFbqX35`Z*&_@^d`H)bt(W{^I*F`;00rGe
zMJU50e@ZpmvEuZ^BaEvSTPgX&bP8KZ(2)cQm!b@i{3+F}#ZqyjiZh~SY>ng((<xvj
zghm)DP>|9!`BSQSjin_<8?A5USoGu%(}}W@<0218m8En_{*-E-WA$LAN6cRJV{wx|
zOed#RCr~<tbrz>IPyUo@eq!~bq+evc3RuMC57P;@>WWC$;Bbjb!{kq@X83>L*3KsR
zQ+BIItce{Ou=Ic>dNidGGv}X1@G)eJSw*7=7A5(^bZS}+!(!M%0#UFK$seXu-D)Hg
zBiD-Rg83(Zm`-<AUo;E`V(@ajG_Ys#2TS$aa0&`j79|D3+>$>`rv>2qN+J1Ux;4^g
zK!*k_QB!Q<(w&-^^Uo*jTmt5<?o$f0PW~{R{#Z?K|MUbLVqvDqAEwg+@U5@`P_baU
z<PVZ+k-@V_8jxg|QSxW&v`*L8$;4I-vq=67otA3(QpsR|S@KGvtP@1rA#Jp{N~`4~
zs3;y{sR+Uj2}7wQS}>(xX?gzM3%F*d*UTz{VDfjP-m-08HZdB(<gb)&<sPq`8;4->
z_e;0M8@zaW1cJ%mU(wd@?)n*e5lsHR75nPz7OmYPNf(02-~7K-fHy4p!?l`Y>Fto$
zeoj^Yt-4pXh*qzjf7`WlyM#>y-^<^Qz1%V9Hi9qZZ_`F@nsx)hH}bb{7x&G)hT!Y?
z+q#8YCx46JyZGC^f4k>@Mes%ZJ)n6HD4{^`E&M&BbI+*ajNmKydraFNQ^<kf^Z9#H
z&z@Av2f>H)_ppXNtel7Q_rPv-{_jhhKQ5CSJa+y)55CXe6O$7#H{j#y`O~52_37uf
zl>E)zF6QcA<UJL>NA9Z!&c6?WPyJ=?z`YC}#osac9yS7xq5iPC9`*h$PTt2H#AoIn
zQ`7^$Ki~Fd>w$5tDEV9TcJbltmbM*xR?E3j=Aw<U(t61K&uq*_gRqgRS*F$Q<^K5-
z_yeCE>kmRRL$K22D61#*BK{Wtgo{k*<ZrpHRXh)o{LC?f1QFWc`4Ghl^Xw67`}s$=
z1erHI6hFtr$-55k74nbkvp0V<d`CMcc9B~;SaO^gZG>0zH|s{|9ec&d{QL2C|G$o~
zF@MGU;Ks>d1S90#rW&bQJIT0c$={D|aWc#XNLUf>Iy2z`2D|ci?PZVdsv01KyHnw+
zO1*KCzfv(FD?JYP<j;$^-u`yfN#>vSYA;9mE4=}=>l;>&xaIsC(}M^-5#M(E$J9Oy
z!TtEF%{lG-iwwd}nY2&yu8a1=G5NE##fKSgX|Gzb7`*-HJVD3J_?xJHd%z4J&m74+
zj=<y(+^FAXHOK}xe&Qx{h=rN%#9yP$BMCUKHFE5k^RM<g#z>fBmHaWfe-IoA{W;4;
z_8}wO#b+D-%<Gp#4m`+|$=7}YBmWdHaExX0$LM@)hAAU(wXMh~_@B=n{F!Yw4I&y9
zzQtN2mj)-?_>^dQlRuwyEByGu#LG1B)!fs11O5;-5u3P-i(LGXViB9TAn^#vAF83*
zQPTij$+ANhLTs#cM*Q>D`9pL>Y=T;XOMqs<WWY~9!;*=Vll<B0xf<y*w%4v$AgdrY
zbOI{JrTGID1kE_fh~R{aH#cwz(9FBK&_4NViAnd5b_81s#s|&7MSGa7%O9>CZs}4m
z7&hqMP8AQ1Te`$i87F`DN=n)$338hs9vQb(A?1p*D1R>1T*inx!hph1=geJUUB-w$
zLYw5T6jR<Uc|h>{%TZX51XKvF$e&j)uYE&1VJLcBA+7c1>9t34kl1X`pHNw0sB3TJ
z!Ce7e#uBi=Aj|RRRmy8$(?u0$*l_hG?6n603YsN<-vSQnjc_4vD6f4GEYN)|{s@f-
zmqMC&1W@abnQA#A4&mY|jWB*Ye^Xi_S(FGuxDZIWTo&SwQ-|}?jv|-hs-?NYIWM9>
z(B-}SP47f70nVNC0%0P|R^gA<WxOMya^ulGK7V>eVc|!pm-4q(52*i)GhG7h_*niT
ziV(hpOAqPKF^QB2m%meoBEE+ROUyr7O2UzF>7n~ICXpE7qI&(PG?~vIEh6zPEwYwM
z@kShPdS3hB#O<NLi};IltB3TrF<nWzjEm(WzCtx7^A}VBcgHP-;&P$zRB_8V>s&3S
z*DLr7_Q@1cZU80>nl--u$TRl_oXKBMKJfk*U&X7b#2!f-v1un0j}R>O;rvb4H_{$6
zdDFmLJs!ba!q@;of7)GAc{_+?3A#Xu<A4I^sx)o>Ny=^nk;IoU6b#b4#<@bx;ZId_
zEsiRF5FM3!?=mOKHI2WonuBHc?uv>YNt}Mgei{+%1zqC={?64#ioca?mX34-a7S&u
zXXW3^-=RJs!L=U`hVLVkq~xpAg!uTjS?>MYsMa+Oi)K6?zFP$GsvFuSf8{1Y6gf+e
zw?VaWC&uv>Zi;Cd^ecAG{qOcDxfa<ThesP;1z#}*8?}Rn$tS`r4VUJxeLI{hT)&Y3
zMsAevnrCxm9L-;3XcZgUr83ymz03*)z=2oP80kn{uATTR#^J0ZBQCly!ZE#QHIhHF
z9kk-)daJqxb$BU%!8>nI^i^46@`^~|eM&R=HGQU?zsaAfm&u<)N!5mni0(*t2h)fY
zs&>#i4V{05QnYZiBQ4Y7j<g`Ej?nrff3$Q9IVOKlGp;gm!f{?uihCMyf~eXN(QM}Y
zqn{w0+!2`;_vHjh{+J&-a#}AAP&_?CmgFz_i-Y$QA^EeVlx#RcXgjn0EeKg|U5Gdl
z@y6Z%YK3_V_S#3(*~r%`i>e(#i8kZUt8!4Cz1&^mB!A4s#U=4x^u)7uiIe;#e{tk~
zMM(Zyf=V`=OJZ?*cL;~;BWXumlKJ;P{3|prZd{j5BY+Y$%)kgLeFpK@t_rLfG*d~l
zV;oQ-NjoI^B!3baR|%5*-FG6s;Xq|q0byPqh*0r%sOsBh{vooeMA<qHB2@BMw%An7
zG}sy%Ve+O>aRX(x!dQ(^@tVyDV+vV+6;r6Vfl!1I=dW3?`3VMzAQWZyQ1Rn+nBd9Z
z?y%kDpZxt21=&n-$sWiNTT)z1q-AV&zuAyPX$Jv|X_$c#2Gp{}5^*Jm3BJnt+qeP_
z(_#y@z$9y;fntJYU^1<TX*`4(0W2mcnVH6`41!{UEsIN<^DnO9iV=eRnO`JSHFxI^
z-$`-FRH8g1&aIyDc4);}h`-xChwG))<pI&I(z(QR8Pjqlf3$R~J0^eM9dd1>pk%8P
zF*d)Tn6Adrl`TF0#z;VGx4vT`pi57eF)c;%M@zSX<J<Wo_R!gdaNhumfhh*X9H4*S
z`9~BGlx$#gH&`ktCec2xDC_b!pm?uXJK7&I5_%FYUWt-FuVS0oCx5<%MfCEm^bYHY
zo^PCg$0x%9#lL~TkBpp{oR>@0j^{6({g)%{>ni>w#t}VxHzN6aK7`4iug4L+d@H@f
zI-=(*=HEx4;@3Oa7*r*#@YDEf2yxz~y~`fd_GOkizk-Y3x3_)oM)bY^fm7{zK=dwq
z888MVQs~(@k-?U!@)q!SJJP^AN6jqxQ#JS#=T=WwkLVM;T?opb3o?YBcJW9AZHJy6
zt)VAQ;Z-6R6}JkP{M91j?J?0o3O0k_`J^TC{aM}=5TsxH1-ow6U>Y2(1T#tI3I#wt
z%?6nUrt;-Y^y~m;c|S=1{G6xu%bRy36H|g08o2Z{o8^ku223;m;@1mqzrK(pu4ICk
z9vAd$8d3flS(@9ZJuf+-(~CHrxPy!6ub98ut|Bta`PX&l5c97%HygdiGgtC=n^2s*
zPccEga7A8XDbcgmTs*jjzuP=i<RyPSwgirdxq77g0{(77{K?47+hrgR=vw`G#&SJt
z6t<;{@>lq4XI}fE{yZi|RwU=|IHs;hxSo~h`?o-?A9;EH_TaJ;f43Ai*dXWM*{wHu
z$=`PT)hN6c!ti(aj3F=i+myd6g||<IqPo`kdjL0*yyS0d{t61O*EW>D54_{aOa30f
z-<85zTkq%J2fMD9R_{Z-M_1kxb8aio2dO>(=8~85ug9*K$lrMu8t;$ez&+;Q#NYI2
z!)s$s>|?QXYyQ2qJz4lH1;jr$n^i`xyQu=n-=>XwNZQHYLmIhh8UF{i3SYAipL?+Y
O0000<MNUMnLSTa1@ZMbj

diff --git a/test/PCBView/polypartition/images/tri_mono.png b/test/PCBView/polypartition/images/tri_mono.png
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..a614a6dae90efb3e548916928e1f0974196eea86
GIT binary patch
literal 5633
zc$@(N7XImpP)<h;3K|Lk000e1NJLTq007kh00BG*0ssI2*dAjl00004XF*Lt006O%
z3;baP000%ZNkl<ZcwX(C>tY<a3WWE(|3mMwx9xUMUqk_ggw*6$HUR|1CnSw0`@etx
z{r8{xRSJw!;ETWdRSJw!;Ga<o*Se*^_t{%2lmY`4DE<bDUrX2g(=*Vxsq2Hi-J|9o
zM8J``h688@E%^?k;_trCry*y6!5_h}=yWc{-(Sl@r&nn3>9E@qF8+R`==}NXyu@%b
zFaEyu{DO}w>)-x9aDDv4pyj3u8>Rb1LeSwuj#~Pn6A6Ay_3iu-IoPoSQ6Mf2u9(p5
zgFn_CC}EvXDLElPMqT^!nz^*15b`+xoXyzcZYfS7t1V9_b06wYA{4Q$C(Y0E&&kae
z-PTv<(pq;_l0@cCd8*RT)=0ExbvBT{J#>Ce!3?!mI$OWNWNg7%UaaPZ@OL_M^9$O@
zFmBXMeGxn==DA|=`MdTqIe)ha_Zf9T&mh*2Q|%C2m&yFyCSl90gNVnw>5w_6YH%Mx
zz*Sg{rt#Mp!fE--#@s}2k*A(&&teXLZNjGD@5o}R--83Gvl*-71pY+4M1#)S?aL)h
z?0D}?m>w=2n7oTWaM*&W^rtXYVplO!rDwPsAb8mM!_~npJ0qAOvE#rq^tiKP`1}Jc
zjr^%Pr!wv-=-9->@h~>Mb|X}|HH_8#iK<=mR^_@pe~p2+<ow%;dcsD>pN%A&R|gO~
zC#K!HozqhZZp-cJrQpxD<nc3JRfQdl%@wI~!w25N^Y7_82=S-gxU=XO&EKlJIcLgI
z7MVYPll&1>^9DB#O3Xa)X4$t+{`MQ;HO|fVpYe7+Sq8N^VPejK_bUEwA0;8*zh9m|
z*1(&KzrAYbZ;n-yzyExkwEl5LkKo@J+<`Y2fBtsdJcmDEWc+i4&<;5zF!L8Q@MhtU
z)zjin{STv9(jz;^ygiWM9vhYj0)KJO98d8?U%bJ62Hq6&ZxaodPW381&jZ#n{y0SJ
z_E1Pxti5i?A4$&;*6A`Of0P~L6z=NYXz-AMSM%@YKIGhmySp<E9lob6F>v7J=a1FR
zCm7z#UxtBK`~~ut@Ce?oG6`pMTDd5n=?<8G2?gC!%KR(h)?to$gvPmJ75q85Ij!W(
z+pL}HQvmuZc)<PknN6q@2A=d<&%Rrwh>Lkb;ayZ&CQ0e|?n#o;QAXk%DgMrUj_vp9
z#XU9|@SyM{spijo1mCXYNnJJARK`QHI+17ASyidQnApd*&W}G2wY7(sw?Q?ni>*fO
zD#u4p{tsLluU(s5<M~Uw%R3}?9e6u}wssomH@FbzNbx7=AH+d}ybjzOm=iaKO(-LO
zHjSPZv!(74QRT}`uT7p!SXDVrV`39UVO!sa6P>Shwq81nFSk0C1>bt+RYdX{w=46a
zTt{vPMTCmKpZ1ALwc8AmH}CMXWiF~Jd>>f!S3T&o(YQNXjAlr0!wz@EEyZku42bg&
zDYp3g=p!Q8eum=4`Hx*B!-#r|zw;asRaOl=@lhEx#%y8RwTsHA4#OYf#Y9!BipHXW
zm`?|TrzCCU*=|l9%GBbb>K$k-|9dbn5Hi4L>BKcpGkNoteBA(C62{EG>H6UzZ=zz6
zRI~F3<_DVfKY(s`{Qkl<|0Y8rVh&(aKr@79bp9z~VV^MLHHfN38<<nwr=~eVbZOel
zA9%k~nSG;$)Cr0Rn&ChrxrN%`742!9&TB)2(28z@<4J;+pjq)J^cvUkY2Rxj^oLJ1
z4#09iGn79tMSN8-;E-k<7sV@jdZyqJ1{RAaiC7{wf5!z_HWC!EIi6GC(gV$qik`^R
z-h@V#iPWg-nl2z%HWC!EQB?xw7H1|_<Tr>*9*iuOpgj<D0f||v7M|h=ZdBABd$Vk_
zh?c2hLhoPjC{ZmuFMl9;plIO!4>F^-OdSv}Objg=T-P$V;0gOJujy$M*4q1XRz=XJ
zC)$e!r}Re7zx*TcsHSS{O>zEeSwZ@xjj7;ITwc4j7*Ms9BaF9-Y~<xXf9d_Q1XQ)H
zy?|l)<Oq7mOU_?JvkWn5^Utt$o(^rCb^fK=`E=umei>qp=db4od?M_&y9kaREL6#O
z7J91A7PA3aIDZXR3~R?-(#6(Bvt?`TejwbY=ZSfKbz<LCQh{p&KsW!g@rPg(-Af`C
z?NH*T!ZWe4(!MX*Vy56vJc3o6;cZyMQp=?c6!EaKg;n$S#ENbCQ&l2oYY@|?iiVh;
z1a2E`?tUWvMEJ^psDK&41^F}Y9<zvxIckq!@xs&4XFPwm*_#<MJ1)i$SPt<yWmEp@
zWsCFkngPoeAMmy$Y+kmU=khX)G(&*~{TJbH)7K!`dM?C~W)Mf)h!yyICwYBFngK!8
zbua~g*Nkzba7&w%8N9}hG@AloUruJA*HcRN6Y#h&o&;`b6S1>b=8<NQ0_={h^|$$S
z<qs^+AY2ER8AqBy7Nkch_&XlKV$#}6u0c4K%VHzVAdA?nz1?Ep#ntWe59iOHrC5f|
z;3Xr?EY9Pl?e~KVe`mw_^QUN&@90${&8Fc~@1~i5{o$*TW<yOJb*KHj{inabuKBlT
zaGQrexrUTA(zu+pr9S=b)>%q_L--Rfuqy3pq^abJFg`UjHGk%9Q6nt^9b(MWwa?t>
zkE7h5-*Iz*In_w>%RVH+KKZ~#i%ELV-|ZgoG>~hgi4B;}VDBj<a~gj&(kT6yA_(z*
zPvCDKflt$}{(MOVC|iZY-<}F_XHd$kAlm70YUS~?jc6{Jzb*TSM2n>Bhj6N~Dhhat
z_VG&nz2b{Ov<4yk9Vuizl(dD-Xs_bQ{|;yX*R6wr{MDg+>Y@s-i2Wl1*S}>w_*?Q&
zR>5>MjsWW^CJtPG@_wl3DaY|H+<9GOIWtmu?z;xyx*fH*E$BD@Zm-V>7EYT5sA?!+
z25!{AJ7eJNuG8H-Ih<6@`zrDSmxR1A=kNUx{(av2sj3K~0{bn<IXfus!_MDp_LP}K
z2|`hp8)U1CQXM4-tGYz|QA$cBE~TO)cI#DF{IMX3igRSH_={4R6?d@?oyu9Py6@4>
zYJ8G7D|P5v%SzQHdjAsHU8X~~g)CFu-)BI?-e(B4Mu(oNSfjclCw2a2*fk$HG$1Sf
z(sk>U(Ci&*=RbROHy`?D2TGaW)EyF&7Y&qZjW@6JcYF_iUV^~?jkx&B(ygaFChZWI
zHfWZ;Nr(Ju{*7-IP8DuBzA7w(;t$g)%u0on$~Y`#X5iwFsiroTmM5*fHlP0X#b1BT
ze^xZWWN;Z)9=34thv`JM`ohRYlFf^nJ2_bKM;25J=V8d>D<(F?p!n-5yAvR%d)HF2
z#fm>nCx(@u9)AQz9n2WTA5+anEDAc5Ae{=vmMQ))oqSd-Zdh@A)iAw_Kc<?uv53$R
zLxq=(El~VnI$5o_#BifoYhwBpe@rz`vFNza0|pk4g)aUuo%B`_tVG1rSH|=x{+Md+
zv4TJe3L7E;7PR=obkbPGQ4$wfQy<f|_+zU16)O~x(BNbtuyDm6rW0lr%|~>6tV*U;
z@kdj$0~{Tepvi#+D*iB?B&$AT^jSr!mHGF@A3@D-Sae&6APN?u_``I1w(7}5&$Ya|
zVE)A)rqi9(7Y&_(=)9a=8rZY=gQfa39D>4-MU4VsZp9y_Qv&#+KU}m3;r1#1)DjLH
zLIamp%Y-=;f0$0cR$~bmySh#(%)0o)bo$R~c>9MZpb!f)E&ec_62O;X1E6BTcEukg
zRg%GzBn?P1%&7R2b;{HAJekO<VHU-opi`=rr%DC`Op=!pB~K7;hq%%FDrL)uP?0}G
zstCjm5ks*gN|=(fv^sz91<cv$oLPAgEdFlPOWWqOiJ1{B{?5{6?s4YaYzP*AAG#%P
zaPssF2o`^TqUG;y{tUGU7JuK0ef4#U)=rV63c=!U{I?45h82IfR%0x+9n#v5sp@yt
zxw1vHdiDI9uAS2*EF$<`{$}juj5)Uvd?|mEHgeLm8wkFUzj?bjZ{|-3zK*}CTR3&{
zw+OzAzuEgYd;V7hU&P-6&0C;^6M}EyZ;j5aQN<C#SMaw?+m<P0M{s@qR_fVGwQLA3
z&fj7UTdbVL`CG7C|138z#Gla3Ww0~19(>#P#O7*;nC)`){MVuN`t);KD*i;G#~OT*
zw<>%~?yCjo--h6-zs7EF`sz#Zx9a5Ehx&R2uEXDYz1a@jQ(cRdS^UwD6i&eX{&4<*
z=~_>aMfh87Dl}hFD-~P(amE!Z3i5t0{#a^r;;hk+rvvx?Yn!W_!Yj<b+4)nEx7Y{K
z)ARR2_*O!&_~YCG3{ebY@8g@BOB}&-^Ec`6bCUP><<0pKEdC6W%kFagsh~Z|uji!O
z?_-MlRTvdvI`vs&Z>3Xs;`uibe-Y%Z@d}xhzgghp9=Pj$7Fhg6T_3uAX=RqJc)xj~
z<d2M-U-2zN<cDb#o$?FvROXcPFSFbo4%}-mGYit*VDs^pR_ksD?n<}7;*W3u9?2WE
zJw~nTly5TrvZ<Vbys3X2QvBIB@V*(6?2065s05vfzdZV;8hca!IHdSfZP$;FRPyYH
zd5_>}_#58r<A-^1KTp%`hCA!wLa9n9{vf%ISG_BUP>5be#UEekftp^gdZ%O(&ccCm
zX?s7%{2L<Z?IYthlkE?Wb5Yv{uKf_XY$Z&<Uw<{9p0|xmP6xED8APxCqS=x!{?58R
z4KuN$M}y(BP|Vhb3*9R_e?4_Pj=hu6U>dhqLwe7^fMCvGv>>zM?_1cX19uZ$)yS*y
zs9C5=I|wf^Y-;{GDA*=X3txlRAry8HP$aBv@M`|VcdNO7PmY}_H0ST63U|-TU#NB)
z2W=Xh2{hb$Qs}G#C&^~{I{pyyY{%}k0qx%Rp|JR~Y>WuiK=N4dfp3=%6h???Y3iL%
z()mZ1Y`^M>!UZiYT*LpvP|VF{5Et2&&(SNYW>02Zz3{QeoqQiEV{FCELawBq=AL|4
z=1)al9DLwGyf-F-!r~9zGZdw?<VC}$MR3c9BE=DFv<DsS(#=1o=mzroz-K^^OQBQP
zASQG1=hSG2PbHRfQPo;D)>*T#bESwfi|}V7&qf0xtN7YA1o2Z?{Iz7asbeN@6nwUW
znDsibiEP*{pi83pr<KNb)ys1q*VcRbK*#28^8#Tqm}TKltBYssIVX@o<tG>Ck!o|-
zN=>Zy8frfN{N#;2d2f1veLBs8xcECO2`WM%FB^QUVXT^kpx~jC@2Bt%YlusTa<ItD
z2_Fl=tvXT6R3eN&e?`4OO-0I6>3*B7C<Rg@NFi%2Fr~-KgVW#d-VlOFUViw9Q*aN}
z*4E!Ue}uvF?@1uyflKeJU-Wha?qq80VeUdUS<>-GCvTR?ckCaXj9Uuns~8X*$=|hp
z?tweq<O@ac_Fgy~!7ThmkT>Jxi$?H7;d}YpD-R-XcKD))_b&Tb1c%MPh<jd#;bFMq
zI9)>dh}-;N)noXJE<3bmpt3}>=yIatH>4QJUr^aWVTn8$Ld6voeGmyBHW{>Vx*VmX
z7a!LrXVrdpZfPgwxxw*b2h6|QQYk0$C=qeFotBgWQ+*bgg}?o|X9khd8z&zf+|6aS
zj~a7WXUVzv+l$dsI7&XJ`ZjlMv51)3n6}KXUP<{=jl)sev3g*LgOsegTO$Dtd5SKn
z`9sFxDB(n9qYWB`BLnZ0-Y6M+^XIAax}iPMqWS0$|5Uze;N2XBzJCT_t9K^;PUG<9
z@a<QWuiqF3Uh!w!Fn?af-w{Etn#%vpx_`N!<XM5hI4o#balo`Qo3W%|#ZhTB@%gK&
zb75o3;kzB;{Z;C{B&A4};{D~0SaFloFRVX;p}Ma8Q7SC>Zl4Y;Z4C^0Tqfg>wbwn8
zCG=&<LV;MNPw}UcE2;6$jT0cJyFs0q_+zPTkSVzfOPS*DvC%AvlapjlkD^cUSNs_X
zJfdU9$n0oL`s>+l_B1$}%cF>ENO&R_mPF<r*|h4%pSiG;qdAUEpjo_FDs`53GX6TN
zGYfoMo)iQ-E1aD_il%d6WX_hNRq^+y|5c05>X=a&;z*IJv%;z8A4Sk1D2!UvuUPT-
z(>uSEqaYZ#u3xk@`O{W)Yp)G5kb_Z6Q*`U8bEorHTM|XbQ4kDV_ep1!{wiZ<u^IU*
z_&iPZtM_XDC_C8GzuA5L0v3Na4D=LbY6KfXff|Bl6qRzFzkcl~qD&pcui<L^f%W)>
zo0=P9@_r@3micq;G5^3~{HpooSR+DPaHJiG4MnRg{P`uL$gxHcznJghPpnonSc4l@
z6{1{z16r!AK#e%gYDM=BB}})3D4KspQZyNV{yLSSsIXoTr>demOR>THA$1})EIF2m
zgNT-41cvkHFA|Y*8E%M$Ai53z%wZ&dPJxK6S~8SVUc}w6+c5sX@<21c5bH$%rF$|1
z-JQA>e@+4Oy5j)dTH@{=3C8dT)&`n+>R;Oz6!2aAfuekofm^PPk-0itz^f(hYfkUG
z#U5wT*SWF!NFY`*uYpRyAqe*7&#B0~C=AKmskX}9R$y2DRQ0HgZN<OAOC{sUSmkRI
zv-q>=HjS5-p`*Rl*C0wi{<Ott?G44h!9^?Mn*3>1sK+mBZ+Mh9_-fM*oPVC3)S+^%
zQuEpy#N1sBzAB-5@MoyO;G!z~RmKJ}*Wu4ld>y{r?cr&G%@@x<eEuN?eA!%o;Wd<{
zsDMr3%}WgKF$j!)n>{E*blD!sX7s()Q|!eG{GEyfn^*jSLV;$uo}CXO!u-44M*AOv
z0-eloy=?K{=4IA1qPa)$QT`fvw0mi*+~)N*s_=SkdWv3VD)!9J{5?g)OTAi(Wl&r^
z87}YJzXc#jAN)BF%|;is^=s{y2gq5VR!^-xlHM&{Xa2T85g@8cQW+z~zuZQpr^;9q
z_Q=vT@;!fl$MdhZxC~-|7lvCR>y{0!CvGX;`!{wzUK^KB6NSH~g9w%fniW`}0-&Ct
zS^J`O#qLPa$rt612qID>VgpKFX4{2I)B&-13Ibl()aS36ba6O44Ma7|pndS2=MVts
zRZ<W;=KS*~u|;U_HqTxx@@{+79wjQ#wAjV+cRHH!N*a(Af4Gc@B}?kY-OiSV`u-;_
zquLx#x)gt+&ME_^&Z?fO1}&ez(>N4Kx-}5JRO*+pO=K2!ozCB<Hj8E4Jc~@%;o_{(
z0{p=t_RFj@^Zjc`qEXl>vzmVfdGUkqX&gGQcVf<i`D-7|$K;AXv6m`?hPH9j4ta(L
z-v1DRPQ~vs6@Q3&xXo4Ap4bh({~<E%a%@T!e~4(f&93SY>?Yt(`)bCeFUxH|N8jxb
zorU|~G122d8uELjp0WWI7}CMpMbFQ0uz)fv1tJuXzZMa(YQ-!CHU)~mB4MNg#otKv
bYwiC7J!JjBz-G%800000NkvXXu0mjfDN$M}

diff --git a/test/PCBView/polypartition/images/tri_opt.png b/test/PCBView/polypartition/images/tri_opt.png
new file mode 100644
index e69de29bb2d1d6434b8b29ae775ad8c2e48c5391..d2ca9411dbf0da33d653db57b1720d66aaf1ea11
GIT binary patch
literal 6285
zc$@)^7;@){P)<h;3K|Lk000e1NJLTq007kh00BG*0ssI2*dAjl00001b5ch_0Itp)
z=>Px#1ZP1_K>z@;j|==^1poj5AY({UO#lFTCIA3{ga82g0001h=l}q9FaQARU;qF*
zm;eA5aGbhPJOBU~3rR#lRCr$PUD=}LHjeB0|Bvpz71ubvvMhoiwArkuO2P#MAWG-d
zlK=bffB*ZR{E-aIV&KPr`6C&a#lU}NHO{`tz@NJ}Sx5#ZGLZh8NPf1?{pa^U<E8E|
z_VtY1e~<&No-4jFIREkf@1fG)4od&k^)Hs(8Fc*n;~$ToT>tU>`Tbk1Z`<r~`t;ww
z)D%nZ&e_#oh4Zckt&(jP|E59He}8o^yj8g2y7ul?yZh3t_D#1{j&u@n-DK6BS2feq
zF09_vcQ+^Pf8Q`kL}ORE{u5$T^P2ve9ACeGpBz@baIfaLCwfb@@92*h@t6NpzXrV#
zcU2o9&TwtJ^W*T=7jX}Jl>Uob$J`w87OD#P4l_RsgBPp$YE+FTucMN+WT1Vgc*iKd
z67!~yjQ4(M#fdUM{1#smj+~nArBb$||IX6L{Y4WYNh}=T1#CLZ1bJO2-tK1c9sw$G
zyZEnI&g&BzWYZkb4EX!)!|z{8>ERny&EScBdY=g1f00*|iXB&-^C|&df<ON7JNl}J
z>S^U7!5genS-k(M64JVQNg?77v4aSabR?#5Au-Od6qV32|20%}Q9q2qpGI-#9YsLQ
zcw})MgY`#-J<Z~!RO7!kvtHhZ@hAc2D&h)unR^&%$l1Wh6!_0<W(ExA?&<N%!EjC2
zFPH;QXPJYT0aYLSK7WAA7KB1`K_^Opd5hrjcqGjLorqvV?7{Cp1Oc+EX$s<r2tj5S
zoCojTB`TX}RRK6Q*V_!;e|Y=FA2F^$?&8tuNFoxW@{_lY3tJ=Dz5j@v;lk=AA`*W9
zi@>9EkwhdWGJYi2i|xraKL2^Uu7Cf|@*mQdV>{w1JeR|E&vN*WYl#qzkFAZIxc`uo
zNfWMRsalQ3RvPa2x2N^@A93eiLDN`!^LPTI5z>jD_203No|v!rFG%tF`;SH#XQtg+
zQoqv~j$^A{K9%4993LQ#HIBi&L<o>XiV0(jdxJi)#rXGowaf3nSLq~o;T0GGl1O=z
z{|@)WfBZUfJ<gv>r>_1Z&a`l@YAIp;-qdmR?*o4K{+;W;YWHRRCjoZ9eE*Pe-+%FD
z@e17WGP4R`E}X7l6G`>saE}%sl6F`eSoOn4>A&+(s`^QW7Z$1P|8BpT4}l#y4@iAU
zjLHo4C&&F0O7&=ZCy9ghc0}S=^Ivfb??M_v^%-*x<?|o$JbJRS3vSoo$g97fIob+!
zB?KuR8T^_H`A>KvBe)S>h?w-Bm$Zn8rui!Gzx&#w5zvWVj_~*=NG4P>0LM^`e0rV-
z%f{2`!NI3(<&V-t9!ZN|!OQyZIQF#Iai29#1yLNg5ad7lEw~z?PlK2^%>Y8AYsz81
z-d(&PIXtdMPW_J(x=OUC;%4wNg~xL%u-_D??fSLA$%$WIUgvzyf7}Y}VUFv<>rtP!
z-I2&a>gYcX6E{YXJ2TxylYE5Ys+HF_$43GPRK(r#_(%DPT2E6ElOO~IWA3PgBR8lh
zy6i%Z$u`HH+keCsT$AGaARL3HFh`?e=SA)~q+>9~D_JAHU5fGF*DUB2<Nm?6>V`<!
zpuNm=7dFFT&0k?B{pYoyYaWvwZNL?q>s{D}QC)av$}WVMRGWj4`wwxL*?SARi%H|}
zv$pdPVolY%1_)&}OSS$gF*DgkB~q;`t&QT173hL(I&bl3pIlIry{P|i#3qzk=DT~s
zypiuvLFeIg&0+(TNfl=NRf?)M>!16pGjRVMwgXvO-+UlKa9$)#<3BC#Sx5hz0`Z^A
zc3T`jxrjskhoDCQO*G%tB?r_hV8VF_InxIRLE<7Jk@jC@j8wtTH(qU`9;d?!w4C!m
zT_?`lLq1SwrT-A3L0Bt@adjK*JcN_!!-D>EX$J<2{fE#EBAc$t`Pm`@IFdV<fi_g{
zAYi=Sf2IXNWP{nSw!2!8{`m@nm>9I?Gd*zPvHgeFx(?ZxXD|O9<I|YwMAI?a0Igp5
z)V=)Ib}f!i%d)rH6({GyEhg2P&$X~R`mcdw3stK4y~w@s-V-8;e*#H^#}gs{xg1?E
zBA-pdI9Q|#-n9sEB|u0$!k)(DdbvjK?!PDRx=?aN#IxEL6EXr46UP~;pf#U&RgLhU
z<RXhuOy`>Ji3iZwREhTy%%R$?UFn1Tx2XjYD%;mFQbFY;qK@2rz4o8C?wyMsqY{j}
zQgHV?xe%}50;UR<i{hOZ-G6ca?YIKnY~KE?gSUdpSYVw3UL38r!chO+E$D>{(y9t0
z;1!FIsGtIG){&c!SW*uE5!I^{T*qEnp2)nX3s)XcE(9^`1pgJf5}?hKtqKTYYkxFR
zf#mAQ&Bq<rIsUt14QkA>Ut}Fd8T><noGx<GF65smHO+rhEcoQG_B(-~^(@%Pb%CLM
z_LO)4i;Q-!OjPsvuM=VdcUzCRwD-3;4bqz!2XC5n5%c}AlZo|yRe4houW&UxN%iCy
zual51hz~9tw#UPiBWJ$<j-A>@FQneo8$n_gk=#vS7cV&`+hAYGVsiUWegz+6oHs(1
zO^y*R3pvL~j6@!8gp*RQHR*N)A%8&<E$L>BUY!o5cRGADJW_iLdnc-HVgkJRh~j`P
zvHyBJhY32ost{+!+k%+FG)fP)>A4vHX|LcDIw7Y}9-cw?{~&jLX$X<yr3&ZKBMYAv
zll^z4pvSrNYJ<mLBV8v)rMegD^_**;1d)lR`R}e-l^`$6TzrH<LQ6?I*QEDzeuW*x
z6G@-rzbfJeM=q|t!4dlCn@HHyoVVy@l5ZBIr>=Y$@-`!mI|z4*|KvWv?_zoDCn*vC
z(Qo?T6y*Nv0T-l+J}}k9Abp_ZBU_uNy)iPu29fgX=}gN>G;XKd|0~hLHBQ(1$Rg|t
z;AuyARcKQh9D(0|t`$g&5gf0<UBAk|&bRgLOg|V;mCcTbSjUWJDRUi+@E?eh=F1$i
z^6a&2LDZ!0Vvrvfr1&L^ph9Ad_34_*d|O16j#Gxu5+@Gtb?gc4trxiy@!8EtGr(l2
z@BVY)8|FV3Dw9DxV37e`<M%!`A^){s0IoUB$Aq^UeH-F_A|e}$aM*y}MqS@UUHoTW
zH&x|KUd#Z~5b+9T3nZYQqR4<q%>AKt&m!tno@WSOjTj*;WF91D&CQ1>YF+}7XWyAi
zb66zOb*@uH_g_I-1QVDGhDAOJ1<xd&KKS$=z-R)mxsf8h{1?Oorh{SkeS_O#WTeW1
zI4yW&<CzpJ^6xT^bA3RG1Hvodk?|8B=f|vYe=c_&&|AEElf;YsmBwTT2{;%GVsfS9
z!FVJxX}_2PCk`8rl$=J1*2?|&>pBm(uoI8ovi%%pR=%EL5H=WAXk;RJx_OCq?OuY<
zAFBOK%x0#T0h|(Dvrfz=cr&2!fOCxyzucbMb@AW1=UuqvY;px%!gLBoEJ#m>Cu*<S
z`eEqAAaN<<ydbv;S8V_rV2ktUJ`F+-h$Ole2RP9*|6SK%11rJ{excCSB5cZYpL`IR
zuAMu~d4F9Yr_6Y7{{K#|z8YyT1*Z{tXbhba?}i9YS4|&q)lS}jMf-lV2Ic8wqhML&
zMF_UIpVf(sb^QE+&~bHPoQ1)62Qr{AMm62l%5lzv15Wl|@k#l-1@b2Y7zkQNlD>rh
zP8Y^UIu7*oV;vs^|D@&ZwG=rE`OnK^TcM>`mW=kwbM;#Py;H4$e{4#1W{mGc#<UsM
z<;7pbyz@j2bH<oP_iOh}7x9~B`TOV}V~b&3p1xci2B2%B^j}wc1;w8fdWUlFnBpq)
zn?HXPc7B0)FBqW|MX+;LD$!PGcl~z9e|O4<_Mh-u?pY@;{Wptwv@fC%5`*>|8@Dg=
zC!RjH|F+(O>A$h(-QNvY2#@rm=#{Y}=1>3nhcWzaznqo+>vghKb-fCC<5f7hI(wl-
zX8h>;@7GtL`)tAVAL8kmF`Pm_SzO}aQMUl;;w1OqzjUpy?)nH_=KBdw|NUZYae)_y
z=QUsYufo{M8n29vFkkwwPTI0EFAIz_U;6Knw>6bs6BTW~^k0j*1;t(vQp9}eKZCv1
z^j-~5(0u7Xo4}<cUkZ%P9T1V<zt|+Lqxw2XY}T-d^dH32BEl~M1ELHIO8;Rzt?_qy
zr2kO0X2o??sB3YAvFQL1kgk~Ae=fQv|IJ3}Kc8CTqX#H7pv4n!6I*wZGWQ=t>?|M5
z>dSD1<)r^Go^DZ7tT3f1Nf4Hn{=;~xMU8jE_>Md~SZ4YU<LM#l#}FeuF|t>P7dScn
z2UGPNILsEq8VN|jN~HfVo~)=b&KT3hnpOGV(|<BH2bg0(3mF|)q4Xcd6BgCmAHC~i
zQ!1m<e@ZrgYIU_p*WzL#uyW}?j3-Z2KbQ2Y?3qs)oBmU>dDiM=lul*4P=FOp|6x4&
zqk4FyM@|1^%8c}%lFg!)+%EEh9f!wCr~fdX*eI=IwAI*|lzHhtC7ab+LemIKbsrmR
zkp9DXibbh>qpA~|Mwy-dQ?l8pC9#gA$e@9-Ht9c%Cq-1;J@E>PIg~Zhe@ZsZT0sK^
z(@l8e1JZw^IgfZKk~?}%tY7*M<4GFzV<XN<T$U8OxLEp6OekKCFcXo2<Czkf{+mMk
z-=<zadE;l!hV@SWVLWw<a#_k1+zqm_aQaWlCRYo06&}eU8K0H@8_#*ABWNrzY>AOD
z5a~aRr~Xlhw~(0rNR=JZe@ZrkwM=`N0YL!c)6;+BId64rJ1qUTmRff-FHop4!V9J=
zB+LD`;)#0lS^959wXT?6qfm8_*GzXxmiuqr6Loi6`fpve4rDJ=s2JyE)BVwFbwfGv
zy-=ac|DOGY(>e8BJ^XzNU6=a%rpx`e`iZ)}E7E_ftMxvG{{5)<Gu!1ZUR?<c-wXHO
zKQg`c2PW$_QLpmfxgK7&CyvAPzEAhB`uux}bUv8g;lk?_#f;l*xo4p7*?(1SwzlAX
zqV(UQN3L-_?Woxk=J(ygFWG;lFdHqx22^v*Mc2c-?_cm^$NG!VL<mm0kqh6j|6Hmp
zy9g0ru1U9W;r9M3J{}^Zn`;IsB8<WD5W@;__9*p5|6PAYs|TleP272R%*ejPk<5zR
z+ke4*;FVu15@(>`$l4L&)jsXNS&J~@`}AMj^qLCA{@~WhU<*c^SA`mxS|dZO%EtRo
z=)dEaR(oqHsjr<nW*$NIuKv4g*+X3c!T*#Hn!D5Bs!6?d(tjmmLa+3=+|z$vi|ga7
zt4^~2POOq@aw{LJ^iHS*tzIXf;+Fewj0O?+L~`4zjhP*AjwWP3|2>`cPCI}oOQhgp
z4jvx|#zm(8Y~Ju?hDX|6A0pC!G<AZ+iR`zx+5qR7Z_}=OS0G-k#Af?%qW>CSqYM^)
zE(uyA?&QCQ%p)Ce?KN`knfveQ)3Meu+G^=PhR?%-BTaurxyU(Wh`Z%%<3IEHC7}Z^
zGG+4}@K&P&C+!}Y{$toX9WZ4DrvDhtA~~kaW<aESkz4c{*&5k@=7JPb5ihmJ{xdZ;
z1L90Iv>(<z{io8=Q3p{MiE*@i2wmjij|_{%#0iO4*kJ!5R3b4!vdk7{KoG#0jx<7I
zRCpqFR`(ymBN7wg2!BxxKmuODIOZTT!SwW>O`ywFu3)>j|0UpBlQaNT;?n*DwFJXB
z%824biWeK$0u1wZ7sjXmT4d7t(TSk6V0|zQY}zAiUH{?S;gK!|gJpy1ZK!y0Jkmvu
zDmeXDXHp`Yq(~JXUKx*6S;|#sQUAGEa|I*p2nz~JU6H%Wx`GjYgfZ#Al1#Z;@`B#)
zR(b$XS#U-FdHM3jH@Fj)qSqB7trw>^9>E}q+1`IbW`(8h+Q^H$3c7+N#sZ5h=RYq~
z-uNe8RCR_eS1(|1JZPX`So-e|fy1;BHu9G8#s`fBrmy8cf+HfOpe9}c<oXCxwIk{f
zDX!6o;II2{iX@VzL=hr|u#_uhA^&mga9P?_<YHXanj4(UA_fFgzU#l~N(2FL>0B0Q
zCL(MV|IxgRPb64weCQsJpYA9e{4DiR|E;9~^?&uHN1zj5>%RyiL@trigZgVt0uqt(
z@7AFl--CoD_8(0pkw~QU;Qd~c07j&!KK-aTneRWEMB=-&NG}!RjXGX<-uU3g?ZLo@
z{1;KH2ldsOE|9L^qFp3c$i`&<1zEt;@kk-LTqztX9vSyKH;b9|3I7FkGD(yNfPlfU
z#<xFm<lcfa{THMUeE-F}csZ5CBe0Q}Hkf#Y;IJ?E-*kQ>@|fVw0JD3%g4x120Kt4Z
zT{3yQh@=HQpd@j?fOA=zw*Mq!H;PE=OFR@T(tF0aM9uM^YUZaps`^3esM33nIgzeu
z{`;9ZICgJURPK?~={M{lL{JNQ#tHtrP8%7%O4%$PX#wy=?Yvj!zw5t~eS(6!9xpcE
zL6l_VJJkgF__0~;^KWBX*E%f3c)j_m7R0A+aGU-s4++A^m3mwT)xn)u$2+)5rWw$0
z*g5aN>Q!<dvb_#Z89rscVhc8A2QQPO!YmG#_FwyTIG4D7D*>$B7~i$e=F&LYf03nC
z9B3EIps0I=6%2q2ub45SNSv;n{8y~QSyx7!bYX>ad(mv9|42D##>sxGrUiNUsQ-d*
z-XQ6#dWpdmp~Cx7n!(r1nRfrC|5RG0{~S!J4qSwE2izS(BUGs5pm`d){|csP;^;)0
zro|I!LR5;-{G|VA>J~~&|3PBhY2t|EvLJ|i262R_<cM%KbN|sFK{&c2G%cRX5t9C6
ze%X=ZdT|5A;Ssc?|I&YP<Nd9W{<Eo+95{k#8`=I51TEDRqE3XoaqqvU!Mp=|<0I^B
zl<TEMB}b5=&HU$OImpgl=`M28f6T+hMe$zliKBIqlm1Kp#Vz-%Li(>osN}%8C>G1R
zLphuui5ziC=D+{&Z=rE=<GgHI0i>uA23An<Gsu7Kslb`RFcmdB)&VJ!$RXh;{U@Pu
zl_KfCx)SjN2Qs^g5$54Qh>FXhns1x^htR4bW$QW!QR%-@Vv{v9U~AI|!J9<I1C(fm
zwHl@3Gn*C046=R~lc;!rkc1KUuQ{;!6%0~ANXqV|;@9gi!qb1do2`OB{r8I$<S@l4
zd!dimk>X?`lCkK1dqYyCT?8Da5e8NmFv}J#;!F-Be3kpR@dO;k#TMQIK|YZNk_m=^
zU|Jtc<0Z@r;4neTOc<XE2$Bg(7N<1#U!21gD+K*#ej}lpxx4@HlN6^+ManzsRQZg{
zp(SS_|5eW%&X<;#7gW1b=OWV;Ow*PAqp4dxG5z;PA=fbqQntDy#^MW-=@O2fZ0Y?s
zh60+q^%DyMU3|KNX)4lxG<6#!e%*h>8M>wr=^L10AjBY<1NiT||A+yClnoSjgH}N@
z3HiLFtn0r4!+XivG5(~H;FC!4Qk4GlGPYTK`p+j=gfCyGZ$wA<{NnyQzcL&!{1+T}
z(8!U=Ww}`Gc>mJqe-i0j*YF<+j_}!Ai1gq4O_=`kX&m9p*XbM45k5b${|<tRAK&oC
zpebpF-{wD%h~8rll6{#rRX!0ddJEC_{YP)L-eWIgj6pzfK55CgNd*3@9;5SLlCb{y
z)*yeV7{L8kbnGGSwFN431IL}C>$KeDT$W0$_toL}G<9^jqRMLNzo&}0B==E?;fWL+
z;RhoLK7%@fM*8JH0_Cq=`cKcg&7JpY5XlD})*ji*XG2GCsr!Zgc>hL9o4IB{VdeCY
zkO3|Eu4-*rHTw?)1cv<}#v_Fyy|@(4Cm0EawU^%?p@UoJxaM)?z+f;8@B8sckWVn|
zAk!;-b*+T_=Yo4W0LemPK5i-3_z0g!%)O~A>mJPe&(+x6!`=WF`x$JCWd<}j#B(+N
zBNngs+~6anw-5%}e8$-ZEg|q<94m4W3%ellygsJEr;uv1RMdZF1Fw)z1?7#rz+M(V
zjA!qnMc;qmf+b|DB2NDiOnRSaok(t2h1`FgfHp4T-W|2-u3xPpyysgpVnA@M*!ypc
z6^brnni8~bnlgo6#Pluy^}BPcDqi8H|FlM*#cg3B$Nf9S0cX=G-L;Z0Rc$V@jqdgR
zH&Onh^+W(m`9=k1I;&3rD*l_U{os3FrSZyjR-m+s0sZ}_NAk!YE6ceZwvocMdll3<
ze(TD1q$l9@8A$)FuhE+krvKio?)tN(|JK*&%?SSo+n4h#sIMnw00000NkvXXu0mjf
DnH!77

diff --git a/test/PCBView/polypartition/src/polypartition.cpp b/test/PCBView/polypartition/src/polypartition.cpp
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/src/polypartition.cpp
@@ -0,0 +1,1547 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <list>
+#include <algorithm>
+#include <set>
+
+using namespace std;
+
+#include "polypartition.h"
+
+#define TPPL_VERTEXTYPE_REGULAR 0
+#define TPPL_VERTEXTYPE_START 1
+#define TPPL_VERTEXTYPE_END 2
+#define TPPL_VERTEXTYPE_SPLIT 3
+#define TPPL_VERTEXTYPE_MERGE 4
+
+TPPLPoly::TPPLPoly() { 
+	hole = false;
+	numpoints = 0;
+	points = NULL;
+}
+
+TPPLPoly::~TPPLPoly() {
+	if(points) delete [] points;
+}
+
+void TPPLPoly::Clear() {
+	if(points) delete [] points;
+	hole = false;
+	numpoints = 0;
+	points = NULL;
+}
+
+void TPPLPoly::Init(long numpoints) {
+	Clear();
+	this->numpoints = numpoints;
+	points = new TPPLPoint[numpoints];
+}
+
+void TPPLPoly::Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) {
+	Init(3);
+	points[0] = p1;
+	points[1] = p2;
+	points[2] = p3;
+}
+
+TPPLPoly::TPPLPoly(const TPPLPoly &src) {
+	hole = src.hole;
+	numpoints = src.numpoints;
+	points = new TPPLPoint[numpoints];
+	memcpy(points, src.points, numpoints*sizeof(TPPLPoint));
+}
+
+TPPLPoly& TPPLPoly::operator=(const TPPLPoly &src) {
+	Clear();
+	hole = src.hole;
+	numpoints = src.numpoints;
+	points = new TPPLPoint[numpoints];
+	memcpy(points, src.points, numpoints*sizeof(TPPLPoint));
+	return *this;
+}
+
+int TPPLPoly::GetOrientation() {
+	long i1,i2;
+	tppl_float area = 0;
+	for(i1=0; i1<numpoints; i1++) {
+		i2 = i1+1;
+		if(i2 == numpoints) i2 = 0;
+		area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
+	}
+	if(area>0) return TPPL_CCW;
+	if(area<0) return TPPL_CW;
+	return 0;
+}
+
+void TPPLPoly::SetOrientation(int orientation) {
+	int polyorientation = GetOrientation();
+	if(polyorientation&&(polyorientation!=orientation)) {
+		Invert();
+	}
+}
+
+void TPPLPoly::Invert() {
+	long i;
+	TPPLPoint *invpoints;
+
+	invpoints = new TPPLPoint[numpoints];
+	for(i=0;i<numpoints;i++) {
+		invpoints[i] = points[numpoints-i-1];
+	}
+
+	delete [] points;
+	points = invpoints;
+}
+
+TPPLPoint TPPLPartition::Normalize(const TPPLPoint &p) {
+	TPPLPoint r;
+	tppl_float n = sqrt(p.x*p.x + p.y*p.y);
+	if(n!=0) {
+		r = p/n;
+	} else {
+		r.x = 0;
+		r.y = 0;
+	}
+	return r;
+}
+
+tppl_float TPPLPartition::Distance(const TPPLPoint &p1, const TPPLPoint &p2) {
+	tppl_float dx,dy;
+	dx = p2.x - p1.x;
+	dy = p2.y - p1.y;
+	return(sqrt(dx*dx + dy*dy));
+}
+
+//checks if two lines intersect
+int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22) {
+	if((p11.x == p21.x)&&(p11.y == p21.y)) return 0;
+	if((p11.x == p22.x)&&(p11.y == p22.y)) return 0;
+	if((p12.x == p21.x)&&(p12.y == p21.y)) return 0;
+	if((p12.x == p22.x)&&(p12.y == p22.y)) return 0;
+
+	TPPLPoint v1ort,v2ort,v;
+	tppl_float dot11,dot12,dot21,dot22;
+
+	v1ort.x = p12.y-p11.y;
+	v1ort.y = p11.x-p12.x;
+
+	v2ort.x = p22.y-p21.y;
+	v2ort.y = p21.x-p22.x;
+
+	v = p21-p11;
+	dot21 = v.x*v1ort.x + v.y*v1ort.y;
+	v = p22-p11;
+	dot22 = v.x*v1ort.x + v.y*v1ort.y;
+
+	v = p11-p21;
+	dot11 = v.x*v2ort.x + v.y*v2ort.y;
+	v = p12-p21;
+	dot12 = v.x*v2ort.x + v.y*v2ort.y;
+
+	if(dot11*dot12>0) return 0;
+	if(dot21*dot22>0) return 0;
+
+	return 1;
+}
+
+//removes holes from inpolys by merging them with non-holes
+int TPPLPartition::RemoveHoles(list<TPPLPoly> *inpolys, list<TPPLPoly> *outpolys) {
+	list<TPPLPoly> polys;
+	list<TPPLPoly>::iterator holeiter,polyiter,iter,iter2;
+	long i,i2,holepointindex,polypointindex;
+	TPPLPoint holepoint,polypoint,bestpolypoint;
+	TPPLPoint linep1,linep2;
+	TPPLPoint v1,v2;
+	TPPLPoly newpoly;
+	bool hasholes;
+	bool pointvisible;
+	bool pointfound;
+	
+	//check for trivial case (no holes)
+	hasholes = false;
+	for(iter = inpolys->begin(); iter!=inpolys->end(); iter++) {
+		if(iter->IsHole()) {
+			hasholes = true;
+			break;
+		}
+	}
+	if(!hasholes) {
+		for(iter = inpolys->begin(); iter!=inpolys->end(); iter++) {
+			outpolys->push_back(*iter);
+		}
+		return 1;
+	}
+
+	polys = *inpolys;
+
+	while(1) {
+		//find the hole point with the largest x
+		hasholes = false;
+		for(iter = polys.begin(); iter!=polys.end(); iter++) {
+			if(!iter->IsHole()) continue;
+
+			if(!hasholes) {
+				hasholes = true;
+				holeiter = iter;
+				holepointindex = 0;
+			}
+
+			for(i=0; i < iter->GetNumPoints(); i++) {
+				if(iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) {
+					holeiter = iter;
+					holepointindex = i;
+				}
+			}
+		}
+		if(!hasholes) break;
+		holepoint = holeiter->GetPoint(holepointindex);
+		
+		pointfound = false;
+		for(iter = polys.begin(); iter!=polys.end(); iter++) {
+			if(iter->IsHole()) continue;
+			for(i=0; i < iter->GetNumPoints(); i++) {
+				if(iter->GetPoint(i).x <= holepoint.x) continue;
+				if(!InCone(iter->GetPoint((i+iter->GetNumPoints()-1)%(iter->GetNumPoints())),
+					iter->GetPoint(i),
+					iter->GetPoint((i+1)%(iter->GetNumPoints())),
+					holepoint)) 
+					continue;
+				polypoint = iter->GetPoint(i);
+				if(pointfound) {
+					v1 = Normalize(polypoint-holepoint);
+					v2 = Normalize(bestpolypoint-holepoint);
+					if(v2.x > v1.x) continue;				
+				}
+				pointvisible = true;
+				for(iter2 = polys.begin(); iter2!=polys.end(); iter2++) {
+					if(iter2->IsHole()) continue;
+					for(i2=0; i2 < iter2->GetNumPoints(); i2++) {
+						linep1 = iter2->GetPoint(i2);
+						linep2 = iter2->GetPoint((i2+1)%(iter2->GetNumPoints()));
+						if(Intersects(holepoint,polypoint,linep1,linep2)) {
+							pointvisible = false;
+							break;
+						}
+					}
+					if(!pointvisible) break;
+				}
+				if(pointvisible) {
+					pointfound = true;
+					bestpolypoint = polypoint;
+					polyiter = iter;
+					polypointindex = i;
+				}
+			}
+		}
+
+		if(!pointfound) return 0;
+
+		newpoly.Init(holeiter->GetNumPoints() + polyiter->GetNumPoints() + 2);
+		i2 = 0;
+		for(i=0;i<=polypointindex;i++) {
+			newpoly[i2] = polyiter->GetPoint(i);
+			i2++;
+		}
+		for(i=0;i<=holeiter->GetNumPoints();i++) {
+			newpoly[i2] = holeiter->GetPoint((i+holepointindex)%holeiter->GetNumPoints());
+			i2++;
+		}
+		for(i=polypointindex;i<polyiter->GetNumPoints();i++) {
+			newpoly[i2] = polyiter->GetPoint(i);
+			i2++;
+		}
+		
+		polys.erase(holeiter);
+		polys.erase(polyiter);
+		polys.push_back(newpoly);
+	}
+
+	for(iter = polys.begin(); iter!=polys.end(); iter++) {
+		outpolys->push_back(*iter);
+	}
+	
+	return 1;
+}
+
+bool TPPLPartition::IsConvex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3) {
+	tppl_float tmp;
+	tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+	if(tmp>0) return 1;
+	else return 0;
+}
+
+bool TPPLPartition::IsReflex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3) {
+	tppl_float tmp;
+	tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+	if(tmp<0) return 1;
+	else return 0;
+}
+
+bool TPPLPartition::IsInside(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3, TPPLPoint &p) {
+	if(IsConvex(p1,p,p2)) return false;
+	if(IsConvex(p2,p,p3)) return false;
+	if(IsConvex(p3,p,p1)) return false;
+	return true;
+}
+
+bool TPPLPartition::InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) {
+	bool convex;
+
+	convex = IsConvex(p1,p2,p3);
+
+	if(convex) {
+		if(!IsConvex(p1,p2,p)) return false;
+		if(!IsConvex(p2,p3,p)) return false;
+		return true;
+	} else {
+		if(IsConvex(p1,p2,p)) return true;
+		if(IsConvex(p2,p3,p)) return true;
+		return false;
+	}
+}
+
+bool TPPLPartition::InCone(PartitionVertex *v, TPPLPoint &p) {
+	TPPLPoint p1,p2,p3;
+
+	p1 = v->previous->p;
+	p2 = v->p;
+	p3 = v->next->p;
+
+	return InCone(p1,p2,p3,p);
+}
+
+void TPPLPartition::UpdateVertexReflexity(PartitionVertex *v) {
+	PartitionVertex *v1,*v3;
+	v1 = v->previous;
+	v3 = v->next;
+	v->isConvex = !IsReflex(v1->p,v->p,v3->p);	
+}
+
+void TPPLPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) {
+	long i;
+	PartitionVertex *v1,*v3;
+	TPPLPoint vec1,vec3;
+
+	v1 = v->previous;
+	v3 = v->next;
+
+	v->isConvex = IsConvex(v1->p,v->p,v3->p);
+
+	vec1 = Normalize(v1->p - v->p);
+	vec3 = Normalize(v3->p - v->p);
+	v->angle = vec1.x*vec3.x + vec1.y*vec3.y;
+
+	if(v->isConvex) {
+		v->isEar = true;
+		for(i=0;i<numvertices;i++) {
+			if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue;
+			if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue;
+			if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue;
+			if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) {
+				v->isEar = false;
+				break;
+			}
+		}
+	} else {
+		v->isEar = false;
+	}
+}
+
+//triangulation by ear removal
+int TPPLPartition::Triangulate_EC(TPPLPoly *poly, list<TPPLPoly> *triangles) {
+	long numvertices;
+	PartitionVertex *vertices;
+	PartitionVertex *ear;
+	TPPLPoly triangle;
+	long i,j;
+	bool earfound;
+
+	if(poly->GetNumPoints() < 3) return 0;
+	if(poly->GetNumPoints() == 3) {
+		triangles->push_back(*poly);
+		return 1;
+	}
+
+	numvertices = poly->GetNumPoints();
+
+	vertices = new PartitionVertex[numvertices];
+	for(i=0;i<numvertices;i++) {
+		vertices[i].isActive = true;
+		vertices[i].p = poly->GetPoint(i);
+		if(i==(numvertices-1)) vertices[i].next=&(vertices[0]);
+		else vertices[i].next=&(vertices[i+1]);
+		if(i==0) vertices[i].previous = &(vertices[numvertices-1]);
+		else vertices[i].previous = &(vertices[i-1]);
+	}
+	for(i=0;i<numvertices;i++) {
+		UpdateVertex(&vertices[i],vertices,numvertices);
+	}
+
+	for(i=0;i<numvertices-3;i++) {
+		earfound = false;
+		//find the most extruded ear
+		for(j=0;j<numvertices;j++) {
+			if(!vertices[j].isActive) continue;
+			if(!vertices[j].isEar) continue;
+			if(!earfound) {
+				earfound = true;
+				ear = &(vertices[j]);
+			} else {
+				if(vertices[j].angle > ear->angle) {
+					ear = &(vertices[j]);				
+				}
+			}
+		}
+		if(!earfound) {
+			delete [] vertices;
+			return 0;
+		}
+
+		triangle.Triangle(ear->previous->p,ear->p,ear->next->p);
+		triangles->push_back(triangle);
+
+		ear->isActive = false;
+		ear->previous->next = ear->next;
+		ear->next->previous = ear->previous;
+
+		if(i==numvertices-4) break;
+
+		UpdateVertex(ear->previous,vertices,numvertices);
+		UpdateVertex(ear->next,vertices,numvertices);
+	}
+	for(i=0;i<numvertices;i++) {
+		if(vertices[i].isActive) {
+			triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p);
+			triangles->push_back(triangle);
+			break;
+		}
+	}
+
+	delete [] vertices;
+
+	return 1;
+}
+
+int TPPLPartition::Triangulate_EC(list<TPPLPoly> *inpolys, list<TPPLPoly> *triangles) {
+	list<TPPLPoly> outpolys;
+	list<TPPLPoly>::iterator iter;
+	
+	if(!RemoveHoles(inpolys,&outpolys)) return 0;
+	for(iter=outpolys.begin();iter!=outpolys.end();iter++) {
+		if(!Triangulate_EC(&(*iter),triangles)) return 0;
+	}
+	return 1;
+}
+
+int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, list<TPPLPoly> *parts) {
+	list<TPPLPoly> triangles;
+	list<TPPLPoly>::iterator iter1,iter2;
+	TPPLPoly *poly1,*poly2;
+	TPPLPoly newpoly;
+	TPPLPoint d1,d2,p1,p2,p3;
+	long i11,i12,i21,i22,i13,i23,j,k;
+	bool isdiagonal;
+	long numreflex;
+
+	//check if the poly is already convex
+	numreflex = 0;
+	for(i11=0;i11<poly->GetNumPoints();i11++) {
+		if(i11==0) i12 = poly->GetNumPoints()-1;
+		else i12=i11-1;
+		if(i11==(poly->GetNumPoints()-1)) i13=0;
+		else i13=i11+1;
+		if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) {
+			numreflex = 1;
+			break;
+		}
+	}
+	if(numreflex == 0) {
+		parts->push_back(*poly);
+		return 1;
+	}
+
+	if(!Triangulate_EC(poly,&triangles)) return 0;
+
+	for(iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
+		poly1 = &(*iter1);
+		for(i11=0;i11<poly1->GetNumPoints();i11++) {
+			d1 = poly1->GetPoint(i11);
+			i12 = (i11+1)%(poly1->GetNumPoints());
+			d2 = poly1->GetPoint(i12);
+
+			isdiagonal = false;
+			for(iter2 = iter1; iter2 != triangles.end(); iter2++) {
+				if(iter1 == iter2) continue;
+				poly2 = &(*iter2);
+
+				for(i21=0;i21<poly2->GetNumPoints();i21++) {
+					if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue;
+					i22 = (i21+1)%(poly2->GetNumPoints());
+					if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue;
+					isdiagonal = true;
+					break;
+				}
+				if(isdiagonal) break;
+			}
+
+			if(!isdiagonal) continue;
+
+			p2 = poly1->GetPoint(i11);
+			if(i11 == 0) i13 = poly1->GetNumPoints()-1;
+			else i13 = i11-1;
+			p1 = poly1->GetPoint(i13);
+			if(i22 == (poly2->GetNumPoints()-1)) i23 = 0;
+			else i23 = i22+1;
+			p3 = poly2->GetPoint(i23);
+
+			if(!IsConvex(p1,p2,p3)) continue;
+			
+			p2 = poly1->GetPoint(i12);
+			if(i12 == (poly1->GetNumPoints()-1)) i13 = 0;
+			else i13 = i12+1;
+			p3 = poly1->GetPoint(i13);
+			if(i21 == 0) i23 = poly2->GetNumPoints()-1;
+			else i23 = i21-1;
+			p1 = poly2->GetPoint(i23);
+			
+			if(!IsConvex(p1,p2,p3)) continue;
+
+			newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2);
+			k = 0;
+			for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) {
+				newpoly[k] = poly1->GetPoint(j);
+				k++;
+			}
+			for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) {
+				newpoly[k] = poly2->GetPoint(j);
+				k++;
+			}
+
+			triangles.erase(iter2);
+			*iter1 = newpoly;
+			poly1 = &(*iter1);
+			i11 = -1;
+
+			continue;
+		}
+	}
+
+	for(iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
+		parts->push_back(*iter1);
+	}
+
+	return 1;
+}
+
+int TPPLPartition::ConvexPartition_HM(list<TPPLPoly> *inpolys, list<TPPLPoly> *parts) {
+	list<TPPLPoly> outpolys;
+	list<TPPLPoly>::iterator iter;
+	
+	if(!RemoveHoles(inpolys,&outpolys)) return 0;
+	for(iter=outpolys.begin();iter!=outpolys.end();iter++) {
+		if(!ConvexPartition_HM(&(*iter),parts)) return 0;
+	}
+	return 1;
+}
+
+//minimum-weight polygon triangulation by dynamic programming
+//O(n^3) time complexity
+//O(n^2) space complexity
+int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, list<TPPLPoly> *triangles) {
+	long i,j,k,gap,n;
+	DPState **dpstates;
+	TPPLPoint p1,p2,p3,p4;
+	long bestvertex;
+	tppl_float weight,minweight,d1,d2;
+	Diagonal diagonal,newdiagonal;
+	list<Diagonal> diagonals;
+	TPPLPoly triangle;
+	int ret = 1;
+
+	n = poly->GetNumPoints();
+	dpstates = new DPState *[n];
+	for(i=1;i<n;i++) {
+		dpstates[i] = new DPState[i];
+	}
+
+	//init states and visibility
+	for(i=0;i<(n-1);i++) {
+		p1 = poly->GetPoint(i);
+		for(j=i+1;j<n;j++) {
+			dpstates[j][i].visible = true;
+			dpstates[j][i].weight = 0;
+			dpstates[j][i].bestvertex = -1;
+			if(j!=(i+1)) {
+				p2 = poly->GetPoint(j);
+				
+				//visibility check
+				if(i==0) p3 = poly->GetPoint(n-1);
+				else p3 = poly->GetPoint(i-1);
+				if(i==(n-1)) p4 = poly->GetPoint(0);
+				else p4 = poly->GetPoint(i+1);
+				if(!InCone(p3,p1,p4,p2)) {
+					dpstates[j][i].visible = false;
+					continue;
+				}
+
+				if(j==0) p3 = poly->GetPoint(n-1);
+				else p3 = poly->GetPoint(j-1);
+				if(j==(n-1)) p4 = poly->GetPoint(0);
+				else p4 = poly->GetPoint(j+1);
+				if(!InCone(p3,p2,p4,p1)) {
+					dpstates[j][i].visible = false;
+					continue;
+				}
+
+				for(k=0;k<n;k++) {
+					p3 = poly->GetPoint(k);
+					if(k==(n-1)) p4 = poly->GetPoint(0);
+					else p4 = poly->GetPoint(k+1);
+					if(Intersects(p1,p2,p3,p4)) {
+						dpstates[j][i].visible = false;
+						break;
+					}
+				}
+			}
+		}
+	}
+	dpstates[n-1][0].visible = true;
+	dpstates[n-1][0].weight = 0;
+	dpstates[n-1][0].bestvertex = -1;
+
+	for(gap = 2; gap<n; gap++) {
+		for(i=0; i<(n-gap); i++) {
+			j = i+gap;
+			if(!dpstates[j][i].visible) continue; 
+			bestvertex = -1;
+			for(k=(i+1);k<j;k++) {
+				if(!dpstates[k][i].visible) continue; 
+				if(!dpstates[j][k].visible) continue;
+
+				if(k<=(i+1)) d1=0;
+				else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k));
+				if(j<=(k+1)) d2=0;
+				else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j));
+
+				weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
+
+				if((bestvertex == -1)||(weight<minweight)) {
+					bestvertex = k;
+					minweight = weight;
+				}
+			}
+			if(bestvertex == -1) {
+				for(i=1;i<n;i++) {
+					delete [] dpstates[i];
+				}
+				delete [] dpstates;
+
+				return 0;
+			}
+			
+			dpstates[j][i].bestvertex = bestvertex;
+			dpstates[j][i].weight = minweight;
+		}
+	}
+
+	newdiagonal.index1 = 0;
+	newdiagonal.index2 = n-1;
+	diagonals.push_back(newdiagonal);
+	while(!diagonals.empty()) {
+		diagonal = *(diagonals.begin());
+		diagonals.pop_front();
+		bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
+		if(bestvertex == -1) {
+			ret = 0;		
+			break;
+		}
+		triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2));
+		triangles->push_back(triangle);
+		if(bestvertex > (diagonal.index1+1)) {
+			newdiagonal.index1 = diagonal.index1;
+			newdiagonal.index2 = bestvertex;
+			diagonals.push_back(newdiagonal);
+		}
+		if(diagonal.index2 > (bestvertex+1)) {
+			newdiagonal.index1 = bestvertex;
+			newdiagonal.index2 = diagonal.index2;
+			diagonals.push_back(newdiagonal);
+		}
+	}
+
+	for(i=1;i<n;i++) {
+		delete [] dpstates[i];
+	}
+	delete [] dpstates;
+
+	return ret;
+}
+
+void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) {
+	Diagonal newdiagonal;
+	list<Diagonal> *pairs;
+	long w2;
+
+	w2 = dpstates[a][b].weight;
+	if(w>w2) return;
+	
+	pairs = &(dpstates[a][b].pairs);
+	newdiagonal.index1 = i;
+	newdiagonal.index2 = j;
+
+	if(w<w2) {
+		pairs->clear();
+		pairs->push_front(newdiagonal);
+		dpstates[a][b].weight = w;
+	} else {
+		if((!pairs->empty())&&(i <= pairs->begin()->index1)) return;
+		while((!pairs->empty())&&(pairs->begin()->index2 >= j)) pairs->pop_front();
+		pairs->push_front(newdiagonal);
+	}
+}
+
+void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+	list<Diagonal> *pairs;
+	list<Diagonal>::iterator iter,lastiter;
+	long top;
+	long w;
+
+	if(!dpstates[i][j].visible) return;
+	top = j;
+	w = dpstates[i][j].weight;
+    if(k-j > 1) {
+		if (!dpstates[j][k].visible) return;
+		w += dpstates[j][k].weight + 1;
+    }
+	if(j-i > 1) {
+		pairs = &(dpstates[i][j].pairs);
+		iter = pairs->end();
+		lastiter = pairs->end();
+		while(iter!=pairs->begin()) {
+			iter--;
+			if(!IsReflex(vertices[iter->index2].p,vertices[j].p,vertices[k].p)) lastiter = iter;
+			else break;
+		}
+		if(lastiter == pairs->end()) w++;
+		else {
+			if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->index1].p)) w++;
+			else top = lastiter->index1;
+		}
+	}
+	UpdateState(i,k,w,top,j,dpstates);
+}
+
+void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+	list<Diagonal> *pairs;
+	list<Diagonal>::iterator iter,lastiter;
+	long top;
+	long w;
+
+	if(!dpstates[j][k].visible) return;
+	top = j;
+	w = dpstates[j][k].weight;
+	
+	if (j-i > 1) {
+		if (!dpstates[i][j].visible) return;
+		w += dpstates[i][j].weight + 1;
+	}
+	if (k-j > 1) {
+		pairs = &(dpstates[j][k].pairs);
+
+		iter = pairs->begin();
+		if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p))) {
+			lastiter = iter;
+			while(iter!=pairs->end()) {
+				if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p)) {
+					lastiter = iter;
+					iter++;
+				}
+				else break;
+			}
+			if(IsReflex(vertices[lastiter->index2].p,vertices[k].p,vertices[i].p)) w++;
+			else top = lastiter->index2;
+		} else w++;
+	}
+	UpdateState(i,k,w,j,top,dpstates);
+}
+
+int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, list<TPPLPoly> *parts) {
+	TPPLPoint p1,p2,p3,p4;
+	PartitionVertex *vertices;
+	DPState2 **dpstates;
+	long i,j,k,n,gap;
+	list<Diagonal> diagonals,diagonals2;
+	Diagonal diagonal,newdiagonal;
+	list<Diagonal> *pairs,*pairs2;
+	list<Diagonal>::iterator iter,iter2;
+	int ret;
+	TPPLPoly newpoly;
+	list<long> indices;
+	list<long>::iterator iiter;
+	bool ijreal,jkreal;
+
+	n = poly->GetNumPoints();
+	vertices = new PartitionVertex[n];
+
+	dpstates = new DPState2 *[n];
+	for(i=0;i<n;i++) {
+		dpstates[i] = new DPState2[n];
+	}
+
+	//init vertex information
+	for(i=0;i<n;i++) {
+		vertices[i].p = poly->GetPoint(i);
+		vertices[i].isActive = true;
+		if(i==0) vertices[i].previous = &(vertices[n-1]);
+		else vertices[i].previous = &(vertices[i-1]);
+		if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]);
+		else vertices[i].next = &(vertices[i+1]);
+	}
+	for(i=1;i<n;i++) {
+		UpdateVertexReflexity(&(vertices[i]));
+	}
+
+	//init states and visibility
+	for(i=0;i<(n-1);i++) {
+		p1 = poly->GetPoint(i);
+		for(j=i+1;j<n;j++) {
+			dpstates[i][j].visible = true;
+			if(j==i+1) {
+				dpstates[i][j].weight = 0;
+			} else {
+				dpstates[i][j].weight = 2147483647;
+			}
+			if(j!=(i+1)) {
+				p2 = poly->GetPoint(j);
+				
+				//visibility check
+				if(!InCone(&vertices[i],p2)) {
+					dpstates[i][j].visible = false;
+					continue;
+				}
+				if(!InCone(&vertices[j],p1)) {
+					dpstates[i][j].visible = false;
+					continue;
+				}
+
+				for(k=0;k<n;k++) {
+					p3 = poly->GetPoint(k);
+					if(k==(n-1)) p4 = poly->GetPoint(0);
+					else p4 = poly->GetPoint(k+1);
+					if(Intersects(p1,p2,p3,p4)) {
+						dpstates[i][j].visible = false;
+						break;
+					}
+				}
+			}
+		}
+	}
+	for(i=0;i<(n-2);i++) {
+		j = i+2;
+		if(dpstates[i][j].visible) {
+			dpstates[i][j].weight = 0;
+			newdiagonal.index1 = i+1;
+			newdiagonal.index2 = i+1;
+			dpstates[i][j].pairs.push_back(newdiagonal);
+		}
+	}
+
+	dpstates[0][n-1].visible = true;
+	vertices[0].isConvex = false; //by convention
+
+	for(gap=3; gap<n; gap++) {
+		for(i=0;i<n-gap;i++) {
+			if(vertices[i].isConvex) continue;
+			k = i+gap;
+			if(dpstates[i][k].visible) {
+				if(!vertices[k].isConvex) {
+					for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates);
+				} else {
+					for(j=i+1;j<(k-1);j++) {
+						if(vertices[j].isConvex) continue;				
+						TypeA(i,j,k,vertices,dpstates);
+					}
+					TypeA(i,k-1,k,vertices,dpstates);
+				}
+			}
+		}
+		for(k=gap;k<n;k++) {
+			if(vertices[k].isConvex) continue;
+			i = k-gap;
+			if((vertices[i].isConvex)&&(dpstates[i][k].visible)) {
+				TypeB(i,i+1,k,vertices,dpstates);
+				for(j=i+2;j<k;j++) {
+					if(vertices[j].isConvex) continue;				
+					TypeB(i,j,k,vertices,dpstates);
+				}
+			}
+		}
+	}
+
+
+	//recover solution
+	ret = 1;
+	newdiagonal.index1 = 0;
+	newdiagonal.index2 = n-1;
+	diagonals.push_front(newdiagonal);
+	while(!diagonals.empty()) {
+		diagonal = *(diagonals.begin());
+		diagonals.pop_front();
+		if((diagonal.index2 - diagonal.index1) <=1) continue;
+		pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+		if(pairs->empty()) {
+			ret = 0;
+			break;
+		}
+		if(!vertices[diagonal.index1].isConvex) {
+			iter = pairs->end();
+			iter--;
+			j = iter->index2;
+			newdiagonal.index1 = j;
+			newdiagonal.index2 = diagonal.index2;
+			diagonals.push_front(newdiagonal);
+			if((j - diagonal.index1)>1) {
+				if(iter->index1 != iter->index2) {
+					pairs2 = &(dpstates[diagonal.index1][j].pairs);
+					while(1) {
+						if(pairs2->empty()) {
+							ret = 0;
+							break;
+						}
+						iter2 = pairs2->end();
+						iter2--;
+						if(iter->index1 != iter2->index1) pairs2->pop_back();
+						else break;
+					}
+					if(ret == 0) break;
+				}
+				newdiagonal.index1 = diagonal.index1;
+				newdiagonal.index2 = j;
+				diagonals.push_front(newdiagonal);
+			}
+		} else {
+			iter = pairs->begin();
+			j = iter->index1;
+			newdiagonal.index1 = diagonal.index1;
+			newdiagonal.index2 = j;
+			diagonals.push_front(newdiagonal);
+			if((diagonal.index2 - j) > 1) {
+				if(iter->index1 != iter->index2) {
+					pairs2 = &(dpstates[j][diagonal.index2].pairs);
+					while(1) {
+						if(pairs2->empty()) {
+							ret = 0;
+							break;
+						}
+						iter2 = pairs2->begin();
+						if(iter->index2 != iter2->index2) pairs2->pop_front();
+						else break;
+					}
+					if(ret == 0) break;
+				}
+				newdiagonal.index1 = j;
+				newdiagonal.index2 = diagonal.index2;
+				diagonals.push_front(newdiagonal);
+			}
+		}
+	}
+
+	if(ret == 0) {
+		for(i=0;i<n;i++) {
+			delete [] dpstates[i];
+		}
+		delete [] dpstates;
+		delete [] vertices;
+
+		return ret;
+	}
+
+	newdiagonal.index1 = 0;
+	newdiagonal.index2 = n-1;
+	diagonals.push_front(newdiagonal);
+	while(!diagonals.empty()) {
+		diagonal = *(diagonals.begin());
+		diagonals.pop_front();
+		if((diagonal.index2 - diagonal.index1) <= 1) continue;
+		
+		indices.clear();
+		diagonals2.clear();
+		indices.push_back(diagonal.index1);
+		indices.push_back(diagonal.index2);
+		diagonals2.push_front(diagonal);
+
+		while(!diagonals2.empty()) {
+			diagonal = *(diagonals2.begin());
+			diagonals2.pop_front();
+			if((diagonal.index2 - diagonal.index1) <= 1) continue;
+			ijreal = true;
+			jkreal = true;
+			pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+			if(!vertices[diagonal.index1].isConvex) {
+				iter = pairs->end();
+				iter--;
+				j = iter->index2;
+				if(iter->index1 != iter->index2) ijreal = false;
+			} else {
+				iter = pairs->begin();
+				j = iter->index1;
+				if(iter->index1 != iter->index2) jkreal = false;
+			}
+
+			newdiagonal.index1 = diagonal.index1;
+			newdiagonal.index2 = j;
+			if(ijreal) {
+				diagonals.push_back(newdiagonal);
+			} else {
+				diagonals2.push_back(newdiagonal);
+			}
+
+			newdiagonal.index1 = j;
+			newdiagonal.index2 = diagonal.index2;
+			if(jkreal) {
+				diagonals.push_back(newdiagonal);
+			} else {
+				diagonals2.push_back(newdiagonal);
+			}
+
+			indices.push_back(j);
+		}
+
+		indices.sort();
+		newpoly.Init((long)indices.size());
+		k=0;
+		for(iiter = indices.begin();iiter!=indices.end();iiter++) {
+			newpoly[k] = vertices[*iiter].p;
+			k++;
+		}
+		parts->push_back(newpoly);
+	}
+
+	for(i=0;i<n;i++) {
+		delete [] dpstates[i];
+	}
+	delete [] dpstates;
+	delete [] vertices;
+
+	return ret;
+}
+
+//triangulates a set of polygons by first partitioning them into monotone polygons
+//O(n*log(n)) time complexity, O(n) space complexity
+//the algorithm used here is outlined in the book
+//"Computational Geometry: Algorithms and Applications" 
+//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
+int TPPLPartition::MonotonePartition(list<TPPLPoly> *inpolys, list<TPPLPoly> *monotonePolys) {
+	list<TPPLPoly>::iterator iter;
+	MonotoneVertex *vertices;
+	long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices;
+	long polystartindex, polyendindex;
+	TPPLPoly *poly;
+	MonotoneVertex *v,*v2,*vprev,*vnext;
+	ScanLineEdge newedge;
+	bool error = false;
+
+	numvertices = 0;
+	for(iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+		numvertices += iter->GetNumPoints();
+	}
+
+	maxnumvertices = numvertices*3;
+	vertices = new MonotoneVertex[maxnumvertices];
+	newnumvertices = numvertices;
+
+	polystartindex = 0;
+	for(iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+		poly = &(*iter);
+		polyendindex = polystartindex + poly->GetNumPoints()-1;
+		for(i=0;i<poly->GetNumPoints();i++) {
+			vertices[i+polystartindex].p = poly->GetPoint(i);
+			if(i==0) vertices[i+polystartindex].previous = polyendindex;
+			else vertices[i+polystartindex].previous = i+polystartindex-1;
+			if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex;
+			else vertices[i+polystartindex].next = i+polystartindex+1;
+		}
+		polystartindex = polyendindex+1;
+	}
+
+	//construct the priority queue
+	long *priority = new long [numvertices];
+	for(i=0;i<numvertices;i++) priority[i] = i;
+	std::sort(priority,&(priority[numvertices]),VertexSorter(vertices));
+
+	//determine vertex types
+	char *vertextypes = new char[maxnumvertices];
+	for(i=0;i<numvertices;i++) {
+		v = &(vertices[i]);
+		vprev = &(vertices[v->previous]);
+		vnext = &(vertices[v->next]);
+
+		if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) {
+			if(IsConvex(vnext->p,vprev->p,v->p)) {
+				vertextypes[i] = TPPL_VERTEXTYPE_START;
+			} else {
+				vertextypes[i] = TPPL_VERTEXTYPE_SPLIT;
+			}
+		} else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) {
+			if(IsConvex(vnext->p,vprev->p,v->p))
+			{
+				vertextypes[i] = TPPL_VERTEXTYPE_END;
+			} else {
+				vertextypes[i] = TPPL_VERTEXTYPE_MERGE;
+			}
+		} else {
+			vertextypes[i] = TPPL_VERTEXTYPE_REGULAR;
+		}
+	}
+
+	//helpers
+	long *helpers = new long[maxnumvertices];
+
+	//binary search tree that holds edges intersecting the scanline
+	//note that while set doesn't actually have to be implemented as a tree
+	//complexity requirements for operations are the same as for the balanced binary search tree
+	set<ScanLineEdge> edgeTree;
+	//store iterators to the edge tree elements
+	//this makes deleting existing edges much faster
+	set<ScanLineEdge>::iterator *edgeTreeIterators,edgeIter;
+	edgeTreeIterators = new set<ScanLineEdge>::iterator[maxnumvertices];
+	pair<set<ScanLineEdge>::iterator,bool> edgeTreeRet;
+	for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = edgeTree.end();
+
+	//for each vertex
+	for(i=0;i<numvertices;i++) {
+		vindex = priority[i];
+		v = &(vertices[vindex]);
+		vindex2 = vindex;
+		v2 = v;
+
+		//depending on the vertex type, do the appropriate action
+		//comments in the following sections are copied from "Computational Geometry: Algorithms and Applications"
+		switch(vertextypes[vindex]) {
+			case TPPL_VERTEXTYPE_START:
+				//Insert ei in T and set helper(ei) to vi.
+				newedge.p1 = v->p;
+				newedge.p2 = vertices[v->next].p;
+				newedge.index = vindex;
+				edgeTreeRet = edgeTree.insert(newedge);
+				edgeTreeIterators[vindex] = edgeTreeRet.first;
+				helpers[vindex] = vindex;
+				break;
+
+			case TPPL_VERTEXTYPE_END:
+				//if helper(ei-1) is a merge vertex
+				if(vertextypes[helpers[v->previous]]==TPPL_VERTEXTYPE_MERGE) {
+					//Insert the diagonal connecting vi to helper(ei-1) in D.
+					AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], 
+						vertextypes, edgeTreeIterators, &edgeTree, helpers);
+				}
+				//Delete ei-1 from T
+				edgeTree.erase(edgeTreeIterators[v->previous]);
+				break;
+
+			case TPPL_VERTEXTYPE_SPLIT:
+				//Search in T to find the edge e j directly left of vi.
+				newedge.p1 = v->p;
+				newedge.p2 = v->p;
+				edgeIter = edgeTree.lower_bound(newedge);
+				if(edgeIter == edgeTree.begin()) {
+					error = true;
+					break;
+				}
+				edgeIter--;
+				//Insert the diagonal connecting vi to helper(ej) in D.
+				AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index],
+					vertextypes, edgeTreeIterators, &edgeTree, helpers);
+				vindex2 = newnumvertices-2;
+				v2 = &(vertices[vindex2]);
+				//helper(e j)�vi
+				helpers[edgeIter->index] = vindex;
+				//Insert ei in T and set helper(ei) to vi.
+				newedge.p1 = v2->p;
+				newedge.p2 = vertices[v2->next].p;
+				newedge.index = vindex2;
+				edgeTreeRet = edgeTree.insert(newedge);
+				edgeTreeIterators[vindex2] = edgeTreeRet.first;
+				helpers[vindex2] = vindex2;
+				break;
+
+			case TPPL_VERTEXTYPE_MERGE:
+				//if helper(ei-1) is a merge vertex
+				if(vertextypes[helpers[v->previous]]==TPPL_VERTEXTYPE_MERGE) {
+					//Insert the diagonal connecting vi to helper(ei-1) in D.
+					AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+						vertextypes, edgeTreeIterators, &edgeTree, helpers);
+					vindex2 = newnumvertices-2;
+					v2 = &(vertices[vindex2]);
+				}
+				//Delete ei-1 from T.
+				edgeTree.erase(edgeTreeIterators[v->previous]);
+				//Search in T to find the edge e j directly left of vi.
+				newedge.p1 = v->p;
+				newedge.p2 = v->p;
+				edgeIter = edgeTree.lower_bound(newedge);
+				if(edgeIter == edgeTree.begin()) {
+					error = true;
+					break;
+				}
+				edgeIter--;
+				//if helper(ej) is a merge vertex
+				if(vertextypes[helpers[edgeIter->index]]==TPPL_VERTEXTYPE_MERGE) {
+					//Insert the diagonal connecting vi to helper(e j) in D.
+					AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->index],
+						vertextypes, edgeTreeIterators, &edgeTree, helpers);
+				}
+				//helper(e j)�vi
+				helpers[edgeIter->index] = vindex2;
+				break;
+
+			case TPPL_VERTEXTYPE_REGULAR:
+				//if the interior of P lies to the right of vi
+				if(Below(v->p,vertices[v->previous].p)) {
+					//if helper(ei-1) is a merge vertex
+					if(vertextypes[helpers[v->previous]]==TPPL_VERTEXTYPE_MERGE) {
+						//Insert the diagonal connecting vi to helper(ei-1) in D.
+						AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+							vertextypes, edgeTreeIterators, &edgeTree, helpers);
+						vindex2 = newnumvertices-2;
+						v2 = &(vertices[vindex2]);
+					}
+					//Delete ei-1 from T.
+					edgeTree.erase(edgeTreeIterators[v->previous]);
+					//Insert ei in T and set helper(ei) to vi.
+					newedge.p1 = v2->p;
+					newedge.p2 = vertices[v2->next].p;
+					newedge.index = vindex2;
+					edgeTreeRet = edgeTree.insert(newedge);
+					edgeTreeIterators[vindex2] = edgeTreeRet.first;
+					helpers[vindex2] = vindex;
+				} else {
+					//Search in T to find the edge ej directly left of vi.
+					newedge.p1 = v->p;
+					newedge.p2 = v->p;
+					edgeIter = edgeTree.lower_bound(newedge);
+					if(edgeIter == edgeTree.begin()) {
+						error = true;
+						break;
+					}
+					edgeIter--;
+					//if helper(ej) is a merge vertex
+					if(vertextypes[helpers[edgeIter->index]]==TPPL_VERTEXTYPE_MERGE) {
+						//Insert the diagonal connecting vi to helper(e j) in D.
+						AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index],
+							vertextypes, edgeTreeIterators, &edgeTree, helpers);
+					}
+					//helper(e j)�vi
+					helpers[edgeIter->index] = vindex;
+				}
+				break;
+		}
+
+		if(error) break;
+	}
+
+	char *used = new char[newnumvertices];
+	memset(used,0,newnumvertices*sizeof(char));
+
+	if(!error) {
+		//return result
+		long size;
+		TPPLPoly mpoly;
+		for(i=0;i<newnumvertices;i++) {
+			if(used[i]) continue;
+			v = &(vertices[i]);
+			vnext = &(vertices[v->next]);
+			size = 1;
+			while(vnext!=v) {
+				vnext = &(vertices[vnext->next]);
+				size++;
+			}
+			mpoly.Init(size);
+			v = &(vertices[i]);
+			mpoly[0] = v->p;
+			vnext = &(vertices[v->next]);
+			size = 1;
+			used[i] = 1;
+			used[v->next] = 1;
+			while(vnext!=v) {
+				mpoly[size] = vnext->p;
+				used[vnext->next] = 1;
+				vnext = &(vertices[vnext->next]);
+				size++;
+			}
+			monotonePolys->push_back(mpoly);
+		}
+	}
+
+	//cleanup
+	delete [] vertices;
+	delete [] priority;
+	delete [] vertextypes;
+	delete [] edgeTreeIterators;
+	delete [] helpers;
+	delete [] used;
+
+	if(error) {
+		return 0;
+	} else {
+		return 1;
+	}
+}
+
+//adds a diagonal to the doubly-connected list of vertices
+void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, 
+								char *vertextypes, set<ScanLineEdge>::iterator *edgeTreeIterators, 
+								set<ScanLineEdge> *edgeTree, long *helpers) 
+{
+	long newindex1,newindex2;
+
+	newindex1 = *numvertices;
+	(*numvertices)++;
+	newindex2 = *numvertices;
+	(*numvertices)++;
+
+	vertices[newindex1].p = vertices[index1].p;
+	vertices[newindex2].p = vertices[index2].p;
+
+	vertices[newindex2].next = vertices[index2].next;
+	vertices[newindex1].next = vertices[index1].next;
+
+	vertices[vertices[index2].next].previous = newindex2;
+	vertices[vertices[index1].next].previous = newindex1;
+
+	vertices[index1].next = newindex2;
+	vertices[newindex2].previous = index1;
+
+	vertices[index2].next = newindex1;
+	vertices[newindex1].previous = index2;
+
+	//update all relevant structures
+	vertextypes[newindex1] = vertextypes[index1];
+	edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
+	helpers[newindex1] = helpers[index1];
+	if(edgeTreeIterators[newindex1] != edgeTree->end())
+		edgeTreeIterators[newindex1]->index = newindex1;
+	vertextypes[newindex2] = vertextypes[index2];
+	edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
+	helpers[newindex2] = helpers[index2];
+	if(edgeTreeIterators[newindex2] != edgeTree->end())
+		edgeTreeIterators[newindex2]->index = newindex2;
+}
+
+bool TPPLPartition::Below(TPPLPoint &p1, TPPLPoint &p2) {
+	if(p1.y < p2.y) return true;
+	else if(p1.y == p2.y) {
+		if(p1.x < p2.x) return true;
+	}
+	return false;
+}
+
+//sorts in the falling order of y values, if y is equal, x is used instead
+bool TPPLPartition::VertexSorter::operator() (long index1, long index2) {
+	if(vertices[index1].p.y > vertices[index2].p.y) return true;
+	else if(vertices[index1].p.y == vertices[index2].p.y) {
+		if(vertices[index1].p.x > vertices[index2].p.x) return true;
+	}
+	return false;
+}
+
+bool TPPLPartition::ScanLineEdge::IsConvex(const TPPLPoint& p1, const TPPLPoint& p2, const TPPLPoint& p3) const {
+	tppl_float tmp;
+	tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+	if(tmp>0) return 1;
+	else return 0;
+}
+
+bool TPPLPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const {
+	if(other.p1.y == other.p2.y) {
+		if(p1.y == p2.y) {
+			if(p1.y < other.p1.y) return true;
+			else return false;
+		}
+		if(IsConvex(p1,p2,other.p1)) return true;
+		else return false;
+	} else if(p1.y == p2.y) {
+		if(IsConvex(other.p1,other.p2,p1)) return false;
+		else return true;	
+	} else if(p1.y < other.p1.y) {
+		if(IsConvex(other.p1,other.p2,p1)) return false;
+		else return true;			
+	} else {
+		if(IsConvex(p1,p2,other.p1)) return true;
+		else return false;
+	}
+}
+
+//triangulates monotone polygon
+//O(n) time, O(n) space complexity
+int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, list<TPPLPoly> *triangles) {
+	long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex;
+	TPPLPoint *points;
+	long numpoints;
+	TPPLPoly triangle;
+
+	numpoints = inPoly->GetNumPoints();
+	points = inPoly->GetPoints();
+
+	//trivial calses
+	if(numpoints < 3) return 0;
+	if(numpoints == 3) {
+		triangles->push_back(*inPoly);
+	}
+
+	topindex = 0; bottomindex=0;
+	for(i=1;i<numpoints;i++) {
+		if(Below(points[i],points[bottomindex])) bottomindex = i;
+		if(Below(points[topindex],points[i])) topindex = i;
+	}
+
+	//check if the poly is really monotone
+	i = topindex;
+	while(i!=bottomindex) {
+		i2 = i+1; if(i2>=numpoints) i2 = 0;
+		if(!Below(points[i2],points[i])) return 0;
+		i = i2;
+	}
+	i = bottomindex;
+	while(i!=topindex) {
+		i2 = i+1; if(i2>=numpoints) i2 = 0;
+		if(!Below(points[i],points[i2])) return 0;
+		i = i2;
+	}
+
+	char *vertextypes = new char[numpoints];
+	long *priority = new long[numpoints];
+
+	//merge left and right vertex chains
+	priority[0] = topindex;
+	vertextypes[topindex] = 0;
+	leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0;
+	rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1;
+	for(i=1;i<(numpoints-1);i++) {
+		if(leftindex==bottomindex) {
+			priority[i] = rightindex;
+			rightindex--; if(rightindex<0) rightindex = numpoints-1;
+			vertextypes[priority[i]] = -1;
+		} else if(rightindex==bottomindex) {
+			priority[i] = leftindex;
+			leftindex++;  if(leftindex>=numpoints) leftindex = 0;
+			vertextypes[priority[i]] = 1;
+		} else {
+			if(Below(points[leftindex],points[rightindex])) {
+				priority[i] = rightindex;
+				rightindex--; if(rightindex<0) rightindex = numpoints-1;
+				vertextypes[priority[i]] = -1;
+			} else {
+				priority[i] = leftindex;
+				leftindex++;  if(leftindex>=numpoints) leftindex = 0;
+				vertextypes[priority[i]] = 1;			
+			}
+		}
+	}
+	priority[i] = bottomindex;
+	vertextypes[bottomindex] = 0;
+
+	long *stack = new long[numpoints];
+	long stackptr = 0;
+
+	stack[0] = priority[0];
+	stack[1] = priority[1];
+	stackptr = 2;
+
+	//for each vertex from top to bottom trim as many triangles as possible
+	for(i=2;i<(numpoints-1);i++) {
+		vindex = priority[i];
+		if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) {
+			for(j=0;j<(stackptr-1);j++) {
+				if(vertextypes[vindex]==1) {
+					triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+				} else {
+					triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+				}
+				triangles->push_back(triangle);
+			}
+			stack[0] = priority[i-1];
+			stack[1] = priority[i];
+			stackptr = 2;
+		} else {
+			stackptr--;
+			while(stackptr>0) {
+				if(vertextypes[vindex]==1) {
+					if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) {
+						triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]);
+						triangles->push_back(triangle);
+						stackptr--;
+					} else {
+						break;
+					}
+				} else {
+					if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) {
+						triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]);
+						triangles->push_back(triangle);
+						stackptr--;
+					} else {
+						break;
+					}
+				}
+			}
+			stackptr++;
+			stack[stackptr] = vindex;
+			stackptr++;
+		}
+	}
+	vindex = priority[i];
+	for(j=0;j<(stackptr-1);j++) {
+		if(vertextypes[stack[j+1]]==1) {
+			triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+		} else {
+			triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+		}
+		triangles->push_back(triangle);
+	}
+
+	delete [] priority;
+	delete [] vertextypes;
+	delete [] stack;
+
+	return 1;
+}
+
+int TPPLPartition::Triangulate_MONO(list<TPPLPoly> *inpolys, list<TPPLPoly> *triangles) {
+	list<TPPLPoly> monotone;
+	list<TPPLPoly>::iterator iter;
+
+	if(!MonotonePartition(inpolys,&monotone)) return 0;
+	for(iter = monotone.begin(); iter!=monotone.end();iter++) {
+		if(!TriangulateMonotone(&(*iter),triangles)) return 0;
+	}
+	return 1;
+}
+
+int TPPLPartition::Triangulate_MONO(TPPLPoly *poly, list<TPPLPoly> *triangles) {
+	list<TPPLPoly> polys;
+	polys.push_back(*poly);
+
+	return Triangulate_MONO(&polys, triangles);
+}
diff --git a/test/PCBView/polypartition/src/polypartition.h b/test/PCBView/polypartition/src/polypartition.h
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/src/polypartition.h
@@ -0,0 +1,350 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+#ifndef POLYPARTITION_H
+#define POLYPARTITION_H
+
+#include <list>
+#include <set>
+
+typedef double tppl_float;
+
+#define TPPL_CCW 1
+#define TPPL_CW -1
+
+//2D point structure
+struct TPPLPoint {
+    tppl_float x;
+    tppl_float y;
+    
+    TPPLPoint operator + (const TPPLPoint& p) const {
+        TPPLPoint r;
+        r.x = x + p.x;
+        r.y = y + p.y;
+        return r;
+    }
+    
+    TPPLPoint operator - (const TPPLPoint& p) const {
+        TPPLPoint r;
+        r.x = x - p.x;
+        r.y = y - p.y;
+        return r;
+    }
+    
+    TPPLPoint operator * (const tppl_float f ) const {
+        TPPLPoint r;
+        r.x = x*f;
+        r.y = y*f;
+        return r;
+    }
+    
+    TPPLPoint operator / (const tppl_float f ) const {
+        TPPLPoint r;
+        r.x = x/f;
+        r.y = y/f;
+        return r;
+    }
+    
+    bool operator==(const TPPLPoint& p) const {
+        if((x == p.x)&&(y==p.y)) return true;
+        else return false;
+    }
+    
+    bool operator!=(const TPPLPoint& p) const {
+        if((x == p.x)&&(y==p.y)) return false;
+        else return true;
+    }
+    };
+    
+    //Polygon implemented as an array of points with a 'hole' flag
+    class TPPLPoly {
+    protected:
+        
+        TPPLPoint *points;
+        long numpoints;
+        bool hole;
+        
+    public:
+        
+        //constructors/destructors
+        TPPLPoly();
+        ~TPPLPoly();
+        
+        TPPLPoly(const TPPLPoly &src);
+        TPPLPoly& operator=(const TPPLPoly &src);
+        
+        //getters and setters
+        long GetNumPoints() {
+            return numpoints;
+        }
+        
+        bool IsHole() {
+            return hole;
+        }
+        
+        void SetHole(bool hole) {
+            this->hole = hole;
+        }
+        
+        TPPLPoint &GetPoint(long i) {
+            return points[i];
+        }
+        
+        TPPLPoint *GetPoints() {
+            return points;
+        }
+        
+        TPPLPoint& operator[] (int i) {
+            return points[i];
+        }
+        
+        //clears the polygon points
+        void Clear();
+        
+        //inits the polygon with numpoints vertices
+        void Init(long numpoints);
+        
+        //creates a triangle with points p1,p2,p3
+        void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
+        
+        //inverts the orfer of vertices
+        void Invert();
+        
+        //returns the orientation of the polygon
+        //possible values:
+        //   TPPL_CCW : polygon vertices are in counter-clockwise order
+        //   TPPL_CW : polygon vertices are in clockwise order
+        //       0 : the polygon has no (measurable) area
+        int GetOrientation();
+        
+        //sets the polygon orientation
+        //orientation can be
+        //   TPPL_CCW : sets vertices in counter-clockwise order
+        //   TPPL_CW : sets vertices in clockwise order
+        void SetOrientation(int orientation);
+    };
+    
+    class TPPLPartition {
+    protected:
+        struct PartitionVertex {
+            bool isActive;
+            bool isConvex;
+            bool isEar;
+            
+            TPPLPoint p;
+            tppl_float angle;
+            PartitionVertex *previous;
+            PartitionVertex *next;
+        };
+        
+        struct MonotoneVertex {
+            TPPLPoint p;
+            long previous;
+            long next;
+        };
+        
+        class VertexSorter{
+            MonotoneVertex *vertices;
+        public:
+            VertexSorter(MonotoneVertex *v) : vertices(v) {}
+            bool operator() (long index1, long index2);
+        };
+        
+        struct Diagonal {
+            long index1;
+            long index2;
+        };
+        
+        //dynamic programming state for minimum-weight triangulation
+        struct DPState {
+            bool visible;
+            tppl_float weight;
+            long bestvertex;
+        };
+        
+        //dynamic programming state for convex partitioning
+        struct DPState2 {
+            bool visible;
+            long weight;
+            std::list<Diagonal> pairs;
+        };
+        
+        //edge that intersects the scanline
+        struct ScanLineEdge {
+            mutable long index;
+            TPPLPoint p1;
+            TPPLPoint p2;
+            
+            //determines if the edge is to the left of another edge
+            bool operator< (const ScanLineEdge & other) const;
+            
+            bool IsConvex(const TPPLPoint& p1, const TPPLPoint& p2, const TPPLPoint& p3) const;
+        };
+        
+        //standard helper functions
+        bool IsConvex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3);
+        bool IsReflex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3);
+        bool IsInside(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3, TPPLPoint &p);
+        
+        bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
+        bool InCone(PartitionVertex *v, TPPLPoint &p);
+        
+        int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
+        
+        TPPLPoint Normalize(const TPPLPoint &p);
+        tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
+        
+        //helper functions for Triangulate_EC
+        void UpdateVertexReflexity(PartitionVertex *v);
+        void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
+        
+        //helper functions for ConvexPartition_OPT
+        void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
+        void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+        void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+        
+        //helper functions for MonotonePartition
+        bool Below(TPPLPoint &p1, TPPLPoint &p2);
+        void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+            char *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators,
+            std::set<ScanLineEdge> *edgeTree, long *helpers);
+        
+        //triangulates a monotone polygon, used in Triangulate_MONO
+        int TriangulateMonotone(TPPLPoly *inPoly, std::list<TPPLPoly> *triangles);
+        
+    public:
+        
+        //simple heuristic procedure for removing holes from a list of polygons
+        //works by creating a diagonal from the rightmost hole vertex to some visible vertex
+        //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   inpolys : a list of polygons that can contain holes
+        //             vertices of all non-hole polys have to be in counter-clockwise order
+        //             vertices of all hole polys have to be in clockwise order
+        //   outpolys : a list of polygons without holes
+        //returns 1 on success, 0 on failure
+        int RemoveHoles(std::list<TPPLPoly> *inpolys, std::list<TPPLPoly> *outpolys);
+        
+        //triangulates a polygon by ear clipping
+        //time complexity O(n^2), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   poly : an input polygon to be triangulated
+        //          vertices have to be in counter-clockwise order
+        //   triangles : a list of triangles (result)
+        //returns 1 on success, 0 on failure
+        int Triangulate_EC(TPPLPoly *poly, std::list<TPPLPoly> *triangles);
+        
+        //triangulates a list of polygons that may contain holes by ear clipping algorithm
+        //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon
+        //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   inpolys : a list of polygons to be triangulated (can contain holes)
+        //             vertices of all non-hole polys have to be in counter-clockwise order
+        //             vertices of all hole polys have to be in clockwise order
+        //   triangles : a list of triangles (result)
+        //returns 1 on success, 0 on failure
+        int Triangulate_EC(std::list<TPPLPoly> *inpolys, std::list<TPPLPoly> *triangles);
+        
+        //creates an optimal polygon triangulation in terms of minimal edge length
+        //time complexity: O(n^3), n is the number of vertices
+        //space complexity: O(n^2)
+        //params:
+        //   poly : an input polygon to be triangulated
+        //          vertices have to be in counter-clockwise order
+        //   triangles : a list of triangles (result)
+        //returns 1 on success, 0 on failure
+        int Triangulate_OPT(TPPLPoly *poly, std::list<TPPLPoly> *triangles);
+        
+        //triangulates a polygons by firstly partitioning it into monotone polygons
+        //time complexity: O(n*log(n)), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   poly : an input polygon to be triangulated
+        //          vertices have to be in counter-clockwise order
+        //   triangles : a list of triangles (result)
+        //returns 1 on success, 0 on failure
+        int Triangulate_MONO(TPPLPoly *poly, std::list<TPPLPoly> *triangles);
+        
+        //triangulates a list of polygons by firstly partitioning them into monotone polygons
+        //time complexity: O(n*log(n)), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   inpolys : a list of polygons to be triangulated (can contain holes)
+        //             vertices of all non-hole polys have to be in counter-clockwise order
+        //             vertices of all hole polys have to be in clockwise order
+        //   triangles : a list of triangles (result)
+        //returns 1 on success, 0 on failure
+        int Triangulate_MONO(std::list<TPPLPoly> *inpolys, std::list<TPPLPoly> *triangles);
+        
+        //creates a monotone partition of a list of polygons that can contain holes
+        //time complexity: O(n*log(n)), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   inpolys : a list of polygons to be triangulated (can contain holes)
+        //             vertices of all non-hole polys have to be in counter-clockwise order
+        //             vertices of all hole polys have to be in clockwise order
+        //   monotonePolys : a list of monotone polygons (result)
+        //returns 1 on success, 0 on failure
+        int MonotonePartition(std::list<TPPLPoly> *inpolys, std::list<TPPLPoly> *monotonePolys);
+        
+        //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm
+        //the algorithm gives at most four times the number of parts as the optimal algorithm
+        //however, in practice it works much better than that and often gives optimal partition
+        //uses triangulation obtained by ear clipping as intermediate result
+        //time complexity O(n^2), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   poly : an input polygon to be partitioned
+        //          vertices have to be in counter-clockwise order
+        //   parts : resulting list of convex polygons
+        //returns 1 on success, 0 on failure
+        int ConvexPartition_HM(TPPLPoly *poly, std::list<TPPLPoly> *parts);
+        
+        //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm
+        //the algorithm gives at most four times the number of parts as the optimal algorithm
+        //however, in practice it works much better than that and often gives optimal partition
+        //uses triangulation obtained by ear clipping as intermediate result
+        //time complexity O(n^2), n is the number of vertices
+        //space complexity: O(n)
+        //params:
+        //   inpolys : an input list of polygons to be partitioned
+        //             vertices of all non-hole polys have to be in counter-clockwise order
+        //             vertices of all hole polys have to be in clockwise order
+        //   parts : resulting list of convex polygons
+        //returns 1 on success, 0 on failure
+        int ConvexPartition_HM(std::list<TPPLPoly> *inpolys, std::list<TPPLPoly> *parts);
+        
+        //optimal convex partitioning (in terms of number of resulting convex polygons)
+        //using the Keil-Snoeyink algorithm
+        //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998
+        //time complexity O(n^3), n is the number of vertices
+        //space complexity: O(n^3)
+        //   poly : an input polygon to be partitioned
+        //          vertices have to be in counter-clockwise order
+        //   parts : resulting list of convex polygons
+        //returns 1 on success, 0 on failure
+        int ConvexPartition_OPT(TPPLPoly *poly, std::list<TPPLPoly> *parts);
+    };
+    
+    
+#endif
diff --git a/test/PCBView/polypartition/test/image.cpp b/test/PCBView/polypartition/test/image.cpp
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/image.cpp
@@ -0,0 +1,351 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+
+#include "image.h"
+
+Image::Image(void)
+{
+	width = 0;
+	height = 0;
+	data = NULL;
+}
+
+Image::Image(long width, long height)
+{
+	this->width = width;
+	this->height = height;
+	data = (unsigned char *)malloc(3*width*height);
+	memset(data,0,3*width*height);
+}
+
+Image::Image(const Image& src) {
+	width = src.width;
+	height = src.height;
+	data = (unsigned char *)malloc(3*width*height);
+	memcpy(data,src.data,3*width*height);
+}
+
+Image& Image::operator=(const Image &src) {
+	width = src.width;
+	height = src.height;
+	if(data) free(data);
+	data = (unsigned char *)malloc(3*width*height);
+	memcpy(data,src.data,3*width*height);
+	return *this;
+}
+
+Image::~Image(void)
+{
+	if(data) free(data);
+}
+
+void Image::Init(long width, long height)
+{
+	if(data) free(data);
+	this->width = width;
+	this->height = height;
+	data = (unsigned char *)malloc(3*width*height);
+	memset(data,0,3*width*height);
+}
+
+unsigned char Image::GetMeanGray() {
+	long sum = 0;
+	for(long i = 0; i <height; i++) {
+		for(long j = 0; j<width;j++) {
+			sum += GetPixelGray(j,i);
+		}
+	}
+	return (unsigned char)(sum/(width*height));
+}
+
+void Image::Binarize(unsigned char threshold) {
+	unsigned char c;
+	for(long i = 0; i <height; i++) {
+		for(long j = 0; j<width;j++) {
+			c = GetPixelGray(j,i);
+			if(c > threshold) {
+				SetPixelGray(j,i,255);
+			} else {
+				SetPixelGray(j,i,0);
+			}
+		}
+	}
+}
+
+void Image::FlipHorizontal() {
+	unsigned char *newdata;
+	newdata = (unsigned char *)malloc(height*width*3);
+	for(long i = 0; i <height; i++) {
+		for(long j = 0; j<width;j++) {
+			long index1 = 3*((i*width)+j);
+			long index2 = 3*((i*width)+width-j-1);
+			newdata[index1] = data[index2];
+			index1++; index2++;
+			newdata[index1] = data[index2];
+			index1++; index2++;
+			newdata[index1] = data[index2];
+			index1++; index2++;
+		}
+	}
+	free(data);
+	data = newdata;
+}
+
+void Image::FlipVertical() {
+	unsigned char *newdata;
+	newdata = (unsigned char *)malloc(height*width*3);
+	for(long i = 0; i <height; i++) {
+		for(long j = 0; j<width;j++) {
+			long index1 = 3*((i*width)+j);
+			long index2 = 3*(((height-i-1)*width)+j);
+			newdata[index1] = data[index2];
+			index1++; index2++;
+			newdata[index1] = data[index2];
+			index1++; index2++;
+			newdata[index1] = data[index2];
+			index1++; index2++;
+		}
+	}
+	free(data);
+	data = newdata;
+}
+
+Image::Pixel Image::GetPixelBilinear(float x, float y) {
+	Image::Pixel c={0,0,0},c1,c2,c3,c4;
+	if(x<0) return c;
+	if(y<0) return c;
+	if(x>(width-1)) return c;
+	if(y>(height-1)) return c;
+	long x1,y1;
+	float dx,dy;
+	x1=(long)floor(x);
+	y1=(long)floor(y);
+	dx=x-x1;
+	dy=y-y1;
+	c1=GetPixelColor(x1,y1);
+	c2=GetPixelColor(x1+1,y1);
+	c3=GetPixelColor(x1,y1+1);
+	c4=GetPixelColor(x1+1,y1+1);
+	c.R=(unsigned char)round(interpolate(c1.R,c2.R,c3.R,c4.R,dx,dy));
+	c.G=(unsigned char)round(interpolate(c1.G,c2.G,c3.G,c4.G,dx,dy));
+	c.B=(unsigned char)round(interpolate(c1.B,c2.B,c3.B,c4.B,dx,dy));
+	return(c);
+}
+
+float Image::interpolate(float x1,float x2,float x3, float x4, float dx, float dy) {
+	float x5,x6;
+	x5=x2*dx+x1*(1-dx);
+	x6=x4*dx+x3*(1-dx);
+	return(x6*dy+x5*(1-dy));
+}
+
+long Image::round(float x) {
+	if((x-floor(x))<0.5) return (long)floor(x);
+	else return (long)ceil(x);
+}
+
+void Image::GetHistogramGray(long *histogram) {
+	for(long i =0;i<256;i++) histogram[i] = 0;
+	for(long i = 0; i <height; i++) {
+		for(long j = 0; j<width;j++) {
+			histogram[GetPixelGray(j,i)]++;
+		}
+	}
+}
+
+void Image::Invert() {
+	long i,n = 3*width*height;
+	for(i=0;i<n;i++) {
+		data[i]=255-data[i];
+	}
+}
+
+Image Image::Crop(int posx, int posy, int width, int height) {
+	Image resultimg;
+	Image::Pixel rgb;
+	resultimg.Init(width,height);
+	long i,j;
+	for(i=0;i<height;i++) {
+		for(j=0;j<width;j++) {
+			rgb = this->GetPixelColor(j+posx,i+posy);
+			resultimg.SetPixelColor(j,i,rgb);
+		}
+	}
+	return resultimg;
+}
+
+Image Image::Resize(int factor) {
+	long width,height;
+	int factor2;
+	long sumR, sumG, sumB;
+
+	width = this->width / factor;
+	height = this->height / factor;
+	factor2 = factor*factor;
+
+	Image resultimg(width,height);
+	Image::Pixel rgb;
+	long i,j,i2,j2,minx,miny,maxx,maxy;
+
+	for(i=0;i<height;i++) {
+		for(j=0;j<width;j++) {
+			minx = j*factor;
+			miny = i*factor;
+			maxx = minx+factor;
+			maxy = miny+factor;
+			
+			sumR = 0; sumG = 0; sumB = 0;
+
+			for(i2=miny;i2<maxy;i2++) {
+				for(j2=minx;j2<maxx;j2++) {
+					rgb = GetPixelColor(j2,i2);
+					sumR += rgb.R;
+					sumG += rgb.G;
+					sumB += rgb.B;
+				}
+			}
+			rgb.R = (unsigned char)round(sumR/((float)factor2));
+			rgb.G = (unsigned char)round(sumG/((float)factor2));
+			rgb.B = (unsigned char)round(sumB/((float)factor2));
+			resultimg.SetPixelColor(j,i,rgb);
+		}
+	}
+	return resultimg;
+}
+
+Image Image::Filter(float *filter, long filterwidth, long filterheight) {
+	Image ret(width,height);
+	long i1,j1,i2,j2;
+	long fox,foy,filtersize;
+	long x,y;
+	float sumr,sumg,sumb;
+	long offset1,offset2,offset3;
+	unsigned char *data1,*data2;
+	fox = filterwidth/2;
+	foy = filterheight/2;
+	filtersize = filterwidth*filterheight;
+	data1 = ret.GetData();
+	data2 = data;
+	for(i1=0;i1<height;i1++) {
+		for(j1=0;j1<width;j1++) {
+			offset1 = (i1*width+j1)*3;
+			sumr = 0;
+			sumg = 0;
+			sumb = 0;
+			for(i2=-foy;i2<=foy;i2++) {
+				for(j2=-fox;j2<=fox;j2++) {
+					x = j1+j2;
+					y = i1+i2;
+					if(x<0) x = 0;
+					if(y<0) y = 0;
+					if(x>=width) x = width-1;
+					if(y>=height) y = height-1;
+					offset2 = (y*width+x)*3;
+					offset3 = (i2+foy)*filterwidth+j2+fox;
+					sumr += data2[offset2]*filter[offset3];
+					sumg += data2[offset2+1]*filter[offset3];
+					sumb += data2[offset2+2]*filter[offset3];
+				}
+			}
+			data1[offset1] = (unsigned char)round(sumr);
+			data1[offset1+1] = (unsigned char)round(sumg);
+			data1[offset1+2] = (unsigned char)round(sumb);
+		}
+	}
+	return ret;
+}
+
+Image Image::GaussBlur(float sigma, long masksize) {
+	Image ret;
+	float *filter;
+	long fsize;
+	long i,j;
+	long fo;
+	float pi = 3.1415926538f;
+
+	if(!masksize) masksize = round(sigma)*2*2+1;
+
+	fsize = masksize*masksize;
+	fo = masksize/2;
+	filter = (float *)malloc(fsize*sizeof(float));
+
+	for(i=-fo;i<=fo;i++) {
+		for(j=-fo;j<=fo;j++) {
+			filter[(i+fo)*masksize+j+fo] = (1/(2*pi*sigma))*exp(-(i*i+j*j)/(2*sigma*sigma));
+		}
+	}
+
+	float sum = 0;
+	for(i=0;i<fsize;i++) sum += filter[i];
+	for(i=0;i<fsize;i++) filter[i]=filter[i]/sum;
+
+	ret = this->Filter(filter,masksize,masksize);
+
+	delete filter;
+	return ret;
+}
+
+void Image::Clear(Pixel color) {
+	long x,y;
+	for(y=0;y<height;y++) {
+		for(x=0;x<width;x++) {
+			SetPixelColor(x,y,color);
+		}
+	}
+}
+
+void Image::DrawLine(int x1, int y1, int x2, int y2, Pixel color) {
+	long i;
+	long y;
+	long dx,dy;
+	dx=labs(x2-x1);
+	dy=labs(y2-y1);
+	if(dx>dy) {
+		if(x2>x1) {
+			for(i=x1;i<=x2;i++) {
+				y=(long)(((y2-(float)(y1))/(x2-x1))*(i-x1)+y1);
+				SetPixelColor(i,y,color);
+			}
+		} else {
+			for(i=x2;i<=x1;i++) {
+				y=(long)(((y1-(float)(y2))/(x1-x2))*(i-x2)+y2);
+				SetPixelColor(i,y,color);
+			}
+		}
+	} else {
+		if(y2>y1) {
+			for(i=y1;i<=y2;i++) {
+				y=(long)(((x2-(float)(x1))/(y2-y1))*(i-y1)+x1);
+				SetPixelColor(y,i,color);
+			}
+		} else {
+			for(i=y2;i<=y1;i++) {
+				y=(long)(((x1-(float)(x2))/(y1-y2))*(i-y2)+x2);
+				SetPixelColor(y,i,color);
+			}
+		}
+	}
+}
diff --git a/test/PCBView/polypartition/test/image.h b/test/PCBView/polypartition/test/image.h
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/image.h
@@ -0,0 +1,211 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+
+#pragma once
+
+//a simple image class with some (very basic) image processing operations
+class Image
+{
+	friend class ImageIO;
+
+protected:
+	unsigned char *data;
+	long width;
+	long height;
+
+	long round(float x);
+	float interpolate(float x1,float x2,float x3, float x4, float dx, float dy);
+
+public:
+
+	struct Pixel {
+		unsigned char B;
+		unsigned char G;
+		unsigned char R;
+	};
+
+	//constructors/destructor
+	Image(void);
+	Image(long width, long height);
+	Image(const Image& src);
+	Image& operator=(const Image &src);
+	~Image(void);
+
+	//initializes the image of specified width and height
+	//all pixels are set to black
+	void Init(long width, long height);
+
+	//property getters
+	long GetWidth();
+	long GetHeight();
+	unsigned char *GetData();
+
+	//pixel getters and setters
+	unsigned char GetPixelGray(long x,long y);
+	unsigned char GetPixelRed(long x,long y);
+	unsigned char GetPixelGreen(long x,long y);
+	unsigned char GetPixelBlue(long x,long y);
+	Image::Pixel GetPixelColor(long x,long y);
+	void SetPixelGray(long x,long y, unsigned char c);
+	void SetPixelColor(long x,long y, Image::Pixel rgb);
+	void SetPixelRed(long x,long y, unsigned char c);
+	void SetPixelGreen(long x,long y, unsigned char c);
+	void SetPixelBlue(long x,long y, unsigned char c);
+
+	//returns the color of a pixel at real coordinates (x,y)
+	//using bilinear interpolation
+	Image::Pixel GetPixelBilinear(float x, float y);
+
+	/////////////////////////////////////////
+	//some basic image processing functions//
+	/////////////////////////////////////////
+
+	//returns the mean value of pixel intensity
+	unsigned char GetMeanGray();
+	
+	//computes the histogram of image intensity and returns it via histogram parameter
+	//parameters:
+	//		histogram : an array of 256 components, used to return the histogram
+	void GetHistogramGray(long *histogram);
+	
+	//binarizes the image
+	//all pixels with the intensity lower than threshold become black
+	//all others become white
+	void Binarize(unsigned char threshold);
+	
+	//flips the image in horizontal direction
+	void FlipHorizontal();
+
+	//flips the image in vertical direction
+	void FlipVertical();
+
+	//inverts image colors
+	void Invert();
+
+	//crops the image
+	//returns the subimage with upper left corner at (posx,posy)
+	//the returned image is of size (width, height)
+	Image Crop(int posx, int posy, int width, int height);
+
+	//resizes the image for a intager facor
+	//for example, if factor is 2, returns the image with size (width/2, height/2)
+	//each pixel in a new image is obtained as an average of corresponding pixels in the original image
+	Image Resize(int factor);
+
+	//computes the convolution of image and a filter
+	//parameters
+	//		filter : an filterwidth x filterheight array containing the filter coefficients
+	//		filterwidth : width of the filter
+	//		filterheight : height of the filter
+	//		zero : a value that will be added to each pixel component after filtering, 0 by default
+	Image Filter(float *filter, long filterwidth, long filterheight);
+
+	//filters the image using Gaussian blur
+	//parameters
+	//		sigma : the standard deviation of the Gaussian filter
+	//		masksize : the size of the corresponding filter
+	//				   if set to 0, the masksize will be calculated as sigma*2*2+1
+	Image GaussBlur(float sigma, long masksize = 0);
+
+	//paints the whole image with color 'color'
+	void Clear(Pixel color);
+
+	//draws a line from point (x1,y1) to point (x2,y2)
+	//the line is in color 'color'
+	void DrawLine(int x1, int y1, int x2, int y2, Pixel color);
+};
+
+inline unsigned char Image::GetPixelGray(long x,long y) {
+	unsigned char c;
+	long index = 3*((y*width)+x);
+	c = (unsigned char)(((long)(data[index])+(long)(data[index+1])+(long)(data[index+2]))/3);
+	return c;
+}
+
+inline unsigned char Image::GetPixelRed(long x,long y) {
+	long index = 3*((y*width)+x);
+	return data[index];
+}
+
+inline unsigned char Image::GetPixelGreen(long x,long y) {
+	long index = 3*((y*width)+x)+1;
+	return data[index];
+}
+
+inline unsigned char Image::GetPixelBlue(long x,long y) {
+	long index = 3*((y*width)+x)+2;
+	return data[index];
+}
+
+inline void Image::SetPixelRed(long x,long y, unsigned char c) {
+	long index = 3*((y*width)+x);
+	data[index]=c;
+}
+
+inline void Image::SetPixelGreen(long x,long y, unsigned char c) {
+	long index = 3*((y*width)+x)+1;
+	data[index]=c;
+}
+
+inline void Image::SetPixelBlue(long x,long y, unsigned char c) {
+	long index = 3*((y*width)+x)+2;
+	data[index]=c;
+}
+
+inline Image::Pixel Image::GetPixelColor(long x,long y) {
+	Image::Pixel rgb;
+	long index = 3*((y*width)+x);
+	rgb.B = data[index];
+	rgb.G = data[index+1];
+	rgb.R = data[index+2];
+	return rgb;
+}
+
+inline void Image::SetPixelGray(long x,long y, unsigned char c) {
+	long index = 3*((y*width)+x);
+	data[index] = c;
+	data[index+1] = c;
+	data[index+2] = c;
+}
+
+inline void Image::SetPixelColor(long x,long y, Image::Pixel rgb) {
+	if(x<0) return;
+	if(y<0) return;
+	if(x>=width) return;
+	if(y>=height) return;
+	long index = 3*((y*width)+x);
+	data[index] = rgb.B;
+	data[index+1] = rgb.G;
+	data[index+2] = rgb.R;
+}
+
+inline long Image::GetWidth() {
+	return width;
+}
+
+inline long Image::GetHeight() {
+	return height;
+}
+
+inline unsigned char *Image::GetData() {
+	return data;
+}
+
diff --git a/test/PCBView/polypartition/test/imageio.cpp b/test/PCBView/polypartition/test/imageio.cpp
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/imageio.cpp
@@ -0,0 +1,496 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+#define _CRT_SECURE_NO_WARNINGS
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <math.h>
+
+#include "image.h"
+#include "imageio.h"
+
+const char *ImageIO::GetFileExtension(const char *filename) {
+	//first remove the folder if present
+	const char *filename2,*tmp,*extension;
+	filename2 = strrchr(filename,'/');
+	tmp = strrchr(filename,'\\');
+	if(tmp > filename2) filename2 = tmp;
+	if(!filename2) filename2 = filename;
+	//now find the dot
+	extension = strrchr(filename2,'.');
+	if(extension) extension++;
+	else extension = filename2 + strlen(filename2);
+	return extension;
+}
+
+int ImageIO::GetImageType(const char *filename) {
+	const char *extension = GetFileExtension(filename);
+	if((strcmp(extension,"bmp")==0)||(strcmp(extension,"BMP")==0)) {
+		return IMGTYPE_BMP;
+	} else if((strcmp(extension,"ppm")==0)||(strcmp(extension,"PPM")==0)) {
+		return IMGTYPE_PPM;
+	} else if((strcmp(extension,"pgm")==0)||(strcmp(extension,"PGM")==0)) {
+		return IMGTYPE_PGM;
+	} else if((strcmp(extension,"raw")==0)||(strcmp(extension,"RAW")==0)) {
+		return IMGTYPE_RAW;
+	} else return IMGTYPE_UNSUPPORTED;
+}
+
+void ImageIO::LoadImage(const char *filename, Image *image) {
+	int imgType = GetImageType(filename);
+	if(imgType == IMGTYPE_UNSUPPORTED) {
+		printf("Error loading image %s, unsupported image type!\n", filename);
+		return;
+	}
+	LoadImage(filename, image, imgType);
+}
+
+void ImageIO::LoadImage(const char *filename, Image *image, int imageType) {
+	switch(imageType) {
+		case IMGTYPE_BMP:
+			LoadImageBMP(filename, image);
+			break;
+		case IMGTYPE_PPM:
+			LoadImagePPM(filename, image);
+			break;
+		case IMGTYPE_PGM:
+			LoadImagePGM(filename, image);
+			break;
+		case IMGTYPE_RAW:
+			LoadImageRAW(filename, image);
+			break;
+	}
+}
+
+void ImageIO::LoadImageBMP(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"rb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	char header[2];
+	fread(header,1,2,fp);
+	if(!((header[0]=='B')&&(header[1]=='M'))) {
+		fclose(fp);
+		printf("Error loading image %s, wrong file format!\n",filename);
+		return;
+	}
+
+	long bmOffset;
+	fseek(fp,10,SEEK_SET);
+	fread(&bmOffset,4,1,fp);
+
+	fseek(fp,18,SEEK_SET);
+	fread(&(image->width),4,1,fp);
+	fread(&(image->height),4,1,fp);
+
+	short bpp;
+	fseek(fp,28,SEEK_SET);
+	fread(&bpp,2,1,fp);
+	if(!((bpp==8)||(bpp==24))) {
+		fclose(fp);
+		printf("Error loading image %s, can only load BMP files with 8 or 24 bpp!\n",filename);
+		return;
+	}
+
+	long compression;
+	fread(&compression,4,1,fp);
+	if(compression) {
+		fclose(fp);
+		printf("Error loading image %s, can only load uncompressed BMP files!\n",filename);
+		return;
+	}
+
+	if(image->data) free(image->data);
+	image->data = (unsigned char *)malloc(image->height * image->width * 3);
+
+	if(bpp == 8) {
+
+		//bytes per row
+		long bpr,tmp;
+		tmp = image->width % 4;
+		if(tmp == 0) {
+			bpr = image->width;
+		} else {
+			bpr = image->width + 4 - tmp;
+			tmp = 4 - tmp;
+		}
+
+
+		long bmSize = bpr * image->height;
+		unsigned char *buffer = (unsigned char *)malloc(bmSize);
+		fseek(fp,bmOffset,SEEK_SET);
+		fread(buffer,1,bmSize,fp);
+
+		long pos = 0;
+		for(long i=0;i<image->height;i++) {
+			for(long j=0;j<image->width;j++) {
+				
+				image->SetPixelGray(j,image->height - i - 1,buffer[pos]);
+				pos++;
+			}
+			pos += tmp;
+		}
+
+		free(buffer);
+
+	} else if (bpp == 24) {
+
+		//bytes per row
+		long bpr,tmp;
+		tmp = (image->width*3) % 4;
+		if(tmp == 0) {
+			bpr = image->width * 3;
+		} else {
+			bpr = image->width * 3 + 4 - tmp;
+			tmp = 4 - tmp;
+		}
+
+		long bmSize = bpr * image->height;
+		unsigned char *buffer = (unsigned char *)malloc(bmSize);
+		fseek(fp,bmOffset,SEEK_SET);
+		fread(buffer,1,bmSize,fp);
+
+		long pos = 0;
+		Image::Pixel rgb;
+		for(long i=0;i<image->height;i++) {
+			for(long j=0;j<image->width;j++) {
+				rgb.B = buffer[pos++];
+				rgb.G = buffer[pos++];
+				rgb.R = buffer[pos++];
+				image->SetPixelColor(j,image->height - i - 1,rgb);
+			}
+			pos += tmp;
+		}
+
+		free(buffer);	
+	}
+
+	fclose(fp);
+}
+
+void ImageIO::SaveImage(const char *filename, Image *image) {
+	int imgType = GetImageType(filename);
+	if(imgType == IMGTYPE_UNSUPPORTED) {
+		printf("Error saving image to %s, unknown image format!\n", filename);
+		return;
+	}
+	SaveImage(filename, image, imgType);
+}
+
+void ImageIO::SaveImage(const char *filename, Image *image, int imageType) {
+	switch(imageType) {
+		case IMGTYPE_BMP:
+			SaveImageBMP(filename, image);
+			break;
+		case IMGTYPE_PPM:
+			SaveImagePPM(filename, image);
+			break;
+		case IMGTYPE_PGM:
+			SaveImagePPM(filename, image);
+			break;
+		case IMGTYPE_RAW:
+			SaveImageRAW(filename, image);
+			break;
+	}
+}
+
+void ImageIO::SaveImageBMP(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"wb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	char header[2];
+	long tmpl;
+	short tmps;
+
+	//header
+	header[0] = 'B';
+	header[1] = 'M';
+	fwrite(header,2,1,fp);
+
+	//filesize;
+	long rowsize;
+	long tmp = (image->width*3)%4;
+	if(tmp==0) rowsize = image->width*3;
+	else rowsize = image->width*3 + 4 - tmp;
+	unsigned char *row = (unsigned char *)malloc(rowsize);
+	tmpl = 54 + rowsize*image->height;
+	fwrite(&tmpl,4,1,fp);
+
+	tmps = 0;
+	fwrite(&tmps,2,1,fp);
+	fwrite(&tmps,2,1,fp);
+
+	//offset to the beginning of bm data
+	tmpl = 54;
+	fwrite(&tmpl,4,1,fp);
+
+	//info header size
+	tmpl = 40;
+	fwrite(&tmpl,4,1,fp);
+
+	//size
+	tmpl = image->width;
+	fwrite(&tmpl,4,1,fp);
+	tmpl = image->height;
+	fwrite(&tmpl,4,1,fp);
+
+	tmps = 1;
+	fwrite(&tmps,2,1,fp);
+	tmps = 24; //bpp
+	fwrite(&tmps,2,1,fp);
+	tmpl = 0;
+	fwrite(&tmpl,4,1,fp);
+	fwrite(&tmpl,4,1,fp);
+	fwrite(&tmpl,4,1,fp);
+	fwrite(&tmpl,4,1,fp);
+	fwrite(&tmpl,4,1,fp);
+	fwrite(&tmpl,4,1,fp);
+
+	//actual bitmap data
+	for(long i = 0; i<image->height;i++) {
+		memset(row,0,rowsize);
+		memcpy(row,image->data + (3*image->width)*(image->height-i-1),3*image->width);
+		fwrite(row,rowsize,1,fp);
+	}
+
+	free(row);
+
+	fclose(fp);
+}
+
+void ImageIO::LoadImagePPM(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"rb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	long filesize;
+	fseek(fp,0,SEEK_END);
+	filesize = ftell(fp);
+	fseek(fp,0,SEEK_SET);
+
+	unsigned char *buffer = (unsigned char *)malloc(filesize);
+	fread(buffer,1,filesize,fp);
+
+	char id[1024];
+	long sizex, sizey, levels;
+	sscanf((char *)buffer,"%s\n%ld %ld\n%ld\n",id,&sizex,&sizey,&levels);
+	
+	if((strncmp(id,"P6",2)!=0)||(levels!=255)) {
+		free(buffer);
+		fclose(fp);
+		printf("Error loading image %s, wrong file format!\n",filename);
+		return;
+	}
+
+	image->width = sizex;
+	image->height = sizey;
+
+	if(image->data) free(image->data);
+	image->data = (unsigned char *)malloc(image->height * image->width * 3);
+
+	long pos = filesize - sizex*sizey*3;
+	for(long i = 0; i < sizey;i++) {
+		for(long j = 0; j < sizex;j++) {
+			Image::Pixel rgb;
+			rgb.R = buffer[pos++];
+			rgb.G = buffer[pos++];
+			rgb.B = buffer[pos++];
+			image->SetPixelColor(j,i,rgb);
+		}
+	}
+
+	free(buffer);
+
+	fclose(fp);
+}
+
+void ImageIO::LoadImagePGM(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"rb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	long filesize;
+	fseek(fp,0,SEEK_END);
+	filesize = ftell(fp);
+	fseek(fp,0,SEEK_SET);
+
+	unsigned char *buffer = (unsigned char *)malloc(filesize);
+	fread(buffer,1,filesize,fp);
+
+	char id[1024];
+	long sizex, sizey, levels;
+	sscanf((char *)buffer,"%s\n%ld %ld\n%ld\n",id,&sizex,&sizey,&levels);
+	
+	if((strncmp(id,"P5",2)!=0)||(levels!=255)) {
+		free(buffer);
+		fclose(fp);
+		printf("Error loading image %s, wrong file format!\n",filename);
+		return;
+	}
+
+	image->width = sizex;
+	image->height = sizey;
+
+	if(image->data) free(image->data);
+	image->data = (unsigned char *)malloc(image->height * image->width * 3);
+
+	long pos = filesize - sizex*sizey;
+	for(long i = 0; i < sizey;i++) {
+		for(long j = 0; j < sizex;j++) {
+			image->SetPixelGray(j,i,buffer[pos]);
+			pos++;
+		}
+	}
+
+	free(buffer);
+
+	fclose(fp);
+}
+
+void ImageIO::SaveImagePPM(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"wb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	fprintf(fp,"P6\n%ld %ld\n255\n",image->width,image->height);
+	
+	long sizex = image->width;
+	long sizey = image->height;
+	unsigned char *buffer = (unsigned char *)malloc(image->width * image->height * 3);
+	long pos = 0;
+	for(long i = 0; i < sizey;i++) {
+		for(long j = 0; j < sizex;j++) {
+			Image::Pixel rgb = image->GetPixelColor(j,i);
+			buffer[pos++] = rgb.R;
+			buffer[pos++] = rgb.G;
+			buffer[pos++] = rgb.B;
+		}
+	}
+
+	fwrite(buffer,1,image->width * image->height * 3,fp);
+
+	free(buffer);
+	fclose(fp);
+}
+
+void ImageIO::SaveImagePGM(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"wb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	fprintf(fp,"P5\n%ld %ld\n255\n",image->width,image->height);
+	
+	long sizex = image->width;
+	long sizey = image->height;
+	unsigned char *buffer = (unsigned char *)malloc(image->width * image->height);
+	long pos = 0;
+	for(long i = 0; i < sizey;i++) {
+		for(long j = 0; j < sizex;j++) {
+			buffer[pos++] = image->GetPixelGray(j,i);
+		}
+	}
+
+	fwrite(buffer,1,image->width * image->height,fp);
+
+	free(buffer);
+	fclose(fp);
+}
+
+void ImageIO::LoadImageRAW(const char *filename, Image *image, long width, long height) {
+	FILE *fp = fopen(filename,"rb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	if((width==0)||(height==0)) {
+		long filesize;
+		fseek(fp,0,SEEK_END);
+		filesize = ftell(fp);	
+		fseek(fp,0,SEEK_SET);
+		width = (long)sqrt((double)filesize);
+		height = width;
+		if((height*width)!=filesize) {
+			fclose(fp);
+			printf("Error loading image %s, wrong file format!\n",filename);
+			return;	
+		}
+	}
+
+	image->width = width;
+	image->height = height;
+	if(image->data) free(image->data);
+	image->data = (unsigned char *)malloc(image->height * image->width * 3);
+
+	unsigned char *buffer = (unsigned char *)malloc(image->width * image->height);
+	fread(buffer,1,image->width * image->height,fp);
+
+	long pos = 0;
+	for(long i = 0; i < height;i++) {
+		for(long j = 0; j < width;j++) {
+			unsigned char c = buffer[pos++];
+			image->SetPixelGray(j,i,c);
+		}
+	}
+
+	free(buffer);
+	fclose(fp);
+}
+
+void ImageIO::SaveImageRAW(const char *filename, Image *image) {
+	FILE *fp = fopen(filename,"wb");
+	if(!fp) {
+		printf("Error opening %s!\n", filename);
+		return;
+	}
+
+	long sizex = image->width;
+	long sizey = image->height;
+	unsigned char *buffer = (unsigned char *)malloc(image->width * image->height);
+	
+	long pos = 0;
+	for(long i = 0; i < sizey;i++) {
+		for(long j = 0; j < sizex;j++) {
+			unsigned char c = image->GetPixelGray(j,i);
+			buffer[pos++] = c;
+		}
+	}
+
+	fwrite(buffer,1,image->width * image->height,fp);
+
+	free(buffer);
+	fclose(fp);
+}
diff --git a/test/PCBView/polypartition/test/imageio.h b/test/PCBView/polypartition/test/imageio.h
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/imageio.h
@@ -0,0 +1,81 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+
+#pragma once
+
+#define IMGTYPE_RAW 0
+#define IMGTYPE_BMP 1
+#define IMGTYPE_PPM 2
+#define IMGTYPE_PGM 3
+#define IMGTYPE_UNSUPPORTED 999
+
+//handles basic image file input/output
+//only supports uncompressed image formats
+class ImageIO
+{
+protected:
+	//gets the file extension of file filename
+	const char *GetFileExtension(const char *filename);
+
+	//determines the imege format from the filename
+	int GetImageType(const char *filename);
+
+public:
+
+	//loads the image from filename into image
+	//automatically determines the image format
+	void LoadImage(const char *filename, Image *image);
+
+	//loads the image of the specified format (imageType) from filename into image
+	void LoadImage(const char *filename, Image *image, int imageType);
+	
+	//saves the image into file named 'filename'
+	//automatically determines the image format
+	void SaveImage(const char *filename, Image *image);
+
+	//saves the image into file named 'filename', using the format given as imageType
+	void SaveImage(const char *filename, Image *image, int imageType);
+
+	//loads the uncompressed BMP image from filename into image
+	void LoadImageBMP(const char *filename, Image *image);
+	//saves the image into file named 'filename' in uncompressed BMP format
+	void SaveImageBMP(const char *filename, Image *image);
+
+	//loads the PPM image from filename into image
+	void LoadImagePPM(const char *filename, Image *image);
+	//saves the image into file named 'filename' in PPM format
+	void SaveImagePPM(const char *filename, Image *image);
+
+	//loads the PGM image from filename into image
+	void LoadImagePGM(const char *filename, Image *image);
+	//saves the image into file named 'filename' in PGM format
+	void SaveImagePGM(const char *filename, Image *image);
+
+	//loads the image from the file named 'filename'
+	//the file is assumed to be structured so that it only contains an array of raw (gray) pixel values
+	//as the file does not contain the image width and height, those are passed as parameters to the function
+	//if width and height are 0, the image is assumed to be square and the width and height are computed based on the file size
+	void LoadImageRAW(const char *filename, Image *image, long width = 0, long height = 0);
+
+	//saves the image to a file named 'filename'
+	//only the array of raw (gray) pixel values is stored, without additional information such as image size
+	void SaveImageRAW(const char *filename, Image *image);
+};
diff --git a/test/PCBView/polypartition/test/test.cpp b/test/PCBView/polypartition/test/test.cpp
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test.cpp
@@ -0,0 +1,360 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//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.
+
+#define _CRT_SECURE_NO_WARNINGS
+
+#include <stdio.h>
+#include <list>
+#include <limits>
+
+using namespace std;
+
+#include "polypartition.h"
+
+#include "image.h"
+#include "imageio.h"
+
+void ReadPoly(FILE *fp, TPPLPoly *poly) {
+	int i,numpoints,hole;
+	float x,y;
+
+	fscanf(fp,"%d\n",&numpoints);
+	poly->Init(numpoints);
+
+	fscanf(fp,"%d\n",&hole);
+	if(hole) poly->SetHole(true);
+
+	for(i=0;i<numpoints;i++) {
+		fscanf(fp,"%g %g\n",&x, &y);
+		(*poly)[i].x = x;
+		(*poly)[i].y = y;
+	}
+}
+
+void ReadPoly(const char *filename, TPPLPoly *poly) {
+	FILE *fp = fopen(filename,"r");
+	if(!fp) {
+		printf("Error reading file %s\n", filename);
+		return;
+	}
+	ReadPoly(fp,poly);
+	fclose(fp);	
+}
+
+void ReadPolyList(FILE *fp, list<TPPLPoly> *polys) {
+	int i,numpolys;
+	TPPLPoly poly;
+
+	polys->clear();
+	fscanf(fp,"%d\n",&numpolys);
+	for(i=0;i<numpolys;i++) {
+		ReadPoly(fp,&poly);
+		polys->push_back(poly);
+	}
+}
+
+void ReadPolyList(const char *filename, list<TPPLPoly> *polys) {
+	FILE *fp = fopen(filename,"r");
+	if(!fp) {
+		printf("Error reading file %s\n", filename);
+		return;
+	}
+	ReadPolyList(fp,polys);
+	fclose(fp);
+}
+
+
+void WritePoly(FILE *fp, TPPLPoly *poly) {
+	int i,numpoints;
+	numpoints = poly->GetNumPoints();
+
+	fprintf(fp,"%d\n",numpoints);
+	
+	if(poly->IsHole()) {
+		fprintf(fp,"1\n");
+	} else {
+		fprintf(fp,"0\n");
+	}
+
+	for(i=0;i<numpoints;i++) {
+		fprintf(fp,"%g %g\n",(*poly)[i].x, (*poly)[i].y);
+	}
+}
+
+void WritePoly(const char *filename, TPPLPoly *poly) {
+	FILE *fp = fopen(filename,"w");
+	if(!fp) {
+		printf("Error writing file %s\n", filename);
+		return;
+	}
+	WritePoly(fp,poly);
+	fclose(fp);	
+}
+
+void WritePolyList(FILE *fp, list<TPPLPoly> *polys) {
+	list<TPPLPoly>::iterator iter;
+
+	fprintf(fp,"%ld\n",polys->size());
+
+	for(iter = polys->begin(); iter != polys->end(); iter++) {
+		WritePoly(fp,&(*iter));
+	}
+}
+
+void WritePolyList(const char *filename, list<TPPLPoly> *polys) {
+	FILE *fp = fopen(filename,"w");
+	if(!fp) {
+		printf("Error writing file %s\n", filename);
+		return;
+	}
+	WritePolyList(fp,polys);
+	fclose(fp);	
+}
+
+void DrawPoly(Image *img, TPPLPoly *poly, tppl_float xmin, tppl_float xmax, tppl_float ymin, tppl_float ymax) {
+	TPPLPoint p1,p2,p1img,p2img,polymin,imgmin;
+	long i;
+	Image::Pixel color={0,0,0};
+
+	polymin.x = xmin;
+	polymin.y = ymin;
+	imgmin.x = 5;
+	imgmin.y = 5;
+
+	tppl_float polySizeX = xmax - xmin;
+	tppl_float polySizeY = ymax - ymin;
+	tppl_float imgSizeX = (tppl_float)img->GetWidth()-10;
+	tppl_float imgSizeY = (tppl_float)img->GetHeight()-10;
+	
+	tppl_float scalex = 0;	
+	tppl_float scaley = 0;
+	tppl_float scale;
+	if(polySizeX>0) scalex = imgSizeX/polySizeX;
+	if(polySizeY>0) scaley = imgSizeY/polySizeY;
+
+	if(scalex>0 && scalex<scaley) scale = scalex;
+	else if(scaley>0) scale = scaley;
+	else scale = 1;
+
+	for(i=0;i<poly->GetNumPoints();i++) {
+		p1 = poly->GetPoint(i);
+		p2 = poly->GetPoint((i+1)%poly->GetNumPoints());
+		p1img = (p1 - polymin)*scale + imgmin;
+		p2img = (p2 - polymin)*scale + imgmin;
+		img->DrawLine((int)p1img.x,(int)p1img.y,(int)p2img.x,(int)p2img.y,color);
+	}
+}
+
+void DrawPoly(const char *filename, TPPLPoly *poly) {
+	Image img(500,500);
+	Image::Pixel white={255,255,255};
+	img.Clear(white);
+	ImageIO io;
+
+	tppl_float xmin = std::numeric_limits<tppl_float>::max();
+	tppl_float xmax = std::numeric_limits<tppl_float>::min();
+	tppl_float ymin = std::numeric_limits<tppl_float>::max();
+	tppl_float ymax = std::numeric_limits<tppl_float>::min();
+	for(int i=0;i<poly->GetNumPoints();i++) {
+		if(poly->GetPoint(i).x < xmin) xmin = poly->GetPoint(i).x;
+		if(poly->GetPoint(i).x > xmax) xmax = poly->GetPoint(i).x;
+		if(poly->GetPoint(i).y < ymin) ymin = poly->GetPoint(i).y;
+		if(poly->GetPoint(i).y > ymax) ymax = poly->GetPoint(i).y;
+	}
+
+	DrawPoly(&img, poly, xmin, xmax, ymin, ymax);
+
+	io.SaveImage(filename,&img);
+}
+
+void DrawPolyList(const char *filename, list<TPPLPoly> *polys) {
+	Image img(500,500);
+	Image::Pixel white={255,255,255};
+	img.Clear(white);
+
+	ImageIO io;
+	list<TPPLPoly>::iterator iter;
+
+	tppl_float xmin = std::numeric_limits<tppl_float>::max();
+	tppl_float xmax = std::numeric_limits<tppl_float>::min();
+	tppl_float ymin = std::numeric_limits<tppl_float>::max();
+	tppl_float ymax = std::numeric_limits<tppl_float>::min();
+	for(iter=polys->begin(); iter!=polys->end(); iter++) {
+		for(int i=0;i<iter->GetNumPoints();i++) {
+			if(iter->GetPoint(i).x < xmin) xmin = iter->GetPoint(i).x;
+			if(iter->GetPoint(i).x > xmax) xmax = iter->GetPoint(i).x;
+			if(iter->GetPoint(i).y < ymin) ymin = iter->GetPoint(i).y;
+			if(iter->GetPoint(i).y > ymax) ymax = iter->GetPoint(i).y;
+		}
+		//if(iter->GetOrientation() == TPPL_CCW) printf("CCW\n");
+		//else if (iter->GetOrientation() == TPPL_CW) printf("CW\n");
+		//else printf("gfdgdg\n");
+	}
+	//printf("\n");
+
+	for(iter=polys->begin(); iter!=polys->end(); iter++) {
+		DrawPoly(&img, &(*iter), xmin, xmax, ymin, ymax);
+	}
+
+	io.SaveImage(filename,&img);
+}
+
+bool ComparePoly(TPPLPoly *p1, TPPLPoly *p2) {
+	long i,n = p1->GetNumPoints();
+	if(n!=p2->GetNumPoints()) return false;
+	for(i=0;i<n;i++) {
+		if((*p1)[i]!=(*p2)[i]) return false;
+	}
+	return true;
+}
+
+bool ComparePoly(list<TPPLPoly> *polys1, list<TPPLPoly> *polys2) {
+	list<TPPLPoly>::iterator iter1, iter2;
+	long i,n = (long)polys1->size();
+	if(n!=(signed)polys2->size()) return false;
+	iter1 = polys1->begin();
+	iter2 = polys2->begin();
+	for(i=0;i<n;i++) {
+		if(!ComparePoly(&(*iter1),&(*iter2))) return false;
+		iter1++;
+		iter2++;
+	}
+	return true;
+}
+
+
+void GenerateTestData() {
+	TPPLPartition pp;
+	
+	list<TPPLPoly> testpolys,result,expectedResult;
+
+	ReadPolyList("test_input.txt",&testpolys);
+
+	DrawPolyList("test_input.bmp",&testpolys);
+
+	pp.Triangulate_EC(&testpolys,&result);
+	//pp.Triangulate_EC(&(*testpolys.begin()),&result);
+	DrawPolyList("test_triangulate_EC.bmp",&result);
+	WritePolyList("test_triangulate_EC.txt",&result);
+
+	result.clear(); expectedResult.clear();
+
+	pp.Triangulate_OPT(&(*testpolys.begin()),&result);
+	DrawPolyList("test_triangulate_OPT.bmp",&result);
+	WritePolyList("test_triangulate_OPT.txt",&result);
+
+	result.clear(); expectedResult.clear();
+
+	pp.Triangulate_MONO(&testpolys,&result);
+	//pp.Triangulate_MONO(&(*testpolys.begin()),&result);
+	DrawPolyList("test_triangulate_MONO.bmp",&result);
+	WritePolyList("test_triangulate_MONO.txt",&result);
+
+	result.clear(); expectedResult.clear();
+
+	pp.ConvexPartition_HM(&testpolys,&result);
+	//pp.ConvexPartition_HM(&(*testpolys.begin()),&result);
+	DrawPolyList("test_convexpartition_HM.bmp",&result);
+	WritePolyList("test_convexpartition_HM.txt",&result);
+
+	result.clear(); expectedResult.clear();
+
+	pp.ConvexPartition_OPT(&(*testpolys.begin()),&result);
+	DrawPolyList("test_convexpartition_OPT.bmp",&result);
+	WritePolyList("test_convexpartition_OPT.txt",&result);
+}
+
+int main() {
+	TPPLPartition pp;
+	list<TPPLPoly> testpolys,result;
+
+	ReadPolyList("failing_mono_clean - copy.txt",&testpolys);
+	DrawPolyList("test.bmp", &testpolys);
+	if(!pp.Triangulate_MONO(&testpolys,&result)) printf("Error\n");
+	DrawPolyList("test2.bmp", &result);
+
+}
+
+/*int main()
+{
+	TPPLPartition pp;
+	
+	list<TPPLPoly> testpolys,result,expectedResult;
+
+	ReadPolyList("test_input.txt",&testpolys);
+
+	DrawPolyList("test_input.bmp",&testpolys);
+
+	printf("Testing Triangulate_EC : ");
+	pp.Triangulate_EC(&testpolys,&result);
+	ReadPolyList("test_triangulate_EC.txt",&expectedResult);
+	if(ComparePoly(&result,&expectedResult)) {
+		printf("success\n");
+	} else {
+		printf("failed\n");
+	}
+
+	result.clear(); expectedResult.clear();
+
+	printf("Testing Triangulate_OPT : ");
+	pp.Triangulate_OPT(&(*testpolys.begin()),&result);
+	ReadPolyList("test_triangulate_OPT.txt",&expectedResult);
+	if(ComparePoly(&result,&expectedResult)) {
+		printf("success\n");
+	} else {
+		printf("failed\n");
+	}
+
+	result.clear(); expectedResult.clear();
+
+	printf("Testing Triangulate_MONO : ");
+	pp.Triangulate_MONO(&testpolys,&result);
+	ReadPolyList("test_triangulate_MONO.txt",&expectedResult);
+	if(ComparePoly(&result,&expectedResult)) {
+		printf("success\n");
+	} else {
+		printf("failed\n");
+	}
+
+	result.clear(); expectedResult.clear();
+
+	printf("Testing ConvexPartition_HM : ");
+	pp.ConvexPartition_HM(&testpolys,&result);
+	ReadPolyList("test_convexpartition_HM.txt",&expectedResult);
+	if(ComparePoly(&result,&expectedResult)) {
+		printf("success\n");
+	} else {
+		printf("failed\n");
+	}
+
+	result.clear(); expectedResult.clear();
+
+	printf("Testing ConvexPartition_OPT : ");
+	pp.ConvexPartition_OPT(&(*testpolys.begin()),&result);
+	ReadPolyList("test_convexpartition_OPT.txt",&expectedResult);
+	if(ComparePoly(&result,&expectedResult)) {
+		printf("success\n");
+	} else {
+		printf("failed\n");
+	}
+
+	return 0;
+}*/
+
diff --git a/test/PCBView/polypartition/test/test_convexpartition_HM.txt b/test/PCBView/polypartition/test/test_convexpartition_HM.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_convexpartition_HM.txt
@@ -0,0 +1,135 @@
+21
+3
+0
+179 196
+189 172
+189 242
+3
+0
+125 191
+153 197
+132 221
+5
+0
+150 266
+132 221
+179 196
+189 242
+196 310
+5
+0
+230 99
+230 80
+254 79
+254 98
+235 163
+4
+0
+212 144
+230 99
+235 163
+212 173
+6
+0
+163 138
+212 144
+212 173
+189 172
+159 161
+141 138
+5
+0
+50 98
+50 79
+74 80
+74 99
+69 163
+4
+0
+69 163
+74 99
+92 144
+92 173
+5
+0
+115 172
+92 173
+92 144
+141 138
+159 161
+4
+0
+189 172
+179 196
+150 183
+159 161
+4
+0
+253 377
+208 377
+208 355
+228 358
+4
+0
+96 355
+96 377
+51 377
+76 358
+3
+0
+228 358
+254 361
+253 377
+5
+0
+219 301
+228 358
+208 355
+196 310
+189 242
+3
+0
+51 377
+50 361
+76 358
+5
+0
+108 310
+96 355
+76 358
+85 301
+115 242
+4
+0
+150 266
+108 310
+115 242
+132 221
+4
+0
+132 221
+115 242
+115 172
+125 191
+3
+0
+159 161
+125 191
+115 172
+4
+0
+163 125
+163 138
+141 138
+141 125
+9
+0
+152 71
+170 75
+179 87
+178 108
+163 125
+141 125
+126 108
+125 87
+134 75
diff --git a/test/PCBView/polypartition/test/test_convexpartition_OPT.txt b/test/PCBView/polypartition/test/test_convexpartition_OPT.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_convexpartition_OPT.txt
@@ -0,0 +1,111 @@
+17
+9
+0
+170 75
+179 87
+178 108
+163 125
+141 125
+126 108
+125 87
+134 75
+152 71
+4
+0
+163 125
+163 138
+141 138
+141 125
+5
+0
+163 138
+212 144
+212 173
+189 172
+141 138
+6
+0
+189 172
+189 242
+150 266
+115 242
+115 172
+141 138
+4
+0
+212 144
+230 99
+235 163
+212 173
+4
+0
+115 172
+92 173
+92 144
+141 138
+3
+0
+150 266
+108 310
+115 242
+3
+0
+189 242
+196 310
+150 266
+5
+0
+230 99
+230 80
+254 79
+254 98
+235 163
+4
+0
+92 173
+69 163
+74 99
+92 144
+4
+0
+108 310
+96 355
+85 301
+115 242
+4
+0
+189 242
+219 301
+208 355
+196 310
+5
+0
+69 163
+50 98
+50 79
+74 80
+74 99
+4
+0
+96 355
+96 377
+76 358
+85 301
+4
+0
+219 301
+228 358
+208 377
+208 355
+4
+0
+96 377
+51 377
+50 361
+76 358
+4
+0
+228 358
+254 361
+253 377
+208 377
diff --git a/test/PCBView/polypartition/test/test_input.txt b/test/PCBView/polypartition/test/test_input.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_input.txt
@@ -0,0 +1,55 @@
+2
+44
+0
+170 75
+179 87
+178 108
+163 125
+163 138
+212 144
+230 99
+230 80
+254 79
+254 98
+235 163
+212 173
+189 172
+189 242
+219 301
+228 358
+254 361
+253 377
+208 377
+208 355
+196 310
+150 266
+108 310
+96 355
+96 377
+51 377
+50 361
+76 358
+85 301
+115 242
+115 172
+92 173
+69 163
+50 98
+50 79
+74 80
+74 99
+92 144
+141 138
+141 125
+126 108
+125 87
+134 75
+152 71
+6
+1
+159 161
+125 191
+153 197
+132 221
+179 196
+150 183
diff --git a/test/PCBView/polypartition/test/test_triangulate_EC.txt b/test/PCBView/polypartition/test/test_triangulate_EC.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_triangulate_EC.txt
@@ -0,0 +1,251 @@
+50
+3
+0
+179 196
+189 172
+189 242
+3
+0
+125 191
+153 197
+132 221
+3
+0
+132 221
+179 196
+189 242
+3
+0
+230 80
+254 79
+254 98
+3
+0
+230 99
+230 80
+254 98
+3
+0
+230 99
+254 98
+235 163
+3
+0
+212 144
+230 99
+235 163
+3
+0
+212 144
+235 163
+212 173
+3
+0
+212 144
+212 173
+189 172
+3
+0
+163 138
+212 144
+189 172
+3
+0
+50 98
+50 79
+74 80
+3
+0
+50 98
+74 80
+74 99
+3
+0
+69 163
+50 98
+74 99
+3
+0
+69 163
+74 99
+92 144
+3
+0
+92 173
+69 163
+92 144
+3
+0
+115 172
+92 173
+92 144
+3
+0
+115 172
+92 144
+141 138
+3
+0
+189 172
+179 196
+150 183
+3
+0
+189 172
+150 183
+159 161
+3
+0
+163 138
+189 172
+159 161
+3
+0
+253 377
+208 377
+208 355
+3
+0
+96 355
+96 377
+51 377
+3
+0
+228 358
+254 361
+253 377
+3
+0
+228 358
+253 377
+208 355
+3
+0
+219 301
+228 358
+208 355
+3
+0
+219 301
+208 355
+196 310
+3
+0
+189 242
+219 301
+196 310
+3
+0
+189 242
+196 310
+150 266
+3
+0
+132 221
+189 242
+150 266
+3
+0
+51 377
+50 361
+76 358
+3
+0
+96 355
+51 377
+76 358
+3
+0
+96 355
+76 358
+85 301
+3
+0
+108 310
+96 355
+85 301
+3
+0
+108 310
+85 301
+115 242
+3
+0
+150 266
+108 310
+115 242
+3
+0
+132 221
+150 266
+115 242
+3
+0
+132 221
+115 242
+115 172
+3
+0
+125 191
+132 221
+115 172
+3
+0
+159 161
+125 191
+115 172
+3
+0
+159 161
+115 172
+141 138
+3
+0
+163 138
+159 161
+141 138
+3
+0
+163 125
+163 138
+141 138
+3
+0
+163 125
+141 138
+141 125
+3
+0
+178 108
+163 125
+141 125
+3
+0
+178 108
+141 125
+126 108
+3
+0
+179 87
+178 108
+126 108
+3
+0
+179 87
+126 108
+125 87
+3
+0
+170 75
+179 87
+125 87
+3
+0
+152 71
+170 75
+125 87
+3
+0
+152 71
+125 87
+134 75
diff --git a/test/PCBView/polypartition/test/test_triangulate_MONO.txt b/test/PCBView/polypartition/test/test_triangulate_MONO.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_triangulate_MONO.txt
@@ -0,0 +1,261 @@
+52
+3
+0
+212 144
+92 144
+163 138
+3
+0
+163 138
+92 144
+141 138
+3
+0
+163 138
+141 138
+163 125
+3
+0
+163 125
+141 138
+141 125
+3
+0
+163 125
+141 125
+178 108
+3
+0
+178 108
+141 125
+126 108
+3
+0
+178 108
+126 108
+179 87
+3
+0
+179 87
+126 108
+125 87
+3
+0
+179 87
+125 87
+170 75
+3
+0
+170 75
+125 87
+134 75
+3
+0
+170 75
+134 75
+152 71
+3
+0
+50 361
+96 377
+51 377
+3
+0
+76 358
+96 377
+50 361
+3
+0
+96 377
+76 358
+96 355
+3
+0
+108 310
+96 355
+76 358
+3
+0
+108 310
+76 358
+85 301
+3
+0
+108 310
+85 301
+150 266
+3
+0
+189 242
+150 266
+85 301
+3
+0
+189 242
+85 301
+115 242
+3
+0
+132 221
+189 242
+115 242
+3
+0
+179 196
+189 242
+132 221
+3
+0
+189 242
+179 196
+189 172
+3
+0
+179 196
+150 183
+189 172
+3
+0
+189 172
+150 183
+159 161
+3
+0
+235 163
+189 172
+159 161
+3
+0
+212 144
+235 163
+159 161
+3
+0
+230 99
+235 163
+212 144
+3
+0
+235 163
+230 99
+254 98
+3
+0
+254 98
+230 99
+230 80
+3
+0
+254 98
+230 80
+254 79
+3
+0
+212 173
+189 172
+235 163
+3
+0
+212 173
+189 172
+235 163
+3
+0
+253 377
+208 377
+254 361
+3
+0
+228 358
+254 361
+208 377
+3
+0
+228 358
+208 377
+208 355
+3
+0
+196 310
+228 358
+208 355
+3
+0
+228 358
+196 310
+219 301
+3
+0
+219 301
+196 310
+150 266
+3
+0
+219 301
+150 266
+189 242
+3
+0
+125 191
+153 197
+132 221
+3
+0
+125 191
+132 221
+115 242
+3
+0
+125 191
+115 242
+115 172
+3
+0
+125 191
+115 172
+159 161
+3
+0
+115 172
+69 163
+159 161
+3
+0
+212 144
+159 161
+69 163
+3
+0
+92 144
+212 144
+69 163
+3
+0
+74 99
+92 144
+69 163
+3
+0
+74 99
+69 163
+50 98
+3
+0
+74 99
+50 98
+74 80
+3
+0
+74 80
+50 98
+50 79
+3
+0
+92 173
+69 163
+115 172
+3
+0
+115 172
+92 173
+69 163
diff --git a/test/PCBView/polypartition/test/test_triangulate_OPT.txt b/test/PCBView/polypartition/test/test_triangulate_OPT.txt
new file mode 100644
--- /dev/null
+++ b/test/PCBView/polypartition/test/test_triangulate_OPT.txt
@@ -0,0 +1,211 @@
+42
+3
+0
+170 75
+179 87
+152 71
+3
+0
+179 87
+178 108
+152 71
+3
+0
+178 108
+141 125
+152 71
+3
+0
+178 108
+163 125
+141 125
+3
+0
+141 125
+125 87
+152 71
+3
+0
+163 125
+163 138
+141 125
+3
+0
+141 125
+126 108
+125 87
+3
+0
+125 87
+134 75
+152 71
+3
+0
+163 138
+141 138
+141 125
+3
+0
+163 138
+189 172
+141 138
+3
+0
+163 138
+212 144
+189 172
+3
+0
+189 172
+115 172
+141 138
+3
+0
+212 144
+212 173
+189 172
+3
+0
+189 172
+189 242
+115 172
+3
+0
+115 172
+92 144
+141 138
+3
+0
+212 144
+235 163
+212 173
+3
+0
+189 242
+115 242
+115 172
+3
+0
+115 172
+92 173
+92 144
+3
+0
+212 144
+254 98
+235 163
+3
+0
+189 242
+150 266
+115 242
+3
+0
+92 173
+69 163
+92 144
+3
+0
+212 144
+230 99
+254 98
+3
+0
+189 242
+196 310
+150 266
+3
+0
+150 266
+108 310
+115 242
+3
+0
+69 163
+50 98
+92 144
+3
+0
+230 99
+230 80
+254 98
+3
+0
+189 242
+219 301
+196 310
+3
+0
+108 310
+85 301
+115 242
+3
+0
+50 98
+74 99
+92 144
+3
+0
+230 80
+254 79
+254 98
+3
+0
+219 301
+208 355
+196 310
+3
+0
+108 310
+96 355
+85 301
+3
+0
+50 98
+74 80
+74 99
+3
+0
+219 301
+228 358
+208 355
+3
+0
+96 355
+76 358
+85 301
+3
+0
+50 98
+50 79
+74 80
+3
+0
+228 358
+208 377
+208 355
+3
+0
+96 355
+96 377
+76 358
+3
+0
+228 358
+253 377
+208 377
+3
+0
+96 377
+51 377
+76 358
+3
+0
+228 358
+254 361
+253 377
+3
+0
+51 377
+50 361
+76 358