~centralelyon2010/inkscape/imagelinks2

Viewing changes to src/removeoverlap/generate-constraints.h

Committer: tgdwyer
Date: 2006-07-12 00:55:58 UTC
Revision ID: tgdwyer@users.sourceforge.net-20060712005558-4pqys3ou7f5er3dm

Previously graph layout was done using the Kamada-Kawai layout algorithm
implemented in Boost. I am replacing this with a custom implementation of
a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

files added:
src/libcola

src/libcola/Makefile_insert

src/libcola/cola.cpp

src/libcola/cola.h

src/libcola/conjugate_gradient.cpp

src/libcola/conjugate_gradient.h

src/libcola/cycle_detector.cpp

src/libcola/cycle_detector.h

src/libcola/defs.h

src/libcola/gradient_projection.cpp

src/libcola/gradient_projection.h

src/libcola/shortest_paths.cpp

src/libcola/shortest_paths.h

src/libcola/straightener.cpp

src/libcola/straightener.h

src/libvpsc

src/libvpsc/COPYING

src/libvpsc/Makefile_insert

src/libvpsc/block.cpp

src/libvpsc/block.h

src/libvpsc/blocks.cpp

src/libvpsc/blocks.h

src/libvpsc/constraint.cpp

src/libvpsc/constraint.h

src/libvpsc/csolve_VPSC.cpp

src/libvpsc/csolve_VPSC.h

src/libvpsc/generate-constraints.cpp

src/libvpsc/generate-constraints.h

src/libvpsc/isnan.h

src/libvpsc/pairingheap

src/libvpsc/pairingheap/.dirstamp

src/libvpsc/pairingheap/PairingHeap.cpp

src/libvpsc/pairingheap/PairingHeap.h

src/libvpsc/pairingheap/dsexceptions.h

src/libvpsc/placement_SolveVPSC.h

src/libvpsc/remove_rectangle_overlap.cpp

src/libvpsc/remove_rectangle_overlap.h

src/libvpsc/solve_VPSC.cpp

src/libvpsc/solve_VPSC.h

src/libvpsc/variable.cpp

src/libvpsc/variable.h

files removed:
src/removeoverlap/block.cpp

src/removeoverlap/block.h

src/removeoverlap/blocks.cpp

src/removeoverlap/blocks.h

src/removeoverlap/constraint.cpp

src/removeoverlap/constraint.h

src/removeoverlap/generate-constraints.cpp

src/removeoverlap/generate-constraints.h

src/removeoverlap/pairingheap

src/removeoverlap/pairingheap/.cvsignore

src/removeoverlap/pairingheap/PairingHeap.cpp

src/removeoverlap/pairingheap/PairingHeap.h

src/removeoverlap/pairingheap/dsexceptions.h

src/removeoverlap/placement_SolveVPSC.cpp

src/removeoverlap/placement_SolveVPSC.h

src/removeoverlap/remove_rectangle_overlap-test.cpp

src/removeoverlap/remove_rectangle_overlap.cpp

src/removeoverlap/remove_rectangle_overlap.h

src/removeoverlap/solve_VPSC.cpp

src/removeoverlap/solve_VPSC.h

src/removeoverlap/variable.cpp

src/removeoverlap/variable.h

files modified:
configure.ac

mkinstalldirs

src/Makefile.am

src/Makefile_insert

src/graphlayout/graphlayout.cpp

src/removeoverlap/Makefile_insert

src/removeoverlap/removeoverlap.cpp

Show diffs side-by-side

added added

removed removed

src/removeoverlap/generate-constraints.h

/**

* \brief Functions to automatically generate constraints for the

* rectangular node overlap removal problem.

* Authors:

* Tim Dwyer <tgdwyer@gmail.com>

* Released under GNU LGPL. Read the file 'COPYING' for more information.

#ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H

#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H

#include <iostream>

class Rectangle {

friend std::ostream& operator <<(std::ostream &os, const Rectangle &r);

public:

static double xBorder,yBorder;

Rectangle(double x, double X, double y, double Y);

double getMaxX() const { return maxX+xBorder; }

double getMaxY() const { return maxY+yBorder; }

double getMinX() const { return minX; }

double getMinY() const { return minY; }

double getMinD(unsigned const d) const {

return ( d == 0 ? getMinX() : getMinY() );

}

double getMaxD(unsigned const d) const {

return ( d == 0 ? getMaxX() : getMaxY() );

}

double getCentreX() const { return minX+width()/2.0; }

double getCentreY() const { return minY+height()/2.0; }

double width() const { return getMaxX()-minX; }

double height() const { return getMaxY()-minY; }

static void setXBorder(double x) {xBorder=x;}

static void setYBorder(double y) {yBorder=y;}

void moveCentreX(double x) {

moveMinX(x-width()/2.0);

}

void moveCentreY(double y) {

moveMinY(y-height()/2.0);

}

void moveMinX(double x) {

maxX=x+width()-xBorder;

minX=x;

}

void moveMinY(double y) {

maxY=y+height()-yBorder;

minY=y;

}

inline double overlapX(Rectangle *r) const {

if (getCentreX() <= r->getCentreX() && r->minX < getMaxX())

return getMaxX() - r->minX;

if (r->getCentreX() <= getCentreX() && minX < r->getMaxX())

return r->getMaxX() - minX;

return 0;

}

inline double overlapY(Rectangle *r) const {

if (getCentreY() <= r->getCentreY() && r->minY < getMaxY())

return getMaxY() - r->minY;

if (r->getCentreY() <= getCentreY() && minY < r->getMaxY())

return r->getMaxY() - minY;

return 0;

}

private:

double minX,maxX,minY,maxY;

};

class Variable;

class Constraint;

// returns number of constraints generated

int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists);

int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs);

#endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H

Older »