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-2015 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 23 */ 24 25 //! @file router.h 26 //! @brief Contains the interface for the Router class. 27 28 29 #ifndef AVOID_ROUTER_H 30 #define AVOID_ROUTER_H 31 32 #include <ctime> 33 #include <list> 34 #include <utility> 35 #include <string> 36 37 #include "libavoid/dllexport.h" 38 #include "libavoid/connector.h" 39 #include "libavoid/vertices.h" 40 #include "libavoid/graph.h" 41 #include "libavoid/timer.h" 42 #include "libavoid/hyperedge.h" 43 #include "libavoid/actioninfo.h" 44 #include "libavoid/hyperedgeimprover.h" 45 46 47 namespace Avoid { 48 49 // LineReps: Used for highlighting certain areas in debugging output. 50 struct LineRep 51 { 52 Point begin; 53 Point end; 54 }; 55 typedef std::list<LineRep> LineReps; 56 57 58 typedef std::list<unsigned int> IntList; 59 60 class ShapeRef; 61 class JunctionRef; 62 class ClusterRef; 63 typedef std::list<ClusterRef *> ClusterRefList; 64 class Obstacle; 65 typedef std::list<Obstacle *> ObstacleList; 66 class DebugHandler; 67 68 //! @brief Flags that can be passed to the router during initialisation 69 //! to specify options. 70 enum RouterFlag 71 { 72 //! @brief This option specifies that the router should maintain the 73 //! structures necessary to allow poly-line connector routing. 74 PolyLineRouting = 1, 75 //! @brief This option specifies that the router should maintain the 76 //! structures necessary to allow orthogonal connector routing. 77 OrthogonalRouting = 2 78 }; 79 80 81 static const unsigned int runningTo = 1; 82 static const unsigned int runningFrom = 2; 83 static const unsigned int runningToAndFrom = runningTo | runningFrom; 84 85 //! @brief Types of routing parameters and penalties that can be used to 86 //! tailor the style and improve the quality of the connector 87 //! routes produced. 88 enum RoutingParameter 89 { 90 //! @brief This penalty is applied for each segment in the connector 91 //! path beyond the first. This should always normally be set 92 //! when doing orthogonal routing to prevent step-like connector 93 //! paths. 94 //! @note This penalty must be set (i.e., be greater than zero) in 95 //! order for orthogonal connector nudging to be performed, since 96 //! this requires reasonable initial routes. 97 segmentPenalty = 0, 98 99 //! @brief This penalty is applied in its full amount to tight acute 100 //! bends in the connector path. A smaller portion of the penalty 101 //! is applied for slight bends, i.e., where the bend is close to 102 //! 180 degrees. This is useful for polyline routing where there 103 //! is some evidence that tighter corners are worse for 104 //! readability, but that slight bends might not be so bad, 105 //! especially when smoothed by curves. 106 anglePenalty, 107 108 //! @brief This penalty is applied whenever a connector path crosses 109 //! another connector path. It takes shared paths into 110 //! consideration and the penalty is only applied if there 111 //! is an actual crossing. 112 //! @note This penalty is still experimental! It is not recommended 113 //! for normal use. 114 crossingPenalty, 115 116 //! @brief This penalty is applied whenever a connector path crosses 117 //! a cluster boundary. 118 //! @note This penalty is still experimental! It is not recommended 119 //! for normal use. 120 //! @note This penalty is very slow. You can override the method 121 //! Router::shouldContinueTransactionWithProgress() to check 122 //! progress and possibly cancel overly slow transactions. 123 clusterCrossingPenalty, 124 125 //! @brief This penalty is applied whenever a connector path shares 126 //! some segments with an immovable portion of an existing 127 //! connector route (such as the first or last segment of a 128 //! connector). 129 //! @note This penalty is still experimental! It is not recommended 130 //! for normal use. 131 fixedSharedPathPenalty, 132 133 //! @brief This penalty is applied to port selection choice when the 134 //! other end of the connector being routed does not appear in 135 //! any of the 90 degree visibility cones centered on the 136 //! visibility directions for the port. 137 //! @note This penalty is still experimental! It is not recommended 138 //! for normal use. 139 //! @note This penalty is very slow. You can override the method 140 //! Router::shouldContinueTransactionWithProgress() to check 141 //! progress and possibly cancel overly slow transactions. 142 portDirectionPenalty, 143 144 //! @brief This parameter defines the spacing distance that will be added 145 //! to the sides of each shape when determining obstacle sizes for 146 //! routing. This controls how closely connectors pass shapes, and 147 //! can be used to prevent connectors overlapping with shape 148 //! boundaries. By default, this distance is set to a value of 0. 149 shapeBufferDistance, 150 151 //! @brief This parameter defines the spacing distance that will be used 152 //! for nudging apart overlapping corners and line segments of 153 //! connectors. By default, this distance is set to a value of 4. 154 idealNudgingDistance, 155 156 //! @brief This penalty is applied whenever a connector path travels 157 //! in the direction opposite of the destination from the source 158 //! endpoint. By default this penalty is set to zero. This 159 //! shouldn't be needed in most cases but can be useful if you 160 //! use penalties such as ::crossingPenalty which cause connectors 161 //! to loop around obstacles. 162 reverseDirectionPenalty, 163 164 // Used for determining the size of the routing parameter array. 165 // This should always we the last value in the enum. 166 lastRoutingParameterMarker 167 }; 168 169 // Backwards compatibility 170 typedef enum RoutingParameter PenaltyType; 171 172 173 //! @brief Types of routing options that can be enabled. 174 enum RoutingOption 175 { 176 //! This option causes the final segments of connectors, which are 177 //! attached to shapes, to be nudged apart. Usually these segments 178 //! are fixed, since they are considered to be attached to ports. 179 //! 180 //! Defaults to false. 181 //! 182 //! This option also causes routes running through the same checkpoint 183 //! to be nudged apart. 184 //! 185 //! This option has no effect if ::nudgeSharedPathsWithCommonEndPoint is 186 //! set to false, 187 //! 188 //! @note This will allow routes to be nudged up to the bounds of shapes. 189 //! 190 nudgeOrthogonalSegmentsConnectedToShapes = 0, 191 192 //! This option causes hyperedge routes to be locally improved fixing 193 //! obviously bad paths. As part of this process libavoid will 194 //! effectively move junctions, setting new ideal positions which can be 195 //! accessed via JunctionRef::recommendedPosition() for each junction. 196 //! 197 //! Defaults to true. 198 //! 199 //! This will not add or remove junctions, so will keep the hyperedge 200 //! topology the same. Better routes can be achieved by enabling the 201 //! ::improveHyperedgeRoutesMovingAddingAndDeletingJunctions option. 202 //! 203 //! If initial sensible positions for junctions in hyperedges are not 204 //! known you can register those hyperedges with the HyperedgeRerouter 205 //! class for complete rerouting. 206 //! 207 //! @sa improveHyperedgeRoutesMovingAddingAndDeletingJunctions 208 //! @sa Router::hyperedgeRerouter() 209 //! 210 improveHyperedgeRoutesMovingJunctions, 211 212 //! This option penalises and attempts to reroute orthogonal shared 213 //! connector paths terminating at a common junction or shape 214 //! connection pin. When multiple connector paths enter or leave 215 //! the same side of a junction (or shape pin), the router will 216 //! attempt to reroute these to different sides of the junction or 217 //! different shape pins. 218 //! 219 //! Defaults to false. 220 //! 221 //! This option depends on the ::fixedSharedPathPenalty penalty having 222 //! been set. 223 //! 224 //! @sa fixedSharedPathPenalty 225 //! @note This option is still experimental! It is not recommended 226 //! for normal use. 227 //! 228 penaliseOrthogonalSharedPathsAtConnEnds, 229 230 //! This option can be used to control whether collinear line 231 //! segments that touch just at their ends will be nudged apart. 232 //! The overlap will usually be resolved in the other dimension, 233 //! so this is not usually required. 234 //! 235 //! Defaults to false. 236 //! 237 nudgeOrthogonalTouchingColinearSegments, 238 239 //! This option can be used to control whether the router performs 240 //! a preprocessing step before orthogonal nudging where is tries 241 //! to unify segments and centre them in free space. This 242 //! generally results in better quality ordering and nudging. 243 //! 244 //! Defaults to true. 245 //! 246 //! You may wish to turn this off for large examples where it 247 //! can be very slow and will make little difference. 248 //! 249 performUnifyingNudgingPreprocessingStep, 250 251 //! This option causes hyperedge routes to be locally improved fixing 252 //! obviously bad paths. 253 //! 254 //! It can cause junctions and connectors to be added or removed from 255 //! hyperedges. To get details of these changes for each connector you can 256 //! call Router::newAndDeletedObjectListsFromHyperedgeImprovement(). 257 //! 258 //! As part of this process libavoid will effectively move junctions by 259 //! setting new ideal positions for each remaining or added junction, 260 //! which can be read from JunctionRef::recommendedPosition() for each 261 //! junction. 262 //! 263 //! Defaults to false. 264 //! 265 //! If set, this option overrides the ::improveHyperedgeRoutesMovingJunctions 266 //! option. 267 //! 268 //! If initial sensible positions for junctions in hyperedges are not 269 //! known you can register those hyperedges with the HyperedgeRerouter 270 //! class for complete rerouting. 271 //! 272 //! @sa improveHyperedgeRoutesMovingJunctions 273 //! @sa Router::hyperedgeRerouter() 274 //! 275 improveHyperedgeRoutesMovingAddingAndDeletingJunctions, 276 277 //! This option determines whether intermediate segments of connectors that 278 //! are attached to common endpoints will be nudged apart. Usually these 279 //! segments get nudged apart, but you may want to turn this off if you would 280 //! prefer that entire shared paths terminating at a common end point should 281 //! overlap. 282 //! 283 //! Defaults to true. 284 //! 285 nudgeSharedPathsWithCommonEndPoint, 286 287 288 // Used for determining the size of the routing options array. 289 // This should always we the last value in the enum. 290 lastRoutingOptionMarker 291 }; 292 293 //! @brief Types of routing phases reported by 294 //! Router::shouldContinueTransactionWithProgress(). 295 //! 296 //! This phases will occur in the order given here, but each phase may take 297 //! varying amounts of time. 298 //! 299 enum TransactionPhases 300 { 301 //! @brief The orthogonal visibility graph is built by conducting a 302 //! scan in each dimension. This is the x-dimension. 303 TransactionPhaseOrthogonalVisibilityGraphScanX = 1, 304 //! @brief The orthogonal visibility graph is built by conducting a 305 //! scan in each dimension. This is the y-dimension. 306 TransactionPhaseOrthogonalVisibilityGraphScanY, 307 //! @brief Initial routes are searched for in the visibility graph. 308 TransactionPhaseRouteSearch, 309 //! @brief With crossing penalties enabled, crossing detection is 310 //! performed to find all crossings. 311 TransactionPhaseCrossingDetection, 312 //! @brief Crossing connectors are rerouted to search for better routes. 313 TransactionPhaseRerouteSearch, 314 //! @brief Orthogonal edge segments are nudged apart in the x-dimension. 315 TransactionPhaseOrthogonalNudgingX, 316 //! @brief Orthogonal edge segments are nudged apart in the y-dimension. 317 TransactionPhaseOrthogonalNudgingY, 318 //! @brief Not a real phase, but represents the router is finished (or has 319 //! aborted) the transaction and you may interact with is again. 320 TransactionPhaseCompleted 321 }; 322 323 // NOTE: This is an internal helper class that should not be used by the user. 324 // 325 // This class allows edges in the visibility graph to store a 326 // pointer to a boolean registering when a connector needs to 327 // reroute, while allowing connectors to be deleted without 328 // needing to scan and remove these references from the visibility 329 // graph. Instead the bool is stored in this delegate and the 330 // connector is alerted later, so long as it hasn't since been 331 // deleted. 332 class ConnRerouteFlagDelegate { 333 public: 334 ConnRerouteFlagDelegate(); 335 ~ConnRerouteFlagDelegate(); 336 bool *addConn(ConnRef *conn); 337 void removeConn(ConnRef *conn); 338 void alertConns(void); 339 private: 340 std::list<std::pair<ConnRef *, bool> > m_mapping; 341 }; 342 343 static const double zeroParamValue = 0; 344 static const double chooseSensibleParamValue = -1; 345 346 // NOTE: This is an internal helper class that should not be used by the user. 347 // 348 // It is used by libtopology to add additional functionality to libavoid 349 // while keeping libavoid dependency free. 350 class TopologyAddonInterface 351 { 352 public: TopologyAddonInterface()353 TopologyAddonInterface() 354 { 355 } ~TopologyAddonInterface()356 virtual ~TopologyAddonInterface() 357 { 358 } clone(void)359 virtual TopologyAddonInterface *clone(void) const 360 { 361 return new TopologyAddonInterface(*this); 362 } 363 improveOrthogonalTopology(Router * router)364 virtual void improveOrthogonalTopology(Router *router) 365 { 366 (void)(router); // Avoid unused parameter warning. 367 } outputCode(FILE * fp)368 virtual bool outputCode(FILE *fp) const 369 { 370 (void)(fp); // Avoid unused parameter warning. 371 return false; 372 } outputDeletionCode(FILE * fp)373 virtual bool outputDeletionCode(FILE *fp) const 374 { 375 (void)(fp); // Avoid unused parameter warning. 376 return false; 377 } 378 }; 379 380 381 //! @brief The Router class represents a libavoid router instance. 382 //! 383 //! Usually you would keep a separate Router instance for each diagram 384 //! or layout you have open in your application. 385 // 386 class AVOID_EXPORT Router { 387 public: 388 //! @brief Constructor for router instance. 389 //! 390 //! @param[in] flags One or more Avoid::RouterFlag options to 391 //! control the behaviour of the router. 392 Router(const unsigned int flags); 393 394 //! @brief Destructor for router instance. 395 //! 396 //! @note Destroying a router instance will delete all remaining 397 //! shapes and connectors, thereby invalidating any existing 398 //! pointers to them. 399 virtual ~Router(); 400 401 ObstacleList m_obstacles; 402 ConnRefList connRefs; 403 ClusterRefList clusterRefs; 404 EdgeList visGraph; 405 EdgeList invisGraph; 406 EdgeList visOrthogGraph; 407 ContainsMap contains; 408 VertInfList vertices; 409 ContainsMap enclosingClusters; 410 411 bool PartialTime; 412 bool SimpleRouting; 413 bool ClusteredRouting; 414 415 // Poly-line routing options: 416 bool IgnoreRegions; 417 bool UseLeesAlgorithm; 418 bool InvisibilityGrph; 419 420 // General routing options: 421 bool SelectiveReroute; 422 423 bool PartialFeedback; 424 bool RubberBandRouting; 425 426 427 // Instrumentation: 428 #ifdef AVOID_PROFILE 429 Timer timers; 430 #endif 431 int st_checked_edges; 432 433 //! @brief Allows setting of the behaviour of the router in regard 434 //! to transactions. This controls whether transactions are 435 //! used to queue changes and process them efficiently at once 436 //! or they are instead processed immediately. 437 //! 438 //! It is more efficient to perform actions like shape movement, 439 //! addition or deletion as batch tasks, and reroute the necessary 440 //! connectors just once after these actions have been performed. 441 //! For this reason, libavoid allows you to group such actions into 442 //! "transactions" that are processed efficiently when the 443 //! processTransaction() method is called. 444 //! 445 //! By default, the router will process all actions as transactions. 446 //! If transactionUse() is set to false, then all actions will get 447 //! processed immediately, and cause immediate routing callbacks to 448 //! all affected connectors after each action. 449 //! 450 //! @param[in] transactions A boolean value specifying whether to 451 //! use transactions. 452 //! 453 void setTransactionUse(const bool transactions); 454 455 //! @brief Reports whether the router groups actions into transactions. 456 //! 457 //! @return A boolean value describing whether transactions are in use. 458 //! 459 //! @sa setTransactionUse 460 //! @sa processTransaction 461 //! 462 bool transactionUse(void) const; 463 464 //! @brief Finishes the current transaction and processes all the 465 //! queued object changes efficiently. 466 //! 467 //! This method will efficiently process all moves, additions and 468 //! deletions that have occurred since processTransaction() was 469 //! last called. 470 //! 471 //! If transactionUse() is false, then all actions will have been 472 //! processed immediately and this method will do nothing. 473 //! 474 //! @return A boolean value describing whether there were any actions 475 //! to process. 476 //! 477 //! @sa setTransactionUse 478 //! 479 bool processTransaction(void); 480 481 //! @brief Delete a shape from the router scene. 482 //! 483 //! Connectors that could have a better (usually shorter) path after 484 //! the removal of this shape will be marked as needing to be rerouted. 485 //! 486 //! If the router is using transactions, then this action will occur 487 //! the next time Router::processTransaction() is called. See 488 //! Router::setTransactionUse() for more information. 489 //! 490 //! You should not use the shape reference again after this call. 491 //! The router will handle freeing of the shape's memory. 492 //! 493 //! @param[in] shape Pointer reference to the shape being removed. 494 //! 495 void deleteShape(ShapeRef *shape); 496 497 //! @brief Move or resize an existing shape within the router scene. 498 //! 499 //! A new polygon for the shape can be given to effectively move or 500 //! resize the shape with the scene. Connectors that intersect the 501 //! new shape polygon, or that could have a better (usually shorter) 502 //! path after the change, will be marked as needing to be rerouted. 503 //! 504 //! If the router is using transactions, then this action will occur 505 //! the next time Router::processTransaction() is called. See 506 //! Router::setTransactionUse() for more information. 507 //! 508 //! @param[in] shape Pointer reference to the shape being 509 //! moved/resized. 510 //! @param[in] newPoly The new polygon boundary for the shape. 511 //! @param[in] first_move This option is used for some advanced 512 //! (currently undocumented) behaviour and 513 //! it should be ignored for the moment. 514 //! 515 void moveShape(ShapeRef *shape, const Polygon& newPoly, 516 const bool first_move = false); 517 518 //! @brief Move an existing shape within the router scene by a relative 519 //! distance. 520 //! 521 //! Connectors that intersect the shape's new position, or that could 522 //! have a better (usually shorter) path after the change, will be 523 //! marked as needing to be rerouted. 524 //! 525 //! If the router is using transactions, then this action will occur 526 //! the next time Router::processTransaction() is called. See 527 //! Router::setTransactionUse() for more information. 528 //! 529 //! @param[in] shape Pointer reference to the shape being moved. 530 //! @param[in] xDiff The distance to move the shape in the 531 //! x dimension. 532 //! @param[in] yDiff The distance to move the shape in the 533 //! y dimension. 534 //! 535 void moveShape(ShapeRef *shape, const double xDiff, const double yDiff); 536 537 //! @brief Remove a junction from the router scene. 538 //! 539 //! If the router is using transactions, then this action will occur 540 //! the next time Router::processTransaction() is called. See 541 //! Router::setTransactionUse() for more information. 542 //! 543 //! You should not use the junction reference again after this call. 544 //! The router will handle freeing of the junction's memory. 545 //! 546 //! @param[in] junction Pointer reference to the junction being 547 //! removed. 548 //! 549 void deleteJunction(JunctionRef *junction); 550 551 //! @brief Remove a connector from the router scene. 552 //! 553 //! If the router is using transactions, then this action will occur 554 //! the next time Router::processTransaction() is called. See 555 //! Router::setTransactionUse() for more information. 556 //! 557 //! You should not use the connector reference again after this call. 558 //! The router will handle freeing of the connector's memory. 559 //! 560 //! @param[in] connector Pointer reference to the connector being 561 //! removed. 562 //! 563 void deleteConnector(ConnRef *connector); 564 565 //! @brief Move an existing junction within the router scene. 566 //! 567 //! Connectors that are attached to this junction will be rerouted 568 //! as a result of the move. 569 //! 570 //! If the router is using transactions, then this action will occur 571 //! the next time Router::processTransaction() is called. See 572 //! Router::setTransactionUse() for more information. 573 //! 574 //! @param[in] junction Pointer reference to the junction being 575 //! moved. 576 //! @param[in] newPosition The new position for the junction. 577 //! 578 void moveJunction(JunctionRef *junction, const Point& newPosition); 579 580 //! @brief Move an existing junction within the router scene by a 581 //! relative distance. 582 //! 583 //! Connectors that are attached to this junction will be rerouted 584 //! as a result of the move. 585 //! 586 //! If the router is using transactions, then this action will occur 587 //! the next time Router::processTransaction() is called. See 588 //! Router::setTransactionUse() for more information. 589 //! 590 //! @param[in] junction Pointer reference to the junction being 591 //! moved. 592 //! @param[in] xDiff The distance to move the junction in the 593 //! x dimension. 594 //! @param[in] yDiff The distance to move the junction in the 595 //! y dimension. 596 //! 597 void moveJunction(JunctionRef *junction, const double xDiff, 598 const double yDiff); 599 600 //! @brief Sets values for routing parameters, including routing 601 //! penalties. 602 //! 603 //! libavoid uses a set of parameters to allow the user more control 604 //! over routing style and quality. These different parameters are 605 //! described and explained by the RoutingParameter enum. All 606 //! parameters have sensible defaults. 607 //! 608 //! Regarding routing penalties, libavoid will by default produce 609 //! shortest path routes between the source and destination points 610 //! for each connector. There are several penalties that can be 611 //! applied during this stage to penalise certain conditions and 612 //! thus improve the aesthetics of the routes generated. 613 //! 614 //! If a value of zero or Avoid::zeroParamValue is given then the 615 //! particular parameter value or penalty will be removed. If no 616 //! parameter value argument (or a negative value) is specified 617 //! when calling this method, then a sensible penalty value will 618 //! be automatically chosen. 619 //! 620 //! This method does not re-trigger processing of connectors. The new 621 //! parameter value will be used the next time rerouting is performed. 622 //! 623 //! @param[in] parameter The type of penalty, a RoutingParameter. 624 //! @param[in] value The value to be set for that parameter. 625 //! 626 void setRoutingParameter(const RoutingParameter parameter, 627 const double value = chooseSensibleParamValue); 628 629 //! @brief Returns the current value for a particular routing 630 //! parameter of a given type. 631 //! 632 //! @param[in] parameter The type of parameter, a RoutingParameter. 633 //! @return The value for the specified routing parameter. 634 //! 635 double routingParameter(const RoutingParameter parameter) const; 636 637 //! @brief Turn specific routing options on or off. 638 //! 639 //! @param[in] option The type of routing option, a RoutingOption. 640 //! @param[in] value A boolean representing the option state. 641 //! 642 void setRoutingOption(const RoutingOption option, const bool value); 643 644 //! @brief Returns the current state for a specific routing option. 645 //! 646 //! @param[in] option The type of routing option, a RoutingOption. 647 //! @return A boolean representing the option state. 648 //! 649 bool routingOption(const RoutingOption option) const; 650 651 //! @brief Sets or removes penalty values that are applied during 652 //! connector routing. 653 //! 654 //! @note This is a convenience wrapper for the setRoutingParameter() 655 // method. See its documentation for more details. 656 //! 657 //! @param[in] penType The type of penalty, a RoutingParameter. 658 //! @param[in] penVal The value to be applied for each occurrence 659 //! of the penalty case. 660 //! 661 void setRoutingPenalty(const RoutingParameter penType, 662 const double penVal = chooseSensibleParamValue); 663 664 //! @brief Returns a pointer to the hyperedge rerouter for the router. 665 //! 666 //! @return A HyperedgeRerouter object that can be used to register 667 //! hyperedges for rerouting. 668 //! 669 HyperedgeRerouter *hyperedgeRerouter(void); 670 671 //! @brief Generates an SVG file containing debug output and code that 672 //! can be used to regenerate the instance. 673 //! 674 //! If transactions are being used, then this method should be called 675 //! after processTransaction() has been called, so that it includes any 676 //! changes being queued by the router. 677 //! 678 //! @param[in] filename A string indicating the filename (without 679 //! extension) for the output file. Defaults to 680 //! "libavoid-debug.svg" if no filename is given. 681 //! 682 void outputInstanceToSVG(std::string filename = std::string()); 683 684 //! @brief Returns the object ID used for automatically generated 685 //! objects, such as during hyperedge routing. 686 //! 687 //! Reimplement this in a subclass to set specific IDs for new objects. 688 //! 689 //! @note Your implementation should return a value that does not 690 //! fail objectIdIsUnused(). 691 //! 692 //! @return The ID for a new object. 693 //! 694 virtual unsigned int newObjectId(void) const; 695 696 //! @brief Returns whether or not the given ID is already used. 697 //! 698 //! You should only need this if you reimplement newObjectId(). 699 //! 700 //! @param[in] id An ID to test. 701 //! @return A boolean denoting that the given ID is unused. 702 //! 703 bool objectIdIsUnused(const unsigned int id) const; 704 705 //! @brief A method called at regular intervals during transaction 706 //! processing to report progress and ask if the Router 707 //! should continue the transaction. 708 //! 709 //! You can subclass the Avoid::Router class to implement your 710 //! own behaviour, such as to show a progress bar or cancel the 711 //! transaction at the user's request. 712 //! 713 //! Note that you can get a sense of progress by looking at the 714 //! phaseNumber divided by the totalPhases and the progress in the 715 //! current phase, but be aware that phases and the intervals and 716 //! proportions at which this method is called will vary, sometime 717 //! unpredictably. 718 //! 719 //! You can return false to request that the Router abort the current 720 //! transaction. Be aware that it may not abort in some phases. For 721 //! others it may need to clean up some state before it is safe for 722 //! you to interact with it again. Hence you should wait for a final 723 //! call to this method with the phase Avoid::TransactionPhaseCompleted 724 //! before continuing. 725 //! 726 //! @note Your implementation of this method should be very fast as 727 //! it will be called many times. Also, you should not change 728 //! or interact with the Router instance at all during these 729 //! calls. Wait till you have received a call with the 730 //! Avoid::TransactionPhaseCompleted phase. 731 //! 732 //! @param elapsedTime The number of msec spent on the transaction 733 //! since it began. 734 //! @param phaseNumber A Router::TransactionPhases representing the 735 //! current phase of the transaction. 736 //! @param totalPhases The total number of phases to be performed 737 //! during the transaction. 738 //! @param proportion A double representing the progress in the 739 //! current phase. Value will be between 0--1. 740 //! 741 //! @return Whether the router should continue the transaction. 742 //! This is true in the default (empty) implementation. 743 virtual bool shouldContinueTransactionWithProgress( 744 unsigned int elapsedTime, unsigned int phaseNumber, 745 unsigned int totalPhases, double proportion); 746 747 //! @brief Returns a HyperedgeNewAndDeletedObjectLists detailing the 748 //! lists of junctions and connectors created and deleted 749 //! during hyperedge improvement. 750 //! 751 //! This method will only return information once the router has 752 //! processed the transaction. You should read and act on this 753 //! information before processTransaction() is called again. 754 //! 755 //! After calling this you should no longer refer to any of the 756 //! objects in the "deleted" lists --- the router will delete these 757 //! and free their memory at its convenience. 758 //! 759 //! @return A HyperedgeNewAndDeletedObjectLists containing lists of 760 //! junctions and connectors created and deleted. 761 //! 762 HyperedgeNewAndDeletedObjectLists 763 newAndDeletedObjectListsFromHyperedgeImprovement(void) const; 764 765 void setDebugHandler(DebugHandler *handler); 766 DebugHandler *debugHandler(void) const; 767 768 // Processes the actions list for the transaction. You shouldn't 769 // need to cal this. Instead use processTransaction(). 770 void processActions(void); 771 772 void deleteCluster(ClusterRef *cluster); 773 void attachedShapes(IntList &shapes, const unsigned int shapeId, 774 const unsigned int type); 775 void attachedConns(IntList &conns, const unsigned int shapeId, 776 const unsigned int type); 777 void markPolylineConnectorsNeedingReroutingForDeletedObstacle( 778 Obstacle *obstacle); 779 void generateContains(VertInf *pt); 780 void printInfo(void); 781 void regenerateStaticBuiltGraph(void); 782 void destroyOrthogonalVisGraph(void); 783 void setStaticGraphInvalidated(const bool invalidated); 784 ConnType validConnType(const ConnType select = ConnType_None) const; 785 bool isInCrossingPenaltyReroutingStage(void) const; 786 void markAllObstaclesAsMoved(void); 787 ShapeRef *shapeContainingPoint(const Point& point); 788 void performContinuationCheck(unsigned int phaseNumber, 789 size_t stepNumber, size_t totalSteps); 790 void registerSettingsChange(void); 791 792 /** 793 * @brief Set an addon for doing orthogonal topology improvement. 794 * 795 * It is expected that you would use the topology::AvoidTopologyAddon() 796 * from libtopology rather than write your own. This is done so that 797 * libavoid does not have to depend on libtopology. 798 */ 799 void setTopologyAddon(TopologyAddonInterface *topologyAddon); 800 void improveOrthogonalTopology(void); 801 802 // Testing and debugging methods. 803 bool existsOrthogonalSegmentOverlap(const bool atEnds = false); 804 bool existsOrthogonalFixedSegmentOverlap(const bool atEnds = false); 805 bool existsOrthogonalTouchingPaths(void); 806 int existsCrossings(const bool optimisedForConnectorType = false); 807 bool existsInvalidOrthogonalPaths(void); 808 809 // Outputs the current diagram. Used for visualising individual 810 // steps of various algorithms. lineReps can be used to draw 811 // attention to specific parts of the diagram that have changed 812 // between steps. 813 void outputDiagramSVG(std::string instanceName = std::string(), 814 LineReps *lineReps = nullptr); 815 816 void outputDiagramText(std::string instanceName = std::string()); 817 void outputDiagram(std::string instanceName = std::string()); 818 819 private: 820 friend class ShapeRef; 821 friend class ConnRef; 822 friend class JunctionRef; 823 friend class Obstacle; 824 friend class ClusterRef; 825 friend class ShapeConnectionPin; 826 friend class MinimumTerminalSpanningTree; 827 friend class ConnEnd; 828 friend struct HyperedgeTreeNode; 829 friend class HyperedgeRerouter; 830 friend class HyperedgeImprover; 831 832 unsigned int assignId(const unsigned int suggestedId); 833 void addShape(ShapeRef *shape); 834 void addJunction(JunctionRef *junction); 835 void addCluster(ClusterRef *cluster); 836 void modifyConnector(ConnRef *conn); 837 void modifyConnector(ConnRef *conn, unsigned int type, 838 const ConnEnd &connEnd, bool connPinUpdate = false); 839 void modifyConnectionPin(ShapeConnectionPin *pin); 840 841 void removeObjectFromQueuedActions(const void *object); 842 void newBlockingShape(const Polygon& poly, int pid); 843 void checkAllBlockedEdges(int pid); 844 void checkAllMissingEdges(void); 845 void adjustContainsWithAdd(const Polygon& poly, const int p_shape); 846 void adjustContainsWithDel(const int p_shape); 847 void adjustClustersWithAdd(const PolygonInterface& poly, 848 const int p_cluster); 849 void adjustClustersWithDel(const int p_cluster); 850 void rerouteAndCallbackConnectors(void); 851 void improveCrossings(void); 852 853 ActionInfoList actionList; 854 unsigned int m_largest_assigned_id; 855 bool m_consolidate_actions; 856 bool m_currently_calling_destructors; 857 double m_routing_parameters[lastRoutingParameterMarker]; 858 bool m_routing_options[lastRoutingOptionMarker]; 859 860 ConnRerouteFlagDelegate m_conn_reroute_flags; 861 HyperedgeRerouter m_hyperedge_rerouter; 862 863 // Progress tracking and transaction cancelling. 864 clock_t m_transaction_start_time; 865 bool m_abort_transaction; 866 867 TopologyAddonInterface *m_topology_addon; 868 869 // Overall modes: 870 bool m_allows_polyline_routing; 871 bool m_allows_orthogonal_routing; 872 873 bool m_static_orthogonal_graph_invalidated; 874 bool m_in_crossing_rerouting_stage; 875 876 bool m_settings_changes; 877 878 HyperedgeImprover m_hyperedge_improver; 879 880 DebugHandler *m_debug_handler; 881 }; 882 883 884 } 885 886 887 888 #endif 889