/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2004-2009 Monash University
*
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* See the file LICENSE.LGPL distributed with the library.
*
* Licensees holding a valid commercial license may use this file in
* accordance with the commercial license agreement provided with the
* library.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
*/
#include <algorithm>
#include <cmath>
#include "libavoid/visibility.h"
#include "libavoid/connector.h"
#include "libavoid/orthogonal.h"
#include "libavoid/assertions.h"
namespace Avoid {
enum ActionType {
};
class ActionInfo {
public:
: type(t),
objPtr(s),
newPoly(p),
{
}
: type(t),
objPtr(s),
newPoly(),
firstMove(0)
{
}
: type(t),
objPtr(c),
newPoly(),
firstMove(0)
{
}
~ActionInfo()
{
}
{
(type == ShapeRemove));
}
{
}
bool operator==(const ActionInfo& rhs) const
{
}
bool operator<(const ActionInfo& rhs) const
{
{
}
}
void *objPtr;
bool firstMove;
};
: visOrthogGraph(true),
PartialTime(false),
SimpleRouting(false),
ClusteredRouting(true),
// Poly-line algorithm options:
IgnoreRegions(true),
UseLeesAlgorithm(true),
InvisibilityGrph(true),
// General algorithm options:
SelectiveReroute(true),
PartialFeedback(false),
RubberBandRouting(false),
// Instrumentation:
st_checked_edges(0),
#ifdef LIBAVOID_SDL
#endif
_consolidateActions(true),
_orthogonalNudgeDistance(4.0),
// Mode options:
_polyLineRouting(false),
_orthogonalRouting(false),
_staticGraphInvalidated(true),
{
// At least one of the Routing modes must be set.
if (flags & PolyLineRouting)
{
_polyLineRouting = true;
}
if (flags & OrthogonalRouting)
{
_orthogonalRouting = true;
}
for (size_t p = 0; p < lastPenaltyMarker; ++p)
{
_routingPenalties[p] = 0.0;
}
}
{
// Delete remaining connectors.
{
delete *conn;
}
// Remove remaining shapes.
{
{
shapePtr->makeInactive();
}
delete shapePtr;
}
// Cleanup orphaned orthogonal graph vertices.
}
{
{
}
else
{
}
if (!_consolidateActions)
{
}
}
{
{
}
if (!_consolidateActions)
{
}
}
{
{
}
}
{
// There shouldn't be remove events or move events for the same shape
// already in the action list.
// XXX: Possibly we could handle this by ordering them intelligently.
{
}
if (!_consolidateActions)
{
}
}
{
// There shouldn't be add events events for the same shape already
// in the action list.
// XXX: Possibly we could handle this by ordering them intelligently.
// Delete any ShapeMove entries for this shape in the action list.
{
}
// Add the ShapeRemove entry.
{
}
if (!_consolidateActions)
{
}
}
{
}
const bool first_move)
{
// There shouldn't be remove events or add events for the same shape
// already in the action list.
// XXX: Possibly we could handle this by ordering them intelligently.
{
// The Add is enough, no need for the Move action too.
return;
}
// Sanely cope with the case where the user requests moving the same
// shape multiple times before rerouting connectors.
{
if (!SimpleRouting)
{
db_printf("warning: multiple moves requested for shape %d "
}
// Just update the ActionInfo with the second polygon, but
// leave the firstMove setting alone.
}
else
{
}
if (!_consolidateActions)
{
}
}
{
}
{
// Remove orthogonal visibility graph edges.
// Remove the now orphaned vertices.
while (curr)
{
{
delete curr;
continue;
}
}
}
{
// Here we do talks involved in updating the static-built visibility
// graph (if necessary) before we do any routing.
{
if (_orthogonalRouting)
{
// Regenerate a new visibility graph.
}
_staticGraphInvalidated = false;
}
}
{
}
{
return _consolidateActions;
}
{
}
{
bool seenShapeMovesOrDeletes = false;
// If SimpleRouting, then don't update here.
{
return false;
}
actionList.sort();
{
{
// Not a move or remove action, so don't do anything.
continue;
}
seenShapeMovesOrDeletes = true;
// o Remove entries related to this shape's vertices
shape->removeFromGraph();
{
}
// 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();
}
{
if (InvisibilityGrph)
{
{
{
// Not a move or remove action, so don't do anything.
continue;
}
// o Check all edges that were blocked by this shape.
}
}
else
{
// check all edges not in graph
}
}
{
{
// Not a move or add action, so don't do anything.
continue;
}
// Restore this shape for visibility.
shape->makeActive();
if (isMove)
{
}
if (_polyLineRouting)
{
// o Check all visibility edges to see if this one shape
// blocks them.
if (!isMove || notPartialTime)
{
}
// o Calculate visibility for the new vertices.
if (UseLeesAlgorithm)
{
}
else
{
}
}
}
// Update connector endpoints.
{
{
continue;
}
{
}
}
// Clear the actionList.
actionList.clear();
_staticGraphInvalidated = true;
return true;
}
{
cluster->makeActive();
}
{
cluster->makeInactive();
}
{
COLA_ASSERT(dist >= 0);
}
{
return _orthogonalNudgeDistance;
}
{
// If the suggestedId is zero, then we assign the object the next
// smallest unassigned ID, otherwise we trust the ID given is unique.
// Have the router record if this ID is larger than the _largestAssignedId.
// If assertions are enabled, then we check that this ID really is unique.
return assignedId;
}
// Returns whether the given ID is unique among all objects known by the
// router. Outputs a warning if the ID is found ore than once.
// It is expected this is only going to be called from assertions while
// debugging, so efficiency is not an issue and we just iterate over all
// objects.
{
unsigned int count = 0;
// Examine shapes.
{
{
count++;
}
}
// Examine connectors.
{
{
count++;
}
}
// Examine clusters.
i != clusterRefs.end(); ++i)
{
{
count++;
}
}
if (count > 1)
{
return false;
}
return true;
}
//----------------------------------------------------------------------------
// XXX: attachedShapes and attachedConns both need to be rewritten
// for constant time lookup of attached objects once this info
// is stored better within libavoid. Also they shouldn't need to
// be friends of ConnRef.
// Returns a list of connector Ids of all the connectors of type
// 'type' attached to the shape with the ID 'shapeId'.
const unsigned int type)
{
{
{
}
{
}
}
}
// Returns a list of shape Ids of all the shapes attached to the
// shape with the ID 'shapeId' with connection type 'type'.
const unsigned int type)
{
{
{
if ((*i)->_srcId != 0)
{
// Only if there is a shape attached to the other end.
}
}
{
if ((*i)->_dstId != 0)
{
// Only if there is a shape attached to the other end.
}
}
}
}
// It's intended this function is called after visibility changes
// resulting from shape movement have happened. It will alert
// rerouted connectors (via a callback) that they need to be redrawn.
{
// Updating the orthogonal visibility graph if necessary.
{
(*i)->_needs_repaint = false;
if (rerouted)
{
reroutedConns.insert(*i);
}
}
// Find and reroute crossing connectors if crossing penalties are set.
// Perform centring and nudging for othogonal routes.
improveOrthogonalRoutes(this);
// Alert connectors that they need redrawing.
{
(*i)->_needs_repaint = true;
(*i)->performCallback();
}
}
{
if ((crossing_penalty == 0) && (shared_path_penalty == 0))
{
// No penalties, return.
return;
}
// Find crossings and reroute connectors.
_inCrossingPenaltyReroutingStage = true;
{
ConnRefList::iterator j = i;
for (++j; j != fin; ++j)
{
{
// We already know both these have crossings.
continue;
}
// Determine if this pair cross.
bool meetsPenaltyCriteria = false;
{
if ((shared_path_penalty > 0) &&
{
// We are penalising fixedSharedPaths and there is a
// fixedSharedPath.
meetsPenaltyCriteria = true;
break;
}
{
// We are penalising crossings and this is a crossing.
meetsPenaltyCriteria = true;
break;
}
}
if (meetsPenaltyCriteria)
{
crossingConns.insert(*i);
crossingConns.insert(*j);
}
}
}
i != crossingConns.end(); ++i)
{
conn->makePathInvalid();
// XXX: Could we free these routes here for extra savings?
// conn->freeRoutes();
}
i != crossingConns.end(); ++i)
{
conn->generatePath();
}
_inCrossingPenaltyReroutingStage = false;
}
{
// o Check all visibility edges to see if this one shape
// blocks them.
{
{
bool blocked = false;
bool countBorder = 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;
}
bool seenIntersectionAtEndpoint = false;
{
{
blocked = true;
break;
}
}
if (blocked)
{
db_printf("\tRemoving newly blocked edge (by shape %3d)"
"... \n\t\t", pid);
tmp->alertConns();
if (InvisibilityGrph)
{
}
else
{
delete tmp;
}
}
}
}
}
{
{
{
tmp->alertConns();
}
{
}
}
}
{
{
// Check remaining, earlier vertices
{
{
// Don't keep visibility between edges of different conns
continue;
}
// See if the edge is already there?
if (!found)
{
// Didn't already exist, check.
bool knownNew = true;
}
}
}
}
{
// Don't count points on the border as being inside.
bool countBorder = false;
// Compute enclosing shapes.
{
{
}
}
// Computer enclosing Clusters
i != clFinish; ++i)
{
{
}
}
}
const int p_cluster)
{
k = k->lstNext)
{
{
}
}
}
{
k != enclosingClusters.end(); ++k)
{
}
}
{
// Don't count points on the border as being inside.
bool countBorder = false;
k = k->lstNext)
{
{
}
}
}
{
{
}
}
#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
}
#endif
{
if (RubberBandRouting)
{
// When rubber-band routing, we do no reroute connectors that
// may have a better route, only invalid connectors.
return;
}
{
{
// Ignore uninitialised connectors.
continue;
}
else if (conn->_needs_reroute_flag)
{
// Already marked, so skip.
continue;
}
double estdist;
{
double offy;
double a;
double b;
double c;
double d;
double min;
double max;
{
// Standard case
a = start.x;
c = end.x;
}
{
// Other Standard case
a = start.y;
c = end.y;
}
else
{
// Need to do rotation
//db_printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
//db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
//db_printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
//db_printf("theta = %.2f\n", theta * (180 / PI));
//db_printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
//db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
//db_printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
// This might be slightly off.
{
}
r_p2.y = 0;
a = start.x;
c = end.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");
{
// It's going to get adjusted.
x = a;
}
else
{
continue;
}
}
else
{
x = ((b*c) + (a*d)) / (b + d);
}
//db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
//db_printf("x = %.1f\n", x);
//db_printf("x = %.1f\n", x);
{
xp.y = x;
}
else
{
xp.x = x;
}
//db_printf("(%.1f, %.1f)\n", xp.x, xp.y);
//db_printf("is %.1f < %.1f\n", estdist, conndist);
{
#ifdef SELECTIVE_DEBUG
//double angle = AngleAFromThreeSides(dist(start, end),
// e1, e2);
db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
#endif
conn->_needs_reroute_flag = true;
break;
}
}
}
}
{
if (select != ConnType_None)
{
{
return ConnType_Orthogonal;
}
{
return ConnType_PolyLine;
}
}
if (_polyLineRouting)
{
return ConnType_PolyLine;
}
else if (_orthogonalRouting)
{
return ConnType_Orthogonal;
}
return ConnType_None;
}
{
if (penVal < 0)
{
// Set some sensible penalty.
switch (penType)
{
case segmentPenalty:
break;
case fixedSharedPathPenalty:
break;
case anglePenalty:
break;
case crossingPenalty:
break;
case clusterCrossingPenalty:
break;
default:
break;
}
}
else
{
}
}
{
return _routingPenalties[penType];
}
{
return _routingPenalties[penType];
}
{
unsigned int 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_orthogonal_visedges = 0;
int st_invalid_visedges = 0;
{
{
st_shapes++;
}
{
st_vertices++;
}
else
{
// The shape 0 ones are temporary and not considered.
st_endpoints++;
}
}
t = t->lstNext)
{
{
}
else
{
}
}
t = t->lstNext)
{
}
t = t->lstNext)
{
}
}
{
}
//=============================================================================
// The following methods are for testing and debugging.
{
{
ConnRefList::iterator j = i;
for (++j; j != fin; ++j)
{
// Determine if this pair overlap
{
{
// We looking for fixedSharedPaths and there is a
// fixedSharedPath.
return true;
}
}
}
}
return false;
}
{
{
ConnRefList::iterator j = i;
for (++j; j != fin; ++j)
{
// Determine if this pair overlap
{
{
return true;
}
}
}
}
return false;
}
{
if (!instanceName.empty())
{
}
else
{
filename = "libavoid-debug";
}
filename += ".svg";
{
return;
}
while (curr)
{
reduceRange(p.x);
reduceRange(p.y);
if (p.x > -LIMIT)
{
}
if (p.x < LIMIT)
{
}
if (p.y > -LIMIT)
{
}
if (p.y < LIMIT)
{
}
}
minX -= 50;
minY -= 50;
maxX += 50;
maxY += 50;
fprintf(fp, "<svg xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\" xmlns=\"http://www.w3.org/2000/svg\" width=\"100%%\" height=\"100%%\" viewBox=\"%g %g %g %g\">\n", minX, minY, maxX - minX, maxY - minY);
// Output source code to generate this instance of the router.
for (size_t p = 0; p < lastPenaltyMarker; ++p)
{
static_cast<long unsigned int>(p), _routingPenalties[p]);
}
{
{
}
++shRefIt;
}
{
{
}
{
}
++revConnRefIt;
}
"inkscape:label=\"ShapesPoly\">\n");
{
"stroke: black; fill: blue; fill-opacity: 0.3;\" d=\"",
{
}
++shRefIt;
}
"style=\"display: none;\" "
"inkscape:label=\"ShapesRect\">\n");
{
"style=\"stroke-width: 1px; stroke: black; fill: blue; fill-opacity: 0.3;\" />\n",
++shRefIt;
}
"inkscape:label=\"VisGraph\""
">\n");
"style=\"display: none;\" "
"inkscape:label=\"VisGraph-shape\""
">\n");
{
if (!isShape)
{
continue;
}
reduceRange(p1.x);
reduceRange(p1.y);
reduceRange(p2.x);
reduceRange(p2.y);
"style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
"red");
}
"style=\"display: none;\" "
"inkscape:label=\"VisGraph-conn\""
">\n");
{
if (isShape)
{
continue;
}
reduceRange(p1.x);
reduceRange(p1.y);
reduceRange(p2.x);
reduceRange(p2.y);
"style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
"red");
}
"style=\"display: none;\" "
"inkscape:label=\"OrthogVisGraph\">\n");
{
reduceRange(p1.x);
reduceRange(p1.y);
reduceRange(p2.x);
reduceRange(p2.y);
"style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
"red");
}
"style=\"display: none;\" "
"inkscape:label=\"RawConnectors\""
">\n");
{
{
{
}
{
}
"stroke-width: 1px;\" />\n");
}
++connRefIt;
}
"style=\"display: none;\" "
"inkscape:label=\"CurvedDisplayConnectors\""
">\n");
{
{
{
{
i += 2;
}
else
{
}
}
{
}
"stroke-width: 1px;\" />\n");
}
++connRefIt;
}
"inkscape:label=\"DisplayConnectors\""
">\n");
{
{
{
}
{
}
"stroke-width: 1px;\" />\n");
}
++connRefIt;
}
}
}