From b78c2dddf7cf723ab55760e964e2ab3b95001749 Mon Sep 17 00:00:00 2001 From: mjwybrow Date: Thu, 9 Aug 2007 04:10:02 +0000 Subject: [PATCH] 2006-08-09 Michael Wybrow * src/libavoid/shape.cpp, src/libavoid/router.cpp, src/libavoid/README, src/libavoid/router.h, src/libavoid/geometry.cpp: Some minor upstream changes to the libavoid library. It now matches Inkscape and uses the correct winding direction. * src/conn-avoid-ref.cpp: Remove a 'TODO' and hack adjusting winding directions before passing object convex hulls to libavoid. --- src/conn-avoid-ref.cpp | 22 +--------------- src/libavoid/README | 29 ++++++++++++++++++--- src/libavoid/geometry.cpp | 53 +++++++++++++++++++-------------------- src/libavoid/router.cpp | 48 +++++++++++++++++++++++------------ src/libavoid/router.h | 1 + src/libavoid/shape.cpp | 8 +++--- 6 files changed, 89 insertions(+), 72 deletions(-) diff --git a/src/conn-avoid-ref.cpp b/src/conn-avoid-ref.cpp index 864eadbba..67538fb77 100644 --- a/src/conn-avoid-ref.cpp +++ b/src/conn-avoid-ref.cpp @@ -203,27 +203,7 @@ static Avoid::Polygn avoid_item_poly(SPItem const *item) poly = Avoid::newPoly(4); for (unsigned n = 0; n < 4; ++n) { - // TODO: I think the winding order in libavoid or inkscape might - // be backwards, probably due to the inverse y co-ordinates - // used for the screen. The '3 - n' reverses the order. - /* On "correct" winding order: Winding order of NR::Rect::corner is in a positive - * direction, like libart. "Positive direction" means the same as in most of Inkscape and - * SVG: if you visualize y as increasing upwards, as is the convention in mathematics, then - * positive angle is visualized as anticlockwise, as in mathematics; so if you visualize y - * as increasing downwards, as is common outside of mathematics, then positive angle - * direction is visualized as clockwise, as is common outside of mathematics. This - * convention makes it easier mix pure mathematics code with graphics code: the important - * thing when mixing code is that the number values stored in variables (representing y - * coordinate, angle) match up; variables store numbers, not visualized positions, and the - * programmer is free to switch between visualizations when thinking about a given piece of - * code. - * - * MathWorld, libart and NR::Rect::corner all seem to take positive winding (i.e. winding - * that yields +1 winding number inside a simple closed shape) to mean winding in a - * positive angle. This, together with the observation that variables store numbers rather - * than positions, suggests that NR::Rect::corner uses the right direction. - */ - NR::Point hullPoint = rExpandedHull.corner(3 - n); + NR::Point hullPoint = rExpandedHull.corner(n); poly.ps[n].x = hullPoint[NR::X]; poly.ps[n].y = hullPoint[NR::Y]; } diff --git a/src/libavoid/README b/src/libavoid/README index ada0e9908..d18de589f 100644 --- a/src/libavoid/README +++ b/src/libavoid/README @@ -1,5 +1,26 @@ -This directory contains libavoid-0.1. It has been included here since it is -a new library without wide availablity. +libavoid - Fast, Incremental, Object-avoiding Line Router +Copyright (C) 2004-2007 Michael Wybrow + +A cross-platform C++ library providing fast, object-avoiding connector +routing for use in interactive diagram editors. + + +This is an alpha release. There is currently no documentation due to the +fact that orthogonal connectors are being worked on as well as other features +such as connector crossing avoidance. Once these features are present, +documentation will be added for the interface. At the same time, the build +system will be cleaned up to use the configure/automake tools, and the first +"offical" release of libavoid will be made. + +libavoid is currently used in the prototype research diagram editor "Dunnart": + http://www.csse.monash.edu.au/~mwybrow/dunnart/ +As well as the professional open-source vector graphics editor "Inkscape": + http://www.inkscape.org/ + +The algorithms used for the connector routing are described in: + + M. Wybrow, K. Marriott, and P.J. Stuckey. Incremental connector routing. + In Proceedings of 13th International Symposium on Graph Drawing, LNCS 3843, + pages 446-457. Springer-Verlag, 2006. + http://www.csse.monash.edu.au/~mwybrow/papers/wybrow-gd-2005.pdf -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/geometry.cpp b/src/libavoid/geometry.cpp index 8f58d4481..15840c381 100644 --- a/src/libavoid/geometry.cpp +++ b/src/libavoid/geometry.cpp @@ -133,58 +133,57 @@ bool segmentIntersect(const Point& a, const Point& b, const Point& c, // 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(bool IgnoreRegions, const Point& a0, const Point& a1, const Point& a2, const Point& b) { + // r is a0--a1 + // s is a1--a2 + int rSide = vecDir(b, a0, a1); int sSide = vecDir(b, a1, a2); - bool rOutOn = (rSide >= 0); - bool sOutOn = (sSide >= 0); + bool rOutOn = (rSide <= 0); + bool sOutOn = (sSide <= 0); - bool rOut = (rSide > 0); - bool sOut = (sSide > 0); + bool rOut = (rSide < 0); + bool sOut = (sSide < 0); if (vecDir(a0, a1, a2) > 0) { - // Concave at a1: + // Convex at a1: // // !rO rO - // !sO !sO + // sO sO // - // +---s--- + // ---s---+ // | // !rO r rO - // sO | sO + // !sO | !sO // // - return (IgnoreRegions ? false : (rOutOn && sOutOn)); + if (IgnoreRegions) + { + return (rOutOn && !sOut) || (!rOut && sOutOn); + } + return (rOutOn || sOutOn); } else { - // Convex at a1: + // Concave at a1: // // !rO rO - // sO sO + // !sO !sO // - // ---s---+ + // +---s--- // | // !rO r rO - // !sO | !sO + // sO | sO // // - if (IgnoreRegions) - { - return (rOutOn && !sOut) || (!rOut && sOutOn); - } - return (rOutOn || sOutOn); + return (IgnoreRegions ? false : (rOutOn && sOutOn)); } } @@ -192,12 +191,12 @@ bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1, // Gives the side of a corner that a point lies on: // 1 anticlockwise // -1 clockwise -// e.g. /| -// /s2 -1 / |s1 +// e.g. /|s2 +// /s3 -1 / | // / / | -// 1 |s1 -1 / 1 | -1 +// 1 |s2 -1 / 1 | -1 // | / | -// |s0 s2/ |s0 +// |s1 s3/ |s1 // int cornerSide(const Point &c1, const Point &c2, const Point &c3, const Point& p) @@ -286,7 +285,7 @@ bool inPoly(const Polygn& poly, const Point& q) { // point index; i1 = i-1 mod n int prev = (i + n - 1) % n; - if (vecDir(P[prev], P[i], q) == 1) + if (vecDir(P[prev], P[i], q) == -1) { return false; } diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp index 6570962a9..4b1652ca0 100644 --- a/src/libavoid/router.cpp +++ b/src/libavoid/router.cpp @@ -59,6 +59,7 @@ class MoveInfo { Router::Router() : PartialTime(false) + , SimpleRouting(false) , segmt_penalty(0) , angle_penalty(0) , crossing_penalty(200) @@ -113,6 +114,21 @@ void Router::delShape(ShapeRef *shape) { 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(); @@ -154,9 +170,12 @@ void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move) { if ((*it)->shape->id() == id) { - fprintf(stderr, - "warning: multiple moves requested for shape %d.\n", - (int) 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); @@ -179,7 +198,8 @@ void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move) void Router::processMoves(void) { - if (moveList.empty()) + // If SimpleRouting, then don't update yet. + if (moveList.empty() || SimpleRouting) { return; } @@ -505,9 +525,6 @@ void Router::adjustContainsWithDel(const int p_shape) } -#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) @@ -570,8 +587,8 @@ void Router::markConnectors(ShapeRef *shape) 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) { @@ -582,8 +599,8 @@ void Router::markConnectors(ShapeRef *shape) 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 { @@ -630,8 +647,8 @@ void Router::markConnectors(ShapeRef *shape) 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); } @@ -664,9 +681,8 @@ void Router::markConnectors(ShapeRef *shape) //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); diff --git a/src/libavoid/router.h b/src/libavoid/router.h index a331527d5..597f48c5e 100644 --- a/src/libavoid/router.h +++ b/src/libavoid/router.h @@ -62,6 +62,7 @@ class Router { VertInfList vertices; bool PartialTime; + bool SimpleRouting; double segmt_penalty; double angle_penalty; double crossing_penalty; diff --git a/src/libavoid/shape.cpp b/src/libavoid/shape.cpp index 2b241b728..c0ff2f6e8 100644 --- a/src/libavoid/shape.cpp +++ b/src/libavoid/shape.cpp @@ -206,10 +206,10 @@ void ShapeRef::boundingBox(BBox& bbox) { const Point& p = _poly.ps[i]; - a.x = (p.x < a.x) ? p.x : a.x; - a.y = (p.y < a.y) ? p.y : a.y; - b.x = (p.x > b.x) ? p.x : b.x; - b.y = (p.y > b.y) ? p.y : b.y; + a.x = std::min(p.x, a.x); + a.y = std::min(p.y, a.y); + b.x = std::max(p.x, b.x); + b.y = std::max(p.y, b.y); } } -- 2.30.2