/* * 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 */ //! @file router.h //! @brief Contains the interface for the Router class. #ifndef AVOID_ROUTER_H #define AVOID_ROUTER_H #include #include #include #include "libavoid/shape.h" #include "libavoid/viscluster.h" #include "libavoid/graph.h" #include "libavoid/timer.h" #include "libavoid/connector.h" #if defined(LINEDEBUG) || defined(ASTAR_DEBUG) || defined(LIBAVOID_SDL) #include #ifndef LIBAVOID_SDL #define LIBAVOID_SDL #endif #endif namespace Avoid { typedef std::list IntList; class ActionInfo; typedef std::list ActionInfoList; class ShapeRef; //! @brief Flags that can be passed to the router during initialisation //! to specify options. enum RouterFlag { //! @brief This option specifies that the router should maintain the //! structures necessary to allow poly-line connector routing. PolyLineRouting = 1, //! @brief This option specifies that the router should maintain the //! structures necessary to allow orthogonal connector routing. OrthogonalRouting = 2 }; static const unsigned int runningTo = 1; static const unsigned int runningFrom = 2; static const unsigned int runningToAndFrom = runningTo | runningFrom; //! @brief Types of penalty cases that can be used to improve the quality //! of the connector routes produced. enum PenaltyType { //! @brief This penalty is applied for each segment in the connector //! path beyond the first. This should always normally be set //! when doing orthogonal routing to prevent step-like connector //! paths. segmentPenalty = 0, //! @brief This penalty is applied in its full amount to tight acute //! bends in the connector path. A smaller portion of the penalty //! is applied for slight bends, i.e., where the bend is close to //! 180 degrees. This is useful for polyline routing where there //! is some evidence that tighter corners are worse for //! readability, but that slight bends might not be so bad, //! especially when smoothed by curves. anglePenalty, //! @brief This penalty is applied whenever a connector path crosses //! another connector path. It takes shared paths into //! consideration and the penalty is only applied if there //! is an actual crossing. //! @note This penalty is still experimental! It is not recommended //! for normal use. crossingPenalty, //! @brief This penalty is applied whenever a connector path crosses //! a cluster boundary. //! @note This penalty is still experimental! It is not recommended //! for normal use. clusterCrossingPenalty, //! @brief This penalty is applied whenever a connector path shares //! some segments with an immovable portion of an existing //! connector route (such as the first or last segment of a //! connector). //! @note This penalty is still experimental! It is not recommended //! for normal use. fixedSharedPathPenalty, // Used for determining the size of the penalty array. // This should always we the last value in the enum. lastPenaltyMarker }; static const double noPenalty = 0; static const double chooseSensiblePenalty = -1; //! @brief The Router class represents a libavoid router instance. //! //! Usually you would keep a separate Router instance for each diagram //! or layout you have open in your application. // class Router { public: //! @brief Constructor for router instance. //! //! @param[in] flags One or more Avoid::RouterFlag options to //! control the behaviour of the router. Router(const unsigned int flags); //! @brief Destructor for router instance. //! //! @note Destroying a router instance will delete all remaining //! shapes and connectors, thereby invalidating any existing //! pointers to them. ~Router(); ShapeRefList shapeRefs; ConnRefList connRefs; ClusterRefList clusterRefs; EdgeList visGraph; EdgeList invisGraph; EdgeList visOrthogGraph; ContainsMap contains; VertInfList vertices; ContainsMap enclosingClusters; bool PartialTime; bool SimpleRouting; bool ClusteredRouting; // Poly-line routing options: bool IgnoreRegions; bool UseLeesAlgorithm; bool InvisibilityGrph; // General routing options: bool SelectiveReroute; bool PartialFeedback; bool RubberBandRouting; // Instrumentation: Timer timers; int st_checked_edges; #ifdef LIBAVOID_SDL SDL_Surface *avoid_screen; #endif //! @brief Allows setting of the behaviour of the router in regard //! to transactions. This controls whether transactions are //! used to queue changes and process them effeciently at once //! or they are instead processed immediately. //! //! It is more efficient to perform actions like shape movement, //! addition or deletion as batch tasks, and reroute the necessary //! connectors just once after these actions have been performed. //! For this reason, libavoid allows you to group such actions into //! "transactions" that are processed efficiently when the //! processTransaction() method is called. //! //! By default, the router will process all actions as tranactions. //! If transactionUse() is set to false, then all actions will get //! processed immediately, and cause immediate routing callbacks to //! all affected connectors after each action. //! //! @param[in] transactions A boolean value specifying whether to //! use transactions. //! void setTransactionUse(const bool transactions); //! @brief Reports whether the router groups actions into transactions. //! //! @return A boolean value describing whether transactions are in use. //! //! @sa setTransactionUse //! @sa processTransaction //! bool transactionUse(void) const; //! @brief Finishes the current transaction and processes all the //! queued object changes efficiently. //! //! This method will efficiently process all moves, additions and //! deletions that have occurred since processTransaction() was //! last called. //! //! If transactionUse() is false, then all actions will have been //! processed immediately and this method will do nothing. //! //! @return A boolean value describing whether there were any actions //! to process. //! //! @sa setTransactionUse //! bool processTransaction(void); //! @brief Add a shape to the router scene. //! //! This shape will be considered to be an obstacle. Calling this //! method will cause connectors intersecting the added shape to //! be marked as needing to be rerouted. //! //! @param[in] shape Pointer reference to the shape being added. //! void addShape(ShapeRef *shape); //! @brief Remove a shape from the router scene. //! //! Connectors that could have a better (usually shorter) path after //! the removal of this shape will be marked as needing to be rerouted. //! //! @param[in] shape Pointer reference to the shape being removed. //! void removeShape(ShapeRef *shape); //! @brief Move or resize an existing shape within the router scene. //! //! A new polygon for the shape can be given to effectively move or //! resize the shape with the scene. Connectors that intersect the //! new shape polygon, or that could have a better (usually shorter) //! path after the change, will be marked as needing to be rerouted. //! //! @param[in] shape Pointer reference to the shape being //! moved/resized. //! @param[in] newPoly The new polygon boundary for the shape. //! @param[in] first_move This option is used for some advanced //! (currently undocumented) behaviour and //! it should be ignored for the moment. //! void moveShape(ShapeRef *shape, const Polygon& newPoly, const bool first_move = false); //! @brief Move an existing shape within the router scene by a relative //! distance. //! //! Connectors that intersect the shape's new position, or that could //! have a better (usually shorter) path after the change, will be //! marked as needing to be rerouted. //! //! @param[in] shape Pointer reference to the shape being moved. //! @param[in] xDiff The distance to move the shape in the //! x dimension. //! @param[in] yDiff The distance to move the shape in the //! y dimension. //! void moveShape(ShapeRef *shape, const double xDiff, const double yDiff); //! @brief Sets a spacing distance for overlapping orthogonal //! connectors to be nudged apart. //! //! By default, this distance is set to a value of 4. //! //! This method does not re-trigger post-processing of connectors. //! The new distance will be used the next time rerouting is performed. //! //! @param[in] dist The distance to be used for orthogonal nudging. //! void setOrthogonalNudgeDistance(const double dist); //! @brief Returns the spacing distance that overlapping orthogonal //! connecotrs are nudged apart. //! //! @return The current spacing distance used for orthogonal nudging. //! double orthogonalNudgeDistance(void) const; //! @brief Sets or removes penalty values that are applied during //! connector routing. //! //! By default, libavoid will produce shortest path routes between //! the source and destination points for each connector. There are //! several penalties that can be applied during this stage to //! improve the aesthetics of the routes generated. These different //! penalties are specified and explained by the PenaltyType enum. //! //! If a value of zero or Avoid::noPenalty is given then the penalty //! for this case will be removed. If no penalty argument (or a //! negative value) is specified when calling this method, then a //! sensible penalty value will be automatically chosen. //! //! @param[in] penType The type of penalty, a PenaltyType. //! @param[in] penVal The value to be applied for each occurance //! of the penalty case. //! void setRoutingPenalty(const PenaltyType penType, const double penVal = chooseSensiblePenalty); //! @brief Returns the current penalty value for a particular //! routing penalty case. //! //! @param[in] penType The type of penalty, a PenaltyType. //! @return The penalty value for the specified penalty case. //! double routingPenalty(const PenaltyType penType) const; void addCluster(ClusterRef *cluster); void delCluster(ClusterRef *cluster); void attachedConns(IntList &conns, const unsigned int shapeId, const unsigned int type); void attachedShapes(IntList &shapes, const unsigned int shapeId, const unsigned int type); void markConnectors(ShapeRef *shape); void generateContains(VertInf *pt); void printInfo(void); void outputInstanceToSVG(std::string filename = std::string()); unsigned int assignId(const unsigned int suggestedId); void regenerateStaticBuiltGraph(void); void destroyOrthogonalVisGraph(void); void setStaticGraphInvalidated(const bool invalidated); ConnType validConnType(const ConnType select = ConnType_None) const; bool shapeInQueuedActionList(ShapeRef *shape) const; double& penaltyRef(const PenaltyType penType); bool existsOrthogonalPathOverlap(void); bool existsOrthogonalTouchingCorners(void); private: friend class ConnRef; void modifyConnector(ConnRef *conn); void modifyConnector(ConnRef *conn, unsigned int type, const ConnEnd &connEnd); void removeQueuedConnectorActions(ConnRef *conn); void newBlockingShape(const Polygon& poly, int pid); void checkAllBlockedEdges(int pid); void checkAllMissingEdges(void); void adjustContainsWithAdd(const Polygon& poly, const int p_shape); void adjustContainsWithDel(const int p_shape); void adjustClustersWithAdd(const PolygonInterface& poly, const int p_cluster); void adjustClustersWithDel(const int p_cluster); void rerouteAndCallbackConnectors(void); bool idIsUnique(const unsigned int id) const; void improveCrossings(void); ActionInfoList actionList; unsigned int _largestAssignedId; bool _consolidateActions; double _orthogonalNudgeDistance; double _routingPenalties[lastPenaltyMarker]; public: // Overall modes: bool _polyLineRouting; bool _orthogonalRouting; bool _staticGraphInvalidated; bool _inCrossingPenaltyReroutingStage; }; } #endif