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-2014 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
26 #include <cstring>
27 #include <cfloat>
28 #include <cmath>
29 #include <cstdlib>
30 #include <algorithm>
31 #include <queue>
32 #include <limits>
33
34 #include "libavoid/connector.h"
35 #include "libavoid/connend.h"
36 #include "libavoid/router.h"
37 #include "libavoid/visibility.h"
38 #include "libavoid/debug.h"
39 #include "libavoid/assertions.h"
40 #include "libavoid/junction.h"
41 #include "libavoid/makepath.h"
42 #include "libavoid/debughandler.h"
43
44
45 namespace Avoid {
46
47
ConnRef(Router * router,const unsigned int id)48 ConnRef::ConnRef(Router *router, const unsigned int id)
49 : m_router(router),
50 m_type(router->validConnType()),
51 m_reroute_flag_ptr(nullptr),
52 m_needs_reroute_flag(true),
53 m_false_path(false),
54 m_needs_repaint(false),
55 m_active(false),
56 m_hate_crossings(false),
57 m_has_fixed_route(false),
58 m_route_dist(0),
59 m_src_vert(nullptr),
60 m_dst_vert(nullptr),
61 m_start_vert(nullptr),
62 m_callback_func(nullptr),
63 m_connector(nullptr),
64 m_src_connend(nullptr),
65 m_dst_connend(nullptr)
66 {
67 COLA_ASSERT(m_router != nullptr);
68 m_id = m_router->assignId(id);
69
70 // TODO: Store endpoints and details.
71 m_route.clear();
72
73 m_reroute_flag_ptr = m_router->m_conn_reroute_flags.addConn(this);
74 }
75
76
ConnRef(Router * router,const ConnEnd & src,const ConnEnd & dst,const unsigned int id)77 ConnRef::ConnRef(Router *router, const ConnEnd& src, const ConnEnd& dst,
78 const unsigned int id)
79 : m_router(router),
80 m_type(router->validConnType()),
81 m_reroute_flag_ptr(nullptr),
82 m_needs_reroute_flag(true),
83 m_false_path(false),
84 m_needs_repaint(false),
85 m_active(false),
86 m_hate_crossings(false),
87 m_has_fixed_route(false),
88 m_route_dist(0),
89 m_src_vert(nullptr),
90 m_dst_vert(nullptr),
91 m_callback_func(nullptr),
92 m_connector(nullptr),
93 m_src_connend(nullptr),
94 m_dst_connend(nullptr)
95 {
96 COLA_ASSERT(m_router != nullptr);
97 m_id = m_router->assignId(id);
98 m_route.clear();
99
100 // Set endpoint values.
101 setEndpoints(src, dst);
102
103 m_reroute_flag_ptr = m_router->m_conn_reroute_flags.addConn(this);
104 }
105
106
~ConnRef()107 ConnRef::~ConnRef()
108 {
109 COLA_ASSERT(m_router);
110
111 if (m_router->m_currently_calling_destructors == false)
112 {
113 err_printf("ERROR: ConnRef::~ConnRef() shouldn't be called directly.\n");
114 err_printf(" It is owned by the router. Call Router::deleteConnector() instead.\n");
115 abort();
116 }
117
118 m_router->m_conn_reroute_flags.removeConn(this);
119
120 m_router->removeObjectFromQueuedActions(this);
121
122 freeRoutes();
123
124 if (m_src_vert)
125 {
126 m_src_vert->removeFromGraph();
127 m_router->vertices.removeVertex(m_src_vert);
128 delete m_src_vert;
129 m_src_vert = nullptr;
130 }
131 if (m_src_connend)
132 {
133 m_src_connend->disconnect();
134 m_src_connend->freeActivePin();
135 delete m_src_connend;
136 m_src_connend = nullptr;
137 }
138
139 if (m_dst_vert)
140 {
141 m_dst_vert->removeFromGraph();
142 m_router->vertices.removeVertex(m_dst_vert);
143 delete m_dst_vert;
144 m_dst_vert = nullptr;
145 }
146 if (m_dst_connend)
147 {
148 m_dst_connend->disconnect();
149 m_dst_connend->freeActivePin();
150 delete m_dst_connend;
151 m_dst_connend = nullptr;
152 }
153
154 // Clear checkpoint vertices.
155 for (size_t i = 0; i < m_checkpoint_vertices.size(); ++i)
156 {
157 m_checkpoint_vertices[i]->removeFromGraph(true);
158 m_router->vertices.removeVertex(m_checkpoint_vertices[i]);
159 delete m_checkpoint_vertices[i];
160 }
161 m_checkpoint_vertices.clear();
162
163 if (m_active)
164 {
165 makeInactive();
166 }
167 }
168
169
routingType(void) const170 ConnType ConnRef::routingType(void) const
171 {
172 return m_type;
173 }
174
175
setRoutingType(ConnType type)176 void ConnRef::setRoutingType(ConnType type)
177 {
178 type = m_router->validConnType(type);
179 if (m_type != type)
180 {
181 m_type = type;
182
183 makePathInvalid();
184
185 m_router->modifyConnector(this);
186 }
187 }
188
189
routingCheckpoints(void) const190 std::vector<Checkpoint> ConnRef::routingCheckpoints(void) const
191 {
192 return m_checkpoints;
193 }
194
195
setRoutingCheckpoints(const std::vector<Checkpoint> & checkpoints)196 void ConnRef::setRoutingCheckpoints(const std::vector<Checkpoint>& checkpoints)
197 {
198 m_checkpoints = checkpoints;
199
200 // Clear previous checkpoint vertices.
201 for (size_t i = 0; i < m_checkpoint_vertices.size(); ++i)
202 {
203 m_checkpoint_vertices[i]->removeFromGraph(true);
204 m_router->vertices.removeVertex(m_checkpoint_vertices[i]);
205 delete m_checkpoint_vertices[i];
206 }
207 m_checkpoint_vertices.clear();
208
209 for (size_t i = 0; i < m_checkpoints.size(); ++i)
210 {
211 VertID ptID(m_id, 2 + i,
212 VertID::PROP_ConnPoint | VertID::PROP_ConnCheckpoint);
213 VertInf *vertex = new VertInf(m_router, ptID, m_checkpoints[i].point);
214 vertex->visDirections = ConnDirAll;
215
216 m_checkpoint_vertices.push_back(vertex);
217 }
218 if (m_router->m_allows_polyline_routing)
219 {
220 for (size_t i = 0; i < m_checkpoints.size(); ++i)
221 {
222 vertexVisibility(m_checkpoint_vertices[i], nullptr, true, true);
223 }
224 }
225 }
226
227
common_updateEndPoint(const unsigned int type,ConnEnd connEnd)228 void ConnRef::common_updateEndPoint(const unsigned int type, ConnEnd connEnd)
229 {
230 const Point& point = connEnd.position();
231 //db_printf("common_updateEndPoint(%d,(pid=%d,vn=%d,(%f,%f)))\n",
232 // type,point.id,point.vn,point.x,point.y);
233 COLA_ASSERT((type == (unsigned int) VertID::src) ||
234 (type == (unsigned int) VertID::tar));
235
236 // The connEnd is a copy of a ConnEnd that will get disconnected,
237 // so don't leave it looking like it is still connected.
238 connEnd.m_conn_ref = nullptr;
239
240 if (!m_active)
241 {
242 makeActive();
243 }
244
245 VertInf *altered = nullptr;
246
247 VertIDProps properties = VertID::PROP_ConnPoint;
248 if (connEnd.isPinConnection())
249 {
250 properties |= VertID::PROP_DummyPinHelper;
251 }
252 VertID ptID(m_id, type, properties);
253 if (type == (unsigned int) VertID::src)
254 {
255 if (m_src_vert)
256 {
257 m_src_vert->Reset(ptID, point);
258 }
259 else
260 {
261 m_src_vert = new VertInf(m_router, ptID, point);
262 }
263 m_src_vert->visDirections = connEnd.directions();
264
265 if (m_src_connend)
266 {
267 m_src_connend->disconnect();
268 m_src_connend->freeActivePin();
269 delete m_src_connend;
270 m_src_connend = nullptr;
271 }
272 if (connEnd.isPinConnection())
273 {
274 m_src_connend = new ConnEnd(connEnd);
275 m_src_connend->connect(this);
276 // Don't need this to have visibility since we won't
277 // be connecting to it.
278 m_src_vert->visDirections = ConnDirNone;
279 }
280
281 altered = m_src_vert;
282 }
283 else // if (type == (unsigned int) VertID::tar)
284 {
285 if (m_dst_vert)
286 {
287 m_dst_vert->Reset(ptID, point);
288 }
289 else
290 {
291 m_dst_vert = new VertInf(m_router, ptID, point);
292 }
293 m_dst_vert->visDirections = connEnd.directions();
294
295 if (m_dst_connend)
296 {
297 m_dst_connend->disconnect();
298 m_dst_connend->freeActivePin();
299 delete m_dst_connend;
300 m_dst_connend = nullptr;
301 }
302 if (connEnd.isPinConnection())
303 {
304 m_dst_connend = new ConnEnd(connEnd);
305 m_dst_connend->connect(this);
306 // Don't need this to have visibility since we won't
307 // be connecting to it.
308 m_dst_vert->visDirections = ConnDirNone;
309 }
310
311 altered = m_dst_vert;
312 }
313
314 // XXX: Seems to be faster to just remove the edges and recreate
315 bool isConn = true;
316 altered->removeFromGraph(isConn);
317
318 makePathInvalid();
319 m_router->setStaticGraphInvalidated(true);
320 }
321
322
setEndpoints(const ConnEnd & srcPoint,const ConnEnd & dstPoint)323 void ConnRef::setEndpoints(const ConnEnd& srcPoint, const ConnEnd& dstPoint)
324 {
325 m_router->modifyConnector(this, VertID::src, srcPoint);
326 m_router->modifyConnector(this, VertID::tar, dstPoint);
327 }
328
329
setEndpoint(const unsigned int type,const ConnEnd & connEnd)330 void ConnRef::setEndpoint(const unsigned int type, const ConnEnd& connEnd)
331 {
332 m_router->modifyConnector(this, type, connEnd);
333 }
334
335
setSourceEndpoint(const ConnEnd & srcPoint)336 void ConnRef::setSourceEndpoint(const ConnEnd& srcPoint)
337 {
338 m_router->modifyConnector(this, VertID::src, srcPoint);
339 }
340
341
setDestEndpoint(const ConnEnd & dstPoint)342 void ConnRef::setDestEndpoint(const ConnEnd& dstPoint)
343 {
344 m_router->modifyConnector(this, VertID::tar, dstPoint);
345 }
346
347
348 // Given the start or end vertex of a connector, returns the ConnEnd that
349 // can be used to reproduce that endpoint. This is used for hyperedge routing.
350 //
getConnEndForEndpointVertex(VertInf * vertex,ConnEnd & connEnd) const351 bool ConnRef::getConnEndForEndpointVertex(VertInf *vertex,
352 ConnEnd& connEnd) const
353 {
354 if (vertex == nullptr)
355 {
356 err_printf("Warning: In ConnRef::getConnEndForEndpointVertex():\n"
357 " ConnEnd for connector %d is uninitialised. It may have been\n"
358 " set but Router::processTrancaction has not yet been called.\n",
359 (int) id());
360 return false;
361 }
362
363 if (vertex == m_src_vert)
364 {
365 if (m_src_connend)
366 {
367 connEnd = *m_src_connend;
368 }
369 else
370 {
371 connEnd = ConnEnd(Point(m_src_vert->point.x, m_src_vert->point.y),
372 m_src_vert->visDirections);
373 }
374 return true;
375 }
376 else if (vertex == m_dst_vert)
377 {
378 if (m_dst_connend)
379 {
380 connEnd = *m_dst_connend;
381 }
382 else
383 {
384 connEnd = ConnEnd(Point(m_dst_vert->point.x, m_dst_vert->point.y),
385 m_dst_vert->visDirections);
386 }
387 return true;
388 }
389 return false;
390 }
391
392
updateEndPoint(const unsigned int type,const ConnEnd & connEnd)393 void ConnRef::updateEndPoint(const unsigned int type, const ConnEnd& connEnd)
394 {
395 common_updateEndPoint(type, connEnd);
396
397 if (m_has_fixed_route)
398 {
399 // Don't need to continue and compute visibility if route is fixed.
400 return;
401 }
402
403 if (m_router->m_allows_polyline_routing)
404 {
405 bool knownNew = true;
406 bool genContains = true;
407 if (type == (unsigned int) VertID::src)
408 {
409 bool dummySrc = m_src_connend && m_src_connend->isPinConnection();
410 if (!dummySrc)
411 {
412 // Only generate visibility if not attached to a pin.
413 vertexVisibility(m_src_vert, m_dst_vert, knownNew, genContains);
414 }
415 }
416 else
417 {
418 bool dummyDst = m_dst_connend && m_dst_connend->isPinConnection();
419 if (!dummyDst)
420 {
421 // Only generate visibility if not attached to a pin.
422 vertexVisibility(m_dst_vert, m_src_vert, knownNew, genContains);
423 }
424 }
425 }
426 }
427
428
outputCode(FILE * fp) const429 void ConnRef::outputCode(FILE *fp) const
430 {
431 fprintf(fp, " // connRef%u\n", id());
432 fprintf(fp, " connRef = new ConnRef(router, %u);\n", id());
433 if (m_src_connend)
434 {
435 m_src_connend->outputCode(fp, "src");
436 fprintf(fp, " connRef->setSourceEndpoint(srcPt);\n");
437 }
438 else if (src())
439 {
440 fprintf(fp, " srcPt = ConnEnd(Point(%" PREC "g, %" PREC "g), %u);\n",
441 src()->point.x, src()->point.y, src()->visDirections);
442 fprintf(fp, " connRef->setSourceEndpoint(srcPt);\n");
443 }
444 if (m_dst_connend)
445 {
446 m_dst_connend->outputCode(fp, "dst");
447 fprintf(fp, " connRef->setDestEndpoint(dstPt);\n");
448 }
449 else if (dst())
450 {
451 fprintf(fp, " dstPt = ConnEnd(Point(%" PREC "g, %" PREC "g), %u);\n",
452 dst()->point.x, dst()->point.y, dst()->visDirections);
453 fprintf(fp, " connRef->setDestEndpoint(dstPt);\n");
454 }
455 fprintf(fp, " connRef->setRoutingType((ConnType)%u);\n", routingType());
456
457 if (m_has_fixed_route)
458 {
459 PolyLine currRoute = route();
460 fprintf(fp, " newRoute._id = %u;\n", id());
461 fprintf(fp, " newRoute.ps.resize(%d);\n", (int)currRoute.size());
462 for (size_t i = 0; i < currRoute.size(); ++i)
463 {
464 fprintf(fp, " newRoute.ps[%d] = Point(%" PREC "g, %" PREC "g);\n",
465 (int) i, currRoute.ps[i].x, currRoute.ps[i].y);
466 fprintf(fp, " newRoute.ps[%d].id = %u;\n",
467 (int) i, currRoute.ps[i].id);
468 fprintf(fp, " newRoute.ps[%d].vn = %u;\n",
469 (int) i, currRoute.ps[i].vn);
470 }
471 fprintf(fp, " connRef->setFixedRoute(newRoute);\n");
472 }
473
474 if (!m_checkpoints.empty())
475 {
476 fprintf(fp, " std::vector<Checkpoint> checkpoints%u(%d);\n", id(),
477 (int) m_checkpoints.size());
478 for (size_t cInd = 0; cInd < m_checkpoints.size(); ++cInd)
479 {
480 fprintf(fp, " checkpoints%u[%d] = Checkpoint(Point("
481 "%" PREC "g, %" PREC "g), (ConnDirFlags) %d, "
482 "(ConnDirFlags) %d);\n", id(), (int) cInd,
483 m_checkpoints[cInd].point.x, m_checkpoints[cInd].point.y,
484 m_checkpoints[cInd].arrivalDirections,
485 m_checkpoints[cInd].departureDirections);
486 }
487 fprintf(fp, " connRef->setRoutingCheckpoints(checkpoints%u);\n",
488 id());
489 }
490 fprintf(fp, "\n");
491 }
492
493
endpointAnchors(void) const494 std::pair<Obstacle *, Obstacle *> ConnRef::endpointAnchors(void) const
495 {
496 std::pair<Obstacle *, Obstacle *> anchors;
497 anchors.first = nullptr;
498 anchors.second = nullptr;
499
500 if (m_src_connend)
501 {
502 anchors.first = m_src_connend->m_anchor_obj;
503 }
504 if (m_dst_connend)
505 {
506 anchors.second = m_dst_connend->m_anchor_obj;
507 }
508 return anchors;
509 }
510
endpointConnEnds(void) const511 std::pair<ConnEnd, ConnEnd> ConnRef::endpointConnEnds(void) const
512 {
513 std::pair<ConnEnd, ConnEnd> endpoints;
514 getConnEndForEndpointVertex(m_src_vert, endpoints.first);
515 getConnEndForEndpointVertex(m_dst_vert, endpoints.second);
516 return endpoints;
517 }
518
setEndpoint(const unsigned int type,const VertID & pointID,Point * pointSuggestion)519 bool ConnRef::setEndpoint(const unsigned int type, const VertID& pointID,
520 Point *pointSuggestion)
521 {
522 VertInf *vInf = m_router->vertices.getVertexByID(pointID);
523 if (vInf == nullptr)
524 {
525 return false;
526 }
527 Point& point = vInf->point;
528 if (pointSuggestion)
529 {
530 if (euclideanDist(point, *pointSuggestion) > 0.5)
531 {
532 return false;
533 }
534 }
535
536 common_updateEndPoint(type, point);
537
538 // Give this visibility just to the point it is over.
539 EdgeInf *edge = new EdgeInf(
540 (type == VertID::src) ? m_src_vert : m_dst_vert, vInf);
541 // XXX: We should be able to set this to zero, but can't due to
542 // assumptions elsewhere in the code.
543 edge->setDist(0.001);
544
545 m_router->processTransaction();
546 return true;
547 }
548
549
makeActive(void)550 void ConnRef::makeActive(void)
551 {
552 COLA_ASSERT(!m_active);
553
554 // Add to connRefs list.
555 m_connrefs_pos = m_router->connRefs.insert(m_router->connRefs.begin(), this);
556 m_active = true;
557 }
558
559
freeActivePins(void)560 void ConnRef::freeActivePins(void)
561 {
562 if (m_src_connend)
563 {
564 m_src_connend->freeActivePin();
565 }
566 if (m_dst_connend)
567 {
568 m_dst_connend->freeActivePin();
569 }
570 }
571
572
makeInactive(void)573 void ConnRef::makeInactive(void)
574 {
575 COLA_ASSERT(m_active);
576
577 // Remove from connRefs list.
578 m_router->connRefs.erase(m_connrefs_pos);
579 m_active = false;
580 }
581
582
freeRoutes(void)583 void ConnRef::freeRoutes(void)
584 {
585 m_route.clear();
586 m_display_route.clear();
587 }
588
589
route(void) const590 const PolyLine& ConnRef::route(void) const
591 {
592 return m_route;
593 }
594
595
routeRef(void)596 PolyLine& ConnRef::routeRef(void)
597 {
598 return m_route;
599 }
600
601
set_route(const PolyLine & route)602 void ConnRef::set_route(const PolyLine& route)
603 {
604 if (&m_display_route == &route)
605 {
606 db_printf("Error:\tTrying to update libavoid route with itself.\n");
607 return;
608 }
609 m_display_route.ps = route.ps;
610
611 //_display_route.clear();
612 }
613
setFixedExistingRoute(void)614 void ConnRef::setFixedExistingRoute(void)
615 {
616 COLA_ASSERT(m_route.size() >= 2);
617 m_has_fixed_route = true;
618 m_router->registerSettingsChange();
619 }
620
setFixedRoute(const PolyLine & route)621 void ConnRef::setFixedRoute(const PolyLine& route)
622 {
623 if (route.size() >= 2)
624 {
625 // Set endpoints based on the fixed route incase the
626 // fixed route is later cleared.
627 setEndpoints(route.ps[0], route.ps[route.size() - 1]);
628 }
629 m_has_fixed_route = true;
630 m_route = route;
631 m_display_route = m_route.simplify();
632 m_router->registerSettingsChange();
633 }
634
hasFixedRoute(void) const635 bool ConnRef::hasFixedRoute(void) const
636 {
637 return m_has_fixed_route;
638 }
639
clearFixedRoute(void)640 void ConnRef::clearFixedRoute(void)
641 {
642 m_has_fixed_route = false;
643 makePathInvalid();
644 m_router->registerSettingsChange();
645 }
646
displayRoute(void)647 Polygon& ConnRef::displayRoute(void)
648 {
649 if (m_display_route.empty())
650 {
651 // No displayRoute is set. Simplify the current route to get it.
652 m_display_route = m_route.simplify();
653 }
654 return m_display_route;
655 }
656
657
calcRouteDist(void)658 void ConnRef::calcRouteDist(void)
659 {
660 double (*dist)(const Point& a, const Point& b) =
661 (m_type == ConnType_PolyLine) ? euclideanDist : manhattanDist;
662
663 m_route_dist = 0;
664 for (size_t i = 1; i < m_route.size(); ++i)
665 {
666 m_route_dist += dist(m_route.at(i), m_route.at(i - 1));
667 }
668 }
669
670
needsRepaint(void) const671 bool ConnRef::needsRepaint(void) const
672 {
673 return m_needs_repaint;
674 }
675
676
id(void) const677 unsigned int ConnRef::id(void) const
678 {
679 return m_id;
680 }
681
682
midpoint(Point a,Point b)683 Point midpoint(Point a, Point b)
684 {
685 Point midpoint;
686
687 midpoint.x = (a.x + b.x) / 2.0;
688 midpoint.y = (a.y + b.y) / 2.0;
689
690 return midpoint;
691 }
692
693
splitAtSegment(const size_t segmentN)694 std::pair<JunctionRef *, ConnRef *> ConnRef::splitAtSegment(
695 const size_t segmentN)
696 {
697 ConnRef *newConn = nullptr;
698 JunctionRef *newJunction = nullptr;
699
700 if (m_display_route.size() > segmentN)
701 {
702 // Position the junction at the midpoint of the desired segment.
703 Point junctionPos = midpoint(m_display_route.at(segmentN - 1),
704 m_display_route.at(segmentN));
705
706 // Create the new junction.
707 newJunction = new JunctionRef(router(), junctionPos);
708 router()->addJunction(newJunction);
709 newJunction->preferOrthogonalDimension(
710 (m_display_route.at(segmentN - 1).x ==
711 m_display_route.at(segmentN).x) ? YDIM : XDIM);
712
713 // Create a new connection routing from the junction to the original
714 // connector's endpoint.
715 ConnEnd newConnSrc = ConnEnd(newJunction);
716 ConnEnd newConnDst = *m_dst_connend;
717 newConn = new ConnRef(router(), newConnSrc, newConnDst);
718
719 // Reroute the endpoint of the original connector to attach to the
720 // new junction.
721 ConnEnd oldConnDst = ConnEnd(newJunction);
722 this->setDestEndpoint(oldConnDst);
723 }
724
725 return std::make_pair(newJunction, newConn);
726 }
727
728
src(void) const729 VertInf *ConnRef::src(void) const
730 {
731 return m_src_vert;
732 }
733
734
dst(void) const735 VertInf *ConnRef::dst(void) const
736 {
737 return m_dst_vert;
738 }
739
740
start(void)741 VertInf *ConnRef::start(void)
742 {
743 return m_start_vert;
744 }
745
746
isInitialised(void) const747 bool ConnRef::isInitialised(void) const
748 {
749 return m_active;
750 }
751
752
unInitialise(void)753 void ConnRef::unInitialise(void)
754 {
755 m_router->vertices.removeVertex(m_src_vert);
756 m_router->vertices.removeVertex(m_dst_vert);
757 makeInactive();
758 }
759
760
removeFromGraph(void)761 void ConnRef::removeFromGraph(void)
762 {
763 if (m_src_vert)
764 {
765 m_src_vert->removeFromGraph();
766 }
767
768 if (m_dst_vert)
769 {
770 m_dst_vert->removeFromGraph();
771 }
772 }
773
774
setCallback(void (* cb)(void *),void * ptr)775 void ConnRef::setCallback(void (*cb)(void *), void *ptr)
776 {
777 m_callback_func = cb;
778 m_connector = ptr;
779 }
780
781
performCallback(void)782 void ConnRef::performCallback(void)
783 {
784 if (m_callback_func)
785 {
786 m_callback_func(m_connector);
787 }
788 }
789
790
makePathInvalid(void)791 void ConnRef::makePathInvalid(void)
792 {
793 m_needs_reroute_flag = true;
794 }
795
796
router(void) const797 Router *ConnRef::router(void) const
798 {
799 return m_router;
800 }
801
802
803 // Validates a bend point on a path to check it does not form a zigzag corner.
804 // a, b, c are consecutive points on the path. d and e are b's neighbours,
805 // forming the shape corner d-b-e.
806 //
validateBendPoint(VertInf * aInf,VertInf * bInf,VertInf * cInf)807 bool validateBendPoint(VertInf *aInf, VertInf *bInf, VertInf *cInf)
808 {
809 if (bInf->id.isConnectionPin() || bInf->id.isConnCheckpoint())
810 {
811 // We shouldn't check connection pins or checkpoints.
812 return true;
813 }
814 bool bendOkay = true;
815
816 if ((aInf == nullptr) || (cInf == nullptr))
817 {
818 // Not a bendpoint, i.e., the end of the connector, so don't test.
819 return bendOkay;
820 }
821
822 COLA_ASSERT(bInf != nullptr);
823 VertInf *dInf = bInf->shPrev;
824 VertInf *eInf = bInf->shNext;
825 COLA_ASSERT(dInf != nullptr);
826 COLA_ASSERT(eInf != nullptr);
827
828 Point& a = aInf->point;
829 Point& b = bInf->point;
830 Point& c = cInf->point;
831 Point& d = dInf->point;
832 Point& e = eInf->point;
833
834 if ((a == b) || (b == c))
835 {
836 return bendOkay;
837 }
838
839 #ifdef PATHDEBUG
840 db_printf("a=(%g, %g)\n", a.x, a.y);
841 db_printf("b=(%g, %g)\n", b.x, b.y);
842 db_printf("c=(%g, %g)\n", c.x, c.y);
843 db_printf("d=(%g, %g)\n", d.x, d.y);
844 db_printf("e=(%g, %g)\n", e.x, e.y);
845 #endif
846 // Check angle:
847 int abc = vecDir(a, b, c);
848 #ifdef PATHDEBUG
849 db_printf("(abc == %d) ", abc);
850 #endif
851
852 if (abc == 0)
853 {
854 // The three consecutive point on the path are in a line.
855 // There should always be an equally short path that skips this
856 // bend point, but this check is used during rubber-band routing
857 // so we allow this case.
858 bendOkay = true;
859 }
860 else // (abc != 0)
861 {
862 COLA_ASSERT(vecDir(d, b, e) > 0);
863 int abe = vecDir(a, b, e);
864 int abd = vecDir(a, b, d);
865 int bce = vecDir(b, c, e);
866 int bcd = vecDir(b, c, d);
867 #ifdef PATHDEBUG
868 db_printf("&& (abe == %d) && (abd == %d) &&\n(bce == %d) && (bcd == %d)",
869 abe, abd, bce, bcd);
870 #endif
871
872 bendOkay = false;
873 if (abe > 0)
874 {
875 if ((abc > 0) && (abd >= 0) && (bce >= 0))
876 {
877 bendOkay = true;
878 }
879 }
880 else if (abd < 0)
881 {
882 if ((abc < 0) && (abe <= 0) && (bcd <= 0))
883 {
884 bendOkay = true;
885 }
886 }
887 }
888 #ifdef PATHDEBUG
889 db_printf("\n");
890 #endif
891 return bendOkay;
892 }
893
894
assignConnectionPinVisibility(const bool connect)895 std::pair<bool, bool> ConnRef::assignConnectionPinVisibility(const bool connect)
896 {
897 // XXX This is kind of a hack for connection pins. Probably we want to
898 // not use m_src_vert and m_dst_vert. For the moment we will clear
899 // their visibility and give them visibility to the pins.
900 bool dummySrc = m_src_connend && m_src_connend->isPinConnection();
901 if (dummySrc)
902 {
903 m_src_vert->removeFromGraph();
904 if (connect)
905 {
906 m_src_connend->assignPinVisibilityTo(m_src_vert, m_dst_vert);
907 }
908 }
909 bool dummyDst = m_dst_connend && m_dst_connend->isPinConnection();
910 if (dummyDst)
911 {
912 m_dst_vert->removeFromGraph();
913 if (connect)
914 {
915 m_dst_connend->assignPinVisibilityTo(m_dst_vert, m_src_vert);
916 }
917 }
918
919 return std::make_pair(dummySrc, dummyDst);
920 }
921
922
generatePath(void)923 bool ConnRef::generatePath(void)
924 {
925 // XXX Currently rubber-band routing only works when dragging the
926 // destination point of a connector, but not the source. The code
927 // needs to be reworked to work in both directions.
928
929 if (!m_false_path && !m_needs_reroute_flag)
930 {
931 // This connector is up to date.
932 return false;
933 }
934
935 if (!m_dst_vert || !m_src_vert)
936 {
937 // Connector is not fully initialised.
938 return false;
939 }
940
941 //COLA_ASSERT(_srcVert->point != _dstVert->point);
942
943 m_false_path = false;
944 m_needs_reroute_flag = false;
945
946 m_start_vert = m_src_vert;
947
948 // Some connectors may attach to connection pins, which means they route
949 // to the closest of multiple pins on a shape. How we handle this is to
950 // add a dummy vertex as the source or target vertex. This is then given
951 // visibility to each of the possible pins and tiny distance. Here we
952 // assign this visibility by adding edges to the visibility graph that we
953 // later remove.
954 std::pair<bool, bool> isDummyAtEnd = assignConnectionPinVisibility(true);
955
956
957 if (m_router->RubberBandRouting && route().size() > 0)
958 {
959 if (isDummyAtEnd.first)
960 {
961 //ShapeConnectionPin *activePin = m_src_connend->active
962 Point firstPoint = m_src_vert->point;
963 firstPoint.id = m_src_vert->id.objID;
964 firstPoint.vn = m_src_vert->id.vn;
965 PolyLine& existingRoute = routeRef();
966 existingRoute.ps.insert(existingRoute.ps.begin(), 1, firstPoint);
967 }
968 }
969
970 std::vector<Point> path;
971 std::vector<VertInf *> vertices;
972 if (m_checkpoints.empty())
973 {
974 generateStandardPath(path, vertices);
975 }
976 else
977 {
978 generateCheckpointsPath(path, vertices);
979 }
980
981 COLA_ASSERT(vertices.size() >= 2);
982 COLA_ASSERT(vertices[0] == src());
983 COLA_ASSERT(vertices[vertices.size() - 1] == dst());
984 COLA_ASSERT(m_reroute_flag_ptr != nullptr);
985
986 for (size_t i = 1; i < vertices.size(); ++i)
987 {
988 if (m_router->InvisibilityGrph && (m_type == ConnType_PolyLine))
989 {
990 // TODO: Again, we could know this edge without searching.
991 EdgeInf *edge = EdgeInf::existingEdge(vertices[i - 1], vertices[i]);
992 if (edge) {
993 edge->addConn(m_reroute_flag_ptr);
994 }
995 }
996 else
997 {
998 m_false_path = true;
999 }
1000
1001 VertInf *vertex = vertices[i];
1002 if (vertex->pathNext &&
1003 (vertex->pathNext->point == vertex->point))
1004 {
1005 if (!(vertex->pathNext->id.isConnPt()) && !(vertex->id.isConnPt()))
1006 {
1007 // Check for consecutive points on opposite
1008 // corners of two touching shapes.
1009 COLA_ASSERT(abs(vertex->pathNext->id.vn - vertex->id.vn) != 2);
1010 }
1011 }
1012 }
1013
1014 // Get rid of dummy ShapeConnectionPin bridging points at beginning
1015 // and end of path.
1016 std::vector<Point> clippedPath;
1017 std::vector<Point>::iterator pathBegin = path.begin();
1018 std::vector<Point>::iterator pathEnd = path.end();
1019 if (path.size() > 2 && isDummyAtEnd.first)
1020 {
1021 ++pathBegin;
1022 m_src_connend->usePinVertex(vertices[1]);
1023 }
1024 if (path.size() > 2 && isDummyAtEnd.second)
1025 {
1026 --pathEnd;
1027 m_dst_connend->usePinVertex(vertices[vertices.size() - 2]);
1028 }
1029 clippedPath.insert(clippedPath.end(), pathBegin, pathEnd);
1030
1031 // Clear visibility edges added for connection pins dummy vertices.
1032 assignConnectionPinVisibility(false);
1033
1034 freeRoutes();
1035 PolyLine& output_route = m_route;
1036 output_route.ps = clippedPath;
1037
1038 #ifdef PATHDEBUG
1039 db_printf("Output route:\n");
1040 for (size_t i = 0; i < output_route.ps.size(); ++i)
1041 {
1042 db_printf("[%d,%d] %g, %g ", output_route.ps[i].id,
1043 output_route.ps[i].vn, output_route.ps[i].x,
1044 output_route.ps[i].y);
1045 }
1046 db_printf("\n\n");
1047 #endif
1048
1049 #ifdef DEBUGHANDLER
1050 if (m_router->debugHandler())
1051 {
1052 m_router->debugHandler()->updateConnectorRoute(this, -1, -1);
1053 }
1054 #endif
1055
1056 return true;
1057 }
1058
generateCheckpointsPath(std::vector<Point> & path,std::vector<VertInf * > & vertices)1059 void ConnRef::generateCheckpointsPath(std::vector<Point>& path,
1060 std::vector<VertInf *>& vertices)
1061 {
1062 std::vector<VertInf *> checkpoints = m_checkpoint_vertices;
1063 checkpoints.insert(checkpoints.begin(), src());
1064 checkpoints.push_back(dst());
1065
1066 path.clear();
1067 vertices.clear();
1068 path.push_back(src()->point);
1069 vertices.push_back(src());
1070
1071 size_t lastSuccessfulIndex = 0;
1072 for (size_t i = 1; i < checkpoints.size(); ++i)
1073 {
1074 VertInf *start = checkpoints[lastSuccessfulIndex];
1075 VertInf *end = checkpoints[i];
1076
1077 // Handle checkpoint directions by disabling some visibility edges.
1078 if (lastSuccessfulIndex > 0)
1079 {
1080 Checkpoint& srcCP = m_checkpoints[lastSuccessfulIndex - 1];
1081 if (srcCP.departureDirections != ConnDirAll)
1082 {
1083 start->setVisibleDirections(srcCP.departureDirections);
1084 }
1085 }
1086 if ((i + 1) < checkpoints.size())
1087 {
1088 Checkpoint& dstCP = m_checkpoints[i - 1];
1089 if (dstCP.arrivalDirections != ConnDirAll)
1090 {
1091 end->setVisibleDirections(dstCP.arrivalDirections);
1092 }
1093 }
1094
1095 AStarPath aStar;
1096 // Route the connector
1097 aStar.search(this, start, end, nullptr);
1098
1099 // Restore changes made for checkpoint visibility directions.
1100 if (lastSuccessfulIndex > 0)
1101 {
1102 start->setVisibleDirections(ConnDirAll);
1103 }
1104 if ((i + 1) < checkpoints.size())
1105 {
1106 end->setVisibleDirections(ConnDirAll);
1107 }
1108
1109 // Process the path.
1110 int pathlen = end->pathLeadsBackTo(start);
1111 if (pathlen >= 2)
1112 {
1113 size_t prev_path_size = path.size();
1114 path.resize(prev_path_size + (pathlen - 1));
1115 vertices.resize(prev_path_size + (pathlen - 1));
1116 VertInf *vertInf = end;
1117 for (size_t index = path.size() - 1; index >= prev_path_size;
1118 --index)
1119 {
1120 path[index] = vertInf->point;
1121 if (vertInf->id.isConnPt())
1122 {
1123 path[index].id = m_id;
1124 path[index].vn = kUnassignedVertexNumber;
1125 }
1126 else
1127 {
1128 path[index].id = vertInf->id.objID;
1129 path[index].vn = vertInf->id.vn;
1130 }
1131 vertices[index] = vertInf;
1132 vertInf = vertInf->pathNext;
1133 }
1134 lastSuccessfulIndex = i;
1135 }
1136 else if (i + 1 == checkpoints.size())
1137 {
1138 // There is no valid path.
1139 db_printf("Warning: Path not found...\n");
1140 m_needs_reroute_flag = true;
1141
1142 path.push_back(dst()->point);
1143 vertices.push_back(dst());
1144
1145 COLA_ASSERT(path.size() >= 2);
1146 }
1147 else
1148 {
1149 err_printf("Warning: skipping checkpoint for connector "
1150 "%d at (%g, %g).\n", (int) id(),
1151 checkpoints[i]->point.x, checkpoints[i]->point.y);
1152 fflush(stderr);
1153 }
1154 }
1155 // Use topbit to differentiate between start and end point of connector.
1156 // They need unique IDs for nudging.
1157 unsigned int topbit = ((unsigned int) 1) << 31;
1158 path[path.size() - 1].id = m_id | topbit;
1159 path[path.size() - 1].vn = kUnassignedVertexNumber;
1160 }
1161
1162
generateStandardPath(std::vector<Point> & path,std::vector<VertInf * > & vertices)1163 void ConnRef::generateStandardPath(std::vector<Point>& path,
1164 std::vector<VertInf *>& vertices)
1165 {
1166 VertInf *tar = m_dst_vert;
1167 size_t existingPathStart = 0;
1168 const PolyLine& currRoute = route();
1169 if (m_router->RubberBandRouting)
1170 {
1171 COLA_ASSERT(m_router->IgnoreRegions == true);
1172
1173 #ifdef PATHDEBUG
1174 db_printf("\n");
1175 src()->id.db_print();
1176 db_printf(": %g, %g\n", src()->point.x, src()->point.y);
1177 tar->id.db_print();
1178 db_printf(": %g, %g\n", tar->point.x, tar->point.y);
1179 for (size_t i = 0; i < currRoute.ps.size(); ++i)
1180 {
1181 db_printf("%g, %g ", currRoute.ps[i].x, currRoute.ps[i].y);
1182 }
1183 db_printf("\n");
1184 #endif
1185 if (currRoute.size() > 2)
1186 {
1187 if (m_src_vert->point == currRoute.ps[0])
1188 {
1189 existingPathStart = currRoute.size() - 2;
1190 COLA_ASSERT(existingPathStart != 0);
1191 const Point& pnt = currRoute.at(existingPathStart);
1192 VertID vID(pnt.id, pnt.vn);
1193
1194 m_start_vert = m_router->vertices.getVertexByID(vID);
1195 COLA_ASSERT(m_start_vert);
1196 }
1197 }
1198 }
1199 //db_printf("GO\n");
1200 //db_printf("src: %X strt: %X dst: %X\n", (int) m_src_vert, (int) m_start_vert, (int) m_dst_vert);
1201 unsigned int pathlen = 0;
1202 while (pathlen == 0)
1203 {
1204 AStarPath aStar;
1205 aStar.search(this, src(), dst(), start());
1206 pathlen = dst()->pathLeadsBackTo(src());
1207 if (pathlen < 2)
1208 {
1209 if (existingPathStart == 0)
1210 {
1211 break;
1212 }
1213 #ifdef PATHDEBUG
1214 db_printf("BACK\n");
1215 #endif
1216 existingPathStart--;
1217 const Point& pnt = currRoute.at(existingPathStart);
1218 VertIDProps props = (existingPathStart > 0) ? 0 :
1219 VertID::PROP_ConnPoint;
1220 VertID vID(pnt.id, pnt.vn, props);
1221
1222 m_start_vert = m_router->vertices.getVertexByID(vID);
1223 COLA_ASSERT(m_start_vert);
1224 }
1225 else if (m_router->RubberBandRouting)
1226 {
1227 // found.
1228 bool unwind = false;
1229
1230 #ifdef PATHDEBUG
1231 db_printf("\n\n\nSTART:\n\n");
1232 #endif
1233 VertInf *prior = nullptr;
1234 for (VertInf *curr = tar; curr != m_start_vert->pathNext;
1235 curr = curr->pathNext)
1236 {
1237 if (!validateBendPoint(curr->pathNext, curr, prior))
1238 {
1239 unwind = true;
1240 break;
1241 }
1242 prior = curr;
1243 }
1244 if (unwind)
1245 {
1246 #ifdef PATHDEBUG
1247 db_printf("BACK II\n");
1248 #endif
1249 if (existingPathStart == 0)
1250 {
1251 break;
1252 }
1253 existingPathStart--;
1254 const Point& pnt = currRoute.at(existingPathStart);
1255 VertIDProps props = (existingPathStart > 0) ? 0 :
1256 VertID::PROP_ConnPoint;
1257 VertID vID(pnt.id, pnt.vn, props);
1258
1259 m_start_vert = m_router->vertices.getVertexByID(vID);
1260 COLA_ASSERT(m_start_vert);
1261
1262 pathlen = 0;
1263 }
1264 }
1265 }
1266
1267 if (pathlen < 2)
1268 {
1269 // There is no valid path.
1270 db_printf("Warning: Path not found...\n");
1271 m_needs_reroute_flag = true;
1272 pathlen = 2;
1273 tar->pathNext = m_src_vert;
1274 if ((m_type == ConnType_PolyLine) && m_router->InvisibilityGrph)
1275 {
1276 // TODO: Could we know this edge already?
1277 //EdgeInf *edge = EdgeInf::existingEdge(m_src_vert, tar);
1278 //COLA_ASSERT(edge != nullptr);
1279 //edge->addCycleBlocker();
1280 }
1281 }
1282 path.resize(pathlen);
1283 vertices.resize(pathlen);
1284
1285 unsigned int j = pathlen - 1;
1286 for (VertInf *i = tar; i != m_src_vert; i = i->pathNext)
1287 {
1288 path[j] = i->point;
1289 vertices[j] = i;
1290 path[j].id = i->id.objID;
1291 path[j].vn = i->id.vn;
1292
1293 j--;
1294 }
1295 vertices[0] = m_src_vert;
1296 path[0] = m_src_vert->point;
1297 path[0].id = m_src_vert->id.objID;
1298 path[0].vn =m_src_vert->id.vn;
1299 }
1300
1301
setHateCrossings(bool value)1302 void ConnRef::setHateCrossings(bool value)
1303 {
1304 m_hate_crossings = value;
1305 }
1306
1307
doesHateCrossings(void) const1308 bool ConnRef::doesHateCrossings(void) const
1309 {
1310 return m_hate_crossings;
1311 }
1312
1313
possibleDstPinPoints(void) const1314 std::vector<Point> ConnRef::possibleDstPinPoints(void) const
1315 {
1316 std::vector<Point> points;
1317 if (m_dst_connend)
1318 {
1319 points = m_dst_connend->possiblePinPoints();
1320 }
1321 return points;
1322 }
1323
1324
PtOrder()1325 PtOrder::PtOrder()
1326 {
1327 // We have sorted neither list initially.
1328 for (size_t dim = 0; dim < 2; ++dim)
1329 {
1330 sorted[dim] = false;
1331 }
1332 }
1333
1334
~PtOrder()1335 PtOrder::~PtOrder()
1336 {
1337 }
1338
1339
sortedPoints(const size_t dim)1340 PointRepVector PtOrder::sortedPoints(const size_t dim)
1341 {
1342 // Sort if not already sorted.
1343 if (sorted[dim] == false)
1344 {
1345 sort(dim);
1346 }
1347 return sortedConnVector[dim];
1348 }
1349
1350
positionFor(const size_t dim,const ConnRef * conn)1351 int PtOrder::positionFor(const size_t dim, const ConnRef *conn)
1352 {
1353 // Sort if not already sorted.
1354 if (sorted[dim] == false)
1355 {
1356 sort(dim);
1357 }
1358
1359 // Just return position from the sorted list.
1360 size_t i = 0;
1361 for ( ; i < sortedConnVector[dim].size(); ++i)
1362 {
1363 if (sortedConnVector[dim][i].second == conn)
1364 {
1365 return (int) i;
1366 }
1367 }
1368 return -1;
1369 }
1370
1371
insertPoint(const size_t dim,const PtConnPtrPair & pointPair)1372 size_t PtOrder::insertPoint(const size_t dim, const PtConnPtrPair& pointPair)
1373 {
1374 // Is this connector bendpoint already inserted?
1375 size_t i = 0;
1376 for ( ; i < nodes[dim].size(); ++i)
1377 {
1378 if (nodes[dim][i].second == pointPair.second)
1379 {
1380 return i;
1381 }
1382 }
1383 // Not found, insert.
1384 nodes[dim].push_back(pointPair);
1385 return nodes[dim].size() - 1;
1386 }
1387
addPoints(const size_t dim,const PtConnPtrPair & arg1,const PtConnPtrPair & arg2)1388 void PtOrder::addPoints(const size_t dim, const PtConnPtrPair& arg1,
1389 const PtConnPtrPair& arg2)
1390 {
1391 // Add points, but not ordering information.
1392 insertPoint(dim, arg1);
1393 insertPoint(dim, arg2);
1394 }
1395
1396
addOrderedPoints(const size_t dim,const PtConnPtrPair & innerArg,const PtConnPtrPair & outerArg,bool swapped)1397 void PtOrder::addOrderedPoints(const size_t dim, const PtConnPtrPair& innerArg,
1398 const PtConnPtrPair& outerArg, bool swapped)
1399 {
1400 PtConnPtrPair inner = (swapped) ? outerArg : innerArg;
1401 PtConnPtrPair outer = (swapped) ? innerArg : outerArg;
1402 COLA_ASSERT(inner != outer);
1403
1404 // Add points.
1405 size_t innerIndex = insertPoint(dim, inner);
1406 size_t outerIndex = insertPoint(dim, outer);
1407
1408 // And edge for ordering information.
1409 links[dim].push_back(std::make_pair(outerIndex, innerIndex));
1410 }
1411
1412
sort(const size_t dim)1413 void PtOrder::sort(const size_t dim)
1414 {
1415 // This is just a topological sort of the points using the edges info.
1416
1417 sorted[dim] = true;
1418
1419 size_t n = nodes[dim].size();
1420
1421 // Build an adjacency matrix for easy lookup.
1422 std::vector<std::vector<bool> > adjacencyMatrix(n);
1423 for (size_t i = 0; i < n; ++i)
1424 {
1425 adjacencyMatrix[i].assign(n, false);
1426 }
1427 std::vector<int> incomingDegree(n);
1428 std::queue<size_t> queue;
1429
1430 // Populate the dependency matrix.
1431 for (NodeIndexPairLinkList::iterator it = links[dim].begin();
1432 it != links[dim].end(); ++it)
1433 {
1434 adjacencyMatrix[it->first][it->second] = true;
1435 }
1436
1437 // Build incoming degree lookup structure, and add nodes with no
1438 // incoming edges to queue.
1439 for (size_t i = 0; i < n; ++i)
1440 {
1441 int degree = 0;
1442
1443 for (size_t j = 0; j < n; ++j)
1444 {
1445 if (adjacencyMatrix[j][i])
1446 {
1447 degree++;
1448 }
1449 }
1450 incomingDegree[i] = degree;
1451
1452 if (degree == 0)
1453 {
1454 queue.push(i);
1455 }
1456 }
1457
1458 while (queue.empty() == false)
1459 {
1460 size_t k = queue.front();
1461 assert(k < nodes[dim].size());
1462 queue.pop();
1463
1464 // Insert node k into the sorted list
1465 sortedConnVector[dim].push_back(nodes[dim][k]);
1466
1467 // Remove all edges leaving node k:
1468 for (size_t i = 0; i < n; ++i)
1469 {
1470 if (adjacencyMatrix[k][i])
1471 {
1472 adjacencyMatrix[k][i] = false;
1473 incomingDegree[i]--;
1474
1475 if (incomingDegree[i] == 0)
1476 {
1477 queue.push(i);
1478 }
1479 }
1480 }
1481 }
1482 }
1483
1484
1485 // Returns a vertex number representing a point on the line between
1486 // two shape corners, represented by p0 and p1.
1487 //
midVertexNumber(const Point & p0,const Point & p1,const Point & c)1488 static int midVertexNumber(const Point& p0, const Point& p1, const Point& c)
1489 {
1490 if (c.vn != kUnassignedVertexNumber)
1491 {
1492 // The split point is a shape corner, so doesn't need its
1493 // vertex number adjusting.
1494 return c.vn;
1495 }
1496 if ((p0.vn >= 4) && (p0.vn < kUnassignedVertexNumber))
1497 {
1498 // The point next to this has the correct nudging direction,
1499 // so use that.
1500 return p0.vn;
1501 }
1502 if ((p1.vn >= 4) && (p1.vn < kUnassignedVertexNumber))
1503 {
1504 // The point next to this has the correct nudging direction,
1505 // so use that.
1506 return p1.vn;
1507 }
1508 if ((p0.vn < 4) && (p1.vn < 4))
1509 {
1510 if (p0.vn != p1.vn)
1511 {
1512 return p0.vn;
1513 }
1514 // Splitting between two ordinary shape corners.
1515 int vn_mid = std::min(p0.vn, p1.vn);
1516 if ((std::max(p0.vn, p1.vn) == 3) && (vn_mid == 0))
1517 {
1518 vn_mid = 3; // Next vn is effectively 4.
1519 }
1520 return vn_mid + 4;
1521 }
1522 COLA_ASSERT((p0.x == p1.x) || (p0.y == p1.y));
1523 if (p0.vn != kUnassignedVertexNumber)
1524 {
1525 if (p0.x == p1.x)
1526 {
1527 if ((p0.vn == 2) || (p0.vn == 3))
1528 {
1529 return 6;
1530 }
1531 return 4;
1532 }
1533 else
1534 {
1535 if ((p0.vn == 0) || (p0.vn == 3))
1536 {
1537 return 7;
1538 }
1539 return 5;
1540 }
1541 }
1542 else if (p1.vn != kUnassignedVertexNumber)
1543 {
1544 if (p0.x == p1.x)
1545 {
1546 if ((p1.vn == 2) || (p1.vn == 3))
1547 {
1548 return 6;
1549 }
1550 return 4;
1551 }
1552 else
1553 {
1554 if ((p1.vn == 0) || (p1.vn == 3))
1555 {
1556 return 7;
1557 }
1558 return 5;
1559 }
1560 }
1561
1562 // Shouldn't both be new (kUnassignedVertexNumber) points.
1563 db_printf("midVertexNumber(): p0.vn and p1.vn both = "
1564 "kUnassignedVertexNumber\n");
1565 db_printf("p0.vn %d p1.vn %d\n", p0.vn, p1.vn);
1566 return kUnassignedVertexNumber;
1567 }
1568
1569
1570 // Break up overlapping parallel segments that are not the same edge in
1571 // the visibility graph, i.e., where one segment is a subsegment of another.
splitBranchingSegments(Avoid::Polygon & poly,bool polyIsConn,Avoid::Polygon & conn,const double tolerance)1572 void splitBranchingSegments(Avoid::Polygon& poly, bool polyIsConn,
1573 Avoid::Polygon& conn, const double tolerance)
1574 {
1575 for (std::vector<Avoid::Point>::iterator i = conn.ps.begin();
1576 i != conn.ps.end(); ++i)
1577 {
1578 if (i == conn.ps.begin())
1579 {
1580 // Skip the first point.
1581 // There are points-1 segments in a connector.
1582 continue;
1583 }
1584
1585 for (std::vector<Avoid::Point>::iterator j = poly.ps.begin();
1586 j != poly.ps.end(); )
1587 {
1588 if (polyIsConn && (j == poly.ps.begin()))
1589 {
1590 // Skip the first point.
1591 // There are points-1 segments in a connector.
1592 ++j;
1593 continue;
1594 }
1595 Point& c0 = *(i - 1);
1596 Point& c1 = *i;
1597
1598 Point& p0 = (j == poly.ps.begin()) ? poly.ps.back() : *(j - 1);
1599 Point& p1 = *j;
1600
1601 // Check the first point of the first segment.
1602 if (((i - 1) == conn.ps.begin()) &&
1603 pointOnLine(p0, p1, c0, tolerance))
1604 {
1605 //db_printf("add to poly %g %g\n", c0.x, c0.y);
1606
1607 c0.vn = midVertexNumber(p0, p1, c0);
1608 j = poly.ps.insert(j, c0);
1609 if (j != poly.ps.begin())
1610 {
1611 --j;
1612 }
1613 continue;
1614 }
1615 // And the second point of every segment.
1616 if (pointOnLine(p0, p1, c1, tolerance))
1617 {
1618 //db_printf("add to poly %g %g\n", c1.x, c1.y);
1619
1620 c1.vn = midVertexNumber(p0, p1, c1);
1621 j = poly.ps.insert(j, c1);
1622 if (j != poly.ps.begin())
1623 {
1624 --j;
1625 }
1626 continue;
1627 }
1628
1629 // Check the first point of the first segment.
1630 if (polyIsConn && ((j - 1) == poly.ps.begin()) &&
1631 pointOnLine(c0, c1, p0, tolerance))
1632 {
1633 //db_printf("add to conn %g %g\n", p0.x, p0.y);
1634
1635 p0.vn = midVertexNumber(c0, c1, p0);
1636 i = conn.ps.insert(i, p0);
1637 continue;
1638 }
1639 // And the second point of every segment.
1640 if (pointOnLine(c0, c1, p1, tolerance))
1641 {
1642 //db_printf("add to conn %g %g\n", p1.x, p1.y);
1643
1644 p1.vn = midVertexNumber(c0, c1, p1);
1645 i = conn.ps.insert(i, p1);
1646 }
1647 ++j;
1648 }
1649 }
1650 }
1651
1652
segDir(const Point & p1,const Point & p2)1653 static int segDir(const Point& p1, const Point& p2)
1654 {
1655 int result = 1;
1656 if (p1.x == p2.x)
1657 {
1658 if (p2.y > p1.y)
1659 {
1660 result = -1;
1661 }
1662 }
1663 else if (p1.y == p2.y)
1664 {
1665 if (p2.x < p1.x)
1666 {
1667 result = -1;
1668 }
1669 }
1670 return result;
1671 }
1672
1673
posInlineWithConnEndSegs(const double pos,const size_t dim,const Avoid::Polygon & poly,const Avoid::Polygon & conn)1674 static bool posInlineWithConnEndSegs(const double pos, const size_t dim,
1675 const Avoid::Polygon& poly, const Avoid::Polygon& conn)
1676 {
1677 size_t pLast = poly.size() - 1;
1678 size_t cLast = conn.size() - 1;
1679 if ((
1680 // Is inline with the beginning of the "poly" line
1681 ((pos == poly.ps[0][dim]) && (pos == poly.ps[1][dim])) ||
1682 // Is inline with the end of the "poly" line
1683 ((pos == poly.ps[pLast][dim]) && (pos == poly.ps[pLast - 1][dim]))
1684 ) && (
1685 // Is inline with the beginning of the "conn" line
1686 ((pos == conn.ps[0][dim]) && (pos == conn.ps[1][dim])) ||
1687 // Is inline with the end of the "conn" line
1688 ((pos == conn.ps[cLast][dim]) && (pos == conn.ps[cLast - 1][dim]))
1689 ))
1690 {
1691 return true;
1692 }
1693 return false;
1694 }
1695
ConnectorCrossings(Avoid::Polygon & poly,bool polyIsConn,Avoid::Polygon & conn,ConnRef * polyConnRef,ConnRef * connConnRef)1696 ConnectorCrossings::ConnectorCrossings(Avoid::Polygon& poly, bool polyIsConn,
1697 Avoid::Polygon& conn, ConnRef *polyConnRef, ConnRef *connConnRef)
1698 : poly(poly),
1699 polyIsConn(polyIsConn),
1700 conn(conn),
1701 checkForBranchingSegments(false),
1702 polyConnRef(polyConnRef),
1703 connConnRef(connConnRef),
1704 crossingPoints(nullptr),
1705 pointOrders(nullptr),
1706 sharedPaths(nullptr)
1707 {
1708 }
1709
clear(void)1710 void ConnectorCrossings::clear(void)
1711 {
1712 crossingCount = 0;
1713 crossingFlags = CROSSING_NONE;
1714 firstSharedPathAtEndLength = DBL_MAX;
1715 secondSharedPathAtEndLength = DBL_MAX;
1716 }
1717
1718
1719 // Computes the *shared* length of these two shared paths.
1720 //
pathLength(Avoid::Point ** c_path,Avoid::Point ** p_path,size_t size)1721 static double pathLength(Avoid::Point **c_path, Avoid::Point **p_path,
1722 size_t size)
1723 {
1724 double length = 0;
1725
1726 for (unsigned int ind = 1; ind < size; ++ind)
1727 {
1728 if ( (*(c_path[ind - 1]) == *(p_path[ind - 1])) &&
1729 (*(c_path[ind]) == *(p_path[ind])) )
1730 {
1731 // This segment is shared by both paths.
1732 //
1733 // This function will only be used for orthogonal paths, so we
1734 // can use Manhattan distance here since it will be faster to
1735 // compute.
1736 length += manhattanDist(*(c_path[ind - 1]), *(c_path[ind]));
1737 }
1738 }
1739
1740 return length;
1741 }
1742
1743 // Works out if the segment conn[cIndex-1]--conn[cIndex] really crosses poly.
1744 // This does not not count non-crossing shared paths as crossings.
1745 // poly can be either a connector (polyIsConn = true) or a cluster
1746 // boundary (polyIsConn = false).
1747 //
countForSegment(size_t cIndex,const bool finalSegment)1748 void ConnectorCrossings::countForSegment(size_t cIndex, const bool finalSegment)
1749 {
1750 clear();
1751
1752 bool polyIsOrthogonal = (polyConnRef &&
1753 (polyConnRef->routingType() == ConnType_Orthogonal));
1754 bool connIsOrthogonal = (connConnRef &&
1755 (connConnRef->routingType() == ConnType_Orthogonal));
1756
1757 // Fixed routes will not have segment breaks at possible crossings.
1758 bool polyIsFixed = (polyConnRef && polyConnRef->hasFixedRoute());
1759 bool connIsFixed = (connConnRef && connConnRef->hasFixedRoute());
1760
1761 // We need to split apart connectors at potential crossing points if
1762 // either has a fixed route or it is a polyline connector. This is not
1763 // needed for orthogonal connectors where crossings occur at vertices
1764 // in visibility graph and on the raw connector routes.
1765 if (checkForBranchingSegments || polyIsFixed || connIsFixed ||
1766 !polyIsOrthogonal || !connIsOrthogonal)
1767 {
1768 double epsilon = std::numeric_limits<double>::epsilon();
1769 size_t conn_pn = conn.size();
1770 // XXX When doing the pointOnLine test we allow the points to be
1771 // slightly non-collinear. This addresses a problem with clustered
1772 // routing where connectors could otherwise route cheaply through
1773 // shape corners that were not quite on the cluster boundary, but
1774 // reported to be on there by the line segment intersection code,
1775 // which I suspect is not numerically accurate enough. This occurred
1776 // for points that only differed by about 10^-12 in the y-dimension.
1777 double tolerance = (!polyIsConn) ? epsilon : 0.0;
1778 splitBranchingSegments(poly, polyIsConn, conn, tolerance);
1779 // cIndex is going to be the last, so take into account added points.
1780 cIndex += (conn.size() - conn_pn);
1781 }
1782 COLA_ASSERT(cIndex >= 1);
1783 COLA_ASSERT(cIndex < conn.size());
1784
1785 size_t poly_size = poly.size();
1786
1787 Avoid::Point& a1 = conn.ps[cIndex - 1];
1788 Avoid::Point& a2 = conn.ps[cIndex];
1789 //db_printf("a1: %g %g\n", a1.x, a1.y);
1790 //db_printf("a2: %g %g\n", a2.x, a2.y);
1791
1792 // Allocate arrays for computing shared paths.
1793 // Don't use dynamic array due to portablity issues.
1794 size_t max_path_size = std::min(poly_size, conn.size());
1795 Avoid::Point **c_path = new Avoid::Point*[max_path_size];
1796 Avoid::Point **p_path = new Avoid::Point*[max_path_size];
1797 size_t size = 0;
1798
1799 for (size_t j = ((polyIsConn) ? 1 : 0); j < poly_size; ++j)
1800 {
1801 Avoid::Point& b1 = poly.ps[(j - 1 + poly_size) % poly_size];
1802 Avoid::Point& b2 = poly.ps[j];
1803 //db_printf("b1: %g %g\n", b1.x, b1.y);
1804 //db_printf("b2: %g %g\n", b2.x, b2.y);
1805
1806 size = 0;
1807
1808 bool converging = false;
1809
1810 const bool a1_eq_b1 = (a1 == b1);
1811 const bool a2_eq_b1 = (a2 == b1);
1812 const bool a2_eq_b2 = (a2 == b2);
1813 const bool a1_eq_b2 = (a1 == b2);
1814
1815 if ( (a1_eq_b1 && a2_eq_b2) ||
1816 (a2_eq_b1 && a1_eq_b2) )
1817 {
1818 if (finalSegment)
1819 {
1820 converging = true;
1821 }
1822 else
1823 {
1824 // Route along same segment: no penalty. We detect
1825 // crossovers when we see the segments diverge.
1826 continue;
1827 }
1828 }
1829 else if (a2_eq_b1 || a2_eq_b2 || a1_eq_b2)
1830 {
1831 // Each crossing that is at a vertex in the
1832 // visibility graph gets noticed four times.
1833 // We ignore three of these cases.
1834 // This also catches the case of a shared path,
1835 // but this is one that terminates at a common
1836 // endpoint, so we don't care about it.
1837 continue;
1838 }
1839
1840 if (a1_eq_b1 || converging)
1841 {
1842 if (!converging)
1843 {
1844 if (polyIsConn && (j == 1))
1845 {
1846 // Can't be the end of a shared path or crossing path
1847 // since the common point is the first point of the
1848 // connector path. This is not a shared path at all.
1849 continue;
1850 }
1851
1852 Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
1853 // The segments share an endpoint -- a1==b1.
1854 if (a2 == b0)
1855 {
1856 // a2 is not a split, continue.
1857 continue;
1858 }
1859 }
1860
1861 // If here and not converging, then we know that a2 != b2
1862 // And a2 and its pair in b are a split.
1863 COLA_ASSERT(converging || !a2_eq_b2);
1864
1865 bool shared_path = false;
1866
1867 // Initial values here don't matter. They are only used after
1868 // being set to sensible values, but we set them to stop a MSVC
1869 // warning.
1870 bool p_dir_back;
1871 int p_dir = 0;
1872 int trace_c = 0;
1873 int trace_p = 0;
1874
1875 if (converging)
1876 {
1877 // Determine direction we have to look through
1878 // the points of connector b.
1879 p_dir_back = a2_eq_b2 ? true : false;
1880 p_dir = p_dir_back ? -1 : 1;
1881 trace_c = (int) cIndex;
1882 trace_p = (int) j;
1883 if (!p_dir_back)
1884 {
1885 if (finalSegment)
1886 {
1887 trace_p--;
1888 }
1889 else
1890 {
1891 trace_c--;
1892 }
1893 }
1894
1895 shared_path = true;
1896 }
1897 else if (cIndex >= 2)
1898 {
1899 Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
1900 Avoid::Point& a0 = conn.ps[cIndex - 2];
1901
1902 //db_printf("a0: %g %g\n", a0.x, a0.y);
1903 //db_printf("b0: %g %g\n", b0.x, b0.y);
1904
1905 if ((a0 == b2) || (a0 == b0))
1906 {
1907 // Determine direction we have to look through
1908 // the points of connector b.
1909 p_dir_back = (a0 == b0) ? true : false;
1910 p_dir = p_dir_back ? -1 : 1;
1911 trace_c = (int) cIndex;
1912 trace_p = (int) (p_dir_back ? j : j - 2);
1913
1914 shared_path = true;
1915 }
1916 }
1917
1918 if (shared_path)
1919 {
1920 crossingFlags |= CROSSING_SHARES_PATH;
1921 // Shouldn't be here if p_dir is still equal to zero.
1922 COLA_ASSERT(p_dir != 0);
1923
1924 // Build the shared path, including the diverging points at
1925 // each end if the connector does not end at a common point.
1926 while ( (trace_c >= 0) && (!polyIsConn ||
1927 ((trace_p >= 0) && (trace_p < (int) poly_size))) )
1928 {
1929 // If poly is a cluster boundary, then it is a closed
1930 // poly-line and so it wraps around.
1931 size_t index_p = (size_t)
1932 ((trace_p + (2 * poly_size)) % poly_size);
1933 size_t index_c = (size_t) trace_c;
1934 c_path[size] = &conn.ps[index_c];
1935 p_path[size] = &poly.ps[index_p];
1936 ++size;
1937 if ((size > 1) && (conn.ps[index_c] != poly.ps[index_p]))
1938 {
1939 // Points don't match, so break out of loop.
1940 break;
1941 }
1942 trace_c--;
1943 trace_p += p_dir;
1944 }
1945
1946 // Are there diverging points at the ends of the shared path.
1947 bool front_same = (*(c_path[0]) == *(p_path[0]));
1948 bool back_same = (*(c_path[size - 1]) == *(p_path[size - 1]));
1949
1950 // Determine if the shared path originates at a junction.
1951 bool terminatesAtJunction = false;
1952 if (polyConnRef && connConnRef && (front_same || back_same))
1953 {
1954 // To do this we find the two ConnEnds at the common
1955 // end of the shared path. Then check if they are
1956 // attached to a junction and it is the same one.
1957 std::pair<ConnEnd, ConnEnd> connEnds =
1958 connConnRef->endpointConnEnds();
1959 JunctionRef *connJunction = nullptr;
1960
1961 std::pair<ConnEnd, ConnEnd> polyEnds =
1962 polyConnRef->endpointConnEnds();
1963 JunctionRef *polyJunction = nullptr;
1964
1965 // The front of the c_path corresponds to destination
1966 // of the connector.
1967 connJunction = (front_same) ? connEnds.second.junction() :
1968 connEnds.first.junction();
1969 bool use_first = back_same;
1970 if (p_dir_back)
1971 {
1972 // Reversed, so use opposite.
1973 use_first = !use_first;
1974 }
1975 // The front of the p_path corresponds to destination
1976 // of the connector.
1977 polyJunction = (use_first) ? polyEnds.second.junction() :
1978 polyEnds.first.junction();
1979
1980 terminatesAtJunction = (connJunction &&
1981 (connJunction == polyJunction));
1982 }
1983
1984 if (sharedPaths)
1985 {
1986 // Store a copy of the shared path
1987 size_t start = (front_same) ? 0 : 1;
1988 size_t limit = size - ((back_same) ? 0 : 1);
1989
1990 PointList sPath(limit - start);
1991 for (size_t i = start; i < limit; ++i)
1992 {
1993 sPath[i - start] = *(c_path[i]);
1994 }
1995 sharedPaths->push_back(sPath);
1996 }
1997
1998 // Check to see if these share a fixed segment.
1999 if (polyIsOrthogonal && connIsOrthogonal)
2000 {
2001 size_t startPt = (front_same) ? 0 : 1;
2002 size_t endPt = size - ((back_same) ? 1 : 2);
2003 for (size_t dim = 0; dim < 2; ++dim)
2004 {
2005 if ((*c_path[startPt])[dim] == (*c_path[endPt])[dim])
2006 {
2007 double pos = (*c_path[startPt])[dim];
2008 // See if this is inline with either the start
2009 // or end point of both connectors. We don't
2010 // count them as crossing if they originate at a
2011 // junction and are part of the same hyperedge.
2012 if ( ((pos == poly.ps[0][dim]) ||
2013 (pos == poly.ps[poly_size - 1][dim])) &&
2014 ((pos == conn.ps[0][dim]) ||
2015 (pos == conn.ps[cIndex][dim])) &&
2016 (terminatesAtJunction == false))
2017 {
2018 crossingFlags |= CROSSING_SHARES_FIXED_SEGMENT;
2019 }
2020 }
2021 }
2022
2023 if (!front_same && !back_same)
2024 {
2025 // Find overlapping segments that are constrained by
2026 // the fact that both the adjoining segments are fixed
2027 // in the other dimension, i.e.,
2028 //
2029 // X------++---X
2030 // ||
2031 // ||
2032 // X---++------X
2033 //
2034 // In the example above, altDim is X, and dim is Y.
2035 //
2036
2037 // For each dimension...
2038 for (size_t dim = 0; dim < 2; ++dim)
2039 {
2040 size_t end = size - 1;
2041 size_t altDim = (dim + 1) % 2;
2042 // If segment is in this dimension...
2043 if ((*c_path[1])[altDim] == (*c_path[end - 1])[altDim])
2044 {
2045 double posBeg = (*c_path[1])[dim];
2046 double posEnd = (*c_path[end - 1])[dim];
2047 // If both segment ends diverge at right-angles...
2048 if ( (posBeg == (*c_path[0])[dim]) &&
2049 (posBeg == (*p_path[0])[dim]) &&
2050 (posEnd == (*c_path[end])[dim]) &&
2051 (posEnd == (*p_path[end])[dim]) )
2052 {
2053 // and these segments are inline with the conn and path ends themselves...
2054 if (posInlineWithConnEndSegs(posBeg, dim,
2055 conn, poly) &&
2056 posInlineWithConnEndSegs(posEnd, dim,
2057 conn, poly))
2058 {
2059 // If all endpoints branch at right angles,
2060 // then penalise this since it is a segment
2061 // will will not be able to nudge apart
2062 // without introducing fixed segment
2063 // crossings.
2064 crossingFlags |=
2065 CROSSING_SHARES_FIXED_SEGMENT;
2066 }
2067 }
2068 }
2069 }
2070 }
2071
2072 #if 0
2073 // XXX: What is this code for? It is pretty much
2074 // incomprehensible and also causes one of the test
2075 // cases to fail.
2076 //
2077 if (!front_same && !back_same)
2078 {
2079 for (size_t dim = 0; dim < 2; ++dim)
2080 {
2081 size_t altDim = (dim + 1) % 2;
2082 if ((*c_path[1])[altDim] == (*c_path[1])[altDim])
2083 {
2084 size_t n = c_path.size();
2085 double yPosB = (*c_path[1])[dim];
2086 if ( (yPosB == (*c_path[0])[dim]) &&
2087 (yPosB == (*p_path[0])[dim]) )
2088 {
2089 crossingFlags |=
2090 CROSSING_SHARES_FIXED_SEGMENT;
2091 }
2092
2093 double yPosE = (*c_path[n - 2])[dim];
2094 if ( (yPosE == (*c_path[n - 1])[dim]) &&
2095 (yPosE == (*p_path[n - 1])[dim]) )
2096 {
2097 crossingFlags |=
2098 CROSSING_SHARES_FIXED_SEGMENT;
2099 }
2100 }
2101 }
2102 }
2103 #endif
2104 }
2105
2106 // {start,end}CornerSide specifies which side of conn the
2107 // poly path enters and leaves.
2108 int startCornerSide = 1;
2109 int endCornerSide = 1;
2110
2111 bool reversed = false;
2112 if (!front_same)
2113 {
2114 // If there is a divergence at the beginning,
2115 // then order the shared path based on this.
2116 startCornerSide = Avoid::cornerSide(*c_path[0], *c_path[1],
2117 *c_path[2], *p_path[0]);
2118 }
2119 if (!back_same)
2120 {
2121 // If there is a divergence at the end of the path,
2122 // then order the shared path based on this.
2123 endCornerSide = Avoid::cornerSide(*c_path[size - 3],
2124 *c_path[size - 2], *c_path[size - 1],
2125 *p_path[size - 1]);
2126 }
2127 else
2128 {
2129 endCornerSide = startCornerSide;
2130 }
2131 if (front_same)
2132 {
2133 startCornerSide = endCornerSide;
2134 }
2135
2136 if (endCornerSide != startCornerSide)
2137 {
2138 // Mark that the shared path crosses.
2139 //db_printf("shared path crosses.\n");
2140 crossingCount += 1;
2141 if (crossingPoints)
2142 {
2143 crossingPoints->insert(*c_path[1]);
2144 }
2145 }
2146
2147 if (front_same || back_same)
2148 {
2149 crossingFlags |= CROSSING_SHARES_PATH_AT_END;
2150
2151 // Reduce the cost of paths that stay straight after
2152 // the split, and make this length available so that the
2153 // paths can be ordered during the improveCrossings()
2154 // step and the straight (usually better) paths will be
2155 // left alone while the router attempts to find better
2156 // paths for the others.
2157 double straightModifier = 200;
2158 firstSharedPathAtEndLength = secondSharedPathAtEndLength =
2159 pathLength(c_path, p_path, size);
2160 if (back_same && (size > 2))
2161 {
2162 if (vecDir(*p_path[0], *p_path[1], *p_path[2]) == 0)
2163 {
2164 firstSharedPathAtEndLength -= straightModifier;
2165 }
2166
2167 if (vecDir(*c_path[0], *c_path[1], *c_path[2]) == 0)
2168 {
2169 secondSharedPathAtEndLength -= straightModifier;
2170 }
2171 }
2172 else if (front_same && (size > 2))
2173 {
2174 if (vecDir(*p_path[size - 3], *p_path[size - 2],
2175 *p_path[size - 1]) == 0)
2176 {
2177 firstSharedPathAtEndLength -= straightModifier;
2178 }
2179
2180 if (vecDir(*c_path[size - 3], *c_path[size - 2],
2181 *c_path[size - 1]) == 0)
2182 {
2183 secondSharedPathAtEndLength -= straightModifier;
2184 }
2185 }
2186 }
2187 else if (polyIsOrthogonal && connIsOrthogonal)
2188 {
2189 int cStartDir = vecDir(*c_path[0], *c_path[1], *c_path[2]);
2190 int pStartDir = vecDir(*p_path[0], *p_path[1], *p_path[2]);
2191 if ((cStartDir != 0) && (cStartDir == -pStartDir))
2192 {
2193 // The start segments diverge at 180 degrees to each
2194 // other. So order based on not introducing overlap
2195 // of the diverging segments when these are nudged
2196 // apart.
2197 startCornerSide = -cStartDir;
2198 }
2199 else
2200 {
2201 int cEndDir = vecDir(*c_path[size - 3],
2202 *c_path[size - 2], *c_path[size - 1]);
2203 int pEndDir = vecDir(*p_path[size - 3],
2204 *p_path[size - 2], *p_path[size - 1]);
2205 if ((cEndDir != 0) && (cEndDir == -pEndDir))
2206 {
2207 // The end segments diverge at 180 degrees to
2208 // each other. So order based on not introducing
2209 // overlap of the diverging segments when these
2210 // are nudged apart.
2211 startCornerSide = -cEndDir;
2212 }
2213 }
2214 }
2215
2216 #if 0
2217 int prevTurnDir = 0;
2218 if (pointOrders)
2219 {
2220 // Return the ordering for the shared path.
2221 COLA_ASSERT(c_path.size() > 0 || back_same);
2222 size_t adj_size = (c_path.size() - ((back_same) ? 0 : 1));
2223 for (size_t i = (front_same) ? 0 : 1; i < adj_size; ++i)
2224 {
2225 Avoid::Point& an = *(c_path[i]);
2226 Avoid::Point& bn = *(p_path[i]);
2227 int currTurnDir = ((i > 0) && (i < (adj_size - 1))) ?
2228 vecDir(*c_path[i - 1], an,
2229 *c_path[i + 1]) : 0;
2230 VertID vID(an.id, true, an.vn);
2231 if ( (currTurnDir == (-1 * prevTurnDir)) &&
2232 (currTurnDir != 0) && (prevTurnDir != 0) )
2233 {
2234 // The connector turns the opposite way around
2235 // this shape as the previous bend on the path,
2236 // so reverse the order so that the inner path
2237 // become the outer path and vice versa.
2238 reversed = !reversed;
2239 }
2240 bool orderSwapped = (*pointOrders)[an].addOrderedPoints(
2241 &bn, &an, reversed);
2242 if (orderSwapped)
2243 {
2244 // Reverse the order for later points.
2245 reversed = !reversed;
2246 }
2247 prevTurnDir = currTurnDir;
2248 }
2249 }
2250 #endif
2251 if (pointOrders)
2252 {
2253 reversed = false;
2254 size_t startPt = (front_same) ? 0 : 1;
2255
2256 // Orthogonal should always have at least one segment.
2257 COLA_ASSERT(size > (startPt + 1));
2258
2259 if (startCornerSide > 0)
2260 {
2261 reversed = !reversed;
2262 }
2263
2264 int prevDir = 0;
2265 // Return the ordering for the shared path.
2266 COLA_ASSERT(size > 0 || back_same);
2267 size_t adj_size = (size - ((back_same) ? 0 : 1));
2268 for (size_t i = startPt; i < adj_size; ++i)
2269 {
2270 Avoid::Point& an = *(c_path[i]);
2271 Avoid::Point& bn = *(p_path[i]);
2272 COLA_ASSERT(an == bn);
2273
2274 if (i > startPt)
2275 {
2276 Avoid::Point& ap = *(c_path[i - 1]);
2277 Avoid::Point& bp = *(p_path[i - 1]);
2278
2279 int thisDir = segDir(ap, an);
2280 if (prevDir == 0)
2281 {
2282 if (thisDir > 0)
2283 {
2284 reversed = !reversed;
2285 }
2286 }
2287 else if (thisDir != prevDir)
2288 {
2289 reversed = !reversed;
2290 }
2291
2292 int orientation = (ap.x == an.x) ? 0 : 1;
2293 //printf("prevOri %d\n", prevOrientation);
2294 //printf("1: %X, %X\n", (int) &(bn), (int) &(an));
2295 (*pointOrders)[an].addOrderedPoints(
2296 orientation,
2297 std::make_pair(&bn, polyConnRef),
2298 std::make_pair(&an, connConnRef),
2299 reversed);
2300 COLA_ASSERT(ap == bp);
2301 //printf("2: %X, %X\n", (int) &bp, (int) &ap);
2302 (*pointOrders)[ap].addOrderedPoints(
2303 orientation,
2304 std::make_pair(&bp, polyConnRef),
2305 std::make_pair(&ap, connConnRef),
2306 reversed);
2307 prevDir = thisDir;
2308 }
2309 }
2310 }
2311 #if 0
2312 int ymod = -1;
2313 if ((id.vn == 1) || (id.vn == 2))
2314 {
2315 // bottom.
2316 ymod = +1;
2317 }
2318
2319 int xmod = -1;
2320 if ((id.vn == 0) || (id.vn == 1))
2321 {
2322 // right.
2323 xmod = +1;
2324 }
2325 if(id.vn > 3)
2326 {
2327 xmod = ymod = 0;
2328 if (id.vn == 4)
2329 {
2330 // right.
2331 xmod = +1;
2332 }
2333 else if (id.vn == 5)
2334 {
2335 // bottom.
2336 ymod = +1;
2337 }
2338 else if (id.vn == 6)
2339 {
2340 // left.
2341 xmod = -1;
2342 }
2343 else if (id.vn == 7)
2344 {
2345 // top.
2346 ymod = -1;
2347 }
2348 }
2349 #endif
2350
2351 crossingFlags |= CROSSING_TOUCHES;
2352 }
2353 else if (cIndex >= 2)
2354 {
2355 // The connectors cross or touch at this point.
2356 //db_printf("Cross or touch at point... \n");
2357
2358 // Crossing shouldn't be at an endpoint.
2359 COLA_ASSERT(cIndex >= 2);
2360 COLA_ASSERT(!polyIsConn || (j >= 2));
2361
2362 Avoid::Point& b0 = poly.ps[(j - 2 + poly_size) % poly_size];
2363 Avoid::Point& a0 = conn.ps[cIndex - 2];
2364
2365 int side1 = Avoid::cornerSide(a0, a1, a2, b0);
2366 int side2 = Avoid::cornerSide(a0, a1, a2, b2);
2367 if (side1 != side2)
2368 {
2369 // The connectors cross at this point.
2370 //db_printf("cross.\n");
2371 crossingCount += 1;
2372 if (crossingPoints)
2373 {
2374 crossingPoints->insert(a1);
2375 }
2376 }
2377
2378 crossingFlags |= CROSSING_TOUCHES;
2379 if (pointOrders)
2380 {
2381 if (polyIsOrthogonal && connIsOrthogonal)
2382 {
2383 // Orthogonal case:
2384 // Just order based on which comes from the left and
2385 // top in each dimension because this can only be two
2386 // L-shaped segments touching at the bend.
2387 bool reversedX = ((a0.x < a1.x) || (a2.x < a1.x));
2388 bool reversedY = ((a0.y < a1.y) || (a2.y < a1.y));
2389 // XXX: Why do we need to invert the reversed values
2390 // here? Are they wrong for orthogonal points
2391 // in the other places?
2392 (*pointOrders)[b1].addOrderedPoints(0,
2393 std::make_pair(&b1, polyConnRef),
2394 std::make_pair(&a1, connConnRef),
2395 !reversedX);
2396 (*pointOrders)[b1].addOrderedPoints(1,
2397 std::make_pair(&b1, polyConnRef),
2398 std::make_pair(&a1, connConnRef),
2399 !reversedY);
2400 }
2401 #if 0
2402 // Unused code.
2403 else
2404 {
2405 int turnDirA = vecDir(a0, a1, a2);
2406 int turnDirB = vecDir(b0, b1, b2);
2407 bool reversed = (side1 != -turnDirA);
2408 if (side1 != side2)
2409 {
2410 // Interesting case where a connector routes round
2411 // the edge of a shape and intersects a connector
2412 // which is connected to a port on the edge of the
2413 // shape.
2414 if (turnDirA == 0)
2415 {
2416 // We'll make B the outer by preference,
2417 // because the points of A are collinear.
2418 reversed = false;
2419 }
2420 else if (turnDirB == 0)
2421 {
2422 reversed = true;
2423 }
2424 // TODO COLA_ASSERT((turnDirB != 0) ||
2425 // (turnDirA != 0));
2426 }
2427 VertID vID(b1.id, b1.vn);
2428 //(*pointOrders)[b1].addOrderedPoints(&b1, &a1, reversed);
2429 }
2430 #endif
2431 }
2432 }
2433 }
2434 else
2435 {
2436 if ( polyIsOrthogonal && connIsOrthogonal)
2437 {
2438 // All crossings in orthogonal connectors will be at a
2439 // vertex in the visibility graph, so we need not bother
2440 // doing normal line intersection.
2441 continue;
2442 }
2443
2444 // No endpoint is shared between these two line segments,
2445 // so just calculate normal segment intersection.
2446
2447 Point cPt;
2448 int intersectResult = Avoid::segmentIntersectPoint(
2449 a1, a2, b1, b2, &(cPt.x), &(cPt.y));
2450
2451 if (intersectResult == Avoid::DO_INTERSECT)
2452 {
2453 if (!polyIsConn &&
2454 ((a1 == cPt) || (a2 == cPt) || (b1 == cPt) || (b2 == cPt)))
2455 {
2456 // XXX: This shouldn't actually happen, because these
2457 // points should be added as bends to each line by
2458 // splitBranchingSegments(). Thus, lets ignore them.
2459 COLA_ASSERT(a1 != cPt);
2460 COLA_ASSERT(a2 != cPt);
2461 COLA_ASSERT(b1 != cPt);
2462 COLA_ASSERT(b2 != cPt);
2463 continue;
2464 }
2465 //db_printf("crossing lines:\n");
2466 //db_printf("cPt: %g %g\n", cPt.x, cPt.y);
2467 crossingCount += 1;
2468 if (crossingPoints)
2469 {
2470 crossingPoints->insert(cPt);
2471 }
2472 }
2473 }
2474 }
2475 //db_printf("crossingcount %d %d\n", crossingCount, crossingFlags);
2476
2477 // Free shared path memory.
2478 delete[] c_path;
2479 delete[] p_path;
2480 }
2481
2482
2483 //============================================================================
2484
2485 }
2486
2487
2488