diff options
Diffstat (limited to 'src/libavoid')
29 files changed, 4873 insertions, 0 deletions
diff --git a/src/libavoid/.cvsignore b/src/libavoid/.cvsignore new file mode 100644 index 000000000..38efca7bc --- /dev/null +++ b/src/libavoid/.cvsignore @@ -0,0 +1,3 @@ +.deps +.dirstamp +makefile diff --git a/src/libavoid/Makefile_insert b/src/libavoid/Makefile_insert new file mode 100644 index 000000000..146344813 --- /dev/null +++ b/src/libavoid/Makefile_insert @@ -0,0 +1,33 @@ +## Makefile.am fragment sourced by src/Makefile.am. + +libavoid/all: libavoid/libavoid.a + +libavoid/clean: + rm -f libavoid/libavoid.a $(libavoid_libavoid_a_OBJECTS) + +libavoid_libavoid_a_SOURCES = \ + libavoid/connector.cpp \ + libavoid/connector.h \ + libavoid/debug.h \ + libavoid/geometry.cpp \ + libavoid/geometry.h \ + libavoid/geomtypes.h \ + libavoid/graph.cpp \ + libavoid/graph.h \ + libavoid/incremental.cpp \ + libavoid/incremental.h \ + libavoid/makepath.cpp \ + libavoid/makepath.h \ + libavoid/polyutil.cpp \ + libavoid/polyutil.h \ + libavoid/shape.cpp \ + libavoid/shape.h \ + libavoid/static.cpp \ + libavoid/static.h \ + libavoid/timer.cpp \ + libavoid/timer.h \ + libavoid/vertices.cpp \ + libavoid/vertices.h \ + libavoid/visibility.cpp \ + libavoid/visibility.h \ + libavoid/libavoid.h diff --git a/src/libavoid/README b/src/libavoid/README new file mode 100644 index 000000000..ada0e9908 --- /dev/null +++ b/src/libavoid/README @@ -0,0 +1,5 @@ +This directory contains libavoid-0.1. It has been included here since it is +a new library without wide availablity. + +The project page is http://www.sourceforge.net/projects/libavoid/ +The library's maintainer is Michael Wybrow, an Inkscape developer. diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp new file mode 100644 index 000000000..cde387c5b --- /dev/null +++ b/src/libavoid/connector.cpp @@ -0,0 +1,408 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/graph.h" +#include "libavoid/makepath.h" +#include "libavoid/visibility.h" +#include "libavoid/debug.h" + + +namespace Avoid { + + +ConnRefList connRefs; + + +ConnRef::ConnRef(const uint id) + : _id(id) + , _needs_reroute_flag(true) + , _false_path(false) + , _active(false) + , _route_dist(0) + , _srcVert(NULL) + , _dstVert(NULL) + , _initialised(false) + , _callback(NULL) + , _connector(NULL) +{ + // TODO: Store endpoints and details. + _route.pn = 0; + _route.ps = NULL; +} + + +ConnRef::ConnRef(const uint id, const Point& src, const Point& dst) + : _id(id) + , _needs_reroute_flag(true) + , _false_path(false) + , _active(false) + , _route_dist(0) + , _srcVert(NULL) + , _dstVert(NULL) + , _initialised(false) + , _callback(NULL) + , _connector(NULL) +{ + _route.pn = 0; + _route.ps = NULL; + + if (IncludeEndpoints) + { + bool isShape = false; + _srcVert = new VertInf(VertID(id, isShape, 1), src); + _dstVert = new VertInf(VertID(id, isShape, 2), dst); + vertices.addVertex(_srcVert); + vertices.addVertex(_dstVert); + makeActive(); + _initialised = true; + } +} + + +ConnRef::~ConnRef() +{ + freeRoute(); + + if (_srcVert) + { + vertices.removeVertex(_srcVert); + delete _srcVert; + _srcVert = NULL; + } + + if (_dstVert) + { + vertices.removeVertex(_dstVert); + delete _dstVert; + _dstVert = NULL; + } + + if (_active) + { + makeInactive(); + } +} + +void ConnRef::updateEndPoint(const uint type, const Point& point) +{ + assert((type == (uint) VertID::src) || (type == (uint) VertID::tar)); + //assert(IncludeEndpoints); + + VertInf *altered = NULL; + VertInf *partner = NULL; + bool isShape = false; + + if (type == (uint) VertID::src) + { + if (_srcVert) + { + _srcVert->Reset(point); + } + else + { + _srcVert = new VertInf(VertID(_id, isShape, type), point); + vertices.addVertex(_srcVert); + } + + altered = _srcVert; + partner = _dstVert; + } + else // if (type == (uint) VertID::dst) + { + if (_dstVert) + { + _dstVert->Reset(point); + } + else + { + _dstVert = new VertInf(VertID(_id, isShape, type), point); + vertices.addVertex(_dstVert); + } + + altered = _dstVert; + partner = _srcVert; + } + + bool knownNew = false; + vertexVisibility(altered, partner, knownNew, true); +} + + +void ConnRef::makeActive(void) +{ + assert(!_active); + + // Add to connRefs list. + _pos = connRefs.insert(connRefs.begin(), this); + _active = true; +} + + +void ConnRef::makeInactive(void) +{ + assert(_active); + + // Remove from connRefs list. + connRefs.erase(_pos); + _active = false; +} + + +void ConnRef::freeRoute(void) +{ + if (_route.ps) + { + _route.pn = 0; + std::free(_route.ps); + _route.ps = NULL; + } +} + + +PolyLine& ConnRef::route(void) +{ + return _route; +} + + +void ConnRef::calcRouteDist(void) +{ + _route_dist = 0; + for (int i = 1; i < _route.pn; i++) + { + _route_dist += dist(_route.ps[i], _route.ps[i - 1]); + } +} + + +bool ConnRef::needsReroute(void) +{ + return (_false_path || _needs_reroute_flag); +} + + +void ConnRef::moveRoute(const int& diff_x, const int& diff_y) +{ + for (int i = 0; i < _route.pn; i++) + { + _route.ps[i].x += diff_x; + _route.ps[i].y += diff_y; + } +} + + +void ConnRef::lateSetup(const Point& src, const Point& dst) +{ + assert(!_initialised); + + bool isShape = false; + _srcVert = new VertInf(VertID(_id, isShape, 1), src); + _dstVert = new VertInf(VertID(_id, isShape, 2), dst); + vertices.addVertex(_srcVert); + vertices.addVertex(_dstVert); + makeActive(); + _initialised = true; +} + + +VertInf *ConnRef::src(void) +{ + return _srcVert; +} + + +VertInf *ConnRef::dst(void) +{ + return _dstVert; +} + + +bool ConnRef::isInitialised(void) +{ + return _initialised; +} + + +void ConnRef::unInitialise(void) +{ + vertices.removeVertex(_srcVert); + vertices.removeVertex(_dstVert); + makeInactive(); + _initialised = false; +} + + +void ConnRef::removeFromGraph(void) +{ + for (VertInf *iter = _srcVert; iter != NULL; ) + { + VertInf *tmp = iter; + iter = (iter == _srcVert) ? _dstVert : NULL; + + // For each vertex. + EdgeInfList& visList = tmp->visList; + EdgeInfList::iterator finish = visList.end(); + EdgeInfList::iterator edge; + while ((edge = visList.begin()) != finish) + { + // Remove each visibility edge + delete (*edge); + } + + EdgeInfList& invisList = tmp->invisList; + finish = invisList.end(); + while ((edge = invisList.begin()) != finish) + { + // Remove each invisibility edge + delete (*edge); + } + } +} + + +void ConnRef::setCallback(void (*cb)(void *), void *ptr) +{ + _callback = cb; + _connector = ptr; +} + + +void ConnRef::handleInvalid(void) +{ + if (_false_path || _needs_reroute_flag) { + if (_callback) { + _callback(_connector); + } + } +} + + +void ConnRef::makePathInvalid(void) +{ + _needs_reroute_flag = true; +} + + +int ConnRef::generatePath(Point p0, Point p1) +{ + if (!_false_path && !_needs_reroute_flag) { + // This connector is up to date. + return (int) false; + } + + _false_path = false; + _needs_reroute_flag = false; + + VertInf *src = _srcVert; + VertInf *tar = _dstVert; + + if (!IncludeEndpoints) + { + lateSetup(p0, p1); + + // Update as they have just been set by lateSetup. + src = _srcVert; + tar = _dstVert; + + bool knownNew = true; + vertexVisibility(src, tar, knownNew); + vertexVisibility(tar, src, knownNew); + } + + bool *flag = &(_needs_reroute_flag); + + makePath(this, flag); + + bool result = true; + + int pathlen = 1; + for (VertInf *i = tar; i != src; i = i->pathNext) + { + pathlen++; + if (i == NULL) + { + db_printf("Warning: Path not found...\n"); + pathlen = 2; + tar->pathNext = src; + if (InvisibilityGrph) + { + // TODO: Could we know this edge already? + EdgeInf *edge = EdgeInf::existingEdge(src, tar); + assert(edge != NULL); + edge->addCycleBlocker(); + } + result = false; + break; + } + if (pathlen > 100) + { + fprintf(stderr, "ERROR: Should never be here...\n"); + exit(1); + } + } + Point *path = (Point *) malloc(pathlen * sizeof(Point)); + + int j = pathlen - 1; + for (VertInf *i = tar; i != src; i = i->pathNext) + { + if (InvisibilityGrph) + { + // TODO: Again, we could know this edge without searching. + EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext); + edge->addConn(flag); + } + else + { + _false_path = true; + } + path[j--] = i->point; + } + path[0] = src->point; + + + // Would clear visibility for endpoints here if required. + + PolyLine& output_route = route(); + output_route.pn = pathlen; + output_route.ps = path; + + return (int) result; +} + + +//============================================================================ + + + // It's intended this function is called after shape movement has + // happened to alert connectors that they need to be rerouted. +void callbackAllInvalidConnectors(void) +{ + ConnRefList::iterator fin = connRefs.end(); + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { + (*i)->handleInvalid(); + } +} + + +} + + diff --git a/src/libavoid/connector.h b/src/libavoid/connector.h new file mode 100644 index 000000000..6abb01d49 --- /dev/null +++ b/src/libavoid/connector.h @@ -0,0 +1,93 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_CONNECTOR_H +#define AVOID_CONNECTOR_H + +#include "libavoid/geometry.h" +#include "libavoid/shape.h" +#include <list> + + +namespace Avoid { + +typedef unsigned int uint; + +class ConnRef; + +typedef std::list<ConnRef *> ConnRefList; + + +class ConnRef +{ + public: + ConnRef(const uint id); + ConnRef(const uint id, const Point& src, const Point& dst); + ~ConnRef(); + + PolyLine& route(void); + bool needsReroute(void); + void moveRoute(const int& diff_x, const int& diff_y); + void freeRoute(void); + void calcRouteDist(void); + void updateEndPoint(const uint type, const Point& point); + void makeActive(void); + void makeInactive(void); + void lateSetup(const Point& src, const Point& dst); + VertInf *src(void); + VertInf *dst(void); + void removeFromGraph(void); + bool isInitialised(void); + void unInitialise(void); + void setCallback(void (*cb)(void *), void *ptr); + void handleInvalid(void); + int generatePath(Point p0, Point p1); + void makePathInvalid(void); + + friend void markConnectors(ShapeRef *shape); + + private: + uint _id; + bool _needs_reroute_flag; + bool _false_path; + bool _active; + PolyLine _route; + double _route_dist; + ConnRefList::iterator _pos; + VertInf *_srcVert; + VertInf *_dstVert; + bool _initialised; + void (*_callback)(void *); + void *_connector; +}; + + +extern ConnRefList connRefs; + +extern void callbackAllInvalidConnectors(void); + +} + + +#endif + + diff --git a/src/libavoid/debug.h b/src/libavoid/debug.h new file mode 100644 index 000000000..0b182d442 --- /dev/null +++ b/src/libavoid/debug.h @@ -0,0 +1,61 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_DEBUG_H +#define AVOID_DEBUG_H + + + +#ifndef NDEBUG + //#define DBPRINTF_DEBUG +#endif + + +#ifdef DBPRINTF_DEBUG + +#include <stdarg.h> +#include <iostream> + +#endif + +namespace Avoid { + +#ifdef DBPRINTF_DEBUG +inline void db_printf(const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + vfprintf(stdout, fmt, ap); + va_end(ap); +} +#else +inline void db_printf(const char *fmt, ...) +{ +} +#endif + +} + + +#endif + + diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp new file mode 100644 index 000000000..d720693ac --- /dev/null +++ b/src/libavoid/geometry.cpp @@ -0,0 +1,260 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * -------------------------------------------------------------------- + * Much of the code in this module is based on code published with + * and/or described in "Computational Geometry in C" (Second Edition), + * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu> + * -------------------------------------------------------------------- + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/graph.h" +#include "libavoid/polyutil.h" + +#include <math.h> + +namespace Avoid { + + +// Returns true iff the point c lies on the closed segment ab. +// +// Based on the code of 'Between'. +// +static const bool inBetween(const Point& a, const Point& b, const Point& c) +{ + // We only call this when we know the points are collinear, + // otherwise we should be checking this here. + assert(vecDir(a, b, c) == 0); + + if (a.x != b.x) + { + // not vertical + return (((a.x < c.x) && (c.x < b.x)) || + ((b.x < c.x) && (c.x < a.x))); + } + else + { + return (((a.y < c.y) && (c.y < b.y)) || + ((b.y < c.y) && (c.y < a.y))); + } +} + + +// Returns true if the segment cd intersects the segment ab, blocking +// visibility. +// +// Based on the code of 'IntersectProp' and 'Intersect'. +// +bool segmentIntersect(const Point& a, const Point& b, const Point& c, + const Point& d) +{ + int ab_c = vecDir(a, b, c); + if ((ab_c == 0) && inBetween(a, b, c)) + { + return true; + } + + int ab_d = vecDir(a, b, d); + if ((ab_d == 0) && inBetween(a, b, d)) + { + return true; + } + + // It's ok for either of the points a or b to be on the line cd, + // so we don't have to check the other two cases. + + int cd_a = vecDir(c, d, a); + int cd_b = vecDir(c, d, b); + + // Is an intersection if a and b are on opposite sides of cd, + // and c and d are on opposite sides of the line ab. + // + // Note: this is safe even though the textbook warns about it + // since, unlike them, out vecDir is equivilent to 'AreaSign' + // rather than 'Area2'. + return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0)); +} + + +// Returns true iff the point p in a valid region that can contain +// shortest paths. a0, a1, a2 are ordered vertices of a shape. +// This function may seem 'backwards' to the user due to some of +// the code being reversed due to screen cooridinated being the +// opposite of graph paper coords. +// TODO: Rewrite this after checking whether it works for Inkscape. +// +// Based on the code of 'InCone'. +// +bool inValidRegion(const Point& a0, const Point& a1, const Point& a2, + const Point& b) +{ + int rSide = vecDir(b, a0, a1); + int sSide = vecDir(b, a1, a2); + + bool rOutOn = (rSide >= 0); + bool sOutOn = (sSide >= 0); + + bool rOut = (rSide > 0); + bool sOut = (sSide > 0); + + if (vecDir(a0, a1, a2) > 0) + { + // Concave at a1: + // + // !rO rO + // !sO !sO + // + // +---s--- + // | + // !rO r rO + // sO | sO + // + // + return (IgnoreRegions ? false : (rOutOn && sOutOn)); + } + else + { + // Convex at a1: + // + // !rO rO + // sO sO + // + // ---s---+ + // | + // !rO r rO + // !sO | !sO + // + // + if (IgnoreRegions) + { + return (rOutOn && !sOut) || (!rOut && sOutOn); + } + return (rOutOn || sOutOn); + } +} + + +// Returns the distance between points a and b. +// +double dist(const Point& a, const Point& b) +{ + double xdiff = a.x - b.x; + double ydiff = a.y - b.y; + + return sqrt((xdiff * xdiff) + (ydiff * ydiff)); +} + + +// Returns true iff the point q is inside (or on the edge of) the +// polygon argpoly. +// +// Based on the code of 'InPoly'. +// +bool inPoly(const Polygn& argpoly, const Point& q) +{ + // Numbers of right and left edge/ray crossings. + int Rcross = 0; + int Lcross = 0; + + // Copy the argument polygon + Polygn poly = copyPoly(argpoly); + Point *P = poly.ps; + int n = poly.pn; + + // Shift so that q is the origin. This is done for pedogical clarity. + for (int i = 0; i < n; ++i) + { + P[i].x = P[i].x - q.x; + P[i].y = P[i].y - q.y; + } + + // For each edge e=(i-1,i), see if crosses ray. + for (int i = 0; i < n; ++i) + { + // First see if q=(0,0) is a vertex. + if ((P[i].x == 0) && (P[i].y == 0)) + { + // We count a vertex as inside. + freePoly(poly); + return true; + } + + // point index; i1 = i-1 mod n + int i1 = ( i + n - 1 ) % n; + + // if e "straddles" the x-axis... + // The commented-out statement is logically equivalent to the one + // following. + // if( ((P[i].y > 0) && (P[i1].y <= 0)) || + // ((P[i1].y > 0) && (P[i].y <= 0)) ) + + if ((P[i].y > 0) != (P[i1].y > 0)) + { + // e straddles ray, so compute intersection with ray. + double x = (P[i].x * P[i1].y - P[i1].x * P[i].y) + / (P[i1].y - P[i].y); + + // crosses ray if strictly positive intersection. + if (x > 0) + { + Rcross++; + } + } + + // if e straddles the x-axis when reversed... + // if( ((P[i].y < 0) && (P[i1].y >= 0)) || + // ((P[i1].y < 0) && (P[i].y >= 0)) ) + + if ((P[i].y < 0) != (P[i1].y < 0)) + { + // e straddles ray, so compute intersection with ray. + double x = (P[i].x * P[i1].y - P[i1].x * P[i].y) + / (P[i1].y - P[i].y); + + // crosses ray if strictly positive intersection. + if (x < 0) + { + Lcross++; + } + } + } + freePoly(poly); + + // q on the edge if left and right cross are not the same parity. + if ( (Rcross % 2) != (Lcross % 2) ) + { + // We count the edge as inside. + return true; + } + + // Inside iff an odd number of crossings. + if ((Rcross % 2) == 1) + { + return true; + } + + // Outside. + return false; +} + + +} + diff --git a/src/libavoid/geometry.h b/src/libavoid/geometry.h new file mode 100644 index 000000000..500da6273 --- /dev/null +++ b/src/libavoid/geometry.h @@ -0,0 +1,75 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * -------------------------------------------------------------------- + * Much of the code in this module is based on code published with + * and/or described in "Computational Geometry in C" (Second Edition), + * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu> + * -------------------------------------------------------------------- + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#ifndef _GEOMETRY_H +#define _GEOMETRY_H + +#include "libavoid/geomtypes.h" + +namespace Avoid { + + +extern double dist(const Point& a, const Point& b); +extern bool segmentIntersect(const Point& a, const Point& b, + const Point& c, const Point& d); +extern bool inPoly(const Polygn& poly, const Point& q); +extern bool inValidRegion(const Point& a0, const Point& a1, const Point& a2, + const Point& b); + + +// Direction from vector. +// Looks at the position of point c from the directed segment ab and +// returns the following: +// 1 counterclockwise +// 0 collinear +// -1 clockwise +// +// Based on the code of 'AreaSign'. +// +static inline int vecDir(const Point& a, const Point& b, const Point& c) +{ + double area2 = ((b.x - a.x) * (c.y - a.y)) - + ((c.x - a.x) * (b.y - a.y)); + + if (area2 < -0.001) + { + return -1; + } + else if (area2 > 0.001) + { + return 1; + } + return 0; +} + + +} + + +#endif diff --git a/src/libavoid/geomtypes.h b/src/libavoid/geomtypes.h new file mode 100644 index 000000000..9b682759a --- /dev/null +++ b/src/libavoid/geomtypes.h @@ -0,0 +1,61 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#ifndef AVOID_GEOMTYPES_H +#define AVOID_GEOMTYPES_H + + +namespace Avoid +{ + + +typedef struct +{ + double x; + double y; +} Point; + + +typedef Point Vector; + + +typedef struct +{ + int id; + Point *ps; + int pn; +} Polygn; + +typedef Polygn PolyLine; + + +typedef struct +{ + Point a; + Point b; +} Edge; + + +} + +#endif diff --git a/src/libavoid/graph.cpp b/src/libavoid/graph.cpp new file mode 100644 index 000000000..9b1d602be --- /dev/null +++ b/src/libavoid/graph.cpp @@ -0,0 +1,986 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/debug.h" +#include "libavoid/graph.h" +#include "libavoid/connector.h" +#include "libavoid/polyutil.h" +#include "libavoid/timer.h" + +#include <math.h> + +namespace Avoid { + + +static int st_checked_edges = 0; + +EdgeList visGraph; +EdgeList invisGraph; + + +EdgeInf::EdgeInf(VertInf *v1, VertInf *v2) + : lstPrev(NULL) + , lstNext(NULL) + , _added(false) + , _visible(false) + , _v1(v1) + , _v2(v2) + , _dist(-1) +{ + _blockers.clear(); + _conns.clear(); +} + + +EdgeInf::~EdgeInf() +{ + if (_added) + { + makeInactive(); + } +} + + +void EdgeInf::makeActive(void) +{ + assert(_added == false); + + if (_visible) + { + visGraph.addEdge(this); + _pos1 = _v1->visList.insert(_v1->visList.begin(), this); + _v1->visListSize++; + _pos2 = _v2->visList.insert(_v2->visList.begin(), this); + _v2->visListSize++; + } + else // if (invisible) + { + invisGraph.addEdge(this); + _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this); + _v1->invisListSize++; + _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this); + _v2->invisListSize++; + } + _added = true; +} + + +void EdgeInf::makeInactive(void) +{ + assert(_added == true); + + if (_visible) + { + visGraph.removeEdge(this); + _v1->visList.erase(_pos1); + _v1->visListSize--; + _v2->visList.erase(_pos2); + _v2->visListSize--; + } + else // if (invisible) + { + invisGraph.removeEdge(this); + _v1->invisList.erase(_pos1); + _v1->invisListSize--; + _v2->invisList.erase(_pos2); + _v2->invisListSize--; + } + _blockers.clear(); + _conns.clear(); + _added = false; +} + + +double EdgeInf::getDist(void) +{ + return _dist; +} + + +void EdgeInf::setDist(double dist) +{ + //assert(dist != 0); + + if (_added && !_visible) + { + makeInactive(); + } + if (!_added) + { + _visible = true; + makeActive(); + } + _dist = dist; + _blockers.clear(); +} + + +void EdgeInf::alertConns(void) +{ + for (FlagList::iterator i = _conns.begin(); i != _conns.end(); ++i) + { + *(*i) = true; + } + _conns.clear(); +} + + +void EdgeInf::addConn(bool *flag) +{ + _conns.push_back(flag); +} + + +void EdgeInf::addCycleBlocker(void) +{ + // Needs to be in invisibility graph. + addBlocker(-1); +} + + +void EdgeInf::addBlocker(int b) +{ + assert(InvisibilityGrph); + + if (_added && _visible) + { + makeInactive(); + } + if (!_added) + { + _visible = false; + makeActive(); + } + _dist = 0; + _blockers.clear(); + _blockers.push_back(b); +} + + +bool EdgeInf::hasBlocker(int b) +{ + assert(InvisibilityGrph); + + ShapeList::iterator finish = _blockers.end(); + for (ShapeList::iterator it = _blockers.begin(); it != finish; ++it) + { + if ((*it) == -1) + { + alertConns(); + return true; + } + else if ((*it) == b) + { + return true; + } + } + return false; +} + + +pair<VertID, VertID> EdgeInf::ids(void) +{ + return std::make_pair(_v1->id, _v2->id); +} + + +pair<Point, Point> EdgeInf::points(void) +{ + return std::make_pair(_v1->point, _v2->point); +} + + +void EdgeInf::db_print(void) +{ + db_printf("Edge("); + _v1->id.db_print(); + db_printf(","); + _v2->id.db_print(); + db_printf(")\n"); +} + + +void EdgeInf::checkVis(void) +{ + if (_added && !_visible) + { + db_printf("\tChecking visibility for existing invisibility edge..." + "\n\t\t"); + db_print(); + } + else if (_added && _visible) + { + db_printf("\tChecking visibility for existing visibility edge..." + "\n\t\t"); + db_print(); + } + + int blocker = 0; + bool cone1 = true; + bool cone2 = true; + + VertInf *i = _v1; + VertInf *j = _v2; + const VertID& iID = i->id; + const VertID& jID = j->id; + const Point& iPoint = i->point; + const Point& jPoint = j->point; + + st_checked_edges++; + + if (iID.isShape) + { + cone1 = inValidRegion(i->shPrev->point, iPoint, i->shNext->point, + jPoint); + } + else + { + ShapeSet& ss = contains[iID]; + + if ((jID.isShape) && (ss.find(jID.objID) != ss.end())) + { + db_printf("1: Edge of bounding shape\n"); + // Don't even check this edge, it should be zero, + // since a point in a shape can't see it's corners + cone1 = false; + } + } + + if (cone1) + { + // If outside the first cone, don't even bother checking. + if (jID.isShape) + { + cone2 = inValidRegion(j->shPrev->point, jPoint, j->shNext->point, + iPoint); + } + else + { + ShapeSet& ss = contains[jID]; + + if ((iID.isShape) && (ss.find(iID.objID) != ss.end())) + { + db_printf("2: Edge of bounding shape\n"); + // Don't even check this edge, it should be zero, + // since a point in a shape can't see it's corners + cone2 = false; + } + } + } + + if (cone1 && cone2 && ((blocker = firstBlocker()) == 0)) + { + + // if i and j see each other, add edge + db_printf("\tSetting visibility edge... \n\t\t"); + db_print(); + + double d = dist(iPoint, jPoint); + + setDist(d); + + } + else if (InvisibilityGrph) + { +#if 0 + db_printf("%d, %d, %d\n", cone1, cone2, blocker); + db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x, + (int) iInfo.point.y, (int) jInfo.point.x, + (int) jInfo.point.y); +#endif + + // if i and j can't see each other, add blank edge + db_printf("\tSetting invisibility edge... \n\t\t"); + db_print(); + addBlocker(blocker); + } +} + + +int EdgeInf::firstBlocker(void) +{ + ShapeSet ss = ShapeSet(); + + Point& pti = _v1->point; + Point& ptj = _v2->point; + VertID& iID = _v1->id; + VertID& jID = _v2->id; + + if (!(iID.isShape)) + { + ss.insert(contains[iID].begin(), contains[iID].end()); + } + if (!(jID.isShape)) + { + ss.insert(contains[jID].begin(), contains[jID].end()); + } + + VertInf *last = vertices.end(); + for (VertInf *k = vertices.shapesBegin(); k != last; ) + { + VertID kID = k->id; + if ((ss.find(kID.objID) != ss.end())) + { + uint shapeID = kID.objID; + db_printf("Endpoint is inside shape %u so ignore shape edges.\n", + kID.objID); + // One of the endpoints is inside this shape so ignore it. + while ((k != last) && (k->id.objID == shapeID)) + { + // And skip the other vertices from this shape. + k = k->lstNext; + } + continue; + } + Point& kPoint = k->point; + Point& kPrevPoint = k->shPrev->point; + + if (segmentIntersect(pti, ptj, kPrevPoint, kPoint)) + { + ss.clear(); + return kID.objID; + } + k = k->lstNext; + } + ss.clear(); + return 0; +} + + +bool EdgeInf::isBetween(VertInf *i, VertInf *j) +{ + if ( ((i == _v1) && (j == _v2)) || + ((i == _v2) && (j == _v1)) ) + { + return true; + } + return false; +} + + +VertInf *EdgeInf::otherVert(VertInf *vert) +{ + assert((vert == _v1) || (vert == _v2)); + + if (vert == _v1) + { + return _v2; + } + return _v1; +} + + +EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew) +{ + EdgeInf *edge = NULL; + + if (knownNew) + { + assert(existingEdge(i, j) == NULL); + edge = new EdgeInf(i, j); + } + else + { + edge = existingEdge(i, j); + if (edge == NULL) + { + edge = new EdgeInf(i, j); + } + } + edge->checkVis(); + if (!(edge->_added) && !InvisibilityGrph) + { + delete edge; + edge = NULL; + } + + return edge; +} + + +EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j) +{ + VertInf *selected = NULL; + + if (i->visListSize <= j->visListSize) + { + selected = i; + } + else + { + selected = j; + } + + EdgeInfList& visList = selected->visList; + EdgeInfList::iterator finish = visList.end(); + for (EdgeInfList::iterator edge = visList.begin(); edge != finish; + ++edge) + { + if ((*edge)->isBetween(i, j)) + { + return (*edge); + } + } + + if (i->invisListSize <= j->invisListSize) + { + selected = i; + } + else + { + selected = j; + } + + EdgeInfList& invisList = selected->invisList; + finish = invisList.end(); + for (EdgeInfList::iterator edge = invisList.begin(); edge != finish; + ++edge) + { + if ((*edge)->isBetween(i, j)) + { + return (*edge); + } + } + + return NULL; +} + + +//=========================================================================== + + +EdgeList::EdgeList() + : _firstEdge(NULL) + , _lastEdge(NULL) + , _count(0) +{ +} + + +void EdgeList::addEdge(EdgeInf *edge) +{ + if (_firstEdge == NULL) + { + assert(_lastEdge == NULL); + + _lastEdge = edge; + _firstEdge = edge; + + edge->lstPrev = NULL; + edge->lstNext = NULL; + } + else + { + assert(_lastEdge != NULL); + + _lastEdge->lstNext = edge; + edge->lstPrev = _lastEdge; + + _lastEdge = edge; + + edge->lstNext = NULL; + } + _count++; +} + + +void EdgeList::removeEdge(EdgeInf *edge) +{ + if (edge->lstPrev) + { + edge->lstPrev->lstNext = edge->lstNext; + } + if (edge->lstNext) + { + edge->lstNext->lstPrev = edge->lstPrev; + } + if (edge == _lastEdge) + { + _lastEdge = edge->lstPrev; + if (edge == _firstEdge) + { + _firstEdge = NULL; + } + } + else if (edge == _firstEdge) + { + _firstEdge = edge->lstNext; + } + + + edge->lstPrev = NULL; + edge->lstNext = NULL; + + _count--; +} + + +EdgeInf *EdgeList::begin(void) +{ + return _firstEdge; +} + + +EdgeInf *EdgeList::end(void) +{ + return NULL; +} + + +// General visibility graph utility functions + + +void newBlockingShape(Polygn *poly, int pid) +{ + // o Check all visibility edges to see if this one shape + // blocks them. + EdgeInf *finish = visGraph.end(); + for (EdgeInf *iter = visGraph.begin(); iter != finish ; ) + { + EdgeInf *tmp = iter; + iter = iter->lstNext; + + if (tmp->getDist() != 0) + { + pair<VertID, VertID> ids(tmp->ids()); + VertID eID1 = ids.first; + VertID eID2 = ids.second; + pair<Point, Point> points(tmp->points()); + Point e1 = points.first; + Point e2 = points.second; + bool blocked = false; + + bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false; + bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false; + if (ep_in_poly1 || ep_in_poly2) + { + // Don't check edges that have a connector endpoint + // and are inside the shape being added. + continue; + } + + for (int pt_i = 0; pt_i < poly->pn; pt_i++) + { + int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1; + if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n])) + { + blocked = true; + break; + } + } + if (blocked) + { + db_printf("\tRemoving newly blocked edge (by shape %3d)" + "... \n\t\t", pid); + tmp->alertConns(); + tmp->db_print(); + if (InvisibilityGrph) + { + tmp->addBlocker(pid); + } + else + { + delete tmp; + } + } + } + } +} + + +void checkAllBlockedEdges(int pid) +{ + assert(InvisibilityGrph); + + for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; ) + { + EdgeInf *tmp = iter; + iter = iter->lstNext; + + if (tmp->hasBlocker(pid)) + { + tmp->checkVis(); + } + } +} + + +void checkAllMissingEdges(void) +{ + assert(!InvisibilityGrph); + + VertInf *first = NULL; + + if (IncludeEndpoints) + { + first = vertices.connsBegin(); + } + else + { + first = vertices.shapesBegin(); + } + + VertInf *pend = vertices.end(); + for (VertInf *i = first; i != pend; i = i->lstNext) + { + VertID iID = i->id; + + // Check remaining, earlier vertices + for (VertInf *j = first ; j != i; j = j->lstNext) + { + VertID jID = j->id; + if (!(iID.isShape) && (iID.objID != jID.objID)) + { + // Don't keep visibility between edges of different conns + continue; + } + + // See if the edge is already there? + bool found = (EdgeInf::existingEdge(i, j) != NULL); + + if (!found) + { + // Didn't already exist, check. + bool knownNew = true; + EdgeInf::checkEdgeVisibility(i, j, knownNew); + } + } + } +} + + +void generateContains(VertInf *pt) +{ + contains[pt->id].clear(); + + ShapeRefList::iterator finish = shapeRefs.end(); + for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i) + { + Polygn poly = copyPoly(*i); + if (inPoly(poly, pt->point)) + { + contains[pt->id].insert((*i)->id()); + } + freePoly(poly); + } +} + + +void adjustContainsWithAdd(const Polygn& poly, const int p_shape) +{ + for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); + k = k->lstNext) + { + if (inPoly(poly, k->point)) + { + contains[k->id].insert(p_shape); + } + } +} + + +void adjustContainsWithDel(const int p_shape) +{ + for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); + k = k->lstNext) + { + contains[k->id].erase(p_shape); + } +} + + +// Maybe this one should be in with the connector stuff, but it may later +// need to operate on a particular section of the visibility graph so it +// may have to stay here. +// +#define MIN(a, b) (((a) <= (b)) ? (a) : (b)) +#define MAX(a, b) (((a) >= (b)) ? (a) : (b)) + +#ifdef SELECTIVE_DEBUG +static double AngleAFromThreeSides(const double a, const double b, + const double c) +{ + // returns angle A, the angle opposite from side a, in radians + return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c)); +} +#endif + +void markConnectors(ShapeRef *shape) +{ + assert(SelectiveReroute); + + ConnRefList::iterator end = connRefs.end(); + for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it) + { + ConnRef *conn = (*it); + + if (conn->_route.pn == 0) + { + // Ignore uninitialised connectors. + continue; + } + + Point start = conn->_route.ps[0]; + Point end = conn->_route.ps[conn->_route.pn - 1]; + + double conndist = conn->_route_dist; + + double estdist; + double e1, e2; + + VertInf *beginV = shape->firstVert(); + VertInf *endV = shape->lastVert()->lstNext; + for (VertInf *i = beginV; i != endV; i = i->lstNext) + { + const Point& p1 = i->point; + const Point& p2 = i->shNext->point; + + double offy; + double a; + double b; + double c; + double d; + + double min; + double max; + + if (p1.y == p2.y) + { + // Standard case + offy = p1.y; + a = start.x; + b = start.y - offy; + c = end.x; + d = end.y - offy; + + min = MIN(p1.x, p2.x); + max = MAX(p1.x, p2.x); + } + else if (p1.x == p2.x) + { + // Other Standard case + offy = p1.x; + a = start.y; + b = start.x - offy; + c = end.y; + d = end.x - offy; + + min = MIN(p1.y, p2.y); + max = MAX(p1.y, p2.y); + } + else + { + // Need to do rotation + Point n_p2 = { p2.x - p1.x, p2.y - p1.y }; + Point n_start = { start.x - p1.x, start.y - p1.y }; + Point n_end = { end.x - p1.x, end.y - p1.y }; + //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y); + //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y); + //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y); + + double theta = 0 - atan2(n_p2.y, n_p2.x); + //printf("theta = %.2f\n", theta * (180 / PI)); + + Point r_p1 = {0, 0}; + Point r_p2 = n_p2; + start = n_start; + end = n_end; + + double cosv = cos(theta); + double sinv = sin(theta); + + r_p2.x = cosv * n_p2.x - sinv * n_p2.y; + r_p2.y = cosv * n_p2.y + sinv * n_p2.x; + start.x = cosv * n_start.x - sinv * n_start.y; + start.y = cosv * n_start.y + sinv * n_start.x; + end.x = cosv * n_end.x - sinv * n_end.y; + end.y = cosv * n_end.y + sinv * n_end.x; + //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y); + //printf("r_start: (%.1f, %.1f)\n", start.x, start.y); + //printf("r_end: (%.1f, %.1f)\n", end.x, end.y); + + if (((int) r_p2.y) != 0) + { + printf("r_p2.y: %f != 0\n", r_p2.y); + abort(); + } + // This might be slightly off. + r_p2.y = 0; + + offy = r_p1.y; + a = start.x; + b = start.y - offy; + c = end.x; + d = end.y - offy; + + min = MIN(r_p1.x, r_p2.x); + max = MAX(r_p1.x, r_p2.x); + + } + + double x; + if ((b + d) == 0) + { + db_printf("WARNING: (b + d) == 0\n"); + d = d * -1; + } + + if ((b == 0) && (d == 0)) + { + db_printf("WARNING: b == d == 0\n"); + if (((a < min) && (c < min)) || + ((a > max) && (c > max))) + { + // It's going to get adjusted. + x = a; + } + else + { + continue; + } + } + else + { + x = ((b*c) + (a*d)) / (b + d); + } + + //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d); + //printf("x = %.1f\n", x); + + // XXX: Use MAX and MIN + x = (x < min) ? min : x; + x = (x > max) ? max : x; + + //printf("x = %.1f\n", x); + + Point xp; + if (p1.x == p2.x) + { + xp.x = offy; + xp.y = x; + } + else + { + xp.x = x; + xp.y = offy; + } + //printf("(%.1f, %.1f)\n", xp.x, xp.y); + + e1 = dist(start, xp); + e2 = dist(xp, end); + estdist = e1 + e2; + + + //printf("is %.1f < %.1f\n", estdist, conndist); + if (estdist < conndist) + { +#ifdef SELECTIVE_DEBUG + //double angle = AngleAFromThreeSides(dist(start, end), + // e1, e2); + printf("[%3d] - Possible better path found (%.1f < %.1f)\n", + conn->_id, estdist, conndist); +#endif + conn->_needs_reroute_flag = true; + break; + } + + } + } +} + + +void printInfo(void) +{ + FILE *fp = stdout; + fprintf(fp, "\nVisibility Graph info:\n"); + fprintf(fp, "----------------------\n"); + + uint currshape = 0; + int st_shapes = 0; + int st_vertices = 0; + int st_endpoints = 0; + int st_valid_shape_visedges = 0; + int st_valid_endpt_visedges = 0; + int st_invalid_visedges = 0; + VertInf *finish = vertices.end(); + for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext) + { + VertID pID = t->id; + + if ((pID.isShape) && (pID.objID != currshape)) + { + currshape = pID.objID; + st_shapes++; + } + if (pID.isShape) + { + st_vertices++; + } + else + { + // The shape 0 ones are temporary and not considered. + st_endpoints++; + } + } + for (EdgeInf *t = visGraph.begin(); t != visGraph.end(); + t = t->lstNext) + { + std::pair<VertID, VertID> idpair = t->ids(); + + if (!(idpair.first.isShape) || !(idpair.second.isShape)) + { + st_valid_endpt_visedges++; + } + else + { + st_valid_shape_visedges++; + } + } + for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end(); + t = t->lstNext) + { + st_invalid_visedges++; + } + fprintf(fp, "Number of shapes: %d\n", st_shapes); + fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n", + st_vertices + st_endpoints, st_vertices, st_endpoints); + fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], " + "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges + + st_valid_endpt_visedges, st_valid_shape_visedges + + st_valid_endpt_visedges, st_valid_shape_visedges, + st_valid_endpt_visedges, st_invalid_visedges); + fprintf(fp, "----------------------\n"); + fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges); + fprintf(fp, "----------------------\n"); + + fprintf(fp, "ADDS: "); timers.Print(tmAdd); + fprintf(fp, "DELS: "); timers.Print(tmDel); + fprintf(fp, "MOVS: "); timers.Print(tmMov); + fprintf(fp, "***S: "); timers.Print(tmSev); + fprintf(fp, "PTHS: "); timers.Print(tmPth); + fprintf(fp, "\n"); +} + + +} + + diff --git a/src/libavoid/graph.h b/src/libavoid/graph.h new file mode 100644 index 000000000..d30f394cf --- /dev/null +++ b/src/libavoid/graph.h @@ -0,0 +1,127 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_GRAPH_H +#define AVOID_GRAPH_H + + +#include <cassert> +#include <list> +#include <utility> +using std::pair; + +#include "libavoid/vertices.h" + + +namespace Avoid { + + +extern bool UseAStarSearch; +extern bool IgnoreRegions; +extern bool SelectiveReroute; +extern bool IncludeEndpoints; +extern bool UseLeesAlgorithm; +extern bool InvisibilityGrph; +extern bool PartialFeedback; + + +typedef std::list<int> ShapeList; +typedef std::list<bool *> FlagList; + + +class EdgeInf +{ + public: + EdgeInf(VertInf *v1, VertInf *v2); + ~EdgeInf(); + double getDist(void); + void setDist(double dist); + void alertConns(void); + void addConn(bool *flag); + void addCycleBlocker(void); + void addBlocker(int b); + bool hasBlocker(int b); + pair<VertID, VertID> ids(void); + pair<Point, Point> points(void); + void db_print(void); + void checkVis(void); + VertInf *otherVert(VertInf *vert); + static EdgeInf *checkEdgeVisibility(VertInf *i, VertInf *j, + bool knownNew = false); + static EdgeInf *existingEdge(VertInf *i, VertInf *j); + + EdgeInf *lstPrev; + EdgeInf *lstNext; + private: + bool _added; + bool _visible; + VertInf *_v1; + VertInf *_v2; + EdgeInfList::iterator _pos1; + EdgeInfList::iterator _pos2; + ShapeList _blockers; + FlagList _conns; + double _dist; + + void makeActive(void); + void makeInactive(void); + int firstBlocker(void); + bool isBetween(VertInf *i, VertInf *j); +}; + + +class EdgeList +{ + public: + EdgeList(); + void addEdge(EdgeInf *edge); + void removeEdge(EdgeInf *edge); + EdgeInf *begin(void); + EdgeInf *end(void); + private: + EdgeInf *_firstEdge; + EdgeInf *_lastEdge; + unsigned int _count; +}; + + +extern EdgeList visGraph; +extern EdgeList invisGraph; + +class ShapeRef; + +extern void newBlockingShape(Polygn *poly, int pid); +extern void checkAllBlockedEdges(int pid); +extern void checkAllMissingEdges(void); +extern void generateContains(VertInf *pt); +extern void adjustContainsWithAdd(const Polygn& poly, const int p_shape); +extern void adjustContainsWithDel(const int p_shape); +extern void markConnectors(ShapeRef *shape); +extern void printInfo(void); + + +} + + +#endif + + diff --git a/src/libavoid/incremental.cpp b/src/libavoid/incremental.cpp new file mode 100644 index 000000000..3830c70ee --- /dev/null +++ b/src/libavoid/incremental.cpp @@ -0,0 +1,139 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/connector.h" +#include "libavoid/graph.h" +#include "libavoid/visibility.h" + +namespace Avoid { + + +void addShape(ShapeRef *shape) +{ + uint pid = shape->id(); + Polygn poly = shape->poly(); + + adjustContainsWithAdd(poly, pid); + + // o Check all visibility edges to see if this one shape + // blocks them. + newBlockingShape(&poly, pid); + + // o Calculate visibility for the new vertices. + if (UseLeesAlgorithm) + { + shapeVisSweep(shape); + } + else + { + shapeVis(shape); + } + callbackAllInvalidConnectors(); +} + + +void delShape(ShapeRef *shape) +{ + uint pid = shape->id(); + + // o Remove entries related to this shape's vertices + shape->removeFromGraph(); + + if (SelectiveReroute) + { + markConnectors(shape); + } + + adjustContainsWithDel(pid); + + delete shape; + + // o Check all edges that were blocked by this shape. + if (InvisibilityGrph) + { + checkAllBlockedEdges(pid); + } + else + { + // check all edges not in graph + checkAllMissingEdges(); + } + callbackAllInvalidConnectors(); +} + + +ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly) +{ + uint pid = oldShape->id(); + + // o Remove entries related to this shape's vertices + oldShape->removeFromGraph(); + + if (SelectiveReroute && !(PartialFeedback && PartialTime)) + { + markConnectors(oldShape); + } + + adjustContainsWithDel(pid); + + delete oldShape; + oldShape = NULL; + + adjustContainsWithAdd(*newPoly, pid); + + // o Check all edges that were blocked by this shape. + if (InvisibilityGrph) + { + checkAllBlockedEdges(pid); + } + else + { + // check all edges not in graph + checkAllMissingEdges(); + } + + ShapeRef *newShape = new ShapeRef(pid, *newPoly); + + // o Check all visibility edges to see if this one shape + // blocks them. + if (!(PartialFeedback && PartialTime)) + { + newBlockingShape(newPoly, pid); + } + + // o Calculate visibility for the new vertices. + if (UseLeesAlgorithm) + { + shapeVisSweep(newShape); + } + else + { + shapeVis(newShape); + } + callbackAllInvalidConnectors(); + + return newShape; +} + + +} + diff --git a/src/libavoid/incremental.h b/src/libavoid/incremental.h new file mode 100644 index 000000000..50ef8f7dc --- /dev/null +++ b/src/libavoid/incremental.h @@ -0,0 +1,39 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#ifndef AVOID_INCREMENTAL_H +#define AVOID_INCREMENTAL_H + +#include "libavoid/shape.h" + + +namespace Avoid { + +extern void addShape(ShapeRef *shape); +extern void delShape(ShapeRef *shape); +extern ShapeRef *moveShape(ShapeRef *oldShape, Polygn *newPoly); + +} + + +#endif diff --git a/src/libavoid/libavoid.h b/src/libavoid/libavoid.h new file mode 100644 index 000000000..0b6c7a819 --- /dev/null +++ b/src/libavoid/libavoid.h @@ -0,0 +1,40 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_LIBAVOID_H +#define AVOID_LIBAVOID_H + +#include "libavoid/geomtypes.h" +#include "libavoid/polyutil.h" +#include "libavoid/connector.h" +#include "libavoid/graph.h" +#include "libavoid/debug.h" +#include "libavoid/timer.h" +#include "libavoid/makepath.h" +#include "libavoid/vertices.h" +#include "libavoid/visibility.h" +#include "libavoid/static.h" +#include "libavoid/incremental.h" + +#endif + + diff --git a/src/libavoid/makefile.in b/src/libavoid/makefile.in new file mode 100644 index 000000000..e651e0ef1 --- /dev/null +++ b/src/libavoid/makefile.in @@ -0,0 +1,17 @@ +# Convenience stub makefile to call the real Makefile. + +@SET_MAKE@ + +# Explicit so that it's the default rule. +all: + cd .. && $(MAKE) libavoid/all + +clean %.a %.o: + cd .. && $(MAKE) libavoid/$@ + +.PHONY: all clean + +OBJEXT = @OBJEXT@ + +.SUFFIXES: +.SUFFIXES: .a .$(OBJEXT) diff --git a/src/libavoid/makepath.cpp b/src/libavoid/makepath.cpp new file mode 100644 index 000000000..776ffd307 --- /dev/null +++ b/src/libavoid/makepath.cpp @@ -0,0 +1,462 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * -------------------------------------------------------------------- + * The dijkstraPath function is based on code published and described + * in "Algorithms in C" (Second Edition), 1990, by Robert Sedgewick. + * -------------------------------------------------------------------- + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/connector.h" +#include "libavoid/graph.h" +#include <vector> +#include <math.h> + +namespace Avoid { + + +double segmt_penalty = 0; +double angle_penalty = 0; + + +static double Dot(const Point& l, const Point& r) +{ + return (l.x * r.x) + (l.y * r.y); +} + +static double CrossLength(const Point& l, const Point& r) +{ + return (l.x * r.y) - (l.y * r.x); +} + + +// Return the angle between the two line segments made by the +// points p1--p2 and p2--p3. Return value is in radians. +// +static double angleBetween(const Point& p1, const Point& p2, const Point& p3) +{ + Point v1 = { p1.x - p2.x, p1.y - p2.y }; + Point v2 = { p3.x - p2.x, p3.y - p2.y }; + + return fabs(atan2(CrossLength(v1, v2), Dot(v1, v2))); +} + + +// Given the two points for a new segment of a path (inf2 & inf3) +// as well as the distance between these points (dist), as well as +// possibly the previous point (inf1) [from inf1--inf2], return a +// cost associated with this route. +// +double cost(const double dist, VertInf *inf1, + VertInf *inf2, VertInf *inf3) +{ + double result = dist; + + if (inf2->pathNext != NULL) + { + // This is not the first segment, so there is a bend + // between it and the last one in the existing path. + if ((angle_penalty > 0) || (segmt_penalty > 0)) + { + Point p1 = inf1->point; + Point p2 = inf2->point; + Point p3 = inf3->point; + + double rad = M_PI - angleBetween(p1, p2, p3); + + // Make `rad' between 0--10 then take its log so small + // angles are not penalised as much as large ones. + result += (angle_penalty * log((rad * 10 / M_PI) + 1)); + + // Don't penalise as an extra segment if there is no turn. + if (rad > 0.0005) + { + result += segmt_penalty; + } + } + + } + + return result; +} + + +// Returns the best path from src to tar using the cost function. +// +// The path is worked out via Dijkstra's algorithm, and is encoded via +// pathNext links in each of the VerInfs along the path. +// +// Based on the code of 'matrixpfs'. +// +static void dijkstraPath(VertInf *src, VertInf *tar) +{ + double unseen = (double) INT_MAX; + + // initialize arrays + VertInf *finish = vertices.end(); + for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext) + { + t->pathNext = NULL; + t->pathDist = -unseen; + } + + VertInf *min = src; + while (min != tar) + { + VertInf *k = min; + min = NULL; + + k->pathDist *= -1; + if (k->pathDist == unseen) + { + k->pathDist = 0; + } + + EdgeInfList& visList = k->visList; + EdgeInfList::iterator finish = visList.end(); + for (EdgeInfList::iterator edge = visList.begin(); edge != finish; + ++edge) + { + VertInf *t = (*edge)->otherVert(k); + VertID tID = t->id; + + // Only check shape verticies, or endpoints. + if ((t->pathDist < 0) && + ((tID.objID == src->id.objID) || tID.isShape)) + { + double kt_dist = (*edge)->getDist(); + double priority = k->pathDist + + cost(kt_dist, k->pathNext, k, t); + + if ((kt_dist != 0) && (t->pathDist < -priority)) + { + t->pathDist = -priority; + t->pathNext = k; + } + if ((min == NULL) || (t->pathDist > min->pathDist)) + { + min = t; + } + } + } + EdgeInfList& invisList = k->invisList; + finish = invisList.end(); + for (EdgeInfList::iterator edge = invisList.begin(); edge != finish; + ++edge) + { + VertInf *t = (*edge)->otherVert(k); + VertID tID = t->id; + + // Only check shape verticies, or endpoints. + if ((t->pathDist < 0) && + ((tID.objID == src->id.objID) || tID.isShape > 0)) + { + if ((min == NULL) || (t->pathDist > min->pathDist)) + { + min = t; + } + } + } + } +} + + +class ANode +{ + public: + VertInf* inf; + double g; // Gone + double h; // Heuristic + double f; // Formula f = g + h + VertInf *pp; + + ANode(VertInf *vinf) + : inf(vinf) + , g(0) + , h(0) + , f(0) + , pp(NULL) + { + } + ANode() + : inf(NULL) + , g(0) + , h(0) + , f(0) + , pp(NULL) + { + } +}; + +bool operator<(const ANode &a, const ANode &b) +{ + return a.f < b.f; +} + + +bool operator>(const ANode &a, const ANode &b) +{ + return a.f > b.f; +} + + +// Returns the best path from src to tar using the cost function. +// +// The path is worked out using the aStar algorithm, and is encoded via +// pathNext links in each of the VerInfs along the path. +// +// The aStar STL code is based on public domain code available on the +// internet. +// +static void aStarPath(VertInf *src, VertInf *tar) +{ + std::vector<ANode> PENDING; // STL Vectors chosen because of rapid + std::vector<ANode> DONE; // insertions/deletions at back, + ANode Node, BestNode; // Temporary Node and BestNode + bool bNodeFound = false; // Flag if node is found in container + + tar->pathNext = NULL; + + // Create the start node + Node = ANode(src); + Node.g = 0; + Node.h = dist(Node.inf->point, tar->point); + Node.f = Node.g + Node.h; + // Set a null parent, so cost function knows this is the first segment. + Node.pp = NULL; + + // Populate the PENDING container with the first location + PENDING.push_back(Node); + // Create a heap from PENDING for sorting + using std::make_heap; using std::push_heap; using std::pop_heap; + make_heap( PENDING.begin(), PENDING.end() ); + + while (!PENDING.empty()) + { + // Ascending sort based on overloaded operators below + sort_heap(PENDING.begin(), PENDING.end()); + + // Set the Node with lowest f value to BESTNODE + BestNode = PENDING.front(); + + // Pop off the heap. Actually this moves the + // far left value to the far right. The node + // is not actually removed since the pop is to + // the heap and not the container. + pop_heap(PENDING.begin(), PENDING.end()); + + + // Remove node from right (the value we pop_heap'd) + PENDING.pop_back(); + + // Push the BestNode onto DONE + BestNode.inf->pathNext = BestNode.pp; + DONE.push_back(BestNode); + +#if 0 + printf("Considering... "); + BestNode.ID->print(stdout); + printf(" - g: %3.1f h: %3.1f f: %3.1f back: ", BestNode.g, BestNode.h, + BestNode.f); + BestNode.pp.print(stdout); + printf("\n"); +#endif + + // If at destination, break and create path below + if (BestNode.inf == tar) + { + //bPathFound = true; // arrived at destination... + break; + } + + // Check adjacent points in graph + EdgeInfList& visList = BestNode.inf->visList; + EdgeInfList::iterator finish = visList.end(); + for (EdgeInfList::iterator edge = visList.begin(); edge != finish; + ++edge) + { + Node.inf = (*edge)->otherVert(BestNode.inf); + + // Only check shape verticies, or the tar endpoint. + if (!(Node.inf->id.isShape) && (Node.inf != tar)) + { + continue; + } + + double edgeDist = (*edge)->getDist(); + + if (edgeDist == 0) + { + continue; + } + + VertInf *prevInf = BestNode.inf->pathNext; + + Node.g = BestNode.g + cost(edgeDist, prevInf, + BestNode.inf, Node.inf); + + // Calculate the Heuristic. + Node.h = dist(Node.inf->point, tar->point); + + // The A* formula + Node.f = Node.g + Node.h; + // Point parent to last BestNode (pushed onto DONE) + Node.pp = BestNode.inf; + + bNodeFound = false; + + // Check to see if already on PENDING + for (unsigned int i = 0; i < PENDING.size(); i++) + { + if (Node.inf == PENDING.at(i).inf) + { // If already on PENDING + if (Node.g < PENDING.at(i).g) + { + PENDING.at(i).g = Node.g; + PENDING.at(i).f = Node.g + PENDING.at(i).h; + PENDING.at(i).pp = Node.pp; + } + bNodeFound = true; + break; + } + } + if (!bNodeFound ) // If Node NOT found on PENDING + { + // Check to see if already on DONE + for (unsigned int i = 0; i < DONE.size(); i++) + { + if (Node.inf == DONE.at(i).inf) + { + // If on DONE, Which has lower gone? + if (Node.g < DONE.at(i).g) + { + DONE.at(i).g = Node.g; + DONE.at(i).f = Node.g + DONE.at(i).h; + DONE.at(i).pp = Node.pp; + DONE.at(i).inf->pathNext = Node.pp; + } + bNodeFound = true; + break; + } + } + } + + if (!bNodeFound ) // If Node NOT found on PENDING or DONE + { + // Push NewNode onto PENDING + PENDING.push_back(Node); + // Push NewNode onto heap + push_heap( PENDING.begin(), PENDING.end() ); + // Re-Assert heap, or will be short by one + make_heap( PENDING.begin(), PENDING.end() ); + +#if 0 + // Display PENDING and DONE containers (For Debugging) + cout << "PENDING: "; + for (int i = 0; i < PENDING.size(); i++) + { + cout << PENDING.at(i).x << "," << PENDING.at(i).y << ","; + cout << PENDING.at(i).g << "," << PENDING.at(i).h << " "; + } + cout << endl; + cout << "DONE: "; + for (int i = 0; i < DONE.size(); i++) + { + cout << DONE.at(i).x << "," << DONE.at(i).y << ","; + cout << DONE.at(i).g << "," << DONE.at(i).h << " "; + } + cout << endl << endl; + int ch = _getch(); +#endif + } + } + } +} + + +// Returns the best path for the connector referred to by lineRef. +// +// The path encoded in the pathNext links in each of the VerInfs +// backwards along the path, from the tar back to the source. +// +void makePath(ConnRef *lineRef, bool *flag) +{ + VertInf *src = lineRef->src(); + VertInf *tar = lineRef->dst(); + + // TODO: Could be more efficient here. + EdgeInf *directEdge = EdgeInf::existingEdge(src, tar); + if (!IncludeEndpoints && directVis(src, tar)) + { + Point p = src->point; + Point q = tar->point; + + assert(directEdge == NULL); + + directEdge = new EdgeInf(src, tar); + tar->pathNext = src; + directEdge->setDist(dist(p, q)); + directEdge->addConn(flag); + + return; + } + else if (IncludeEndpoints && directEdge && (directEdge->getDist() > 0)) + { + tar->pathNext = src; + directEdge->addConn(flag); + } + else + { + // Mark the path endpoints as not being able to see + // each other. This is true if we are here. + if (!IncludeEndpoints && InvisibilityGrph) + { + directEdge->addBlocker(0); + } + + if (UseAStarSearch) + { + aStarPath(src, tar); + } + else + { + dijkstraPath(src, tar); + } + +#if 0 + PointMap::iterator t; + for (VertInf *t = vertices.connsBegin(); t != vertices.end(); + t = t->lstNext) + { + + t->id.print(); + printf(" -> "); + t->pathNext->id.print(); + printf("\n"); + } +#endif + } +} + + +} + + diff --git a/src/libavoid/makepath.h b/src/libavoid/makepath.h new file mode 100644 index 000000000..5ab21b993 --- /dev/null +++ b/src/libavoid/makepath.h @@ -0,0 +1,42 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_MAKEPATH_H +#define AVOID_MAKEPATH_H + +#include "libavoid/connector.h" + +namespace Avoid { + + +extern double segmt_penalty; +extern double angle_penalty; + +extern void makePath(ConnRef *lineRef, bool *flag); + + +} + + +#endif + + diff --git a/src/libavoid/polyutil.cpp b/src/libavoid/polyutil.cpp new file mode 100644 index 000000000..6ece50e63 --- /dev/null +++ b/src/libavoid/polyutil.cpp @@ -0,0 +1,86 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#include "libavoid/shape.h" + +namespace Avoid { + + +Polygn newPoly(int size) +{ + Polygn newpoly; + + newpoly.pn = size; + newpoly.ps = (Point *) calloc(size, sizeof(Point)); + if (!newpoly.ps) + { + fprintf(stderr, + "Error: Unable to allocate Point array in Avoid::newPoly\n"); + abort(); + } + return newpoly; +} + + +Polygn copyPoly(Polygn poly) +{ + Polygn newpoly = newPoly(poly.pn); + + newpoly.id = poly.id; + for (int i = 0; i < poly.pn; i++) + { + newpoly.ps[i] = poly.ps[i]; + } + return newpoly; +} + + +Polygn copyPoly(ShapeRef *shape) +{ + Polygn poly = shape->poly(); + Polygn newpoly = newPoly(poly.pn); + + newpoly.id = poly.id; + for (int i = 0; i < poly.pn; i++) + { + newpoly.ps[i] = poly.ps[i]; + } + return newpoly; +} + + +void freePoly(Polygn& poly) +{ + std::free(poly.ps); +} + + +void freePtrPoly(Polygn *poly) +{ + std::free(poly->ps); + std::free(poly); +} + + +} + diff --git a/src/libavoid/polyutil.h b/src/libavoid/polyutil.h new file mode 100644 index 000000000..456e190fb --- /dev/null +++ b/src/libavoid/polyutil.h @@ -0,0 +1,41 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/geometry.h" +#include "libavoid/shape.h" + +#ifndef AVOID_POLYUTIL_H +#define AVOID_POLYUTIL_H + +namespace Avoid { + + +extern Polygn newPoly(int size); +extern Polygn copyPoly(Polygn); +extern Polygn copyPoly(ShapeRef *shape); +extern void freePoly(Polygn&); +extern void freePtrPoly(Polygn *argpoly); + + +} + +#endif diff --git a/src/libavoid/shape.cpp b/src/libavoid/shape.cpp new file mode 100644 index 000000000..b08e75f3e --- /dev/null +++ b/src/libavoid/shape.cpp @@ -0,0 +1,176 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#include "libavoid/graph.h" // For alertConns +#include "libavoid/polyutil.h" + + +namespace Avoid { + + +ShapeRefList shapeRefs; + + +ShapeRef::ShapeRef(uint id, Polygn& ply) + : _id(id) + , _poly(copyPoly(ply)) + , _active(false) + , _firstVert(NULL) + , _lastVert(NULL) +{ + bool isShape = true; + VertID i = VertID(id, isShape, 0); + + VertInf *last = NULL; + VertInf *node = NULL; + for (int pt_i = 0; pt_i < _poly.pn; pt_i++) + { + node = new VertInf(i, _poly.ps[pt_i]); + + if (!_firstVert) + { + _firstVert = node; + } + else + { + node->shPrev = last; + last->shNext = node; + //node->lstPrev = last; + //last->lstNext = node; + } + vertices.addVertex(node); + + last = node; + i++; + // Increase total vertices count ++; + } + _lastVert = node; + + _lastVert->shNext = _firstVert; + _firstVert->shPrev = _lastVert; + + // Increase total shape count ++; + makeActive(); +} + + +ShapeRef::~ShapeRef() +{ + assert(_firstVert != NULL); + + VertInf *it = _firstVert; + do + { + VertInf *tmp = it; + it = it->shNext; + + // XXX: This could possibly be done less + // safely but faster, all at once. + vertices.removeVertex(tmp); + delete tmp; + } + while (it != _firstVert); + _firstVert = _lastVert = NULL; + + freePoly(_poly); + + makeInactive(); +} + + +void ShapeRef::makeActive(void) +{ + assert(!_active); + + // Add to connRefs list. + _pos = shapeRefs.insert(shapeRefs.begin(), this); + _active = true; +} + + +void ShapeRef::makeInactive(void) +{ + assert(_active); + + // Remove from connRefs list. + shapeRefs.erase(_pos); + _active = false; +} + + +VertInf *ShapeRef::firstVert(void) +{ + return _firstVert; +} + + +VertInf *ShapeRef::lastVert(void) +{ + return _lastVert; +} + + +uint ShapeRef::id(void) +{ + return _id; +} + + +Polygn ShapeRef::poly(void) +{ + return _poly; +} + + +void ShapeRef::removeFromGraph(void) +{ + for (VertInf *iter = firstVert(); iter != lastVert()->lstNext; ) + { + VertInf *tmp = iter; + iter = iter->lstNext; + + // For each vertex. + EdgeInfList& visList = tmp->visList; + EdgeInfList::iterator finish = visList.end(); + EdgeInfList::iterator edge; + while ((edge = visList.begin()) != finish) + { + // Remove each visibility edge + (*edge)->alertConns(); + delete (*edge); + } + + EdgeInfList& invisList = tmp->invisList; + finish = invisList.end(); + while ((edge = invisList.begin()) != finish) + { + // Remove each invisibility edge + delete (*edge); + } + } +} + + +} + + diff --git a/src/libavoid/shape.h b/src/libavoid/shape.h new file mode 100644 index 000000000..acdb36983 --- /dev/null +++ b/src/libavoid/shape.h @@ -0,0 +1,73 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_SHAPE_H +#define AVOID_SHAPE_H + +#include "libavoid/geometry.h" +#include <list> + + +namespace Avoid { + +typedef unsigned int uint; + +class ShapeRef; +class VertInf; + +typedef std::list<ShapeRef *> ShapeRefList; + + +class ShapeRef +{ + public: + ShapeRef(uint id, Polygn& poly); + ~ShapeRef(); + VertInf *firstVert(void); + VertInf *lastVert(void); + uint id(void); + Polygn poly(void); + + void makeActive(void); + void makeInactive(void); + + void removeFromGraph(void); + + private: + uint _id; + Polygn _poly; + bool _active; + ShapeRefList::iterator _pos; + VertInf *_firstVert; + VertInf *_lastVert; +}; + + +extern ShapeRefList shapeRefs; + + +} + + +#endif + + diff --git a/src/libavoid/static.cpp b/src/libavoid/static.cpp new file mode 100644 index 000000000..d424a2e7f --- /dev/null +++ b/src/libavoid/static.cpp @@ -0,0 +1,76 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cassert> +#include "libavoid/connector.h" +#include "libavoid/visibility.h" + +namespace Avoid { + + +// This should only be used for the static algorithm. +// +// XXX: If to set up the vis graph for incremental it would need +// the shapeRef ppinters in obs. +// +void CreateVisGraph(Polygn **obs, int n_obs) +{ + for (int poly_i = 0; poly_i < n_obs; poly_i++) + { + uint id = obs[poly_i]->id; + + new ShapeRef(id, *(obs[poly_i])); + } + computeCompleteVis(); +} + + +void DestroyVisGraph(void) +{ + ShapeRefList::iterator sFinish = shapeRefs.end(); + ShapeRefList::iterator sCurr; + + while ((sCurr = shapeRefs.begin()) != sFinish) + { + ShapeRef *shape = (*sCurr); + + shape->removeFromGraph(); + delete shape; + } + + ConnRefList::iterator cFinish = connRefs.end(); + ConnRefList::iterator cCurr; + + while ((cCurr = connRefs.begin())!= cFinish) + { + ConnRef *conn = (*cCurr); + + conn->removeFromGraph(); + conn->unInitialise(); + } + + assert(vertices.connsBegin() == NULL); +} + + +} + diff --git a/src/libavoid/static.h b/src/libavoid/static.h new file mode 100644 index 000000000..c02c6be2f --- /dev/null +++ b/src/libavoid/static.h @@ -0,0 +1,38 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#ifndef AVOID_STATIC_H +#define AVOID_STATIC_H + +#include "libavoid/geomtypes.h" + + +namespace Avoid { + +extern void CreateVisGraph(Polygn **obstacles, int n_obstacles); +extern void DestroyVisGraph(void); + +} + + +#endif diff --git a/src/libavoid/timer.cpp b/src/libavoid/timer.cpp new file mode 100644 index 000000000..7e930d011 --- /dev/null +++ b/src/libavoid/timer.cpp @@ -0,0 +1,168 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cstdio> +#include <cstdlib> +#include <cassert> +using std::abort; +#include <climits> + +#include "libavoid/timer.h" + +namespace Avoid { + + +Timer timers = Timer(); + + +Timer::Timer() +{ + Reset(); +} + + +void Timer::Reset(void) +{ + for (int i = 0; i < tmCount; i++) + { + //tTotal[i] = 0; + cTotal[i] = cPath[i] = 0; + cTally[i] = cPathTally[i] = 0; + cMax[i] = cPathMax[i] = 0; + } + running = false; + count = 0; + type = lasttype = tmNon; +} + + +void Timer::Register(const int t, const bool start) +{ + assert(t != tmNon); + + if (type == tmNon) + { + type = t; + } + else + { + type = tmSev; + } + + if (start) + { + Start(); + } +} + +void Timer::Start(void) +{ + if (running) + { + fprintf(stderr, "ERROR: Timer already running in Timer::Start()\n"); + abort(); + } + cStart[type] = clock(); // CPU time + running = true; +} + + +void Timer::Stop(void) +{ + if (!running) + { + fprintf(stderr, "ERROR: Timer not running in Timer::Stop()\n"); + abort(); + } + clock_t cStop = clock(); // CPU time + running = false; + + bigclock_t cDiff; + if (cStop < cStart[type]) + { + // Uh-oh, the clock value has wrapped around. + // + bigclock_t realStop = ((bigclock_t) cStop) + ULONG_MAX + 1; + cDiff = realStop - cStart[type]; + } + else + { + cDiff = cStop - cStart[type]; + } + + if (cDiff > LONG_MAX) + { + fprintf(stderr, "Error: cDiff overflow in Timer:Stop()\n"); + abort(); + } + + if (type == tmPth) + { + cPath[lasttype] += cDiff; + cPathTally[lasttype]++; + if (((clock_t) cDiff) > cPathMax[lasttype]) + { + cPathMax[lasttype] = (clock_t) cDiff; + } + } + else + { + cTotal[type] += cDiff; + cTally[type]++; + if (((clock_t) cDiff) > cMax[type]) + { + cMax[type] = (clock_t) cDiff; + } + lasttype = type; + } + + type = tmNon; +} + + +void Timer::PrintAll(void) +{ + for (int i = 0; i < tmCount; i++) + { + Print(i); + } +} + + +#define toMsec(tot) ((bigclock_t) ((tot) / (((double) CLOCKS_PER_SEC) / 1000))) +#define toAvg(tot, cnt) ((((cnt) > 0) ? ((long double) (tot)) / (cnt) : 0)) + +void Timer::Print(const int t) +{ + bigclock_t avg = toMsec(toAvg(cTotal[t], cTally[t])); + bigclock_t pind = toMsec(toAvg(cPath[t], cPathTally[t])); + bigclock_t pavg = toMsec(toAvg(cPath[t], cTally[t])); + double max = toMsec(cMax[t]); + double pmax = toMsec(cPathMax[t]); + printf("\t%lld %d %lld %.0f %lld %d %lld %.0f %lld\n", + cTotal[t], cTally[t], avg, max, + cPath[t], cPathTally[t], pavg, pmax, pind); +} + + +} + diff --git a/src/libavoid/timer.h b/src/libavoid/timer.h new file mode 100644 index 000000000..9446ecc51 --- /dev/null +++ b/src/libavoid/timer.h @@ -0,0 +1,92 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef PROFILE_H +#define PROFILE_H + +#include <ctime> + +namespace Avoid { + + +#ifdef NOTIMERS + + #define register_timer(t) do {} while(0) + #define regstart_timer(t) do {} while(0) + #define start_timer() do {} while(0) + #define stop_timer() do {} while(0) + +#else + + #define register_timer(t) timers.Register(t) + #define regstart_timer(t) timers.Register(t, timerStart) + #define start_timer() timers.Start() + #define stop_timer() timers.Stop() + +#endif + +typedef unsigned long long int bigclock_t; + +static const int tmCount = 5; + +static const int tmNon = -1; +static const int tmAdd = 0; +static const int tmDel = 1; +static const int tmMov = 2; +static const int tmPth = 3; +static const int tmSev = 4; + + +static const bool timerStart = true; +static const bool timerDelay = false; + + +class Timer +{ + public: + Timer(); + void Register(const int t, const bool start = timerDelay); + void Start(void); + void Stop(void); + void Reset(void); + void Print(const int t); + void PrintAll(void); + + private: + clock_t cStart[tmCount]; + bigclock_t cTotal[tmCount]; + bigclock_t cPath[tmCount]; + int cTally[tmCount]; + int cPathTally[tmCount]; + clock_t cMax[tmCount]; + clock_t cPathMax[tmCount]; + + bool running; + long count; + int type, lasttype; +}; + +extern Timer timers; + +} + +#endif diff --git a/src/libavoid/vertices.cpp b/src/libavoid/vertices.cpp new file mode 100644 index 000000000..7e74509f0 --- /dev/null +++ b/src/libavoid/vertices.cpp @@ -0,0 +1,438 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/geometry.h" +#include "libavoid/graph.h" // For alertConns +#include "libavoid/debug.h" + + + +namespace Avoid { + + +ContainsMap contains; + + +VertID::VertID() +{ +} + + +VertID::VertID(unsigned int id, bool s, int n) + : objID(id) + , isShape(s) + , vn(n) +{ +} + + +VertID::VertID(const VertID& other) + : objID(other.objID) + , isShape(other.isShape) + , vn(other.vn) +{ +} + + +VertID& VertID::operator= (const VertID& rhs) +{ + // Gracefully handle self assignment + //if (this == &rhs) return *this; + + objID = rhs.objID; + isShape = rhs.isShape; + vn = rhs.vn; + + return *this; +} + + +bool VertID::operator==(const VertID& rhs) const +{ + if ((objID != rhs.objID) || (vn != rhs.vn)) + { + return false; + } + assert(isShape == rhs.isShape); + return true; +} + + +bool VertID::operator!=(const VertID& rhs) const +{ + if ((objID != rhs.objID) || (vn != rhs.vn)) + { + return true; + } + assert(isShape == rhs.isShape); + return false; +} + + +bool VertID::operator<(const VertID& rhs) const +{ + if ((objID < rhs.objID) || + ((objID == rhs.objID) && (vn < rhs.vn))) + { + return true; + } + return false; +} + + +VertID VertID::operator+(const int& rhs) const +{ + return VertID(objID, isShape, vn + rhs); +} + + +VertID VertID::operator-(const int& rhs) const +{ + return VertID(objID, isShape, vn - rhs); +} + + +VertID& VertID::operator++(int) +{ + vn += 1; + return *this; +} + + +void VertID::print(FILE *file) const +{ + fprintf(file, "[%u,%d]", objID, vn); +} + + +void VertID::db_print(void) const +{ + db_printf("[%u,%d]", objID, vn); +} + + +const int VertID::src = 1; +const int VertID::tar = 2; + + +VertInf::VertInf(const VertID& vid, const Point& vpoint) + : id(vid) + , point(vpoint) + , lstPrev(NULL) + , lstNext(NULL) + , shPrev(NULL) + , shNext(NULL) + , visListSize(0) + , invisListSize(0) + , pathNext(NULL) + , pathDist(0) +{ +} + + +void VertInf::Reset(const Point& vpoint) +{ + point = vpoint; +} + + +void VertInf::removeFromGraph(const bool isConnVert) +{ + if (isConnVert) + { + assert(!(id.isShape)); + } + + VertInf *tmp = this; + + // For each vertex. + EdgeInfList& visList = tmp->visList; + EdgeInfList::iterator finish = visList.end(); + EdgeInfList::iterator edge; + while ((edge = visList.begin()) != finish) + { + // Remove each visibility edge + (*edge)->alertConns(); + delete (*edge); + } + + EdgeInfList& invisList = tmp->invisList; + finish = invisList.end(); + while ((edge = invisList.begin()) != finish) + { + // Remove each invisibility edge + delete (*edge); + } +} + + +bool directVis(VertInf *src, VertInf *dst) +{ + ShapeSet ss = ShapeSet(); + + Point& p = src->point; + Point& q = dst->point; + + VertID& pID = src->id; + VertID& qID = dst->id; + + if (!(pID.isShape)) + { + ss.insert(contains[pID].begin(), contains[pID].end()); + } + if (!(qID.isShape)) + { + ss.insert(contains[qID].begin(), contains[qID].end()); + } + + // The "beginning" should be the first shape vertex, rather + // than an endpoint, which are also stored in "vertices". + VertInf *endVert = vertices.end(); + for (VertInf *k = vertices.shapesBegin(); k != endVert; k = k->lstNext) + { + if ((ss.find(k->id.objID) == ss.end())) + { + if (segmentIntersect(p, q, k->point, k->shNext->point)) + { + return false; + } + } + } + return true; +} + + +VertInfList::VertInfList() + : _firstShapeVert(NULL) + , _firstConnVert(NULL) + , _lastShapeVert(NULL) + , _lastConnVert(NULL) + , _shapeVertices(0) + , _connVertices(0) +{ +} + + +#define checkVertInfListConditions() \ + do { \ + assert((!_firstConnVert && (_connVertices == 0)) || \ + ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \ + assert((!_firstShapeVert && (_shapeVertices == 0)) || \ + ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \ + assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \ + assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \ + assert((!_firstConnVert && !_lastConnVert) || \ + (_firstConnVert && _lastConnVert) ); \ + assert((!_firstShapeVert && !_lastShapeVert) || \ + (_firstShapeVert && _lastShapeVert) ); \ + assert(!_firstShapeVert || _firstShapeVert->id.isShape); \ + assert(!_lastShapeVert || _lastShapeVert->id.isShape); \ + assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \ + assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \ + } while(0) + + +void VertInfList::addVertex(VertInf *vert) +{ + checkVertInfListConditions(); + assert(vert->lstPrev == NULL); + assert(vert->lstNext == NULL); + + if (!(vert->id.isShape)) + { + // A Connector vertex + if (_firstConnVert) + { + // Join with previous front + vert->lstNext = _firstConnVert; + _firstConnVert->lstPrev = vert; + + // Make front + _firstConnVert = vert; + } + else + { + // Make front and back + _firstConnVert = vert; + _lastConnVert = vert; + + // Link to front of shapes list + vert->lstNext = _firstShapeVert; + } + _connVertices++; + } + else // if (vert->id.shape > 0) + { + // A Shape vertex + if (_lastShapeVert) + { + // Join with previous back + vert->lstPrev = _lastShapeVert; + _lastShapeVert->lstNext = vert; + + // Make back + _lastShapeVert = vert; + } + else + { + // Make first and last + _firstShapeVert = vert; + _lastShapeVert = vert; + + // Join with conns list + if (_lastConnVert) + { + assert (_lastConnVert->lstNext == NULL); + + _lastConnVert->lstNext = vert; + } + } + _shapeVertices++; + } + checkVertInfListConditions(); +} + + +void VertInfList::removeVertex(VertInf *vert) +{ + // Conditions for correct data structure + checkVertInfListConditions(); + + if (!(vert->id.isShape)) + { + // A Connector vertex + if (vert == _firstConnVert) + { + + if (vert == _lastConnVert) + { + _firstConnVert = NULL; + _lastConnVert = NULL; + } + else + { + // Set new first + _firstConnVert = _firstConnVert->lstNext; + + if (_firstConnVert) + { + // Set previous + _firstConnVert->lstPrev = NULL; + } + } + } + else if (vert == _lastConnVert) + { + // Set new last + _lastConnVert = _lastConnVert->lstPrev; + + // Make last point to shapes list + _lastConnVert->lstNext = _firstShapeVert; + } + else + { + vert->lstNext->lstPrev = vert->lstPrev; + vert->lstPrev->lstNext = vert->lstNext; + } + _connVertices--; + } + else // if (vert->id.shape > 0) + { + // A Shape vertex + if (vert == _lastShapeVert) + { + // Set new last + _lastShapeVert = _lastShapeVert->lstPrev; + + if (vert == _firstShapeVert) + { + _firstShapeVert = NULL; + if (_lastConnVert) + { + _lastConnVert->lstNext = NULL; + } + } + + if (_lastShapeVert) + { + _lastShapeVert->lstNext = NULL; + } + } + else if (vert == _firstShapeVert) + { + // Set new first + _firstShapeVert = _firstShapeVert->lstNext; + + // Correct the last conn vertex + if (_lastConnVert) + { + _lastConnVert->lstNext = _firstShapeVert; + } + + if (_firstShapeVert) + { + _firstShapeVert->lstPrev = NULL; + } + } + else + { + vert->lstNext->lstPrev = vert->lstPrev; + vert->lstPrev->lstNext = vert->lstNext; + } + _shapeVertices--; + } + vert->lstPrev = NULL; + vert->lstNext = NULL; + + checkVertInfListConditions(); +} + + +VertInf *VertInfList::shapesBegin(void) +{ + return _firstShapeVert; +} + + +VertInf *VertInfList::connsBegin(void) +{ + if (_firstConnVert) + { + return _firstConnVert; + } + // No connector vertices + return _firstShapeVert; +} + + +VertInf *VertInfList::end(void) +{ + return NULL; +} + + +VertInfList vertices; + + +} + + diff --git a/src/libavoid/vertices.h b/src/libavoid/vertices.h new file mode 100644 index 000000000..c2ff6977f --- /dev/null +++ b/src/libavoid/vertices.h @@ -0,0 +1,124 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_VERTICES_H +#define AVOID_VERTICES_H + +#include <list> +#include <set> +#include <map> +#include <iostream> +#include "libavoid/geomtypes.h" + +namespace Avoid { + +class EdgeInf; + +typedef std::list<EdgeInf *> EdgeInfList; + + +class VertID +{ + public: + unsigned int objID; + bool isShape; + int vn; + + static const int src; + static const int tar; + + VertID(); + VertID(unsigned int id, bool s, int n); + VertID(const VertID& other); + VertID& operator= (const VertID& rhs); + bool operator==(const VertID& rhs) const; + bool operator!=(const VertID& rhs) const; + bool operator<(const VertID& rhs) const; + VertID operator+(const int& rhs) const; + VertID operator-(const int& rhs) const; + VertID& operator++(int); + void print(FILE *file = stdout) const; + void db_print(void) const; +}; + + +class VertInf +{ + public: + VertInf(const VertID& vid, const Point& vpoint); + void Reset(const Point& vpoint); + void removeFromGraph(const bool isConnVert = true); + + VertID id; + Point point; + VertInf *lstPrev; + VertInf *lstNext; + VertInf *shPrev; + VertInf *shNext; + EdgeInfList visList; + unsigned int visListSize; + EdgeInfList invisList; + unsigned int invisListSize; + VertInf *pathNext; + double pathDist; +}; + + +bool directVis(VertInf *src, VertInf *dst); + + +class VertInfList +{ + public: + VertInfList(); + void addVertex(VertInf *vert); + void removeVertex(VertInf *vert); + VertInf *shapesBegin(void); + VertInf *connsBegin(void); + VertInf *end(void); + void stats(void) + { + printf("Conns %d, shapes %d\n", _connVertices, _shapeVertices); + } + private: + VertInf *_firstShapeVert; + VertInf *_firstConnVert; + VertInf *_lastShapeVert; + VertInf *_lastConnVert; + unsigned int _shapeVertices; + unsigned int _connVertices; +}; + + +typedef std::set<unsigned int> ShapeSet; +typedef std::map<VertID, ShapeSet> ContainsMap; + +extern ContainsMap contains; +extern VertInfList vertices; + + +} + + +#endif + + diff --git a/src/libavoid/visibility.cpp b/src/libavoid/visibility.cpp new file mode 100644 index 000000000..e13656f5f --- /dev/null +++ b/src/libavoid/visibility.cpp @@ -0,0 +1,653 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + + +#include <cfloat> + +#include "libavoid/shape.h" +#include "libavoid/debug.h" +#include "libavoid/visibility.h" +#include "libavoid/graph.h" + +#include <math.h> + +#ifdef LINEDEBUG + #include "SDL_gfxPrimitives.h" +#endif + +namespace Avoid { + + +bool UseAStarSearch = true; +bool IgnoreRegions = true; +bool SelectiveReroute = true; +bool IncludeEndpoints = true; +bool UseLeesAlgorithm = false; +bool InvisibilityGrph = true; +bool PartialFeedback = false; + +bool PartialTime = false; + + +void computeCompleteVis(void) +{ + VertInf *beginVert = vertices.shapesBegin(); + VertInf *endVert = vertices.end(); + for (VertInf *i = beginVert; i != endVert; i = i->lstNext) + { + db_printf("-- CONSIDERING --\n"); + i->id.db_print(); + + for (VertInf *j = i->lstPrev ; j != NULL; j = j->lstPrev) + { + bool knownNew = true; + EdgeInf::checkEdgeVisibility(i, j, knownNew); + } + } +} + + +void shapeVis(ShapeRef *shape) +{ + if (!InvisibilityGrph) + { + // Clear shape from graph. + shape->removeFromGraph(); + } + + VertInf *shapeBegin = shape->firstVert(); + VertInf *shapeEnd = shape->lastVert()->lstNext; + + VertInf *pointsBegin = NULL; + if (IncludeEndpoints) + { + pointsBegin = vertices.connsBegin(); + } + else + { + pointsBegin = vertices.shapesBegin(); + } + + for (VertInf *curr = shapeBegin; curr != shapeEnd; curr = curr->lstNext) + { + bool knownNew = true; + + db_printf("-- CONSIDERING --\n"); + curr->id.db_print(); + + db_printf("\tFirst Half:\n"); + for (VertInf *j = pointsBegin ; j != curr; j = j->lstNext) + { + EdgeInf::checkEdgeVisibility(curr, j, knownNew); + } + + db_printf("\tSecond Half:\n"); + VertInf *pointsEnd = vertices.end(); + for (VertInf *k = shapeEnd; k != pointsEnd; k = k->lstNext) + { + EdgeInf::checkEdgeVisibility(curr, k, knownNew); + } + } +} + + +void shapeVisSweep(ShapeRef *shape) +{ + if (!InvisibilityGrph) + { + // Clear shape from graph. + shape->removeFromGraph(); + } + + VertInf *startIter = shape->firstVert(); + VertInf *endIter = shape->lastVert()->lstNext; + + for (VertInf *i = startIter; i != endIter; i = i->lstNext) + { + vertexSweep(i); + } +} + + +void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew, + const bool gen_contains) +{ + const VertID& pID = point->id; + + // Make sure we're only doing ptVis for endpoints. + assert(!(pID.isShape)); + + if (!InvisibilityGrph) + { + point->removeFromGraph(); + } + + if (gen_contains && !(pID.isShape)) + { + generateContains(point); + } + + if (UseLeesAlgorithm) + { + vertexSweep(point); + } + else + { + VertInf *shapesEnd = vertices.end(); + for (VertInf *k = vertices.shapesBegin(); k != shapesEnd; + k = k->lstNext) + { + EdgeInf::checkEdgeVisibility(point, k, knownNew); + } + if (IncludeEndpoints && partner) + { + EdgeInf::checkEdgeVisibility(point, partner, knownNew); + } + } +} + + +//============================================================================ +// SWEEP CODE +// + +static VertInf *centerInf; +static Point centerPoint; +static VertID centerID; +static double centerAngle; + +#ifdef LINEDEBUG + SDL_Surface *avoid_screen = NULL; +#endif + + +class PointPair +{ + public: + PointPair(VertInf *inf) + : vInf(inf) + { + double x = vInf->point.x - centerPoint.x; + double y = vInf->point.y - centerPoint.y; + + angle = pos_to_angle(x, y); + } + bool operator==(const PointPair& rhs) const + { + if (vInf->id == rhs.vInf->id) + { + return true; + } + return false; + } + static double pos_to_angle(double x, double y) + { + double ang = atan(y / x); + ang = (ang * 180) / M_PI; + if (x < 0) + { + ang += 180; + } + else if (y < 0) + { + ang += 360; + } + return ang; + } + + VertInf *vInf; + double angle; +}; + + +typedef std::list<PointPair > VertList; + + +class EdgePair +{ + public: + EdgePair(VertInf *v1, VertInf *v2, double d, double a) + : vInf1(v1), vInf2(v2), initdist(d), initangle(a) + { + currdist = initdist; + currangle = initangle; + } + bool operator<(const EdgePair& rhs) const + { + if (initdist == rhs.initdist) + { + // TODO: This is a bit of a hack, should be + // set by the call to the constructor. + return dist(centerPoint, vInf2->point) < + dist(centerPoint, rhs.vInf2->point); + } + return (initdist < rhs.initdist); + } + bool operator==(const EdgePair& rhs) const + { + if (((vInf1->id == rhs.vInf1->id) && + (vInf2->id == rhs.vInf2->id)) || + ((vInf1->id == rhs.vInf2->id) && + (vInf2->id == rhs.vInf1->id))) + { + return true; + } + return false; + } + bool operator!=(const EdgePair& rhs) const + { + if (((vInf1->id == rhs.vInf1->id) && + (vInf2->id == rhs.vInf2->id)) || + ((vInf1->id == rhs.vInf2->id) && + (vInf2->id == rhs.vInf1->id))) + { + return false; + } + return true; + } + void SetObsAng(double a) + { + obsAngle = fmod(initangle - (a - 180), 360); + + //db_printf("SetObsAng: %.2f (from init %.2f, a %.2f)\n", + // obsAngle, initangle, a); + } + + VertInf *vInf1; + VertInf *vInf2; + double initdist; + double initangle; + double currdist; + double currangle; + double obsAngle; +}; + +typedef std::set<EdgePair> EdgeSet; + + +static bool ppCompare(PointPair& pp1, PointPair& pp2) +{ + if (pp1.angle == pp2.angle) + { + // If the points are colinear, then order them in increasing + // distance from the point we are sweeping around. + return dist(centerPoint, pp1.vInf->point) < + dist(centerPoint, pp2.vInf->point); + } + return pp1.angle < pp2.angle; +} + + +#define AHEAD 1 +#define BEHIND -1 + +class isBoundingShape +{ + public: + // constructor remembers the value provided + isBoundingShape(ShapeSet& set) + : ss(set) + { } + // the following is an overloading of the function call operator + bool operator () (const PointPair& pp) + { + if (pp.vInf->id.isShape && + (ss.find(pp.vInf->id.objID) != ss.end())) + { + return true; + } + return false; + } + private: + ShapeSet& ss; +}; + + +static bool sweepVisible(EdgeSet& T, VertInf *currInf, VertInf *lastInf, + bool lastVisible, double lastAngle, int *blocker) +{ + + if (!lastInf || (lastAngle != centerAngle)) + { + // Nothing before it on the current ray + EdgeSet::iterator closestIt = T.begin(); + if (closestIt != T.end()) + { + + Point &e1 = (*closestIt).vInf1->point; + Point &e2 = (*closestIt).vInf2->point; + + if (segmentIntersect(centerInf->point, currInf->point, e1, e2)) + { + *blocker = (*closestIt).vInf1->id.objID; + return false; + } + else + { + return true; + } + } + else + { + return true; + } + } + else + { + // There was another point before this on the ray (lastInf) + if (!lastVisible) + { + *blocker = -1; + return false; + } + else + { + // Check if there is an edge in T that blocks the ray + // between lastInf and currInf. + EdgeSet::iterator tfin = T.end(); + for (EdgeSet::iterator l = T.begin(); l != tfin; ++l) + { + Point &e1 = (*l).vInf1->point; + Point &e2 = (*l).vInf2->point; + + if (segmentIntersect(lastInf->point, currInf->point, e1, e2)) + { + *blocker = (*l).vInf1->id.objID; + return false; + } + } + return true; + } + } +} + + +void vertexSweep(VertInf *vert) +{ + VertID& pID = vert->id; + Point& pPoint = vert->point; + + centerInf = vert; + centerID = pID; + centerPoint = pPoint; + Point centerPt = pPoint; + centerAngle = -1; + + // List of shape (and maybe endpt) vertices, except p + // Sort list, around + VertList v; + + // Initialise the vertex list + VertInf *beginVert = vertices.connsBegin(); + VertInf *endVert = vertices.end(); + for (VertInf *inf = beginVert; inf != endVert; inf = inf->lstNext) + { + if (inf->id == centerID) + { + // Don't include the center point + continue; + } + + if (inf->id.isShape) + { + // Add shape vertex + v.push_back(inf); + } + else + { + if (IncludeEndpoints) + { + if (centerID.isShape) + { + // Add endpoint vertex + v.push_back(inf); + } + else + { + // Center is an endpoint, so only include the other + // endpoint from the matching connector. + VertID partnerID = VertID(centerID.objID, false, + (centerID.vn == 1) ? 2 : 1); + if (inf->id == partnerID) + { + v.push_back(inf); + } + } + } + } + } + // TODO: This should be done with a sorted data type and insertion sort. + v.sort(ppCompare); + + EdgeSet e; + ShapeSet& ss = contains[centerID]; + + // And edge to T that intersect the initial ray. + VertInf *last = vertices.end(); + for (VertInf *k = vertices.shapesBegin(); k != last; ) + { + VertID kID = k->id; + if (!(centerID.isShape) && (ss.find(kID.objID) != ss.end())) + { + uint shapeID = kID.objID; + db_printf("Center is inside shape %u so ignore shape edges.\n", + shapeID); + // One of the endpoints is inside this shape so ignore it. + while ((k != last) && (k->id.objID == shapeID)) + { + // And skip the other vertices from this shape. + k = k->lstNext; + } + continue; + } + + VertInf *kPrev = k->shPrev; + if ((centerInf == k) || (centerInf == kPrev)) + { + k = k->lstNext; + continue; + } + + Point xaxis = { DBL_MAX, centerInf->point.y }; + + if (segmentIntersect(centerInf->point, xaxis, kPrev->point, k->point)) + { + double distance; + if (vecDir(centerInf->point, xaxis, kPrev->point) == BEHIND) + { + distance = dist(centerInf->point, kPrev->point); + } + else + { + distance = dist(centerInf->point, k->point); + } + + EdgePair intPair = EdgePair(k, kPrev, distance, 0.0); + e.insert(intPair).first; + } + k = k->lstNext; + } + + // Start the actual sweep. + db_printf("SWEEP: "); centerID.db_print(); db_printf("\n"); + + VertInf *lastInf = NULL; + double lastAngle = 0; + bool lastVisible = false; + int lastBlocker = 0; + + isBoundingShape isBounding(contains[centerID]); + VertList::iterator vfst = v.begin(); + VertList::iterator vfin = v.end(); + for (VertList::iterator t = vfst; t != vfin; ++t) + { + VertInf *currInf = (*t).vInf; + VertID& currID = currInf->id; + Point& currPt = currInf->point; + centerAngle = (*t).angle; + +#ifdef LINEDEBUG + Sint16 ppx = (int) centerPt.x; + Sint16 ppy = (int) centerPt.y; + + Sint16 cx = (int) currPt.x; + Sint16 cy = (int) currPt.y; +#endif + + double currDist = dist(centerPt, currPt); + db_printf("Dist: %.1f.\n", currDist); + + EdgeInf *edge = EdgeInf::existingEdge(centerInf, currInf); + if (edge == NULL) + { + edge = new EdgeInf(centerInf, currInf); + } + // Ignore vertices from bounding shapes, if sweeping round an endpoint. + if (!(centerID.isShape) && isBounding(*t)) + { + if (InvisibilityGrph) + { + // if p and t can't see each other, add blank edge + db_printf("\tSkipping visibility edge... \n\t\t"); + edge->addBlocker(currInf->id.objID); + edge->db_print(); + } + continue; + } + + + bool cone1 = true, cone2 = true; + if (centerID.isShape) + { + cone1 = inValidRegion(centerInf->shPrev->point, centerPoint, + centerInf->shNext->point, currInf->point); + } + if (currInf->id.isShape) + { + cone2 = inValidRegion(currInf->shPrev->point, currInf->point, + currInf->shNext->point, centerPoint); + } + + if (!cone1 || !cone2) + { + lastInf = NULL; + if (InvisibilityGrph) + { + db_printf("\tSetting invisibility edge... \n\t\t"); + edge->addBlocker(0); + edge->db_print(); + } + } + else + { + int blocker = 0; + // Check visibility. + bool currVisible = sweepVisible(e, currInf, + lastInf, lastVisible, lastAngle, &blocker); + if (blocker == -1) + { + blocker = lastBlocker; + } + if (currVisible) + { +#ifdef LINEDEBUG + lineRGBA(avoid_screen, ppx, ppy, cx, cy, 255, 0, 0, 32); +#endif + db_printf("\tSetting visibility edge... \n\t\t"); + edge->setDist(currDist); + edge->db_print(); + } + else if (InvisibilityGrph) + { + db_printf("\tSetting invisibility edge... \n\t\t"); + edge->addBlocker(blocker); + edge->db_print(); + } + + lastVisible = currVisible; + lastInf = currInf; + lastAngle = centerAngle; + lastBlocker = blocker; + } + + if (currID.isShape) + { + // This is a shape edge + Point& prevPt = currInf->shPrev->point; + Point& nextPt = currInf->shNext->point; + + int prevDir = vecDir(centerPt, currPt, prevPt); + EdgePair prevPair = EdgePair(currInf, currInf->shPrev, + currDist, centerAngle); + + EdgeSet::iterator ePtr; + if (prevDir == BEHIND) + { + ePtr = e.find(prevPair); + if (ePtr != e.end()) + { + e.erase(ePtr); + } + } + else if ((prevDir == AHEAD) && (currInf->shPrev != centerInf)) + { + double x = prevPt.x - currPt.x; + double y = prevPt.y - currPt.y; + double angle = PointPair::pos_to_angle(x, y); + prevPair.SetObsAng(angle); + + ePtr = e.insert(prevPair).first; + } + + + int nextDir = vecDir(centerPt, currPt, nextPt); + EdgePair nextPair = EdgePair(currInf, currInf->shNext, + currDist, centerAngle); + + if (nextDir == BEHIND) + { + ePtr = e.find(nextPair); + if (ePtr != e.end()) + { + e.erase(ePtr); + } + } + else if ((nextDir == AHEAD) && (currInf->shNext != centerInf)) + { + double x = nextPt.x - currPt.x; + double y = nextPt.y - currPt.y; + double angle = PointPair::pos_to_angle(x, y); + nextPair.SetObsAng(angle); + + ePtr = e.insert(nextPair).first; + } + } + +#ifdef LINEDEBUG + SDL_Flip(avoid_screen); +#endif + } +} + + +} + diff --git a/src/libavoid/visibility.h b/src/libavoid/visibility.h new file mode 100644 index 000000000..edfc3b16c --- /dev/null +++ b/src/libavoid/visibility.h @@ -0,0 +1,57 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#ifndef AVOID_VISIBILITY_H +#define AVOID_VISIBILITY_H + +#include "libavoid/vertices.h" + + +//#define LINEDEBUG + +#ifdef LINEDEBUG + #include <SDL.h> +#endif + + +namespace Avoid { + +extern bool PartialTime; +#ifdef LINEDEBUG + extern SDL_Surface *avoid_screen; +#endif + + +extern void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew, + const bool gen_contains = false); +extern void vertexSweep(VertInf *point); +extern void computeCompleteVis(void); +extern void shapeVis(ShapeRef *shape); +extern void shapeVisSweep(ShapeRef *shape); + + +} + + +#endif + + |