From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Sun, 7 Apr 2024 20:24:48 +0200
Subject: Adding upstream version 1.2.2.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 src/3rdparty/adaptagrams/libvpsc/rectangle.cpp | 744 +++++++++++++++++++++++++
 1 file changed, 744 insertions(+)
 create mode 100644 src/3rdparty/adaptagrams/libvpsc/rectangle.cpp

(limited to 'src/3rdparty/adaptagrams/libvpsc/rectangle.cpp')

diff --git a/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp b/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp
new file mode 100644
index 0000000..6d80c34
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libvpsc/rectangle.cpp
@@ -0,0 +1,744 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libvpsc - A solver for the problem of Variable Placement with 
+ *           Separation Constraints.
+ *
+ * Copyright (C) 2005-2008  Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s):  Tim Dwyer
+*/
+
+/*
+ * @brief Functions to automatically generate constraints for the
+ * rectangular node overlap removal problem.
+ *
+ */
+
+#include <cmath>
+#include <set>
+#include <cstdlib>
+#include <algorithm>
+#include <cstdio>
+
+#include "libvpsc/assertions.h"
+#include "libvpsc/solve_VPSC.h"
+#include "libvpsc/rectangle.h"
+#include "libvpsc/constraint.h"
+#include "libvpsc/variable.h"
+
+using std::set;
+using std::vector;
+
+namespace vpsc {
+
+double Rectangle::xBorder = 0;
+double Rectangle::yBorder = 0;
+
+std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
+    os << "Hue[0.17],Rectangle[{"<<r.getMinX()<<","<<r.getMinY()<<"},{"<<r.getMaxX()<<","<<r.getMaxY()<<"}]";
+    return os;
+}
+
+Rectangle::Rectangle(double x, double X, double y, double Y,bool allowOverlap) 
+    : minX(x),
+      maxX(X),
+      minY(y),
+      maxY(Y),
+      overlap(allowOverlap) 
+{
+    COLA_ASSERT(x<X);
+    COLA_ASSERT(y<Y);
+    COLA_ASSERT(getMinX()<getMaxX());
+    COLA_ASSERT(getMinY()<getMaxY());
+}
+
+Rectangle::Rectangle()
+    : minX(1),
+      maxX(-1),
+      minY(1),
+      maxY(-1),
+      overlap(false) 
+{
+    // Creates an invalid Rectangle
+}
+
+bool Rectangle::isValid(void) const
+{
+    return ((minX <= maxX) && (minY <= maxY));
+}
+
+Rectangle Rectangle::unionWith(const Rectangle& rhs) const
+{
+    if (!isValid())
+    {
+        return Rectangle(rhs);
+    }
+    else if (!rhs.isValid())
+    {
+        return Rectangle(*this);
+    }
+    
+    double newMaxY = std::max(rhs.getMaxY(),maxY);
+    double newMinY = std::min(rhs.getMinY(),minY);
+    double newMinX = std::min(rhs.getMinX(),minX);
+    double newMaxX = std::max(rhs.getMaxX(),maxX);
+
+    return Rectangle(newMinX, newMaxX, newMinY, newMaxY);
+}
+    
+void Rectangle::reset(unsigned d, double x, double X) {
+    if(d==0) {
+        minX=x;
+        maxX=X;
+    } else {
+        minY=x;
+        maxY=X;
+    }
+}
+
+struct Node;
+struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
+
+typedef set<Node*,CmpNodePos> NodeSet;
+
+struct Node {
+    Variable *v;
+    Rectangle *r;
+    double pos;
+    Node *firstAbove, *firstBelow;
+    NodeSet *leftNeighbours, *rightNeighbours;
+    Node(Variable *v, Rectangle *r, double p) 
+        : v(v),r(r),pos(p),
+          firstAbove(nullptr), firstBelow(nullptr),
+          leftNeighbours(nullptr), rightNeighbours(nullptr)
+     
+    {
+        COLA_ASSERT(r->width()<1e40);
+    }
+    ~Node() {
+        delete leftNeighbours;
+        delete rightNeighbours;
+    }
+    void addLeftNeighbour(Node *u) {
+        COLA_ASSERT(leftNeighbours!=nullptr);
+        leftNeighbours->insert(u);
+    }
+    void addRightNeighbour(Node *u) {
+        COLA_ASSERT(rightNeighbours!=nullptr);
+        rightNeighbours->insert(u);
+    }
+    void setNeighbours(NodeSet *left, NodeSet *right) {
+        leftNeighbours=left;
+        rightNeighbours=right;
+        for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
+            Node *v=*(i);
+            v->addRightNeighbour(this);
+        }
+        for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
+            Node *v=*(i);
+            v->addLeftNeighbour(this);
+        }
+    }
+};
+bool CmpNodePos::operator() (const Node* u, const Node* v) const {
+    COLA_ASSERT(!std::isnan(u->pos));
+    COLA_ASSERT(!std::isnan(v->pos));
+    if (u->pos < v->pos) {
+        return true;
+    }
+    if (v->pos < u->pos) {
+        return false;
+    }
+    return u < v;
+}
+
+NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
+    NodeSet *leftv = new NodeSet;
+    NodeSet::iterator i=scanline.find(v);
+    while(i!=scanline.begin()) {
+        Node *u=*(--i);
+        if(u->r->overlapX(v->r)<=0) {
+            leftv->insert(u);
+            return leftv;
+        }
+        if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
+            leftv->insert(u);
+        }
+    }
+    return leftv;
+}
+NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
+    NodeSet *rightv = new NodeSet;
+    NodeSet::iterator i=scanline.find(v);
+    for(++i;i!=scanline.end(); ++i) {
+        Node *u=*(i);
+        if(u->r->overlapX(v->r)<=0) {
+            rightv->insert(u);
+            return rightv;
+        }
+        if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
+            rightv->insert(u);
+        }
+    }
+    return rightv;
+}
+
+typedef enum {Open, Close} EventType;
+struct Event {
+    EventType type;
+    Node *v;
+    double pos;
+    Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
+};
+int compare_events(const void *a, const void *b) {
+    Event *ea=*(Event**)a;
+    Event *eb=*(Event**)b;
+    if(ea->pos==eb->pos) {
+        // when comparing opening and closing
+        // open must come first
+        if(ea->type==Open) return -1;
+        return 1;
+    } else if(ea->pos > eb->pos) {
+        return 1;
+    } else if(ea->pos < eb->pos) {
+        return -1;
+    } else if(std::isnan(ea->pos) != std::isnan(ea->pos)) {
+        /* See comment in CmpNodePos. */
+        return ( std::isnan(ea->pos)
+             ? -1
+             : 1 );
+    }
+    return 0;
+}
+
+/*
+ * Prepares constraints in order to apply VPSC horizontally.  Assumes 
+ * variables have already been created.
+ * useNeighbourLists determines whether or not a heuristic is used to 
+ * deciding whether to resolve all overlap in the x pass, or leave some
+ * overlaps for the y pass.
+ */
+void generateXConstraints(const Rectangles& rs, const Variables& vars,
+        Constraints& cs, const bool useNeighbourLists)
+{
+    const unsigned n = rs.size();
+    COLA_ASSERT(vars.size()>=n);
+    Event **events=new Event*[2*n];
+    unsigned i,ctr=0;
+    for(i=0;i<n;i++) {
+        vars[i]->desiredPosition=rs[i]->getCentreX();
+        Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
+        events[ctr++]=new Event(Open,v,rs[i]->getMinY());
+        events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
+    }
+    qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
+
+    NodeSet scanline;
+    for(i=0;i<2*n;i++) {
+        Event *e=events[i];
+        Node *v=e->v;
+        if(e->type==Open) {
+            scanline.insert(v);
+            if(useNeighbourLists) {
+                v->setNeighbours(
+                    getLeftNeighbours(scanline,v),
+                    getRightNeighbours(scanline,v)
+                );
+            } else {
+                NodeSet::iterator it=scanline.find(v);
+                if(it!=scanline.begin()) {
+                    Node *u=*(--it);
+                    v->firstAbove=u;
+                    u->firstBelow=v;
+                }
+                it=scanline.find(v);
+                if(++it!=scanline.end()) {
+                    Node *u=*it;
+                    v->firstBelow=u;
+                    u->firstAbove=v;
+                }
+            }
+        } else {
+            size_t result;
+            // Close event
+            if(useNeighbourLists) {
+                for(NodeSet::iterator i=v->leftNeighbours->begin();
+                    i!=v->leftNeighbours->end();i++
+                ) {
+                    Node *u=*i;
+                    double sep = (v->r->width()+u->r->width())/2.0;
+                    cs.push_back(new Constraint(u->v,v->v,sep));
+                    result=u->rightNeighbours->erase(v);
+                    COLA_ASSERT(result==1);
+                }
+                
+                for(NodeSet::iterator i=v->rightNeighbours->begin();
+                    i!=v->rightNeighbours->end();i++
+                ) {
+                    Node *u=*i;
+                    double sep = (v->r->width()+u->r->width())/2.0;
+                    cs.push_back(new Constraint(v->v,u->v,sep));
+                    result=u->leftNeighbours->erase(v);
+                    COLA_ASSERT(result==1);
+                }
+            } else {
+                Node *l=v->firstAbove, *r=v->firstBelow;
+                if(l!=nullptr) {
+                    double sep = (v->r->width()+l->r->width())/2.0;
+                    cs.push_back(new Constraint(l->v,v->v,sep));
+                    l->firstBelow=v->firstBelow;
+                }
+                if(r!=nullptr) {
+                    double sep = (v->r->width()+r->r->width())/2.0;
+                    cs.push_back(new Constraint(v->v,r->v,sep));
+                    r->firstAbove=v->firstAbove;
+                }
+            }
+            result=scanline.erase(v);
+            COLA_ASSERT(result==1);
+            delete v;
+        }
+        delete e;
+    }
+    COLA_ASSERT(scanline.size()==0);
+    delete [] events;
+}
+
+/*
+ * Prepares constraints in order to apply VPSC vertically to remove ALL
+ * overlap.
+ */
+void generateYConstraints(const Rectangles& rs, const Variables& vars,
+        Constraints& cs)
+{
+    const unsigned n = rs.size();
+    COLA_ASSERT(vars.size()>=n);
+    Event **events=new Event*[2*n];
+    unsigned ctr=0;
+    Rectangles::const_iterator ri=rs.begin(), re=rs.end();
+    Variables::const_iterator vi=vars.begin(), ve=vars.end();
+    for(;ri!=re&&vi!=ve;++ri,++vi) {
+        Rectangle* r=*ri;
+        Variable* v=*vi;
+        v->desiredPosition=r->getCentreY();
+        Node *node = new Node(v,r,r->getCentreY());
+        COLA_ASSERT(r->getMinX()<r->getMaxX());
+        events[ctr++]=new Event(Open,node,r->getMinX());
+        events[ctr++]=new Event(Close,node,r->getMaxX());
+    }
+    COLA_ASSERT(ri==rs.end());
+    qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
+    NodeSet scanline;
+#ifndef NDEBUG
+    size_t deletes=0;
+#endif
+    for(unsigned i=0;i<2*n;i++) {
+        Event *e=events[i];
+        Node *v=e->v;
+        if(e->type==Open) {
+            scanline.insert(v);
+            NodeSet::iterator it=scanline.find(v);
+            if(it!=scanline.begin()) {
+                Node *u=*(--it);
+                v->firstAbove=u;
+                u->firstBelow=v;
+            }
+            it=scanline.find(v);
+            if(++it!=scanline.end())     {
+                Node *u=*it;
+                v->firstBelow=u;
+                u->firstAbove=v;
+            }
+        } else {
+            // Close event
+            Node *l=v->firstAbove, *r=v->firstBelow;
+            if(l!=nullptr) {
+                double sep = (v->r->height()+l->r->height())/2.0;
+                cs.push_back(new Constraint(l->v,v->v,sep));
+                l->firstBelow=v->firstBelow;
+            }
+            if(r!=nullptr) {
+                double sep = (v->r->height()+r->r->height())/2.0;
+                cs.push_back(new Constraint(v->v,r->v,sep));
+                r->firstAbove=v->firstAbove;
+            }
+#ifndef NDEBUG
+            deletes++;
+            size_t erased=
+#endif
+            scanline.erase(v);
+            COLA_ASSERT(erased==1);
+            delete v;
+        }
+        delete e;
+    }
+    COLA_ASSERT(scanline.size()==0);
+    COLA_ASSERT(deletes==n);
+    delete [] events;
+}
+#include "libvpsc/linesegment.h"
+using namespace linesegment;
+inline bool checkIntersection(
+        const LineSegment::IntersectResult result, 
+        Vector const &intersection,
+        RectangleIntersections &ri, 
+        bool &side, double &sideX, double &sideY) {
+    switch(result) {
+    case LineSegment::INTERSECTING:
+        ri.intersects=side=true;
+        sideX=intersection.x_;
+        sideY=intersection.y_;
+    case LineSegment::PARALLEL:
+    case LineSegment::NOT_INTERSECTING:
+        return true;
+    case LineSegment::COINCIDENT:
+        ri.intersects=ri.top=ri.bottom=ri.left=ri.right=false;
+        return false;
+    }
+    return false;
+}
+void Rectangle::
+lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const {
+    Vector intersection;
+    LineSegment l(Vector(x1,y1),Vector(x2,y2));
+    LineSegment top(Vector(getMinX(),getMaxY()),Vector(getMaxX(),getMaxY()));
+    if(!checkIntersection(
+            l.Intersect(top,intersection),intersection,
+            ri,ri.top,ri.topX,ri.topY)) {
+        return;
+    }
+    LineSegment bottom(Vector(getMinX(),getMinY()),Vector(getMaxX(),getMinY()));
+    if(!checkIntersection(
+            l.Intersect(bottom,intersection),intersection,
+            ri,ri.bottom,ri.bottomX,ri.bottomY)) {
+        return;
+    }
+    LineSegment left(Vector(getMinX(),getMinY()),Vector(getMinX(),getMaxY()));
+    if(!checkIntersection(
+            l.Intersect(left,intersection),intersection,
+            ri,ri.left,ri.leftX,ri.leftY)) {
+        return;
+    }
+    LineSegment right(Vector(getMaxX(),getMinY()),Vector(getMaxX(),getMaxY()));
+    if(!checkIntersection(
+            l.Intersect(right,intersection),intersection,
+            ri,ri.right,ri.rightX,ri.rightY)) {
+        return;
+    }
+}
+static const double ERROR_MARGIN = 1e-4;
+inline bool eq(double a, double b) {
+    return fabs(a-b)<ERROR_MARGIN;
+    //return a==b;
+}
+/*
+bool Rectangle::inside(double x, double y) const {
+    return x>(minX+ERROR_MARGIN) && x<(maxX-ERROR_MARGIN) 
+        && y>(minY+ERROR_MARGIN) && y<(maxY-ERROR_MARGIN);
+}
+*/
+// p1=(x1,y1),p2=(x2,y2) are points on the boundary.  Puts the shortest
+// path round the outside of the rectangle  from p1 to p2 into xs, ys.
+void Rectangle::routeAround(double x1, double y1, double x2, double y2,
+        std::vector<double> &xs, std::vector<double> &ys) {
+    COLA_ASSERT(eq(x1,minX) || eq(x1,maxX) || eq(y1,minY) || eq(y1,maxY));
+    COLA_ASSERT(eq(x2,minX) || eq(x2,maxX) || eq(y2,minY) || eq(y2,maxY));
+    xs.push_back(x1);
+    ys.push_back(y1);
+    bool top1=eq(y1,maxY), top2=eq(y2,maxY),
+         bottom1=eq(y1,minY), bottom2=eq(y2,minY);
+    bool left1=eq(x1,minX), left2=eq(x2,minX), 
+         right1=eq(x1,maxX), right2=eq(x2,maxX);
+    bool leftright = (left1 && right2) || (right1 && left2);
+    bool topbottom = (top1 && bottom2) || (bottom1 && top2);
+    bool lefttop = (left1 && top2) || (top1 && left2);
+    bool righttop = (right1 && top2) || (top1 && right2);
+    bool leftbottom = (left1 && bottom2) || (bottom1 && left2);
+    bool rightbottom = (right1 && bottom2) || (bottom1 && right2);
+    if(lefttop) {
+        xs.push_back(minX);
+        ys.push_back(maxY);
+    } else if(righttop) {
+        xs.push_back(maxX);
+        ys.push_back(maxY);
+    } else if(leftbottom) {
+        xs.push_back(minX);
+        ys.push_back(minY);
+    } else if(rightbottom) {
+        xs.push_back(maxX);
+        ys.push_back(minY);
+    } else if(leftright) {
+        double midY = y1+(y2-y1)/2.0;
+        if(left1) { // left to right
+            if(midY<getCentreY()) { // route below
+                // bottom left
+                xs.push_back(getMinX());
+                ys.push_back(getMinY());
+                // bottom right
+                xs.push_back(getMaxX());
+                ys.push_back(getMinY());
+            } else { // route above
+                // top left
+                xs.push_back(getMinX());
+                ys.push_back(getMaxY());
+                // top right
+                xs.push_back(getMaxX());
+                ys.push_back(getMaxY());
+            }
+        } else { // right to left
+            if(midY<getCentreY()) { // route below
+                // bottom right
+                xs.push_back(getMaxX());
+                ys.push_back(getMinY());
+                // bottom left
+                xs.push_back(getMinX());
+                ys.push_back(getMinY());
+            } else { // route above
+                // top right
+                xs.push_back(getMaxX());
+                ys.push_back(getMaxY());
+                // top left
+                xs.push_back(getMinX());
+                ys.push_back(getMaxY());
+            }
+        }
+    } else if(topbottom) {
+        double midX = x1+(x2-x1)/2.0;
+        if(top1) {
+            if(midX<getCentreX()) { // route left
+                // top left
+                xs.push_back(getMinX());
+                ys.push_back(getMaxY());
+                // bottom left
+                xs.push_back(getMinX());
+                ys.push_back(getMinY());
+            } else { // route right
+                // top right
+                xs.push_back(getMaxX());
+                ys.push_back(getMaxY());
+                // bottom right
+                xs.push_back(getMaxX());
+                ys.push_back(getMinY());
+            }
+        } else { // bottom to top
+            if(midX<getCentreX()) { // route left
+                // bottom left
+                xs.push_back(getMinX());
+                ys.push_back(getMinY());
+                // top left
+                xs.push_back(getMinX());
+                ys.push_back(getMaxY());
+            } else { // route right
+                // bottom right
+                xs.push_back(getMaxX());
+                ys.push_back(getMinY());
+                // top right
+                xs.push_back(getMaxX());
+                ys.push_back(getMaxY());
+            }
+        }
+    }
+    xs.push_back(x2);
+    ys.push_back(y2);
+}
+
+/* 
+ * moves all the rectangles to remove all overlaps.  Heuristic
+ * attempts to move by as little as possible.
+ * no overlaps guaranteed.
+ * @param rs the rectangles which will be moved to remove overlap
+ */
+void removeoverlaps(Rectangles& rs) {
+    const set<unsigned> fixed = set<unsigned>();
+    removeoverlaps(rs,fixed);
+}
+#define ISNOTNAN(d) (d)==(d)
+/*
+ * Moves rectangles to remove all overlaps.  A heuristic
+ * attempts to move by as little as possible.  The heuristic is
+ * that the overlaps are removed horizontally and then vertically,
+ * each pass being a quadratic program in which the total squared movement
+ * is minimised subject to non-overlap constraints.  An optional third
+ * horizontal pass (in addition to the first horizontal pass and the second
+ * vertical pass) can be applied wherein the x-positions of rectangles are reset to their
+ * original positions and overlap removal repeated.  This may avoid some
+ * unnecessary movement. 
+ * @param rs the rectangles which will be moved to remove overlap
+ * @param fixed a set of indices to rectangles which should not be moved
+ * @param thirdPass optionally run the third horizontal pass described above.
+ */
+void removeoverlaps(Rectangles& rs, const set<unsigned>& fixed, bool thirdPass) {
+    const double xBorder=Rectangle::xBorder, yBorder=Rectangle::yBorder;
+    static const double EXTRA_GAP=1e-3;
+    static const size_t ARRAY_UNUSED=1;
+    unsigned n=rs.size();
+    try {
+        // The extra gap avoids numerical imprecision problems
+        Rectangle::setXBorder(xBorder+EXTRA_GAP);
+        Rectangle::setYBorder(yBorder+EXTRA_GAP);
+        Variables vs(n);
+        Variables::iterator v;
+        unsigned i=0;
+        vector<double> initX(thirdPass?n:ARRAY_UNUSED);
+        for(v=vs.begin();v!=vs.end();++v,++i) {
+            double weight=1;
+            if(fixed.find(i)!=fixed.end()) {
+                weight=10000;
+            }
+            *v=new Variable(i,0,weight);
+            if(thirdPass) {
+                initX[i]=rs[i]->getCentreX();
+            }
+        }
+        Constraints cs;
+        generateXConstraints(rs,vs,cs,true);
+        Solver vpsc_x(vs,cs);
+        vpsc_x.solve();
+        Rectangles::iterator r=rs.begin();
+        for(v=vs.begin();v!=vs.end();++v,++r) {
+            COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
+            (*r)->moveCentreX((*v)->finalPosition);
+        }
+        COLA_ASSERT(r==rs.end());
+        for_each(cs.begin(),cs.end(),delete_object());
+        cs.clear();
+        // Removing the extra gap here ensures things that were moved to be
+        // adjacent to one another above are not considered overlapping
+        Rectangle::setXBorder(xBorder);
+        generateYConstraints(rs,vs,cs);
+        Solver vpsc_y(vs,cs);
+        vpsc_y.solve();
+        r=rs.begin();
+        for(v=vs.begin();v!=vs.end();++v,++r) {
+            COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
+            (*r)->moveCentreY((*v)->finalPosition);
+        }
+        for_each(cs.begin(),cs.end(),delete_object());
+        cs.clear();
+        Rectangle::setYBorder(yBorder);
+        if(thirdPass) {
+            // we reset x positions to their original values
+            // and apply a third pass horizontally so that
+            // rectangles which were moved unnecessarily in the
+            // first horizontal pass (i.e. their overlap
+            // was later resolved vertically) have an
+            // opportunity now to stay put.
+            Rectangle::setXBorder(xBorder+EXTRA_GAP);
+            r=rs.begin();
+            for(v=vs.begin();v!=vs.end();++v,++r) {
+                (*r)->moveCentreX(initX[(*v)->id]);
+            }
+            generateXConstraints(rs,vs,cs,false);
+            Solver vpsc_x2(vs,cs);
+            vpsc_x2.solve();
+            r=rs.begin();
+            for(v=vs.begin();v!=vs.end();++v,++r) {
+                COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
+                (*r)->moveCentreX((*v)->finalPosition);
+            }
+        }
+        Rectangle::setXBorder(xBorder);
+        for_each(cs.begin(),cs.end(),delete_object());
+        for_each(vs.begin(),vs.end(),delete_object());
+    } catch (char *str) {
+        std::cerr<<str<<std::endl;
+        for(Rectangles::iterator r=rs.begin();r!=rs.end();++r) {
+            std::cerr << **r <<std::endl;
+        }
+    }
+    COLA_ASSERT(noRectangleOverlaps(rs));
+}
+
+
+bool noRectangleOverlaps(const Rectangles& rs) 
+{
+    Rectangle *u, *v;
+    Rectangles::const_iterator i=rs.begin(), j, e=rs.end();
+    for (;i!=e;++i) 
+    {
+        u=*i;
+        for (j=i+1;j!=e;++j) 
+        {
+            v=*j;
+            if (u->overlapX(v)>0) 
+            {
+                COLA_ASSERT(u->overlapY(v)==0);
+            }
+        }
+    }
+    return true;
+}
+
+// checks if line segment is strictly overlapping.
+// That is, if any point on the line is inside the rectangle.
+bool Rectangle::overlaps(double x1, double y1, double x2, double y2) 
+{
+    RectangleIntersections ri;
+    lineIntersections(x1,y1,x2,y2,ri);
+    if(ri.intersects) {
+        if(ri.countIntersections()==1) {
+            // special case when one point is touching
+            // the boundary of the rectangle but no part
+            // of the line is interior
+            if(!inside(x1,y1)&&!inside(x2,y2)) {
+                return false;
+            }
+        }
+        printf("Rectangle/Segment intersection (SVG):\n");
+        printf("<svg style=\"stroke: black; fill: none;\">\n");
+        printf("<polyline points=\"%f,%f %f,%f\" />\n",x1,y1,x2,y2);
+        printf("<rect x=\"%f\" y=\"%f\" width=\"%f\" height=\"%f\" />\n",
+                getMinX(),getMinY(),width(),height());
+        printf("</svg>\n");
+        ri.printIntersections();
+        return true;
+    }
+    return false;
+}
+
+
+void RectangleIntersections::printIntersections() 
+{
+    printf("intersections:\n");
+    if(top) printf("  top=%d:(%f,%f)\n",top,topX,topY);
+    if(bottom) printf("  bottom=%d:(%f,%f)\n",bottom,bottomX,bottomY);
+    if(left) printf("  left=%d:(%f,%f)\n",left,leftX,leftY);
+    if(right) printf("  right=%d:(%f,%f)\n",right,rightX,rightY);
+}
+
+// Of the stored intersections, this returns the one closest to the
+// specified point
+void RectangleIntersections::nearest(double x, double y, double &xi, double &yi) {
+    bool is[]={top, right, bottom, left};
+    double xs[]={topX, rightX, bottomX, leftX};
+    double ys[]={topY, rightY, bottomY, leftY};
+    double dx, dy, l, minl = 999999999999999.0;
+    for(unsigned i=0;i<4;i++) 
+    {
+        if(is[i]) 
+        {
+            dx=xs[i]-x;
+            dy=ys[i]-y;
+            l=dx*dx + dy*dy;
+            if(l<minl) 
+            {
+                minl=l;
+                xi=xs[i];
+                yi=ys[i];
+            }
+        }
+    }
+}
+
+}
-- 
cgit v1.2.3