1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2004-2009 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
25 //! @file router.h
26 //! @brief Contains the interface for the Router class.
29 #ifndef AVOID_ROUTER_H
30 #define AVOID_ROUTER_H
32 #include <list>
33 #include <utility>
34 #include <string>
36 #include "libavoid/shape.h"
37 #include "libavoid/viscluster.h"
38 #include "libavoid/graph.h"
39 #include "libavoid/timer.h"
40 #include "libavoid/connector.h"
42 #if defined(LINEDEBUG) || defined(ASTAR_DEBUG) || defined(LIBAVOID_SDL)
43 #include <SDL.h>
44 #ifndef LIBAVOID_SDL
45 #define LIBAVOID_SDL
46 #endif
47 #endif
50 namespace Avoid {
52 typedef std::list<unsigned int> IntList;
54 class ActionInfo;
55 typedef std::list<ActionInfo> ActionInfoList;
56 class ShapeRef;
58 //! @brief Flags that can be passed to the router during initialisation
59 //! to specify options.
60 enum RouterFlag
61 {
62 //! @brief This option specifies that the router should maintain the
63 //! structures necessary to allow poly-line connector routing.
64 PolyLineRouting = 1,
65 //! @brief This option specifies that the router should maintain the
66 //! structures necessary to allow orthogonal connector routing.
67 OrthogonalRouting = 2
68 };
71 static const unsigned int runningTo = 1;
72 static const unsigned int runningFrom = 2;
73 static const unsigned int runningToAndFrom = runningTo | runningFrom;
75 //! @brief Types of penalty cases that can be used to improve the quality
76 //! of the connector routes produced.
77 enum PenaltyType
78 {
79 //! @brief This penalty is applied for each segment in the connector
80 //! path beyond the first. This should always normally be set
81 //! when doing orthogonal routing to prevent step-like connector
82 //! paths.
83 segmentPenalty = 0,
84 //! @brief This penalty is applied in its full amount to tight acute
85 //! bends in the connector path. A smaller portion of the penalty
86 //! is applied for slight bends, i.e., where the bend is close to
87 //! 180 degrees. This is useful for polyline routing where there
88 //! is some evidence that tighter corners are worse for
89 //! readability, but that slight bends might not be so bad,
90 //! especially when smoothed by curves.
91 anglePenalty,
92 //! @brief This penalty is applied whenever a connector path crosses
93 //! another connector path. It takes shared paths into
94 //! consideration and the penalty is only applied if there
95 //! is an actual crossing.
96 //! @note This penalty is still experimental! It is not recommended
97 //! for normal use.
98 crossingPenalty,
99 //! @brief This penalty is applied whenever a connector path crosses
100 //! a cluster boundary.
101 //! @note This penalty is still experimental! It is not recommended
102 //! for normal use.
103 clusterCrossingPenalty,
104 //! @brief This penalty is applied whenever a connector path shares
105 //! some segments with an immovable portion of an existing
106 //! connector route (such as the first or last segment of a
107 //! connector).
108 //! @note This penalty is still experimental! It is not recommended
109 //! for normal use.
110 fixedSharedPathPenalty,
111 // Used for determining the size of the penalty array.
112 // This should always we the last value in the enum.
113 lastPenaltyMarker
114 };
117 static const double noPenalty = 0;
118 static const double chooseSensiblePenalty = -1;
121 //! @brief The Router class represents a libavoid router instance.
122 //!
123 //! Usually you would keep a separate Router instance for each diagram
124 //! or layout you have open in your application.
125 //
126 class Router {
127 public:
128 //! @brief Constructor for router instance.
129 //!
130 //! @param[in] flags One or more Avoid::RouterFlag options to
131 //! control the behaviour of the router.
132 Router(const unsigned int flags);
134 //! @brief Destructor for router instance.
135 //!
136 //! @note Destroying a router instance will delete all remaining
137 //! shapes and connectors, thereby invalidating any existing
138 //! pointers to them.
139 ~Router();
141 ShapeRefList shapeRefs;
142 ConnRefList connRefs;
143 ClusterRefList clusterRefs;
144 EdgeList visGraph;
145 EdgeList invisGraph;
146 EdgeList visOrthogGraph;
147 ContainsMap contains;
148 VertInfList vertices;
149 ContainsMap enclosingClusters;
151 bool PartialTime;
152 bool SimpleRouting;
153 bool ClusteredRouting;
155 // Poly-line routing options:
156 bool IgnoreRegions;
157 bool UseLeesAlgorithm;
158 bool InvisibilityGrph;
160 // General routing options:
161 bool SelectiveReroute;
163 bool PartialFeedback;
164 bool RubberBandRouting;
167 // Instrumentation:
168 Timer timers;
169 int st_checked_edges;
170 #ifdef LIBAVOID_SDL
171 SDL_Surface *avoid_screen;
172 #endif
174 //! @brief Allows setting of the behaviour of the router in regard
175 //! to transactions. This controls whether transactions are
176 //! used to queue changes and process them effeciently at once
177 //! or they are instead processed immediately.
178 //!
179 //! It is more efficient to perform actions like shape movement,
180 //! addition or deletion as batch tasks, and reroute the necessary
181 //! connectors just once after these actions have been performed.
182 //! For this reason, libavoid allows you to group such actions into
183 //! "transactions" that are processed efficiently when the
184 //! processTransaction() method is called.
185 //!
186 //! By default, the router will process all actions as tranactions.
187 //! If transactionUse() is set to false, then all actions will get
188 //! processed immediately, and cause immediate routing callbacks to
189 //! all affected connectors after each action.
190 //!
191 //! @param[in] transactions A boolean value specifying whether to
192 //! use transactions.
193 //!
194 void setTransactionUse(const bool transactions);
196 //! @brief Reports whether the router groups actions into transactions.
197 //!
198 //! @return A boolean value describing whether transactions are in use.
199 //!
200 //! @sa setTransactionUse
201 //! @sa processTransaction
202 //!
203 bool transactionUse(void) const;
205 //! @brief Finishes the current transaction and processes all the
206 //! queued object changes efficiently.
207 //!
208 //! This method will efficiently process all moves, additions and
209 //! deletions that have occurred since processTransaction() was
210 //! last called.
211 //!
212 //! If transactionUse() is false, then all actions will have been
213 //! processed immediately and this method will do nothing.
214 //!
215 //! @return A boolean value describing whether there were any actions
216 //! to process.
217 //!
218 //! @sa setTransactionUse
219 //!
220 bool processTransaction(void);
222 //! @brief Add a shape to the router scene.
223 //!
224 //! This shape will be considered to be an obstacle. Calling this
225 //! method will cause connectors intersecting the added shape to
226 //! be marked as needing to be rerouted.
227 //!
228 //! @param[in] shape Pointer reference to the shape being added.
229 //!
230 void addShape(ShapeRef *shape);
232 //! @brief Remove a shape from the router scene.
233 //!
234 //! Connectors that could have a better (usually shorter) path after
235 //! the removal of this shape will be marked as needing to be rerouted.
236 //!
237 //! @param[in] shape Pointer reference to the shape being removed.
238 //!
239 void removeShape(ShapeRef *shape);
241 //! @brief Move or resize an existing shape within the router scene.
242 //!
243 //! A new polygon for the shape can be given to effectively move or
244 //! resize the shape with the scene. Connectors that intersect the
245 //! new shape polygon, or that could have a better (usually shorter)
246 //! path after the change, will be marked as needing to be rerouted.
247 //!
248 //! @param[in] shape Pointer reference to the shape being
249 //! moved/resized.
250 //! @param[in] newPoly The new polygon boundary for the shape.
251 //! @param[in] first_move This option is used for some advanced
252 //! (currently undocumented) behaviour and
253 //! it should be ignored for the moment.
254 //!
255 void moveShape(ShapeRef *shape, const Polygon& newPoly,
256 const bool first_move = false);
258 //! @brief Move an existing shape within the router scene by a relative
259 //! distance.
260 //!
261 //! Connectors that intersect the shape's new position, or that could
262 //! have a better (usually shorter) path after the change, will be
263 //! marked as needing to be rerouted.
264 //!
265 //! @param[in] shape Pointer reference to the shape being moved.
266 //! @param[in] xDiff The distance to move the shape in the
267 //! x dimension.
268 //! @param[in] yDiff The distance to move the shape in the
269 //! y dimension.
270 //!
271 void moveShape(ShapeRef *shape, const double xDiff, const double yDiff);
273 //! @brief Sets a spacing distance for overlapping orthogonal
274 //! connectors to be nudged apart.
275 //!
276 //! By default, this distance is set to a value of 4.
277 //!
278 //! This method does not re-trigger post-processing of connectors.
279 //! The new distance will be used the next time rerouting is performed.
280 //!
281 //! @param[in] dist The distance to be used for orthogonal nudging.
282 //!
283 void setOrthogonalNudgeDistance(const double dist);
285 //! @brief Returns the spacing distance that overlapping orthogonal
286 //! connecotrs are nudged apart.
287 //!
288 //! @return The current spacing distance used for orthogonal nudging.
289 //!
290 double orthogonalNudgeDistance(void) const;
292 //! @brief Sets or removes penalty values that are applied during
293 //! connector routing.
294 //!
295 //! By default, libavoid will produce shortest path routes between
296 //! the source and destination points for each connector. There are
297 //! several penalties that can be applied during this stage to
298 //! improve the aesthetics of the routes generated. These different
299 //! penalties are specified and explained by the PenaltyType enum.
300 //!
301 //! If a value of zero or Avoid::noPenalty is given then the penalty
302 //! for this case will be removed. If no penalty argument (or a
303 //! negative value) is specified when calling this method, then a
304 //! sensible penalty value will be automatically chosen.
305 //!
306 //! @param[in] penType The type of penalty, a PenaltyType.
307 //! @param[in] penVal The value to be applied for each occurance
308 //! of the penalty case.
309 //!
310 void setRoutingPenalty(const PenaltyType penType,
311 const double penVal = chooseSensiblePenalty);
313 //! @brief Returns the current penalty value for a particular
314 //! routing penalty case.
315 //!
316 //! @param[in] penType The type of penalty, a PenaltyType.
317 //! @return The penalty value for the specified penalty case.
318 //!
319 double routingPenalty(const PenaltyType penType) const;
321 void addCluster(ClusterRef *cluster);
322 void delCluster(ClusterRef *cluster);
324 void attachedConns(IntList &conns, const unsigned int shapeId,
325 const unsigned int type);
326 void attachedShapes(IntList &shapes, const unsigned int shapeId,
327 const unsigned int type);
329 void markConnectors(ShapeRef *shape);
330 void generateContains(VertInf *pt);
331 void printInfo(void);
332 void outputInstanceToSVG(std::string filename = std::string());
333 unsigned int assignId(const unsigned int suggestedId);
334 void regenerateStaticBuiltGraph(void);
335 void destroyOrthogonalVisGraph(void);
336 void setStaticGraphInvalidated(const bool invalidated);
337 ConnType validConnType(const ConnType select = ConnType_None) const;
338 bool shapeInQueuedActionList(ShapeRef *shape) const;
339 double& penaltyRef(const PenaltyType penType);
340 bool existsOrthogonalPathOverlap(void);
341 bool existsOrthogonalTouchingCorners(void);
343 private:
344 friend class ConnRef;
346 void modifyConnector(ConnRef *conn);
347 void modifyConnector(ConnRef *conn, unsigned int type,
348 const ConnEnd &connEnd);
349 void removeQueuedConnectorActions(ConnRef *conn);
350 void newBlockingShape(const Polygon& poly, int pid);
351 void checkAllBlockedEdges(int pid);
352 void checkAllMissingEdges(void);
353 void adjustContainsWithAdd(const Polygon& poly, const int p_shape);
354 void adjustContainsWithDel(const int p_shape);
355 void adjustClustersWithAdd(const PolygonInterface& poly,
356 const int p_cluster);
357 void adjustClustersWithDel(const int p_cluster);
358 void rerouteAndCallbackConnectors(void);
359 bool idIsUnique(const unsigned int id) const;
360 void improveCrossings(void);
362 ActionInfoList actionList;
363 unsigned int _largestAssignedId;
364 bool _consolidateActions;
365 double _orthogonalNudgeDistance;
366 double _routingPenalties[lastPenaltyMarker];
368 public:
369 // Overall modes:
370 bool _polyLineRouting;
371 bool _orthogonalRouting;
373 bool _staticGraphInvalidated;
374 bool _inCrossingPenaltyReroutingStage;
375 };
377 }
381 #endif