/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2004-2009 Monash University
*
* 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.
* 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/graph.h"
#include "libavoid/connector.h"
#include "libavoid/makepath.h"
#include "libavoid/visibility.h"
#include "libavoid/debug.h"
#include "libavoid/router.h"
#include "libavoid/assertions.h"
namespace Avoid {
ConnEnd::ConnEnd(const Point& point)
: _point(point),
_directions(ConnDirAll),
_shapeRef(NULL)
{
}
ConnEnd::ConnEnd(const Point& point, const ConnDirFlags visDirs)
: _point(point),
_directions(visDirs),
_shapeRef(NULL)
{
}
ConnEnd::ConnEnd(ShapeRef *shapeRef, const double x_pos, const double y_pos,
const double insideOffset, const ConnDirFlags visDirs)
: _directions(visDirs),
_shapeRef(shapeRef),
_xPosition(x_pos),
_yPosition(y_pos),
_insideOffset(insideOffset)
{
}
const Point ConnEnd::point(void) const
{
if (_shapeRef)
{
const Polygon& poly = _shapeRef->polygon();
double x_min = DBL_MAX;
double x_max = -DBL_MAX;
double y_min = DBL_MAX;
double y_max = -DBL_MAX;
for (size_t i = 0; i < poly.size(); ++i)
{
x_min = std::min(x_min, poly.ps[i].x);
x_max = std::max(x_max, poly.ps[i].x);
y_min = std::min(y_min, poly.ps[i].y);
y_max = std::max(y_max, poly.ps[i].y);
}
Point point;
// We want to place connection points on the edges of shapes,
// or possibly slightly inside them (if _insideOfset is set).
point.vn = kUnassignedVertexNumber;
if (_xPosition == ATTACH_POS_LEFT)
{
point.x = x_min + _insideOffset;
point.vn = 6;
}
else if (_xPosition == ATTACH_POS_RIGHT)
{
point.x = x_max - _insideOffset;
point.vn = 4;
}
else
{
point.x = x_min + (_xPosition * (x_max - x_min));
}
if (_yPosition == ATTACH_POS_TOP)
{
point.y = y_max - _insideOffset;
point.vn = 5;
}
else if (_yPosition == ATTACH_POS_BOTTOM)
{
point.y = y_min + _insideOffset;
point.vn = 7;
}
else
{
point.y = y_min + (_yPosition * (y_max - y_min));
point.vn = kUnassignedVertexNumber;
}
return point;
}
else
{
return _point;
}
}
ConnDirFlags ConnEnd::directions(void) const
{
if (_shapeRef)
{
ConnDirFlags visDir = _directions;
if (_directions == ConnDirNone)
{
// None is set, use the defaults:
if (_xPosition == ATTACH_POS_LEFT)
{
visDir = ConnDirLeft;
}
else if (_xPosition == ATTACH_POS_RIGHT)
{
visDir = ConnDirRight;
}
if (_yPosition == ATTACH_POS_TOP)
{
visDir = ConnDirDown;
}
else if (_yPosition == ATTACH_POS_BOTTOM)
{
visDir = ConnDirUp;
}
if (visDir == ConnDirNone)
{
visDir = ConnDirAll;
}
}
return visDir;
}
else
{
return _directions;
}
}
ConnRef::ConnRef(Router *router, const unsigned int id)
: _router(router),
_type(router->validConnType()),
_srcId(0),
_dstId(0),
_needs_reroute_flag(true),
_false_path(false),
_needs_repaint(false),
_active(false),
_route_dist(0),
_srcVert(NULL),
_dstVert(NULL),
_startVert(NULL),
_initialised(false),
_callback(NULL),
_connector(NULL),
_hateCrossings(false)
{
_id = router->assignId(id);
// TODO: Store endpoints and details.
_route.clear();
}
ConnRef::ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst,
const unsigned int id)
: _router(router),
_type(router->validConnType()),
_srcId(0),
_dstId(0),
_needs_reroute_flag(true),
_false_path(false),
_needs_repaint(false),
_active(false),
_route_dist(0),
_srcVert(NULL),
_dstVert(NULL),
_initialised(false),
_callback(NULL),
_connector(NULL),
_hateCrossings(false)
{
_id = router->assignId(id);
_route.clear();
bool isShape = false;
_srcVert = new VertInf(_router, VertID(_id, isShape, 1), src.point());
_srcVert->visDirections = src.directions();
_dstVert = new VertInf(_router, VertID(_id, isShape, 2), dst.point());
_dstVert->visDirections = dst.directions();
makeActive();
_initialised = true;
setEndpoints(src, dst);
}
ConnRef::~ConnRef()
{
_router->removeQueuedConnectorActions(this);
removeFromGraph();
freeRoutes();
if (_srcVert)
{
_router->vertices.removeVertex(_srcVert);
delete _srcVert;
_srcVert = NULL;
}
if (_dstVert)
{
_router->vertices.removeVertex(_dstVert);
delete _dstVert;
_dstVert = NULL;
}
makeInactive();
}
ConnType ConnRef::routingType(void) const
{
return _type;
}
void ConnRef::setRoutingType(ConnType type)
{
type = _router->validConnType(type);
if (_type != type)
{
_type = type;
makePathInvalid();
_router->modifyConnector(this);
}
}
void ConnRef::common_updateEndPoint(const unsigned int type, const ConnEnd& connEnd)
{
const Point& point = connEnd.point();
//db_printf("common_updateEndPoint(%d,(pid=%d,vn=%d,(%f,%f)))\n",
// type,point.id,point.vn,point.x,point.y);
COLA_ASSERT((type == (unsigned int) VertID::src) ||
(type == (unsigned int) VertID::tar));
if (!_initialised)
{
makeActive();
_initialised = true;
}
VertInf *altered = NULL;
// VertInf *partner = NULL;
bool isShape = false;
if (type == (unsigned int) VertID::src)
{
if (_srcVert)
{
_srcVert->Reset(VertID(_id, isShape, type), point);
}
else
{
_srcVert = new VertInf(_router, VertID(_id, isShape, type), point);
}
_srcVert->visDirections = connEnd.directions();
altered = _srcVert;
// partner = _dstVert;
}
else // if (type == (unsigned int) VertID::tar)
{
if (_dstVert)
{
_dstVert->Reset(VertID(_id, isShape, type), point);
}
else
{
_dstVert = new VertInf(_router, VertID(_id, isShape, type), point);
}
_dstVert->visDirections = connEnd.directions();
altered = _dstVert;
// partner = _srcVert;
}
// XXX: Seems to be faster to just remove the edges and recreate
bool isConn = true;
altered->removeFromGraph(isConn);
makePathInvalid();
_router->setStaticGraphInvalidated(true);
}
void ConnRef::setEndpoints(const ConnEnd& srcPoint, const ConnEnd& dstPoint)
{
_router->modifyConnector(this, VertID::src, srcPoint);
_router->modifyConnector(this, VertID::tar, dstPoint);
}
void ConnRef::setEndpoint(const unsigned int type, const ConnEnd& connEnd)
{
_router->modifyConnector(this, type, connEnd);
}
void ConnRef::setSourceEndpoint(const ConnEnd& srcPoint)
{
_router->modifyConnector(this, VertID::src, srcPoint);
}
void ConnRef::setDestEndpoint(const ConnEnd& dstPoint)
{
_router->modifyConnector(this, VertID::tar, dstPoint);
}
void ConnRef::updateEndPoint(const unsigned int type, const ConnEnd& connEnd)
{
common_updateEndPoint(type, connEnd);
if (_router->_polyLineRouting)
{
bool knownNew = true;
bool genContains = true;
if (type == (unsigned int) VertID::src)
{
vertexVisibility(_srcVert, _dstVert, knownNew, genContains);
}
else
{
vertexVisibility(_dstVert, _srcVert, knownNew, genContains);
}
}
}
bool ConnRef::setEndpoint(const unsigned int type, const VertID& pointID,
Point *pointSuggestion)
{
VertInf *vInf = _router->vertices.getVertexByID(pointID);
if (vInf == NULL)
{
return false;
}
Point& point = vInf->point;
if (pointSuggestion)
{
if (euclideanDist(point, *pointSuggestion) > 0.5)
{
return false;
}
}
common_updateEndPoint(type, point);
// Give this visibility just to the point it is over.
EdgeInf *edge = new EdgeInf(
(type == VertID::src) ? _srcVert : _dstVert, vInf);
// XXX: We should be able to set this to zero, but can't due to
// assumptions elsewhere in the code.
edge->setDist(0.001);
_router->processTransaction();
return true;
}
void ConnRef::setEndPointId(const unsigned int type, const unsigned int id)
{
if (type == (unsigned int) VertID::src)
{
_srcId = id;
}
else // if (type == (unsigned int) VertID::dst)
{
_dstId = id;
}
}
unsigned int ConnRef::getSrcShapeId(void)
{
return _srcId;
}
unsigned int ConnRef::getDstShapeId(void)
{
return _dstId;
}
void ConnRef::makeActive(void)
{
COLA_ASSERT(!_active);
// Add to connRefs list.
_pos = _router->connRefs.insert(_router->connRefs.begin(), this);
_active = true;
}
void ConnRef::makeInactive(void)
{
if (_active) {
// Remove from connRefs list.
_router->connRefs.erase(_pos);
_active = false;
}
}
void ConnRef::freeRoutes(void)
{
_route.clear();
_display_route.clear();
}
const PolyLine& ConnRef::route(void) const
{
return _route;
}
PolyLine& ConnRef::routeRef(void)
{
return _route;
}
void ConnRef::set_route(const PolyLine& route)
{
if (&_display_route == &route)
{
db_printf("Error:\tTrying to update libavoid route with itself.\n");
return;
}
_display_route.ps = route.ps;
//_display_route.clear();
}
Polygon& ConnRef::displayRoute(void)
{
if (_display_route.empty())
{
// No displayRoute is set. Simplify the current route to get it.
_display_route = _route.simplify();
}
return _display_route;
}
void ConnRef::calcRouteDist(void)
{
double (*dist)(const Point& a, const Point& b) =
(_type == ConnType_PolyLine) ? euclideanDist : manhattanDist;
_route_dist = 0;
for (size_t i = 1; i < _route.size(); ++i)
{
_route_dist += dist(_route.at(i), _route.at(i - 1));
}
}
bool ConnRef::needsRepaint(void) const
{
return _needs_repaint;
}
unsigned int ConnRef::id(void) const
{
return _id;
}
VertInf *ConnRef::src(void)
{
return _srcVert;
}
VertInf *ConnRef::dst(void)
{
return _dstVert;
}
VertInf *ConnRef::start(void)
{
return _startVert;
}
bool ConnRef::isInitialised(void)
{
return _initialised;
}
void ConnRef::unInitialise(void)
{
_router->vertices.removeVertex(_srcVert);
_router->vertices.removeVertex(_dstVert);
makeInactive();
_initialised = false;
}
void ConnRef::removeFromGraph(void)
{
if (_srcVert) {
_srcVert->removeFromGraph();
}
if (_dstVert) {
_dstVert->removeFromGraph();
}
}
void ConnRef::setCallback(void (*cb)(void *), void *ptr)
{
_callback = cb;
_connector = ptr;
}
void ConnRef::performCallback(void)
{
if (_callback)
{
_callback(_connector);
}
}
void ConnRef::makePathInvalid(void)
{
_needs_reroute_flag = true;
}
Router *ConnRef::router(void) const
{
return _router;
}
bool ConnRef::generatePath(Point /*p0*/, Point /*p1*/)
{
// 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 validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf)
{
bool bendOkay = true;
if ((aInf == NULL) || (cInf == NULL))
{
// Not a bendpoint, i.e., the end of the connector, so don't test.
return bendOkay;
}
COLA_ASSERT(bInf != NULL);
VertInf *dInf = bInf->shPrev;
VertInf *eInf = bInf->shNext;
COLA_ASSERT(dInf != NULL);
COLA_ASSERT(eInf != NULL);
Point& a = aInf->point;
Point& b = bInf->point;
Point& c = cInf->point;
Point& d = dInf->point;
Point& e = eInf->point;
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:
int abc = vecDir(a, b, c);
#ifdef PATHDEBUG
db_printf("(abc == %d) ", abc);
#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);
int abe = vecDir(a, b, e);
int abd = vecDir(a, b, d);
int bce = vecDir(b, c, e);
int bcd = vecDir(b, c, d);
#ifdef PATHDEBUG
db_printf("&& (abe == %d) && (abd == %d) &&\n(bce == %d) && (bcd == %d)",
abe, abd, bce, bcd);
#endif
bendOkay = false;
if (abe > 0)
{
if ((abc > 0) && (abd >= 0) && (bce >= 0))
{
bendOkay = true;
}
}
else if (abd < 0)
{
if ((abc < 0) && (abe <= 0) && (bcd <= 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;
}
if (!_dstVert || !_srcVert)
{
// Connector is not fully initialised..
return false;
}
//COLA_ASSERT(_srcVert->point != _dstVert->point);
_false_path = false;
_needs_reroute_flag = false;
VertInf *tar = _dstVert;
_startVert = _srcVert;
bool *flag = &(_needs_reroute_flag);
size_t existingPathStart = 0;
const PolyLine& currRoute = route();
if (_router->RubberBandRouting)
{
COLA_ASSERT(_router->IgnoreRegions == true);
#ifdef PATHDEBUG
db_printf("\n");
_srcVert->id.db_print();
db_printf(": %g, %g\n", _srcVert->point.x, _srcVert->point.y);
tar->id.db_print();
db_printf(": %g, %g\n", tar->point.x, tar->point.y);
for (size_t i = 0; i < currRoute.ps.size(); ++i)
{
db_printf("%g, %g ", currRoute.ps[i].x, currRoute.ps[i].y);
}
db_printf("\n");
#endif
if (currRoute.size() > 2)
{
if (_srcVert->point == currRoute.ps[0])
{
existingPathStart = currRoute.size() - 2;
COLA_ASSERT(existingPathStart != 0);
const Point& pnt = currRoute.at(existingPathStart);
bool isShape = true;
VertID vID(pnt.id, isShape, pnt.vn);
_startVert = _router->vertices.getVertexByID(vID);
}
}
}
//db_printf("GO\n");
//db_printf("src: %X strt: %X dst: %x\n", (int) _srcVert, (int) _startVert, (int) _dstVert);
bool found = false;
while (!found)
{
makePath(this, flag);
for (VertInf *i = tar; i != NULL; i = i->pathNext)
{
if (i == _srcVert)
{
found = true;
break;
}
}
if (!found)
{
if (existingPathStart == 0)
{
break;
}
#ifdef PATHDEBUG
db_printf("BACK\n");
#endif
existingPathStart--;
const Point& pnt = currRoute.at(existingPathStart);
bool isShape = (existingPathStart > 0);
VertID vID(pnt.id, isShape, pnt.vn);
_startVert = _router->vertices.getVertexByID(vID);
COLA_ASSERT(_startVert);
}
else if (_router->RubberBandRouting)
{
// found.
bool unwind = false;
#ifdef PATHDEBUG
db_printf("\n\n\nSTART:\n\n");
#endif
VertInf *prior = NULL;
for (VertInf *curr = tar; curr != _startVert->pathNext;
curr = curr->pathNext)
{
if (!validateBendPoint(curr->pathNext, curr, prior))
{
unwind = true;
break;
}
prior = curr;
}
if (unwind)
{
#ifdef PATHDEBUG
db_printf("BACK II\n");
#endif
if (existingPathStart == 0)
{
break;
}
existingPathStart--;
const Point& pnt = currRoute.at(existingPathStart);
bool isShape = (existingPathStart > 0);
VertID vID(pnt.id, isShape, pnt.vn);
_startVert = _router->vertices.getVertexByID(vID);
COLA_ASSERT(_startVert);
found = false;
}
}
}
bool result = true;
int pathlen = 1;
for (VertInf *i = tar; i != _srcVert; i = i->pathNext)
{
pathlen++;
if (i == NULL)
{
db_printf("Warning: Path not found...\n");
pathlen = 2;
tar->pathNext = _srcVert;
if ((_type == ConnType_PolyLine) && _router->InvisibilityGrph)
{
// TODO: Could we know this edge already?
EdgeInf *edge = EdgeInf::existingEdge(_srcVert, tar);
COLA_ASSERT(edge != NULL);
edge->addCycleBlocker();
}
break;
}
// Check we don't have an apparent infinite connector path.
//#ifdef PATHDEBUG
db_printf("Path length: %i\n", pathlen);
//#endif
COLA_ASSERT(pathlen < 10000);
}
std::vector<Point> path(pathlen);
int j = pathlen - 1;
for (VertInf *i = tar; i != _srcVert; i = i->pathNext)
{
if (_router->InvisibilityGrph && (_type == ConnType_PolyLine))
{
// TODO: Again, we could know this edge without searching.
EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext);
COLA_ASSERT(edge != NULL);
edge->addConn(flag);
}
else
{
_false_path = true;
}
path[j] = i->point;
if (i->id.isShape)
{
path[j].id = i->id.objID;
path[j].vn = i->id.vn;
}
else
{
path[j].id = _id;
path[j].vn = kUnassignedVertexNumber;
}
j--;
if (i->pathNext && (i->pathNext->point == i->point))
{
if (i->pathNext->id.isShape && i->id.isShape)
{
// Check for consecutive points on opposite
// corners of two touching shapes.
COLA_ASSERT(abs(i->pathNext->id.objID - i->id.objID) != 2);
}
}
}
path[0] = _srcVert->point;
// Use topbit to differentiate between start and end point of connector.
// They need unique IDs for nudging.
unsigned int topbit = ((unsigned int) 1) << 31;
path[0].id = _id | topbit;
path[0].vn = kUnassignedVertexNumber;
// Would clear visibility for endpoints here if required.
freeRoutes();
PolyLine& output_route = _route;
output_route.ps = path;
#ifdef PATHDEBUG
db_printf("Output route:\n");
for (size_t i = 0; i < output_route.ps.size(); ++i)
{
db_printf("[%d,%d] %g, %g ", output_route.ps[i].id,
output_route.ps[i].vn, output_route.ps[i].x,
output_route.ps[i].y);
}
db_printf("\n\n");
#endif
return result;
}
void ConnRef::setHateCrossings(bool value)
{
_hateCrossings = value;
}
bool ConnRef::doesHateCrossings(void)
{
return _hateCrossings;
}
PtOrder::~PtOrder()
{
// Free the PointRep lists.
for (int dim = 0; dim < 2; ++dim)
{
PointRepList::iterator curr = connList[dim].begin();
while (curr != connList[dim].end())
{
PointRep *doomed = *curr;
curr = connList[dim].erase(curr);
delete doomed;
}
}
}
bool PointRep::follow_inner(PointRep *target)
{
if (this == target)
{
return true;
}
else
{
for (PointRepSet::iterator curr = inner_set.begin();
curr != inner_set.end(); ++curr)
{
if ((*curr)->follow_inner(target))
{
return true;
}
}
}
return false;
}
int PtOrder::positionFor(const ConnRef *conn, const size_t dim) const
{
int position = 0;
for (PointRepList::const_iterator curr = connList[dim].begin();
curr != connList[dim].end(); ++curr)
{
if ((*curr)->conn == conn)
{
return position;
}
++position;
}
// Not found.
return -1;
}
bool PtOrder::addPoints(const int dim, PtConnPtrPair innerArg,
PtConnPtrPair outerArg, bool swapped)
{
PtConnPtrPair inner = (swapped) ? outerArg : innerArg;
PtConnPtrPair outer = (swapped) ? innerArg : outerArg;
COLA_ASSERT(inner != outer);
//printf("addPoints(%d, [%g, %g]-%X, [%g, %g]-%X)\n", dim,
// inner->x, inner->y, (int) inner, outer->x, outer->y, (int) outer);
PointRep *innerPtr = NULL;
PointRep *outerPtr = NULL;
for (PointRepList::iterator curr = connList[dim].begin();
curr != connList[dim].end(); ++curr)
{
if ((*curr)->point == inner.first)
{
innerPtr = *curr;
}
if ((*curr)->point == outer.first)
{
outerPtr = *curr;
}
}
if (innerPtr == NULL)
{
innerPtr = new PointRep(inner.first, inner.second);
connList[dim].push_back(innerPtr);
}
if (outerPtr == NULL)
{
outerPtr = new PointRep(outer.first, outer.second);
connList[dim].push_back(outerPtr);
}
// TODO COLA_ASSERT(innerPtr->inner_set.find(outerPtr) == innerPtr->inner_set.end());
bool cycle = innerPtr->follow_inner(outerPtr);
if (cycle)
{
// Must reverse to avoid a cycle.
innerPtr->inner_set.insert(outerPtr);
}
else
{
outerPtr->inner_set.insert(innerPtr);
}
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.
static bool pointRepLessThan(PointRep *r1, PointRep *r2)
{
size_t r1less = r1->inner_set.size();
size_t r2less = r2->inner_set.size();
//COLA_ASSERT(r1less != r2less);
return (r1less > r2less);
}
void PtOrder::sort(const int dim)
{
connList[dim].sort(pointRepLessThan);
}
// Returns a vertex number representing a point on the line between
// two shape corners, represented by p0 and p1.
//
static int midVertexNumber(const Point& p0, const Point& p1, const Point& c)
{
if (c.vn != kUnassignedVertexNumber)
{
// The split point is a shape corner, so doesn't need its
// vertex number adjusting.
return c.vn;
}
if ((p0.vn >= 4) && (p0.vn < kUnassignedVertexNumber))
{
// The point next to this has the correct nudging direction,
// so use that.
return p0.vn;
}
if ((p1.vn >= 4) && (p1.vn < kUnassignedVertexNumber))
{
// The point next to this has the correct nudging direction,
// so use that.
return p1.vn;
}
if ((p0.vn < 4) && (p1.vn < 4))
{
if (p0.vn != p1.vn)
{
return p0.vn;
}
// Splitting between two ordinary shape corners.
int vn_mid = std::min(p0.vn, p1.vn);
if ((std::max(p0.vn, p1.vn) == 3) && (vn_mid == 0))
{
vn_mid = 3; // Next vn is effectively 4.
}
return vn_mid + 4;
}
COLA_ASSERT((p0.x == p1.x) || (p0.y == p1.y));
if (p0.vn != kUnassignedVertexNumber)
{
if (p0.x == p1.x)
{
if ((p0.vn == 2) || (p0.vn == 3))
{
return 6;
}
return 4;
}
else
{
if ((p0.vn == 0) || (p0.vn == 3))
{
return 7;
}
return 5;
}
}
else if (p1.vn != kUnassignedVertexNumber)
{
if (p0.x == p1.x)
{
if ((p1.vn == 2) || (p1.vn == 3))
{
return 6;
}
return 4;
}
else
{
if ((p1.vn == 0) || (p1.vn == 3))
{
return 7;
}
return 5;
}
}
// Shouldn't both be new (kUnassignedVertexNumber) points.
db_printf("midVertexNumber(): p0.vn and p1.vn both = "
"kUnassignedVertexNumber\n");
db_printf("p0.vn %d p1.vn %d\n", p0.vn, p1.vn);
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.
void splitBranchingSegments(Avoid::Polygon& poly, bool polyIsConn,
Avoid::Polygon& conn, const double tolerance)
{
for (std::vector<Avoid::Point>::iterator i = conn.ps.begin();
i != conn.ps.end(); ++i)
{
if (i == conn.ps.begin())
{
// Skip the first point.
// There are points-1 segments in a connector.
continue;
}
for (std::vector<Avoid::Point>::iterator j = poly.ps.begin();
j != poly.ps.end(); )
{
if (polyIsConn && (j == poly.ps.begin()))
{
// Skip the first point.
// There are points-1 segments in a connector.
++j;
continue;
}
Point& c0 = *(i - 1);
Point& c1 = *i;
Point& p0 = (j == poly.ps.begin()) ? poly.ps.back() : *(j - 1);
Point& p1 = *j;
// Check the first point of the first segment.
if (((i - 1) == conn.ps.begin()) &&
pointOnLine(p0, p1, c0, tolerance))
{
//db_printf("add to poly %g %g\n", c0.x, c0.y);
c0.vn = midVertexNumber(p0, p1, c0);
j = poly.ps.insert(j, c0);
if (j != poly.ps.begin())
{
--j;
}
continue;
}
// And the second point of every segment.
if (pointOnLine(p0, p1, c1, tolerance))
{
//db_printf("add to poly %g %g\n", c1.x, c1.y);
c1.vn = midVertexNumber(p0, p1, c1);
j = poly.ps.insert(j, c1);
if (j != poly.ps.begin())
{
--j;
}
continue;
}
// Check the first point of the first segment.
if (polyIsConn && ((j - 1) == poly.ps.begin()) &&
pointOnLine(c0, c1, p0, tolerance))
{
//db_printf("add to conn %g %g\n", p0.x, p0.y);
p0.vn = midVertexNumber(c0, c1, p0);
i = conn.ps.insert(i, p0);
continue;
}
// And the second point of every segment.
if (pointOnLine(c0, c1, p1, tolerance))
{
//db_printf("add to conn %g %g\n", p1.x, p1.y);
p1.vn = midVertexNumber(c0, c1, p1);
i = conn.ps.insert(i, p1);
}
++j;
}
}
}
static int segDir(const Point& p1, const Point& p2)
{
int result = 1;
if (p1.x == p2.x)
{
if (p2.y > p1.y)
{
result = -1;
}
}
else if (p1.y == p2.y)
{
if (p2.x < p1.x)
{
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).
//
CrossingsInfoPair countRealCrossings(Avoid::Polygon& poly,
bool polyIsConn, Avoid::Polygon& conn, size_t cIndex,
bool checkForBranchingSegments, const bool finalSegment,
PointSet *crossingPoints, PtOrderMap *pointOrders,
ConnRef *polyConnRef, ConnRef *connConnRef)
{
unsigned int crossingFlags = CROSSING_NONE;
if (checkForBranchingSegments)
{
size_t conn_pn = conn.size();
// 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.
double tolerance = (!polyIsConn) ? 0.00001 : 0.0;
splitBranchingSegments(poly, polyIsConn, conn, tolerance);
// cIndex is going to be the last, so take into account added points.
cIndex += (conn.size() - conn_pn);
}
COLA_ASSERT(cIndex >= 1);
COLA_ASSERT(cIndex < conn.size());
bool polyIsOrthogonal = (polyConnRef &&
(polyConnRef->routingType() == ConnType_Orthogonal));
bool connIsOrthogonal = (connConnRef &&
(connConnRef->routingType() == ConnType_Orthogonal));
size_t poly_size = poly.size();
int crossingCount = 0;
std::vector<Avoid::Point *> c_path;
std::vector<Avoid::Point *> p_path;
Avoid::Point& a1 = conn.ps[cIndex - 1];
Avoid::Point& a2 = conn.ps[cIndex];
//db_printf("a1: %g %g\n", a1.x, a1.y);
//db_printf("a2: %g %g\n", a2.x, a2.y);
for (size_t j = ((polyIsConn) ? 1 : 0); j < poly_size; ++j)
{
Avoid::Point& b1 = poly.ps[(j - 1 + poly_size) % poly_size];
Avoid::Point& b2 = poly.ps[j];
//db_printf("b1: %g %g\n", b1.x, b1.y);
//db_printf("b2: %g %g\n", b2.x, b2.y);
p_path.clear();
c_path.clear();
bool converging = false;
const bool a1_eq_b1 = (a1 == b1);
const bool a2_eq_b1 = (a2 == b1);
const bool a2_eq_b2 = (a2 == b2);
const bool a1_eq_b2 = (a1 == b2);
if ( (a1_eq_b1 && a2_eq_b2) ||
(a2_eq_b1 && a1_eq_b2) )
{
if (finalSegment)
{
converging = true;
}
else
{
// Route along same segment: no penalty. We detect
// crossovers when we see the segments diverge.
continue;
}
}
else if (a2_eq_b1 || a2_eq_b2 || a1_eq_b2)
{
// 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;
}
Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
// The segments share an endpoint -- a1==b1.
if (a2 == b0)
{
// 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.
COLA_ASSERT(converging || !a2_eq_b2);
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;
p_dir = p_dir_back ? -1 : 1;
trace_c = (int) cIndex;
trace_p = (int) j;
if (!p_dir_back)
{
if (finalSegment)
{
trace_p--;
}
else
{
trace_c--;
}
}
shared_path = true;
}
else if (cIndex >= 2)
{
Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
Avoid::Point& a0 = conn.ps[cIndex - 2];
//db_printf("a0: %g %g\n", a0.x, a0.y);
//db_printf("b0: %g %g\n", b0.x, b0.y);
if ((a0 == b2) || (a0 == b0))
{
// Determine direction we have to look through
// the points of connector b.
p_dir_back = (a0 == b0) ? true : false;
p_dir = p_dir_back ? -1 : 1;
trace_c = (int) cIndex;
trace_p = (int) (p_dir_back ? j : j - 2);
shared_path = true;
}
}
if (shared_path)
{
crossingFlags |= CROSSING_SHARES_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 ||
((trace_p >= 0) && (trace_p < (int) poly_size))) )
{
// If poly is a cluster boundary, then it is a closed
// poly-line and so it wraps arounds.
size_t index_p = (size_t)
((trace_p + (2 * poly_size)) % poly_size);
size_t index_c = (size_t) trace_c;
c_path.push_back(&conn.ps[index_c]);
p_path.push_back(&poly.ps[index_p]);
if ((c_path.size() > 1) &&
(conn.ps[index_c] != poly.ps[index_p]))
{
// Points don't match, so break out of loop.
break;
}
trace_c--;
trace_p += p_dir;
}
// Are there diverging points at the ends of the shared path.
bool front_same = (*(c_path.front()) == *(p_path.front()));
bool back_same = (*(c_path.back()) == *(p_path.back()));
size_t size = c_path.size();
// Check to see if these share a fixed segment.
if (polyIsOrthogonal && connIsOrthogonal)
{
size_t startPt = (front_same) ? 0 : 1;
if (c_path[startPt]->x == c_path[startPt + 1]->x)
{
// Vertical
double xPos = c_path[startPt]->x;
// See if this is inline with either the start
// or end point of both connectors.
if ( ((xPos == poly.ps[0].x) ||
(xPos == poly.ps[poly_size - 1].x)) &&
((xPos == conn.ps[0].x) ||
(xPos == conn.ps[cIndex].x)) )
{
crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT;
}
}
else
{
// Horizontal
double yPos = c_path[startPt]->y;
// See if this is inline with either the start
// or end point of both connectors.
if ( ((yPos == poly.ps[0].y) ||
(yPos == poly.ps[poly_size - 1].y)) &&
((yPos == conn.ps[0].y) ||
(yPos == conn.ps[cIndex].y)) )
{
crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT;
}
}
}
int prevTurnDir = -1;
int startCornerSide = 1;
int endCornerSide = 1;
if (!front_same)
{
// If there is a divergence at the beginning,
// then order the shared path based on this.
prevTurnDir = vecDir(*c_path[0], *c_path[1], *c_path[2]);
startCornerSide = Avoid::cornerSide(*c_path[0], *c_path[1],
*c_path[2], *p_path[0])
* segDir(*c_path[1], *c_path[2]);
}
if (!back_same)
{
// If there is a divergence at the end of the path,
// then order the shared path based on this.
prevTurnDir = vecDir(*c_path[size - 3],
*c_path[size - 2], *c_path[size - 1]);
endCornerSide = Avoid::cornerSide(*c_path[size - 3],
*c_path[size - 2], *c_path[size - 1],
*p_path[size - 1])
* segDir(*c_path[size - 3], *c_path[size - 2]);
}
else
{
endCornerSide = startCornerSide;
}
if (front_same)
{
startCornerSide = endCornerSide;
}
if (front_same || back_same)
{
crossingFlags |= CROSSING_SHARES_PATH_AT_END;
}
else if (polyIsOrthogonal && connIsOrthogonal)
{
int cStartDir = vecDir(*c_path[0], *c_path[1], *c_path[2]);
int pStartDir = vecDir(*p_path[0], *p_path[1], *p_path[2]);
if ((cStartDir != 0) && (cStartDir == -pStartDir))
{
// 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 *
segDir(*c_path[1], *c_path[2]);
}
else
{
int cEndDir = vecDir(*c_path[size - 3],
*c_path[size - 2], *c_path[size - 1]);
int pEndDir = vecDir(*p_path[size - 3],
*p_path[size - 2], *p_path[size - 1]);
if ((cEndDir != 0) && (cEndDir == -pEndDir))
{
// 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.
startCornerSide = -cEndDir * segDir(
*c_path[size - 3], *c_path[size - 2]);
}
}
}
#if 0
prevTurnDir = 0;
if (pointOrders)
{
// Return the ordering for the shared path.
COLA_ASSERT(c_path.size() > 0 || back_same);
size_t adj_size = (c_path.size() - ((back_same) ? 0 : 1));
for (size_t i = (front_same) ? 0 : 1; i < adj_size; ++i)
{
Avoid::Point& an = *(c_path[i]);
Avoid::Point& bn = *(p_path[i]);
int currTurnDir = ((i > 0) && (i < (adj_size - 1))) ?
vecDir(*c_path[i - 1], an,
*c_path[i + 1]) : 0;
VertID vID(an.id, true, an.vn);
if ( (currTurnDir == (-1 * prevTurnDir)) &&
(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.
reversed = !reversed;
}
bool orderSwapped = (*pointOrders)[an].addPoints(
&bn, &an, reversed);
if (orderSwapped)
{
// Reverse the order for later points.
reversed = !reversed;
}
prevTurnDir = currTurnDir;
}
}
#endif
if (pointOrders)
{
bool reversed = false;
size_t startPt = (front_same) ? 0 : 1;
// Orthogonal should always have at least one segment.
COLA_ASSERT(c_path.size() > (startPt + 1));
if (startCornerSide > 0)
{
reversed = !reversed;
}
int prevDir = 0;
// Return the ordering for the shared path.
COLA_ASSERT(c_path.size() > 0 || back_same);
size_t adj_size = (c_path.size() - ((back_same) ? 0 : 1));
for (size_t i = (front_same) ? 0 : 1; i < adj_size; ++i)
{
Avoid::Point& an = *(c_path[i]);
Avoid::Point& bn = *(p_path[i]);
COLA_ASSERT(an == bn);
int thisDir = prevDir;
if ((i > 0) && (*(c_path[i - 1]) == *(p_path[i - 1])))
{
thisDir = segDir(*c_path[i - 1], *c_path[i]);
}
if (thisDir != prevDir)
{
reversed = !reversed;
}
prevDir = thisDir;
if (i > startPt)
{
Avoid::Point& ap = *(c_path[i - 1]);
Avoid::Point& bp = *(p_path[i - 1]);
int orientation = (ap.x == an.x) ? 0 : 1;
//printf("prevOri %d\n", prevOrientation);
//printf("1: %X, %X\n", (int) &(bn), (int) &(an));
bool orderSwapped = (*pointOrders)[an].addPoints(
orientation,
std::make_pair(&bn, polyConnRef),
std::make_pair(&an, connConnRef),
reversed);
if (orderSwapped)
{
// Reverse the order for later points.
reversed = !reversed;
}
COLA_ASSERT(ap == bp);
//printf("2: %X, %X\n", (int) &bp, (int) &ap);
orderSwapped = (*pointOrders)[ap].addPoints(
orientation,
std::make_pair(&bp, polyConnRef),
std::make_pair(&ap, connConnRef),
reversed);
COLA_ASSERT(!orderSwapped);
}
}
}
#if 0
int ymod = -1;
if ((id.vn == 1) || (id.vn == 2))
{
// bottom.
ymod = +1;
}
int xmod = -1;
if ((id.vn == 0) || (id.vn == 1))
{
// right.
xmod = +1;
}
if(id.vn > 3)
{
xmod = ymod = 0;
if (id.vn == 4)
{
// right.
xmod = +1;
}
else if (id.vn == 5)
{
// bottom.
ymod = +1;
}
else if (id.vn == 6)
{
// left.
xmod = -1;
}
else if (id.vn == 7)
{
// top.
ymod = -1;
}
}
#endif
if (endCornerSide != startCornerSide)
{
// Mark that the shared path crosses.
//db_printf("shared path crosses.\n");
crossingCount += 1;
if (crossingPoints)
{
crossingPoints->insert(*c_path[1]);
}
}
crossingFlags |= CROSSING_TOUCHES;
}
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.
COLA_ASSERT(cIndex >= 2);
COLA_ASSERT(polyIsConn && (j >= 2));
Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
Avoid::Point& a0 = conn.ps[cIndex - 2];
int side1 = Avoid::cornerSide(a0, a1, a2, b0);
int side2 = Avoid::cornerSide(a0, a1, a2, b2);
if (side1 != side2)
{
// The connectors cross at this point.
//db_printf("cross.\n");
crossingCount += 1;
if (crossingPoints)
{
crossingPoints->insert(a1);
}
}
crossingFlags |= CROSSING_TOUCHES;
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.
bool reversedX = ((a0.x < a1.x) || (a2.x < a1.x));
bool reversedY = ((a0.y < a1.y) || (a2.y < a1.y));
// XXX: Why do we need to invert the reversed values
// here? Are they wrong for orthogonal points
// in the other places?
(*pointOrders)[b1].addPoints(0,
std::make_pair(&b1, polyConnRef),
std::make_pair(&a1, connConnRef),
!reversedX);
(*pointOrders)[b1].addPoints(1,
std::make_pair(&b1, polyConnRef),
std::make_pair(&a1, connConnRef),
!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.
Point cPt;
int intersectResult = Avoid::segmentIntersectPoint(
a1, a2, b1, b2, &(cPt.x), &(cPt.y));
if (intersectResult == Avoid::DO_INTERSECT)
{
if (!polyIsConn &&
((a1 == cPt) || (a2 == cPt) || (b1 == cPt) || (b2 == cPt)))
{
// XXX: This shouldn't actually happen, because these
// points should be added as bends to each line by
// splitBranchingSegments(). Thus, lets ignore them.
COLA_ASSERT(a1 != cPt);
COLA_ASSERT(a2 != cPt);
COLA_ASSERT(b1 != cPt);
COLA_ASSERT(b2 != cPt);
continue;
}
//db_printf("crossing lines:\n");
//db_printf("cPt: %g %g\n", cPt.x, cPt.y);
crossingCount += 1;
if (crossingPoints)
{
crossingPoints->insert(cPt);
}
}
}
}
//db_printf("crossingcount %d\n", crossingCount);
return std::make_pair(crossingCount, crossingFlags);
}
//============================================================================
}