![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
index 36514e24e37bbaada9956576515d280348cad796..df0bacd0266e848fd15e7f889c85397897dc45dc 100644 (file)
--- a/src/libavoid/router.cpp
+++ b/src/libavoid/router.cpp
* 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 <cstdlib>
#include "libavoid/shape.h"
#include "libavoid/router.h"
#include "libavoid/visibility.h"
#include "libavoid/connector.h"
#include "libavoid/polyutil.h"
#include "libavoid/debug.h"
+#include "libavoid/region.h"
#include "math.h"
//#define ORTHOGONAL_ROUTING
namespace Avoid {
+static const unsigned int infoAdd = 1;
+static const unsigned int infoDel = 2;
+static const unsigned int infoMov = 3;
+
+
+class MoveInfo {
+ public:
+ MoveInfo(ShapeRef *s, Polygn *p, bool fM)
+ : shape(s)
+ , newPoly(copyPoly(*p))
+ , firstMove(fM)
+ { }
+ ~MoveInfo()
+ {
+ freePoly(newPoly);
+ }
+ ShapeRef *shape;
+ Polygn newPoly;
+ bool firstMove;
+};
+
+
+
Router::Router()
: PartialTime(false)
+ , SimpleRouting(false)
+ , segmt_penalty(0)
+ , angle_penalty(0)
+ , crossing_penalty(200)
// Algorithm options:
, UseAStarSearch(true)
, IgnoreRegions(true)
, IncludeEndpoints(true)
, UseLeesAlgorithm(false)
, InvisibilityGrph(true)
- , ConsolidateMoves(false)
+ , ConsolidateMoves(true)
, PartialFeedback(false)
// Instrumentation:
, st_checked_edges(0)
{
unsigned int pid = shape->id();
+ // Delete items that are queued in the movList.
+ for (MoveInfoList::iterator it = moveList.begin(); it != moveList.end(); )
+ {
+ if ((*it)->shape->id() == pid)
+ {
+ MoveInfoList::iterator doomed = it;
+ ++it;
+ moveList.erase(doomed);
+ }
+ else
+ {
+ ++it;
+ }
+ }
+
// o Remove entries related to this shape's vertices
shape->removeFromGraph();
void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
{
- unsigned int pid = shape->id();
- bool notPartialTime = !(PartialFeedback && PartialTime);
+ // Sanely cope with the case where the user requests moving the same
+ // shape multiple times before rerouting connectors.
+ bool alreadyThere = false;
+ unsigned int id = shape->id();
+ MoveInfoList::iterator finish = moveList.end();
+ for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
+ {
+ if ((*it)->shape->id() == id)
+ {
+ if (!SimpleRouting)
+ {
+ fprintf(stderr,
+ "warning: multiple moves requested for shape %d.\n",
+ (int) id);
+ }
+ // Just update the MoveInfo with the second polygon, but
+ // leave the firstMove setting alone.
+ (*it)->newPoly = copyPoly(*newPoly);
+ alreadyThere = true;
+ }
+ }
- // o Remove entries related to this shape's vertices
- shape->removeFromGraph();
-
- if (SelectiveReroute && (notPartialTime || first_move))
+ if (!alreadyThere)
{
- markConnectors(shape);
+ MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
+ moveList.push_back(moveInfo);
}
- adjustContainsWithDel(pid);
-
+ if (!ConsolidateMoves)
+ {
+ processMoves();
+ }
+}
+
+
+void Router::processMoves(void)
+{
+ // If SimpleRouting, then don't update yet.
+ if (moveList.empty() || SimpleRouting)
+ {
+ return;
+ }
+
+ MoveInfoList::iterator curr;
+ MoveInfoList::iterator finish = moveList.end();
+ for (curr = moveList.begin(); curr != finish; ++curr)
+ {
+ MoveInfo *moveInf = *curr;
+ ShapeRef *shape = moveInf->shape;
+ Polygn *newPoly = &(moveInf->newPoly);
+ bool first_move = moveInf->firstMove;
+
+ unsigned int pid = shape->id();
+ bool notPartialTime = !(PartialFeedback && PartialTime);
+
+ // o Remove entries related to this shape's vertices
+ shape->removeFromGraph();
+
+ if (SelectiveReroute && (notPartialTime || first_move))
+ {
+ markConnectors(shape);
+ }
+
+ adjustContainsWithDel(pid);
+
#ifdef ORTHOGONAL_ROUTING
- Region::removeShape(shape);
+ Region::removeShape(shape);
#endif
- shape->setNewPoly(*newPoly);
+ shape->setNewPoly(*newPoly);
+
+ adjustContainsWithAdd(*newPoly, pid);
- adjustContainsWithAdd(*newPoly, pid);
+ // Ignore this shape for visibility.
+ // XXX: We don't really need to do this if we're not using Partial
+ // Feedback. Without this the blocked edges still route
+ // around the shape until it leaves the connector.
+ shape->makeInactive();
+
+ }
- // o Check all edges that were blocked by this shape.
if (InvisibilityGrph)
{
- checkAllBlockedEdges(pid);
+ for (curr = moveList.begin(); curr != finish; ++curr)
+ {
+ MoveInfo *moveInf = *curr;
+ ShapeRef *shape = moveInf->shape;
+ unsigned int pid = shape->id();
+
+ // o Check all edges that were blocked by this shape.
+ checkAllBlockedEdges(pid);
+ }
}
else
{
@@ -150,31 +261,46 @@ void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
checkAllMissingEdges();
}
+ while ( ! moveList.empty() )
+ {
+ MoveInfo *moveInf = moveList.front();
+ ShapeRef *shape = moveInf->shape;
+ Polygn *newPoly = &(moveInf->newPoly);
+
+ unsigned int pid = shape->id();
+ bool notPartialTime = !(PartialFeedback && PartialTime);
+
+ // Restore this shape for visibility.
+ shape->makeActive();
+
#ifdef ORTHOGONAL_ROUTING
- Region::addShape(shape);
+ Region::addShape(shape);
#endif
- // o Check all visibility edges to see if this one shape
- // blocks them.
- if (notPartialTime)
- {
- newBlockingShape(newPoly, pid);
- }
+ // o Check all visibility edges to see if this one shape
+ // blocks them.
+ if (notPartialTime)
+ {
+ newBlockingShape(newPoly, pid);
+ }
- // o Calculate visibility for the new vertices.
- if (UseLeesAlgorithm)
- {
- shapeVisSweep(shape);
- }
- else
- {
- shapeVis(shape);
+ // o Calculate visibility for the new vertices.
+ if (UseLeesAlgorithm)
+ {
+ shapeVisSweep(shape);
+ }
+ else
+ {
+ shapeVis(shape);
+ }
+
+ moveList.pop_front();
+ delete moveInf;
}
callbackAllInvalidConnectors();
}
-
//----------------------------------------------------------------------------
// XXX: attachedShapes and attachedConns both need to be rewritten
if (tmp->getDist() != 0)
{
- pair<VertID, VertID> ids(tmp->ids());
+ std::pair<VertID, VertID> ids(tmp->ids());
VertID eID1 = ids.first;
VertID eID2 = ids.second;
- pair<Point, Point> points(tmp->points());
+ std::pair<Point, Point> points(tmp->points());
Point e1 = points.first;
Point e2 = points.second;
bool blocked = false;
}
-#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)
// Ignore uninitialised connectors.
continue;
}
+ else if (conn->_needs_reroute_flag)
+ {
+ // Already marked, so skip.
+ continue;
+ }
Point start = conn->_route.ps[0];
Point end = conn->_route.ps[conn->_route.pn - 1];
c = end.x;
d = end.y - offy;
- min = MIN(p1.x, p2.x);
- max = MAX(p1.x, p2.x);
+ min = std::min(p1.x, p2.x);
+ max = std::max(p1.x, p2.x);
}
else if (p1.x == p2.x)
{
c = end.y;
d = end.x - offy;
- min = MIN(p1.y, p2.y);
- max = MAX(p1.y, p2.y);
+ min = std::min(p1.y, p2.y);
+ max = std::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 };
+ 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_p1(0, 0);
Point r_p2 = n_p2;
start = n_start;
end = n_end;
if (((int) r_p2.y) != 0)
{
printf("r_p2.y: %f != 0\n", r_p2.y);
- abort();
+ std::abort();
}
// This might be slightly off.
r_p2.y = 0;
c = end.x;
d = end.y - offy;
- min = MIN(r_p1.x, r_p2.x);
- max = MAX(r_p1.x, r_p2.x);
+ min = std::min(r_p1.x, r_p2.x);
+ max = std::max(r_p1.x, r_p2.x);
}
//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;
+ x = std::max(min, x);
+ x = std::min(max, x);
//printf("x = %.1f\n", x);