connector.cpp revision 429dcd1f473b38d2298b2764fab4cb8e6d7e0914
/*
* 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 <cstring>
#include <cfloat>
#include <cmath>
#include <cstdlib>
#include "libavoid/connector.h"
#include "libavoid/makepath.h"
#include "libavoid/visibility.h"
#include "libavoid/assertions.h"
namespace Avoid {
{
}
{
}
: _directions(visDirs),
{
}
{
if (_shapeRef)
{
{
}
// We want to place connection points on the edges of shapes,
// or possibly slightly inside them (if _insideOfset is set).
if (_xPosition == ATTACH_POS_LEFT)
{
}
else if (_xPosition == ATTACH_POS_RIGHT)
{
}
else
{
}
if (_yPosition == ATTACH_POS_TOP)
{
}
else if (_yPosition == ATTACH_POS_BOTTOM)
{
}
else
{
}
return point;
}
else
{
return _point;
}
}
{
if (_shapeRef)
{
if (_directions == ConnDirNone)
{
// None is set, use the defaults:
if (_xPosition == ATTACH_POS_LEFT)
{
}
else if (_xPosition == ATTACH_POS_RIGHT)
{
}
if (_yPosition == ATTACH_POS_TOP)
{
}
else if (_yPosition == ATTACH_POS_BOTTOM)
{
}
if (visDir == ConnDirNone)
{
visDir = ConnDirAll;
}
}
return visDir;
}
else
{
return _directions;
}
}
_srcId(0),
_dstId(0),
_needs_reroute_flag(true),
_false_path(false),
_needs_repaint(false),
_active(false),
_route_dist(0),
_initialised(false),
_hateCrossings(false)
{
// TODO: Store endpoints and details.
}
const unsigned int id)
_srcId(0),
_dstId(0),
_needs_reroute_flag(true),
_false_path(false),
_needs_repaint(false),
_active(false),
_route_dist(0),
_initialised(false),
_hateCrossings(false)
{
bool isShape = false;
makeActive();
_initialised = true;
}
{
_router->removeQueuedConnectorActions(this);
freeRoutes();
if (_srcVert)
{
delete _srcVert;
}
if (_dstVert)
{
delete _dstVert;
}
makeInactive();
}
{
return _type;
}
{
{
_router->modifyConnector(this);
}
}
{
//db_printf("common_updateEndPoint(%d,(pid=%d,vn=%d,(%f,%f)))\n",
// type,point.id,point.vn,point.x,point.y);
if (!_initialised)
{
makeActive();
_initialised = true;
}
// VertInf *partner = NULL;
bool isShape = false;
{
if (_srcVert)
{
}
else
{
}
// partner = _dstVert;
}
else // if (type == (unsigned int) VertID::tar)
{
if (_dstVert)
{
}
else
{
}
// partner = _srcVert;
}
// XXX: Seems to be faster to just remove the edges and recreate
bool isConn = true;
_router->setStaticGraphInvalidated(true);
}
{
}
{
}
{
}
{
}
{
if (_router->_polyLineRouting)
{
bool knownNew = true;
bool genContains = true;
{
}
else
{
}
}
}
{
{
return false;
}
if (pointSuggestion)
{
{
return false;
}
}
// Give this visibility just to the point it is over.
// XXX: We should be able to set this to zero, but can't due to
// assumptions elsewhere in the code.
return true;
}
{
{
}
else // if (type == (unsigned int) VertID::dst)
{
}
}
unsigned int ConnRef::getSrcShapeId(void)
{
return _srcId;
}
unsigned int ConnRef::getDstShapeId(void)
{
return _dstId;
}
void ConnRef::makeActive(void)
{
// Add to connRefs list.
_active = true;
}
void ConnRef::makeInactive(void)
{
if (_active) {
// Remove from connRefs list.
_active = false;
}
}
void ConnRef::freeRoutes(void)
{
}
{
return _route;
}
{
return _route;
}
{
if (&_display_route == &route)
{
db_printf("Error:\tTrying to update libavoid route with itself.\n");
return;
}
//_display_route.clear();
}
{
if (_display_route.empty())
{
// No displayRoute is set. Simplify the current route to get it.
}
return _display_route;
}
void ConnRef::calcRouteDist(void)
{
_route_dist = 0;
{
}
}
bool ConnRef::needsRepaint(void) const
{
return _needs_repaint;
}
{
return _id;
}
{
return _srcVert;
}
{
return _dstVert;
}
{
return _startVert;
}
bool ConnRef::isInitialised(void)
{
return _initialised;
}
void ConnRef::unInitialise(void)
{
makeInactive();
_initialised = false;
}
void ConnRef::removeFromGraph(void)
{
if (_srcVert) {
}
if (_dstVert) {
}
}
{
_connector = ptr;
}
void ConnRef::performCallback(void)
{
if (_callback)
{
}
}
void ConnRef::makePathInvalid(void)
{
_needs_reroute_flag = true;
}
{
return _router;
}
{
// XXX Code to determine when connectors really need to be rerouted
// does not yet work for orthogonal connectors.
if (_type != ConnType_Orthogonal)
{
if (!_false_path && !_needs_reroute_flag)
{
// This connector is up to date.
return false;
}
}
bool result = generatePath();
return result;
}
// Validates a bend point on a path to check it does not form a zigzag corner.
// a, b, c are consecutive points on the path. d and e are b's neighbours,
// forming the shape corner d-b-e.
//
{
bool bendOkay = true;
{
// Not a bendpoint, i.e., the end of the connector, so don't test.
return bendOkay;
}
if ((a == b) || (b == c))
{
return bendOkay;
}
#ifdef PATHDEBUG
db_printf("a=(%g, %g)\n", a.x, a.y);
db_printf("b=(%g, %g)\n", b.x, b.y);
db_printf("c=(%g, %g)\n", c.x, c.y);
db_printf("d=(%g, %g)\n", d.x, d.y);
db_printf("e=(%g, %g)\n", e.x, e.y);
#endif
// Check angle:
#ifdef PATHDEBUG
#endif
if (abc == 0)
{
// The three consecutive point on the path are in a line.
// Thus, there should always be an equally short path that
// skips this bend point.
bendOkay = false;
}
else // (abc != 0)
{
COLA_ASSERT(vecDir(d, b, e) > 0);
#ifdef PATHDEBUG
db_printf("&& (abe == %d) && (abd == %d) &&\n(bce == %d) && (bcd == %d)",
#endif
bendOkay = false;
if (abe > 0)
{
{
bendOkay = true;
}
}
else if (abd < 0)
{
{
bendOkay = true;
}
}
}
#ifdef PATHDEBUG
db_printf("\n");
#endif
return bendOkay;
}
bool ConnRef::generatePath(void)
{
if (!_false_path && !_needs_reroute_flag)
{
// This connector is up to date.
return false;
}
{
// Connector is not fully initialised..
return false;
}
//COLA_ASSERT(_srcVert->point != _dstVert->point);
_false_path = false;
_needs_reroute_flag = false;
bool *flag = &(_needs_reroute_flag);
size_t existingPathStart = 0;
if (_router->RubberBandRouting)
{
#ifdef PATHDEBUG
db_printf("\n");
{
}
db_printf("\n");
#endif
{
{
COLA_ASSERT(existingPathStart != 0);
bool isShape = true;
}
}
}
//db_printf("GO\n");
//db_printf("src: %X strt: %X dst: %x\n", (int) _srcVert, (int) _startVert, (int) _dstVert);
bool found = false;
while (!found)
{
{
if (i == _srcVert)
{
found = true;
break;
}
}
if (!found)
{
if (existingPathStart == 0)
{
break;
}
#ifdef PATHDEBUG
db_printf("BACK\n");
#endif
bool isShape = (existingPathStart > 0);
}
else if (_router->RubberBandRouting)
{
// found.
bool unwind = false;
#ifdef PATHDEBUG
db_printf("\n\n\nSTART:\n\n");
#endif
{
{
unwind = true;
break;
}
}
if (unwind)
{
#ifdef PATHDEBUG
db_printf("BACK II\n");
#endif
if (existingPathStart == 0)
{
break;
}
bool isShape = (existingPathStart > 0);
found = false;
}
}
}
bool result = true;
int pathlen = 1;
{
pathlen++;
if (i == NULL)
{
db_printf("Warning: Path not found...\n");
pathlen = 2;
{
// TODO: Could we know this edge already?
edge->addCycleBlocker();
}
break;
}
// Check we don't have an apparent infinite connector path.
}
int j = pathlen - 1;
{
{
// TODO: Again, we could know this edge without searching.
}
else
{
_false_path = true;
}
{
}
else
{
}
j--;
{
{
// Check for consecutive points on opposite
// corners of two touching shapes.
}
}
}
// Use topbit to differentiate between start and end point of connector.
// They need unique IDs for nudging.
// Would clear visibility for endpoints here if required.
freeRoutes();
#ifdef PATHDEBUG
db_printf("Output route:\n");
{
output_route.ps[i].y);
}
db_printf("\n\n");
#endif
return result;
}
{
}
bool ConnRef::doesHateCrossings(void)
{
return _hateCrossings;
}
{
// Free the PointRep lists.
{
{
delete doomed;
}
}
}
{
if (this == target)
{
return true;
}
else
{
{
{
return true;
}
}
}
return false;
}
{
int position = 0;
{
{
return position;
}
++position;
}
// Not found.
return -1;
}
{
//printf("addPoints(%d, [%g, %g]-%X, [%g, %g]-%X)\n", dim,
// inner->x, inner->y, (int) inner, outer->x, outer->y, (int) outer);
{
{
}
{
}
}
{
}
{
}
// TODO COLA_ASSERT(innerPtr->inner_set.find(outerPtr) == innerPtr->inner_set.end());
if (cycle)
{
// Must reverse to avoid a cycle.
}
else
{
}
return cycle;
}
// Assuming that addPoints has been called for each pair of points in the
// shared path at that corner, then the contents of inner_set can be used
// to determine the correct ordering.
{
//COLA_ASSERT(r1less != r2less);
}
{
}
// Returns a vertex number representing a point on the line between
// two shape corners, represented by p0 and p1.
//
{
if (c.vn != kUnassignedVertexNumber)
{
// The split point is a shape corner, so doesn't need its
// vertex number adjusting.
return c.vn;
}
{
// The point next to this has the correct nudging direction,
// so use that.
}
{
// The point next to this has the correct nudging direction,
// so use that.
}
{
{
}
// Splitting between two ordinary shape corners.
{
}
return vn_mid + 4;
}
{
{
{
return 6;
}
return 4;
}
else
{
{
return 7;
}
return 5;
}
}
{
{
{
return 6;
}
return 4;
}
else
{
{
return 7;
}
return 5;
}
}
// Shouldn't both be new (kUnassignedVertexNumber) points.
db_printf("midVertexNumber(): p0.vn and p1.vn both = "
"kUnassignedVertexNumber\n");
return kUnassignedVertexNumber;
}
// Break up overlapping parallel segments that are not the same edge in
// the visibility graph, i.e., where one segment is a subsegment of another.
{
{
{
// Skip the first point.
// There are points-1 segments in a connector.
continue;
}
{
{
// Skip the first point.
// There are points-1 segments in a connector.
++j;
continue;
}
// Check the first point of the first segment.
{
//db_printf("add to poly %g %g\n", c0.x, c0.y);
{
--j;
}
continue;
}
// And the second point of every segment.
{
//db_printf("add to poly %g %g\n", c1.x, c1.y);
{
--j;
}
continue;
}
// Check the first point of the first segment.
{
//db_printf("add to conn %g %g\n", p0.x, p0.y);
continue;
}
// And the second point of every segment.
{
//db_printf("add to conn %g %g\n", p1.x, p1.y);
}
++j;
}
}
}
{
int result = 1;
{
{
result = -1;
}
}
{
{
result = -1;
}
}
return result;
}
// Works out if the segment conn[cIndex-1]--conn[cIndex] really crosses poly.
// This does not not count non-crossing shared paths as crossings.
// poly can be either a connector (polyIsConn = true) or a cluster
// boundary (polyIsConn = false).
//
bool checkForBranchingSegments, const bool finalSegment,
{
unsigned int crossingFlags = CROSSING_NONE;
{
// XXX When doing the pointOnLine test we allow the points to be
// slightly non-collinear. This addresses a problem with clustered
// routing where connectors could otherwise route cheaply through
// shape corners that were not quite on the cluster boundary, but
// reported to be on there by the line segment intersection code,
// which I suspect is not numerically accurate enough. This occured
// for points that only differed by about 10^-12 in the y-dimension.
// cIndex is going to be the last, so take into account added points.
}
bool polyIsOrthogonal = (polyConnRef &&
bool connIsOrthogonal = (connConnRef &&
int crossingCount = 0;
//db_printf("a1: %g %g\n", a1.x, a1.y);
//db_printf("a2: %g %g\n", a2.x, a2.y);
{
//db_printf("b1: %g %g\n", b1.x, b1.y);
//db_printf("b2: %g %g\n", b2.x, b2.y);
bool converging = false;
{
if (finalSegment)
{
converging = true;
}
else
{
// Route along same segment: no penalty. We detect
// crossovers when we see the segments diverge.
continue;
}
}
{
// Each crossing that is at a vertex in the
// visibility graph gets noticed four times.
// We ignore three of these cases.
// This also catches the case of a shared path,
// but this is one that terminates at a common
// endpoint, so we don't care about it.
continue;
}
if (a1_eq_b1 || converging)
{
if (!converging)
{
if (polyIsConn && (j == 1))
{
// Can't be the end of a shared path or crossing path
// since the common point is the first point of the
// connector path. This is not a shared path at all.
continue;
}
// The segments share an endpoint -- a1==b1.
{
// a2 is not a split, continue.
continue;
}
}
// If here and not converging, then we know that a2 != b2
// And a2 and its pair in b are a split.
bool shared_path = false;
// Initial values here don't matter. They are only used after
// being set to sensible values, but we set them to stop a MSVC
// warning.
bool p_dir_back;
int p_dir = 0;
int trace_c = 0;
int trace_p = 0;
if (converging)
{
// Determine direction we have to look through
// the points of connector b.
p_dir_back = a2_eq_b2 ? true : false;
trace_p = (int) j;
if (!p_dir_back)
{
if (finalSegment)
{
trace_p--;
}
else
{
trace_c--;
}
}
shared_path = true;
}
else if (cIndex >= 2)
{
//db_printf("a0: %g %g\n", a0.x, a0.y);
//db_printf("b0: %g %g\n", b0.x, b0.y);
{
// Determine direction we have to look through
// the points of connector b.
shared_path = true;
}
}
if (shared_path)
{
// Shouldn't be here if p_dir is still equal to zero.
COLA_ASSERT(p_dir != 0);
// Build the shared path, including the diverging points at
// each end if the connector does not end at a common point.
while ( (trace_c >= 0) && (!polyIsConn ||
{
// If poly is a cluster boundary, then it is a closed
// poly-line and so it wraps arounds.
{
// Points don't match, so break out of loop.
break;
}
trace_c--;
}
// Are there diverging points at the ends of the shared path.
// Check to see if these share a fixed segment.
if (polyIsOrthogonal && connIsOrthogonal)
{
{
// Vertical
// See if this is inline with either the start
// or end point of both connectors.
{
}
}
else
{
// Horizontal
// See if this is inline with either the start
// or end point of both connectors.
{
}
}
}
int prevTurnDir = -1;
int startCornerSide = 1;
int endCornerSide = 1;
bool reversed = false;
if (!front_same)
{
// If there is a divergence at the beginning,
// then order the shared path based on this.
}
if (!back_same)
{
// If there is a divergence at the end of the path,
// then order the shared path based on this.
}
else
{
}
if (front_same)
{
}
if (front_same || back_same)
{
}
else if (polyIsOrthogonal && connIsOrthogonal)
{
{
// The start segments diverge at 180 degrees to each
// other. So order based on not introducing overlap
// of the diverging segments when these are nudged
// apart.
startCornerSide = -cStartDir *
}
else
{
{
// The end segments diverge at 180 degrees to
// each other. So order based on not introducing
// overlap of the diverging segments when these
// are nudged apart.
}
}
}
#if 0
prevTurnDir = 0;
if (pointOrders)
{
// Return the ordering for the shared path.
{
*c_path[i + 1]) : 0;
(currTurnDir != 0) && (prevTurnDir != 0) )
{
// The connector turns the opposite way around
// this shape as the previous bend on the path,
// so reverse the order so that the inner path
// become the outer path and vice versa.
}
if (orderSwapped)
{
// Reverse the order for later points.
}
}
}
#endif
prevTurnDir = 0;
if (pointOrders)
{
reversed = false;
// Orthogonal should always have at least one segment.
if (startCornerSide > 0)
{
}
int prevDir = 0;
// Return the ordering for the shared path.
{
{
}
{
}
if (i > startPt)
{
//printf("prevOri %d\n", prevOrientation);
//printf("1: %X, %X\n", (int) &(bn), (int) &(an));
reversed);
if (orderSwapped)
{
// Reverse the order for later points.
}
//printf("2: %X, %X\n", (int) &bp, (int) &ap);
reversed);
}
}
}
#if 0
int ymod = -1;
{
// bottom.
ymod = +1;
}
int xmod = -1;
{
// right.
xmod = +1;
}
{
{
// right.
xmod = +1;
}
{
// bottom.
ymod = +1;
}
{
// left.
xmod = -1;
}
{
// top.
ymod = -1;
}
}
#endif
if (endCornerSide != startCornerSide)
{
// Mark that the shared path crosses.
//db_printf("shared path crosses.\n");
crossingCount += 1;
if (crossingPoints)
{
}
}
}
else if (cIndex >= 2)
{
// The connectors cross or touch at this point.
//db_printf("Cross or touch at point... \n");
// Crossing shouldn't be at an endpoint.
{
// The connectors cross at this point.
//db_printf("cross.\n");
crossingCount += 1;
if (crossingPoints)
{
}
}
if (pointOrders)
{
if (polyIsOrthogonal && connIsOrthogonal)
{
// Orthogonal case:
// Just order based on which comes from the left and
// top in each dimension because this can only be two
// L-shaped segments touching at the bend.
// XXX: Why do we need to invert the reversed values
// here? Are they wrong for orthogonal points
// in the other places?
!reversedX);
!reversedY);
}
else
{ /// \todo FIXME: this whole branch was not doing anything
/*
int turnDirA = vecDir(a0, a1, a2);
int turnDirB = vecDir(b0, b1, b2);
bool reversed = (side1 != -turnDirA);
if (side1 != side2)
{
// Interesting case where a connector routes round
// the edge of a shape and intersects a connector
// which is connected to a port on the edge of the
// shape.
if (turnDirA == 0)
{
// We'll make B the outer by preference,
// because the points of A are collinear.
reversed = false;
}
else if (turnDirB == 0)
{
reversed = true;
}
// TODO COLA_ASSERT((turnDirB != 0) ||
// (turnDirA != 0));
}
VertID vID(b1.id, true, b1.vn);
//(*pointOrders)[b1].addPoints(&b1, &a1, reversed);
*/
}
}
}
}
else
{
if ( polyIsOrthogonal && connIsOrthogonal)
{
// All crossings in orthogonal connectors will be at a
// vertex in the visibility graph, so we need not bother
// doing normal line intersection.
continue;
}
// No endpoint is shared between these two line segments,
// so just calculate normal segment intersection.
{
if (!polyIsConn &&
{
// XXX: This shouldn't actually happen, because these
// points should be added as bends to each line by
// splitBranchingSegments(). Thus, lets ignore them.
continue;
}
//db_printf("crossing lines:\n");
//db_printf("cPt: %g %g\n", cPt.x, cPt.y);
crossingCount += 1;
if (crossingPoints)
{
}
}
}
}
//db_printf("crossingcount %d\n", crossingCount);
}
//============================================================================
}