1 files changed, 302 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libvpsc/rectangle.h b/src/3rdparty/adaptagrams/libvpsc/rectangle.h
new file mode 100644
index 0000000..df76399
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libvpsc/rectangle.h
@@ -0,0 +1,302 @@
+/*
+ * 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-2010  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
+*/
+
+/*
+ * Functions to automatically generate constraints for the
+ * rectangular node overlap removal problem.
+ *
+ */
+#ifndef VPSC_RECTANGLE_H
+#define VPSC_RECTANGLE_H
+
+#include <iostream>
+#include <vector>
+#include <set>
+#include <cassert>
+#include <cmath>
+
+#include "libvpsc/assertions.h"
+
+namespace vpsc {
+
+//! @brief Indicates the x- or y-dimension.
+enum Dim {
+    //! The x-dimension (0).
+    HORIZONTAL = 0,
+    //! The x-dimension (0).
+    XDIM = 0,
+    //! The y-dimension (1).
+    VERTICAL = 1,
+    //! The y-dimension (1).
+    YDIM = 1,
+    // The dimension is not set.
+    UNSET = 2
+};
+
+inline Dim conjugate(Dim d) {
+	return static_cast<Dim>(!d);
+}
+/* records the positions and sides through which a particular line intersects with a rectangle
+ */
+struct RectangleIntersections {
+    bool intersects, top, bottom, left, right;
+    double topX, topY, bottomX, bottomY, leftX, leftY, rightX, rightY;
+    RectangleIntersections()
+        : intersects(false),top(false),bottom(false),left(false),right(false),
+      topX(0),topY(0),bottomX(0),bottomY(0),leftX(0),leftY(0),rightX(0),rightY(0) {} 
+    int countIntersections() {
+        return left+right+top+bottom;
+    }
+    void printIntersections(void);
+    // Of the stored intersections, this returns the one closest to the
+    // specified point
+    void nearest(double x, double y, double & xi, double & yi);
+};
+
+/**
+ * @brief  A rectangle represents a fixed-size shape in the diagram that may
+ *         be moved to prevent overlaps and satisfy constraints.
+ */
+class Rectangle {   
+public:
+    /**
+     * @brief Constructs a rectangle by specifying the positions of all 
+     *        four sides.
+     *
+     * @param[in] x  Minimum horizontal value.
+     * @param[in] X  Maximum horizontal value.
+     * @param[in] y  Minimum vertical value.
+     * @param[in] Y  Maximum vertical value.
+     * @param[in] allowOverlap not used currently.
+     */
+    Rectangle(double x, double X, double y, double Y,
+            bool allowOverlap = false);
+    Rectangle(Rectangle const &Other)
+        :  minX(Other.minX)
+        ,  maxX(Other.maxX)
+        ,  minY(Other.minY)
+        ,  maxY(Other.maxY)
+        ,  overlap(Other.overlap) { }
+    Rectangle();
+    bool isValid(void) const;
+    Rectangle unionWith(const Rectangle& rhs) const;
+    /*
+     * reset the dimensions in one axis
+     * @param d axis (0==X, 1==Y)
+     * @param x min value
+     * @param X max value
+     */
+    void reset(const unsigned d, double x, double X);
+    double getMaxX() const { return maxX+xBorder; }
+    double getMaxY() const { return maxY+yBorder; }
+    double getMinX() const { return minX-xBorder; }
+    double getMinY() const { return minY-yBorder; }
+    /*
+     * @param d axis: 0=horizontal 1=vertical
+     */
+    double getMinD(unsigned const d) const {
+        COLA_ASSERT(d==0||d==1);
+        return ( d == 0 ? getMinX() : getMinY() );
+    }
+    /*
+     * @param d axis: 0=horizontal 1=vertical
+     */
+    double getMaxD(unsigned const d) const {
+        COLA_ASSERT(d==0||d==1);
+        return ( d == 0 ? getMaxX() : getMaxY() );
+    }
+    void setMinD(unsigned const d, const double val)
+    { if ( d == 0) { minX = val; } else { minY = val; } }
+    void setMaxD(unsigned const d, const double val)
+    { if ( d == 0) { maxX = val; } else { maxY = val; } }
+    double getCentreX() const { return getMinX()+width()/2.0; }
+    double getCentreY() const { return getMinY()+height()/2.0; }
+    /*
+     * @param d axis: 0=horizontal 1=vertical
+     */
+    double getCentreD(unsigned const d) const {
+        COLA_ASSERT(d==0||d==1);
+        return getMinD(d)+length(d)/2.0;
+    }
+    double width() const { return getMaxX()-getMinX(); }
+    double height() const { return getMaxY()-getMinY(); }
+    /*
+     * @param d axis: 0=width 1=height
+     * @return width or height
+     */
+    double length(unsigned const d) const {
+        COLA_ASSERT(d==0||d==1);
+        return ( d == 0 ? width() : height() );
+    }
+    void set_width(double w) { maxX = minX + w - 2.0*xBorder; }
+    void set_height(double h) { maxY = minY + h - 2.0*yBorder; }
+    void moveCentreD(const unsigned d, double p) {
+        COLA_ASSERT(d==0||d==1);
+        if(d == 0) { moveCentreX(p);
+        } else { moveCentreY(p); }
+    }
+    void moveCentreX(double x) {
+        moveMinX(x-width()/2.0);
+    }
+    void moveCentreY(double y) {
+        moveMinY(y-height()/2.0);
+    }
+    void moveCentre(double x, double y) {
+        moveCentreX(x);
+        moveCentreY(y);
+    }
+    void moveMinX(double x) {
+        double w=width();
+        minX=x+xBorder;
+        maxX=x+w-xBorder;
+        COLA_ASSERT(fabs(width()-w)<1e-9);
+    }
+    void moveMinY(double y) {
+        double h=height();
+        maxY=y+h-yBorder;
+        minY=y+yBorder;
+        COLA_ASSERT(fabs(height()-h)<1e-9);
+    }
+    double overlapD(const unsigned d, Rectangle* r) {
+        if(d==0) {
+            return overlapX(r);
+        } else {
+            return overlapY(r);
+        }
+    }
+    double overlapX(Rectangle *r) const {
+        double ux=getCentreX(), vx=r->getCentreX();
+        if (ux <= vx && r->getMinX() < getMaxX())
+            return getMaxX() - r->getMinX();
+        if (vx <= ux && getMinX() < r->getMaxX())
+            return r->getMaxX() - getMinX();
+        return 0;
+    }
+    double overlapY(Rectangle *r) const {
+        double uy=getCentreY(), vy=r->getCentreY();
+        if (uy <= vy && r->getMinY() < getMaxY()) {
+            return getMaxY() - r->getMinY();
+        }
+        if (vy <= uy && getMinY() < r->getMaxY()) {
+            return r->getMaxY() - getMinY();
+        }
+        return 0;
+    }
+    bool allowOverlap() {
+        return overlap;
+    }
+    void offset(double dx, double dy) {
+        minX += dx;
+        maxX += dx;
+        minY += dy;
+        maxY += dy;
+    }
+    // returns the intersections between the line segment from (x1,y1) 
+    // to (x2,y2) and this rectangle.  Any intersections points with
+    // sides are reported, lines coincident with a side are considered not
+    // to intersect.
+    void lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const;
+    bool inside(double x, double y) const {
+        return x>getMinX() && x<getMaxX() && y>getMinY() && y<getMaxY();
+    }
+    // checks if line segment is strictly overlapping.
+    // That is, if any point on the line is inside the rectangle.
+    bool overlaps(double x1, double y1, double x2, double y2);
+    // 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 routeAround(double x1, double y1, double x2, double y2,
+            std::vector<double> &xs, std::vector<double> &ys);
+    /*
+     * xBorder and yBorder can be set to add a border to the boundary of the
+     * rectangle.  In other words, the size of the rectangle returned by the
+     * getters (getMinX, getMaxX, etc) will be slightly larger than the
+     * internal representation.  This is useful in situations where we need the
+     * size considered in one axis to be slightly different to that considered
+     * in the other axis for example, to avoid numerical precision problems in
+     * the axis-by-axis overlap removal process.
+     */
+    static double xBorder,yBorder;
+    static void setXBorder(double x) {xBorder=x;}
+    static void setYBorder(double y) {yBorder=y;}
+    
+private:
+    double minX,maxX,minY,maxY;
+    bool overlap;
+};
+
+//! @brief A vector of pointers to Rectangle objects.
+typedef std::vector<Rectangle*> Rectangles;
+
+std::ostream& operator<<(std::ostream& os, vpsc::Rectangle const &r);
+
+class Variable;
+typedef std::vector<Variable *> Variables;
+class Constraint;
+typedef std::vector<Constraint *> Constraints;
+
+void generateXConstraints(const Rectangles& rs, const Variables& vars,
+        Constraints& cs, const bool useNeighbourLists);
+void generateYConstraints(const Rectangles& rs, const Variables& vars,
+        Constraints& cs);
+
+/**
+ * @brief Uses VPSC to remove overlaps between rectangles.
+ *
+ * Moves rectangles to remove all overlaps.  Heuristic attempts to move 
+ * shapes by as little as possible.
+ *
+ * @param[in,out] rs  The rectangles which will be moved to remove overlap
+ */
+void removeoverlaps(Rectangles& rs);
+
+/** 
+ * @brief Uses VPSC to remove overlaps between rectangles, excluding some 
+ *        that should not be moved.
+ *
+ * Moves rectangles to remove all overlaps.  A heuristic attempts to move 
+ * shapes 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[in,out] rs    The rectangles which will be moved to remove overlap
+ * @param[in] fixed     A set of indices to rectangles which should not be moved.
+ * @param[in] thirdPass Optionally run the third horizontal pass described above.
+ */
+void removeoverlaps(Rectangles& rs, const std::set<unsigned>& fixed, 
+        bool thirdPass = true);
+
+// Useful for assertions:
+bool noRectangleOverlaps(const Rectangles& rs);
+
+struct delete_object
+{
+    template <typename T>
+    void operator()(T *ptr){ delete ptr;}
+};
+
+} // namespace vpsc
+#endif // VPSC_RECTANGLE_H