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 connector.h 26 //! @brief Contains the interface for the ConnRef class. 27 28 29 #ifndef AVOID_CONNECTOR_H 30 #define AVOID_CONNECTOR_H 31 32 #include <utility> 33 #include <list> 34 #include <vector> 35 36 #include "libavoid/dllexport.h" 37 #include "libavoid/vertices.h" 38 #include "libavoid/geometry.h" 39 #include "libavoid/connend.h" 40 41 42 namespace Avoid { 43 44 class Router; 45 class ConnRef; 46 class JunctionRef; 47 class ShapeRef; 48 typedef std::list<ConnRef *> ConnRefList; 49 50 51 //! @brief Describes the type of routing that is performed for each 52 //! connector. 53 enum ConnType { 54 ConnType_None = 0, 55 //! @brief The connector path will be a shortest-path poly-line that 56 //! routes around obstacles. 57 ConnType_PolyLine = 1, 58 //! @brief The connector path will be a shortest-path orthogonal 59 //! poly-line (only vertical and horizontal line segments) that 60 //! routes around obstacles. 61 ConnType_Orthogonal = 2 62 }; 63 64 //! @brief A checkpoint is a point that the route for a particular connector 65 //! must visit. They may optionally be given an arrival/departure 66 //! direction. 67 //! 68 class AVOID_EXPORT Checkpoint 69 { 70 public: 71 //! @brief A point that a route must visit. 72 //! 73 //! The connector will be able to enter and leave this checkpoint from 74 //! any direction. 75 //! 76 //! @param[in] p The Point that must be visited. Checkpoint(const Point & p)77 Checkpoint(const Point& p) 78 : point(p), 79 arrivalDirections(ConnDirAll), 80 departureDirections(ConnDirAll) 81 { 82 } 83 //! @brief A point that a route must visit. 84 //! 85 //! The connector will be able to enter and leave this checkpoint from 86 //! the directions specified. Give Avoid::ConnDirAll to specify all 87 //! directions. 88 //! 89 //! @param[in] p The Point that must be visited. 90 //! @param[in] ad Avoid::ConnDirFlags denoting arrival directions for 91 //! the connector portion leading up to this checkpoint. 92 //! @param[in] dd Avoid::ConnDirFlags denoting departure directions 93 //! for the connector portion leading away from this 94 //! checkpoint. Checkpoint(const Point & p,ConnDirFlags ad,ConnDirFlags dd)95 Checkpoint(const Point& p, ConnDirFlags ad, ConnDirFlags dd) 96 : point(p), 97 arrivalDirections(ad), 98 departureDirections(dd) 99 { 100 } 101 // Default constructor. Checkpoint()102 Checkpoint() 103 : point(Point()), 104 arrivalDirections(ConnDirAll), 105 departureDirections(ConnDirAll) 106 { 107 } 108 109 Point point; 110 ConnDirFlags arrivalDirections; 111 ConnDirFlags departureDirections; 112 }; 113 114 115 //! @brief The ConnRef class represents a connector object. 116 //! 117 //! Connectors are a (possible multi-segment) line between two points. 118 //! They are routed intelligently so as not to overlap any of the shape 119 //! objects in the Router scene. 120 //! 121 //! Routing penalties can be applied, resulting in more aesthetically pleasing 122 //! connector paths with fewer segments or less severe bend-points. 123 //! 124 //! You can set a function to be called when the connector has been rerouted 125 //! and needs to be redrawn. Alternatively, you can query the connector's 126 //! needsRepaint() function to determine this manually. 127 //! 128 //! Usually, it is expected that you would create a ConnRef for each connector 129 //! in your diagram and keep that reference in your own connector class. 130 //! 131 class AVOID_EXPORT ConnRef 132 { 133 public: 134 //! @brief Constructs a connector with no endpoints specified. 135 //! 136 //! The constructor requires a valid Router instance. This router 137 //! will take ownership of the connector. Hence, you should not 138 //! call the destructor yourself, but should instead call 139 //! Router::deleteConnector() and the router instance will remove 140 //! and then free the connector's memory. 141 //! 142 //! @note Regarding IDs: 143 //! You can let libavoid manually handle IDs by not specifying 144 //! them. Alternatively, you can specify all IDs yourself, but 145 //! you must be careful to makes sure that each object in the 146 //! scene (shape, connector, cluster, etc) is given a unique, 147 //! positive ID. This uniqueness is checked if assertions are 148 //! enabled, but if not and there are clashes then strange 149 //! things can happen. 150 //! 151 //! @param[in] router The router scene to place the connector into. 152 //! @param[in] id Optionally, a positive integer ID unique 153 //! among all objects. 154 //! 155 ConnRef(Router *router, const unsigned int id = 0); 156 //! @brief Constructs a connector with endpoints specified. 157 //! 158 //! The constructor requires a valid Router instance. This router 159 //! will take ownership of the connector. Hence, you should not 160 //! call the destructor yourself, but should instead call 161 //! Router::deleteConnector() and the router instance will remove 162 //! and then free the connector's memory. 163 //! 164 //! If an ID is not specified, then one will be assigned to the shape. 165 //! If assigning an ID yourself, note that it should be a unique 166 //! positive integer. Also, IDs are given to all objects in a scene, 167 //! so the same ID cannot be given to a shape and a connector for 168 //! example. 169 //! 170 //! @param[in] router The router scene to place the connector into. 171 //! @param[in] id A unique positive integer ID for the connector. 172 //! @param[in] src The source endpoint of the connector. 173 //! @param[in] dst The destination endpoint of the connector. 174 //! 175 ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst, 176 const unsigned int id = 0); 177 178 // To prevent C++ objects from being destroyed in garbage collected languages 179 // when the libraries are called from SWIG, we hide the declarations of the 180 // destructors and prevent generation of default destructors. 181 #ifndef SWIG 182 //! @brief Connector reference destuctor. 183 //! 184 //! Do not call this yourself, instead call 185 //! Router::deleteConnector(). Ownership of this object 186 //! belongs to the router scene. 187 ~ConnRef(); 188 #endif 189 //! @brief Sets both a new source and destination endpoint for this 190 //! connector. 191 //! 192 //! If the router is using transactions, then this action will occur 193 //! the next time Router::processTransaction() is called. See 194 //! Router::setTransactionUse() for more information. 195 //! 196 //! @param[in] srcPoint New source endpoint for the connector. 197 //! @param[in] dstPoint New destination endpoint for the connector. 198 void setEndpoints(const ConnEnd& srcPoint, const ConnEnd& dstPoint); 199 200 //! @brief Sets just a new source endpoint for this connector. 201 //! 202 //! If the router is using transactions, then this action will occur 203 //! the next time Router::processTransaction() is called. See 204 //! Router::setTransactionUse() for more information. 205 //! 206 //! @param[in] srcPoint New source endpoint for the connector. 207 void setSourceEndpoint(const ConnEnd& srcPoint); 208 209 //! @brief Sets just a new destination endpoint for this connector. 210 //! 211 //! If the router is using transactions, then this action will occur 212 //! the next time Router::processTransaction() is called. See 213 //! Router::setTransactionUse() for more information. 214 //! 215 //! @param[in] dstPoint New destination endpoint for the connector. 216 void setDestEndpoint(const ConnEnd& dstPoint); 217 218 //! @brief Returns the ID of this connector. 219 //! @returns The ID of the connector. 220 unsigned int id(void) const; 221 222 //! @brief Returns a pointer to the router scene this connector is in. 223 //! @returns A pointer to the router scene for this connector. 224 Router *router(void) const; 225 226 //! @brief Returns an indication of whether this connector has a 227 //! new route and thus needs to be repainted. 228 //! 229 //! If the connector has been rerouted and need repainting, the 230 //! displayRoute() method can be called to get a reference to the 231 //! new route. 232 //! 233 //! @returns Returns true if the connector requires repainting, or 234 //! false if it does not. 235 bool needsRepaint(void) const; 236 237 //! @brief Returns a reference to the current raw "debug" route for 238 //! the connector. 239 //! 240 //! This is a raw "debug" shortest path version of the route, where 241 //! each line segment in the route may be made up of multiple collinear 242 //! line segments. It also has no post-processing (i.e., centering, 243 //! nudging apart of overlapping paths, or curving of corners) applied 244 //! to it. A route to display to the user can be obtained by calling 245 //! displayRoute(). 246 //! 247 //! @returns The PolyLine route for the connector. 248 const PolyLine& route(void) const; 249 250 //! @brief Returns a reference to the current display version of the 251 //! route for the connector. 252 //! 253 //! The display version of a route has been simplified to collapse all 254 //! collinear line segments into single segments. It also has all 255 //! post-processing applied to the route, including centering, curved 256 //! corners and nudging apart of overlapping segments. 257 //! 258 //! @returns The PolyLine display route for the connector. 259 PolyLine& displayRoute(void); 260 261 //! @brief Sets a callback function that will called to indicate that 262 //! the connector needs rerouting. 263 //! 264 //! The cb function will be called when shapes are added to, removed 265 //! from or moved about on the page. The pointer ptr will be passed 266 //! as an argument to the callback function. 267 //! 268 //! @param[in] cb A pointer to the callback function. 269 //! @param[in] ptr A generic pointer that will be passed to the 270 //! callback function. 271 void setCallback(void (*cb)(void *), void *ptr); 272 273 //! @brief Returns the type of routing performed for this connector. 274 //! @return The type of routing performed. 275 //! 276 ConnType routingType(void) const; 277 278 //! @brief Sets the type of routing to be performed for this 279 //! connector. 280 //! 281 //! If a call to this method changes the current type of routing 282 //! being used for the connector, then it will get rerouted during 283 //! the next processTransaction() call, or immediately if 284 //! transactions are not being used. 285 //! 286 //! @param type The type of routing to be performed. 287 //! 288 void setRoutingType(ConnType type); 289 290 //! @brief Splits a connector in the centre of the segmentNth 291 //! segment and creates a junction point there as well 292 //! as a second connector. 293 //! 294 //! The new junction and connector will be automatically added to 295 //! the router scene. A slight preference will be given to the 296 //! connectors connecting to the junction in the same orientation 297 //! the line segment already existed in. 298 //! 299 //! @return A pair containing pointers to the new JunctionRef and 300 //! ConnRef. 301 std::pair<JunctionRef *, ConnRef *> splitAtSegment( 302 const size_t segmentN); 303 304 //! @brief Allows the user to specify a set of checkpoints that this 305 //! connector will route via. 306 //! 307 //! When routing, the connector will attempt to visit each of the 308 //! points in the checkpoints list in order. It will route from the 309 //! source point to the first checkpoint, to the second checkpoint, 310 //! etc. If a checkpoint is unreachable because it lies inside an 311 //! obstacle, then that checkpoint will be skipped. 312 //! 313 //! @param[in] checkpoints An ordered list of Checkpoints that the 314 //! connector will attempt to route via. 315 void setRoutingCheckpoints(const std::vector<Checkpoint>& checkpoints); 316 317 //! @brief Returns the current set of routing checkpoints for this 318 //! connector. 319 //! @returns The ordered list of Checkpoints that this connector will 320 //! route via. 321 std::vector<Checkpoint> routingCheckpoints(void) const; 322 323 //! @brief Returns ConnEnds specifying what this connector is 324 //! attached to. 325 //! 326 //! This may be useful during hyperedge rerouting. You can check the 327 //! type and properties of the ConnEnd objects to find out what this 328 //! connector is attached to. The ConnEnd::type() will be ConnEndEmpty 329 //! if the connector has not had its endpoints initialised. 330 //! 331 //! @note If the router is using transactions, you might get 332 //! unexpected results if you call this after changing objects 333 //! but before calling Router::processTransaction(). In this 334 //! case changes to ConnEnds for the connector may be queued 335 //! and not yet applied, so you will get old (or empty) values. 336 //! 337 //! @returns A pair of ConnEnd objects specifying what the connector 338 //! is attached to. 339 //! 340 std::pair<ConnEnd, ConnEnd> endpointConnEnds(void) const; 341 342 // @brief Returns the source endpoint vertex in the visibility graph. 343 // @returns The source endpoint vertex. 344 VertInf *src(void) const; 345 // @brief Returns the destination endpoint vertex in the 346 // visibility graph. 347 // @returns The destination endpoint vertex. 348 VertInf *dst(void) const; 349 350 //! @brief Sets a fixed user-specified route for this connector. 351 //! 352 //! libavoid will no longer calculate object-avoiding paths for this 353 //! connector but instead just return the specified route. The path 354 //! of this connector will still be considered for the purpose of 355 //! nudging and routing other non-fixed connectors. 356 //! 357 //! @note This will reset the endpoints of the connector to the two 358 //! ends of the given route, which may cause it to become 359 //! dettached from any shapes or junctions. You can 360 //! alternatively call setFixedExistingRoute() for connectors 361 //! with valid routes in hyperedges that you would like to 362 //! remain attached. 363 //! 364 //! @param[in] route The new fixed route for the connector. 365 //! @sa setFixedExistingRoute() 366 //! @sa clearFixedRoute() 367 //! 368 void setFixedRoute(const PolyLine& route); 369 370 //! @brief Sets a fixed existing route for this connector. 371 //! 372 //! libavoid will no longer calculate object-avoiding paths for this 373 //! connector but instead just return the current exisitng route. 374 //! The path of this connector will still be considered for the 375 //! purpose of nudging and routing other non-fixed connectors. 376 //! 377 //! @note The endpoints of this connector will remain at their current 378 //! positions, even while remaining 'attached' to shapes 379 //! or junctions that move. 380 //! 381 //! @sa setFixedRoute() 382 //! @sa clearFixedRoute() 383 //! 384 void setFixedExistingRoute(void); 385 386 //! @brief Returns whether the connector route is marked as fixed. 387 //! 388 //! @return True if the connector route is fixed, false otherwise. 389 //! 390 bool hasFixedRoute(void) const; 391 392 //! @brief Returns the connector to being automatically routed if it 393 //! was marked as fixed. 394 //! 395 //! @sa setFixedRoute() 396 //! 397 void clearFixedRoute(void); 398 399 void set_route(const PolyLine& route); 400 void calcRouteDist(void); 401 void makeActive(void); 402 void makeInactive(void); 403 VertInf *start(void); 404 void removeFromGraph(void); 405 bool isInitialised(void) const; 406 void makePathInvalid(void); 407 void setHateCrossings(bool value); 408 bool doesHateCrossings(void) const; 409 void setEndpoint(const unsigned int type, const ConnEnd& connEnd); 410 bool setEndpoint(const unsigned int type, const VertID& pointID, 411 Point *pointSuggestion = nullptr); 412 std::vector<Point> possibleDstPinPoints(void) const; 413 414 private: 415 friend class Router; 416 friend class ConnEnd; 417 friend class JunctionRef; 418 friend class ConnRerouteFlagDelegate; 419 friend class HyperedgeImprover; 420 friend struct HyperedgeTreeEdge; 421 friend struct HyperedgeTreeNode; 422 friend class HyperedgeRerouter; 423 424 PolyLine& routeRef(void); 425 void freeRoutes(void); 426 void performCallback(void); 427 bool generatePath(void); 428 void generateCheckpointsPath(std::vector<Point>& path, 429 std::vector<VertInf *>& vertices); 430 void generateStandardPath(std::vector<Point>& path, 431 std::vector<VertInf *>& vertices); 432 void unInitialise(void); 433 void updateEndPoint(const unsigned int type, const ConnEnd& connEnd); 434 void common_updateEndPoint(const unsigned int type, ConnEnd connEnd); 435 void freeActivePins(void); 436 bool getConnEndForEndpointVertex(VertInf *vertex, ConnEnd& connEnd) 437 const; 438 std::pair<Obstacle *, Obstacle *> endpointAnchors(void) const; 439 void outputCode(FILE *fp) const; 440 std::pair<bool, bool> assignConnectionPinVisibility(const bool connect); 441 442 443 Router *m_router; 444 unsigned int m_id; 445 ConnType m_type; 446 bool *m_reroute_flag_ptr; 447 bool m_needs_reroute_flag:1; 448 bool m_false_path:1; 449 bool m_needs_repaint:1; 450 bool m_active:1; 451 bool m_initialised:1; 452 bool m_hate_crossings:1; 453 bool m_has_fixed_route:1; 454 PolyLine m_route; 455 Polygon m_display_route; 456 double m_route_dist; 457 ConnRefList::iterator m_connrefs_pos; 458 VertInf *m_src_vert; 459 VertInf *m_dst_vert; 460 VertInf *m_start_vert; 461 void (*m_callback_func)(void *); 462 void *m_connector; 463 ConnEnd *m_src_connend; 464 ConnEnd *m_dst_connend; 465 std::vector<Checkpoint> m_checkpoints; 466 std::vector<VertInf *> m_checkpoint_vertices; 467 }; 468 469 470 typedef std::pair<Point *, ConnRef *> PtConnPtrPair; 471 472 typedef std::vector< PtConnPtrPair > PointRepVector; 473 typedef std::list<std::pair<size_t, size_t> > NodeIndexPairLinkList; 474 475 class PtOrder 476 { 477 public: 478 PtOrder(); 479 ~PtOrder(); 480 void addPoints(const size_t dim, const PtConnPtrPair& arg1, 481 const PtConnPtrPair& arg2); 482 void addOrderedPoints(const size_t dim, const PtConnPtrPair& innerArg, 483 const PtConnPtrPair& outerArg, bool swapped); 484 int positionFor(const size_t dim, const ConnRef *conn); 485 PointRepVector sortedPoints(const size_t dim); 486 private: 487 size_t insertPoint(const size_t dim, const PtConnPtrPair& point); 488 void sort(const size_t dim); 489 490 // One for each dimension. 491 bool sorted[2]; 492 PointRepVector nodes[2]; 493 NodeIndexPairLinkList links[2]; 494 PointRepVector sortedConnVector[2]; 495 }; 496 497 typedef std::map<Avoid::Point,PtOrder> PtOrderMap; 498 typedef std::set<Avoid::Point> PointSet; 499 500 501 const unsigned int CROSSING_NONE = 0; 502 const unsigned int CROSSING_TOUCHES = 1; 503 const unsigned int CROSSING_SHARES_PATH = 2; 504 const unsigned int CROSSING_SHARES_PATH_AT_END = 4; 505 const unsigned int CROSSING_SHARES_FIXED_SEGMENT = 8; 506 507 508 typedef std::pair<int, unsigned int> CrossingsInfoPair; 509 typedef std::vector<Avoid::Point> PointList; 510 typedef std::vector<PointList> SharedPathList; 511 512 class ConnectorCrossings 513 { 514 public: 515 ConnectorCrossings(Avoid::Polygon& poly, bool polyIsConn, 516 Avoid::Polygon& conn, ConnRef *polyConnRef = nullptr, 517 ConnRef *connConnRef = nullptr); 518 void clear(void); 519 void countForSegment(size_t cIndex, const bool finalSegment); 520 521 Avoid::Polygon& poly; 522 bool polyIsConn; 523 Avoid::Polygon& conn; 524 bool checkForBranchingSegments; 525 ConnRef *polyConnRef; 526 ConnRef *connConnRef; 527 528 unsigned int crossingCount; 529 unsigned int crossingFlags; 530 PointSet *crossingPoints; 531 PtOrderMap *pointOrders; 532 SharedPathList *sharedPaths; 533 534 double firstSharedPathAtEndLength; 535 double secondSharedPathAtEndLength; 536 }; 537 538 extern void splitBranchingSegments(Avoid::Polygon& poly, bool polyIsConn, 539 Avoid::Polygon& conn, const double tolerance = 0); 540 extern bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf); 541 542 } 543 544 545 #endif 546 547 548