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 <cmath>
27 #include <cfloat>
28 #include <cstdlib>
29 #include <algorithm>
30
31 #include "libavoid/geomtypes.h"
32 #include "libavoid/shape.h"
33 #include "libavoid/router.h"
34 #include "libavoid/assertions.h"
35
36
37 namespace Avoid
38 {
39
40
Point()41 Point::Point() :
42 id(0),
43 vn(kUnassignedVertexNumber)
44 {
45 }
46
47
Point(const double xv,const double yv)48 Point::Point(const double xv, const double yv) :
49 x(xv),
50 y(yv),
51 id(0),
52 vn(kUnassignedVertexNumber)
53 {
54 }
55
56
operator ==(const Point & rhs) const57 bool Point::operator==(const Point& rhs) const
58 {
59 if ((x == rhs.x) && (y == rhs.y))
60 {
61 return true;
62 }
63 return false;
64 }
65
66
operator !=(const Point & rhs) const67 bool Point::operator!=(const Point& rhs) const
68 {
69 if ((x != rhs.x) || (y != rhs.y))
70 {
71 return true;
72 }
73 return false;
74 }
75
76
equals(const Point & rhs,double epsilon) const77 bool Point::equals(const Point& rhs, double epsilon) const
78 {
79 if ( (fabs(x - rhs.x) < epsilon) && (fabs(y - rhs.y) < epsilon) )
80 {
81 return true;
82 }
83 return false;
84 }
85
86
87 // Just defined to allow std::set<Point>. Not particularly meaningful!
operator <(const Point & rhs) const88 bool Point::operator<(const Point& rhs) const
89 {
90 if (x == rhs.x)
91 {
92 return (y < rhs.y);
93 }
94 return (x < rhs.x);
95 }
96
97
operator [](const size_t dimension)98 double& Point::operator[](const size_t dimension)
99 {
100 COLA_ASSERT((dimension == 0) || (dimension == 1));
101 return ((dimension == 0) ? x : y);
102 }
103
104
operator [](const size_t dimension) const105 const double& Point::operator[](const size_t dimension) const
106 {
107 COLA_ASSERT((dimension == 0) || (dimension == 1));
108 return ((dimension == 0) ? x : y);
109 }
110
operator +(const Point & rhs) const111 Point Point::operator+(const Point& rhs) const
112 {
113 return Point(x + rhs.x, y + rhs.y);
114 }
115
116
operator -(const Point & rhs) const117 Point Point::operator-(const Point& rhs) const
118 {
119 return Point(x - rhs.x, y - rhs.y);
120 }
121
122
ReferencingPolygon(const Polygon & poly,const Router * router)123 ReferencingPolygon::ReferencingPolygon(const Polygon& poly, const Router *router)
124 : PolygonInterface(),
125 _id(poly._id),
126 psRef(poly.size()),
127 psPoints(poly.size())
128 {
129 COLA_ASSERT(router != nullptr);
130 for (size_t i = 0; i < poly.size(); ++i)
131 {
132 if (poly.ps[i].id == 0)
133 {
134 // Can't be referenced, so just make a copy of the point.
135 psRef[i] = std::make_pair((Polygon *) nullptr,
136 kUnassignedVertexNumber);
137 psPoints[i] = poly.ps[i];
138 }
139 else
140 {
141 const Polygon *polyPtr = nullptr;
142 for (ObstacleList::const_iterator sh = router->m_obstacles.begin();
143 sh != router->m_obstacles.end(); ++sh)
144 {
145 if ((*sh)->id() == poly.ps[i].id)
146 {
147 const Polygon& poly = (*sh)->polygon();
148 polyPtr = &poly;
149 break;
150 }
151 }
152 COLA_ASSERT(polyPtr != nullptr);
153 psRef[i] = std::make_pair(polyPtr, poly.ps[i].vn);
154 }
155 }
156 }
157
158
ReferencingPolygon()159 ReferencingPolygon::ReferencingPolygon()
160 : PolygonInterface()
161 {
162 clear();
163 }
164
165
clear(void)166 void ReferencingPolygon::clear(void)
167 {
168 psRef.clear();
169 psPoints.clear();
170 }
171
172
empty(void) const173 bool ReferencingPolygon::empty(void) const
174 {
175 return psRef.empty();
176 }
177
178
size(void) const179 size_t ReferencingPolygon::size(void) const
180 {
181 return psRef.size();
182 }
183
184
id(void) const185 int ReferencingPolygon::id(void) const
186 {
187 return _id;
188 }
189
190
at(size_t index) const191 const Point& ReferencingPolygon::at(size_t index) const
192 {
193 COLA_ASSERT(index < size());
194
195 if (psRef[index].first != nullptr)
196 {
197 const Polygon& poly = *(psRef[index].first);
198 unsigned short poly_index = psRef[index].second;
199 COLA_ASSERT(poly_index < poly.size());
200
201 return poly.ps[poly_index];
202 }
203 else
204 {
205 return psPoints[index];
206 }
207 }
208
209
offsetBoundingBox(double offset) const210 Box PolygonInterface::offsetBoundingBox(double offset) const
211 {
212 Box bBox;
213 bBox.min.x = DBL_MAX;
214 bBox.min.y = DBL_MAX;
215 bBox.max.x = -DBL_MAX;
216 bBox.max.y = -DBL_MAX;
217
218 for (size_t i = 0; i < size(); ++i)
219 {
220 bBox.min.x = std::min(bBox.min.x, at(i).x);
221 bBox.min.y = std::min(bBox.min.y, at(i).y);
222 bBox.max.x = std::max(bBox.max.x, at(i).x);
223 bBox.max.y = std::max(bBox.max.y, at(i).y);
224 }
225
226 // Add buffer space.
227 bBox.min.x -= offset;
228 bBox.min.y -= offset;
229 bBox.max.x += offset;
230 bBox.max.y += offset;
231
232 return bBox;
233 }
234
length(size_t dimension) const235 double Box::length(size_t dimension) const
236 {
237 if (dimension == 0)
238 {
239 return (max.x - min.x);
240 }
241 return (max.y - min.y);
242 }
243
width(void) const244 double Box::width(void) const
245 {
246 return (max.x - min.x);
247 }
248
height(void) const249 double Box::height(void) const
250 {
251 return (max.y - min.y);
252 }
253
Polygon()254 Polygon::Polygon()
255 : PolygonInterface(),
256 _id(0)
257 {
258 clear();
259 }
260
261
Polygon(const int pn)262 Polygon::Polygon(const int pn)
263 : PolygonInterface(),
264 _id(0),
265 ps(pn)
266 {
267 }
268
269
Polygon(const PolygonInterface & poly)270 Polygon::Polygon(const PolygonInterface& poly)
271 : PolygonInterface(),
272 _id(poly.id()),
273 ps(poly.size())
274 {
275 for (size_t i = 0; i < poly.size(); ++i)
276 {
277 ps[i] = poly.at(i);
278 }
279 }
280
281
boundingRectPolygon(void) const282 Polygon PolygonInterface::boundingRectPolygon(void) const
283 {
284 Box boundingBox = offsetBoundingBox(0.0);
285
286 return Rectangle(boundingBox.min, boundingBox.max);
287 }
288
unitNormalForEdge(const Point & pt1,const Point & pt2)289 static Point unitNormalForEdge(const Point &pt1, const Point &pt2)
290 {
291 if (pt2 == pt1)
292 {
293 return Point(0, 0);
294 }
295 double dx = pt2.x - pt1.x;
296 double dy = pt2.y - pt1.y;
297 double f = 1.0 / std::sqrt((dx * dx) + (dy * dy));
298 dx *= f;
299 dy *= f;
300 return Point(dy, -dx);
301 }
302
offsetPolygon(double offset) const303 Polygon PolygonInterface::offsetPolygon(double offset) const
304 {
305 Polygon newPoly;
306 newPoly._id = id();
307 if (offset == 0)
308 {
309 for (size_t i = 0; i < size(); ++i)
310 {
311 newPoly.ps.push_back(at(i));
312 }
313 return newPoly;
314 }
315
316 size_t numOfEdges = size();
317 std::vector<Vector> normals(numOfEdges);
318 for (size_t i = 0; i < numOfEdges; ++i)
319 {
320 normals[i] = unitNormalForEdge(at(i), at((i + 1) % numOfEdges));
321 }
322
323 size_t j = numOfEdges - 1;
324 for (size_t i = 0; i < numOfEdges; ++i)
325 {
326 double R = 1 + ((normals[i].x * normals[j].x) +
327 (normals[i].y * normals[j].y));
328 if (((normals[j].x * normals[i].y) - (normals[i].x * normals[j].y)) *
329 offset >= 0)
330 {
331 double q = offset / R;
332 Point pt = Point(at(i).x + (normals[j].x + normals[i].x) * q,
333 at(i).y + (normals[j].y + normals[i].y) * q);
334
335 pt.id = id();
336 pt.vn = newPoly.size();
337 newPoly.ps.push_back(pt);
338 }
339 else
340 {
341 Point pt1 = Point(at(i).x + normals[j].x * offset,
342 at(i).y + normals[j].y * offset);
343 Point pt2 = at(i);
344 Point pt3 = Point(at(i).x + normals[i].x * offset,
345 at(i).y + normals[i].y * offset);
346
347 pt1.id = id();
348 pt1.vn = newPoly.size();
349 newPoly.ps.push_back(pt1);
350
351 pt2.id = id();
352 pt2.vn = newPoly.size();
353 newPoly.ps.push_back(pt2);
354
355 pt3.id = id();
356 pt3.vn = newPoly.size();
357 newPoly.ps.push_back(pt3);
358 }
359 j = i;
360 }
361
362 return newPoly;
363 }
364
clear(void)365 void Polygon::clear(void)
366 {
367 ps.clear();
368 ts.clear();
369 }
370
371
empty(void) const372 bool Polygon::empty(void) const
373 {
374 return ps.empty();
375 }
376
377
size(void) const378 size_t Polygon::size(void) const
379 {
380 return ps.size();
381 }
382
383
id(void) const384 int Polygon::id(void) const
385 {
386 return _id;
387 }
388
389
at(size_t index) const390 const Point& Polygon::at(size_t index) const
391 {
392 COLA_ASSERT(index < size());
393
394 return ps[index];
395 }
396
setPoint(size_t index,const Point & point)397 void Polygon::setPoint(size_t index, const Point& point)
398 {
399 COLA_ASSERT(index < size());
400
401 ps[index] = point;
402 }
403
404
405 static const unsigned int SHORTEN_NONE = 0;
406 static const unsigned int SHORTEN_START = 1;
407 static const unsigned int SHORTEN_END = 2;
408 static const unsigned int SHORTEN_BOTH = SHORTEN_START | SHORTEN_END;
409
410 // shorten_line():
411 // Given the two endpoints of a line segment, this function adjusts the
412 // endpoints of the line to shorten the line by shorten_length at either
413 // or both ends.
414 //
shorten_line(double & x1,double & y1,double & x2,double & y2,const unsigned int mode,const double shorten_length)415 static void shorten_line(double& x1, double& y1, double& x2, double& y2,
416 const unsigned int mode, const double shorten_length)
417 {
418 if (mode == SHORTEN_NONE)
419 {
420 return;
421 }
422
423 double rise = y1 - y2;
424 double run = x1 - x2;
425 double disty = fabs(rise);
426 double distx = fabs(run);
427
428 // Handle case where shorten length is greater than the length of the
429 // line segment.
430 if ((mode == SHORTEN_BOTH) &&
431 (((distx > disty) && ((shorten_length * 2) > distx)) ||
432 ((disty >= distx) && ((shorten_length * 2) > disty))))
433 {
434 x1 = x2 = x1 - (run / 2);
435 y1 = y2 = y1 - (rise / 2);
436 return;
437 }
438 else if ((mode == SHORTEN_START) &&
439 (((distx > disty) && (shorten_length > distx)) ||
440 ((disty >= distx) && (shorten_length > disty))))
441 {
442 x1 = x2;
443 y1 = y2;
444 return;
445 }
446 else if ((mode == SHORTEN_END) &&
447 (((distx > disty) && (shorten_length > distx)) ||
448 ((disty >= distx) && (shorten_length > disty))))
449 {
450 x2 = x1;
451 y2 = y1;
452 return;
453 }
454
455 // Handle orthogonal line segments.
456 if (x1 == x2)
457 {
458 // Vertical
459 int sign = (y1 < y2) ? 1: -1;
460
461 if (mode & SHORTEN_START)
462 {
463 y1 += (sign * shorten_length);
464 }
465 if (mode & SHORTEN_END)
466 {
467 y2 -= (sign * shorten_length);
468 }
469 return;
470 }
471 else if (y1 == y2)
472 {
473 // Horizontal
474 int sign = (x1 < x2) ? 1: -1;
475
476 if (mode & SHORTEN_START)
477 {
478 x1 += (sign * shorten_length);
479 }
480 if (mode & SHORTEN_END)
481 {
482 x2 -= (sign * shorten_length);
483 }
484 return;
485 }
486
487 int xpos = (x1 < x2) ? -1 : 1;
488 int ypos = (y1 < y2) ? -1 : 1;
489
490 double tangent = rise / run;
491
492 if (mode & SHORTEN_END)
493 {
494 if (disty > distx)
495 {
496 y2 += shorten_length * ypos;
497 x2 += shorten_length * ypos * (1 / tangent);
498 }
499 else if (disty < distx)
500 {
501 y2 += shorten_length * xpos * tangent;
502 x2 += shorten_length * xpos;
503 }
504 }
505
506 if (mode & SHORTEN_START)
507 {
508 if (disty > distx)
509 {
510 y1 -= shorten_length * ypos;
511 x1 -= shorten_length * ypos * (1 / tangent);
512 }
513 else if (disty < distx)
514 {
515 y1 -= shorten_length * xpos * tangent;
516 x1 -= shorten_length * xpos;
517 }
518 }
519 }
520
521
translate(const double xDist,const double yDist)522 void Polygon::translate(const double xDist, const double yDist)
523 {
524 for (size_t i = 0; i < size(); ++i)
525 {
526 ps[i].x += xDist;
527 ps[i].y += yDist;
528 }
529 }
530
531
simplify(void) const532 Polygon Polygon::simplify(void) const
533 {
534 // Copy the PolyLine.
535 Polygon simplified = *this;
536
537 std::vector<std::pair<size_t, Point> >& checkpoints =
538 simplified.checkpointsOnRoute;
539 bool hasCheckpointInfo = !(checkpoints.empty());
540
541 std::vector<Point>::iterator it = simplified.ps.begin();
542 if (it != simplified.ps.end()) ++it;
543
544 // Combine collinear line segments into single segments:
545 for (size_t j = 2; j < simplified.size(); )
546 {
547 if (vecDir(simplified.ps[j - 2], simplified.ps[j - 1],
548 simplified.ps[j]) == 0)
549 {
550 // These three points make up two collinear segments, so just
551 // combine them into a single segment.
552 it = simplified.ps.erase(it);
553
554 if (hasCheckpointInfo)
555 {
556 // 0 1 2 3 4 <- vertices on path
557 // +-----+-----+-----+-----+
558 // 0 1 2 3 4 5 6 7 8 <- checkpoints on points & edges
559 // |
560 // \_ deletedPointValue = 4
561 //
562 // If 1-2-3 is collinear then we want to end up with
563 //
564 // 0 1 2 3
565 // +-----+-----------+-----+
566 // 0 1 2 3 3 3 4 5 6
567 //
568 //
569 //
570 size_t deletedPointValue = (j - 1) - 1;
571 for (size_t i = 0; i < checkpoints.size(); ++i)
572 {
573 if (checkpoints[i].first == deletedPointValue)
574 {
575 checkpoints[i].first -= 1;
576 }
577 else if (checkpoints[i].first > deletedPointValue)
578 {
579 checkpoints[i].first -= 2;
580 }
581 }
582 }
583 }
584 else
585 {
586 ++j;
587 ++it;
588 }
589 }
590
591 return simplified;
592 }
593
checkpointsOnSegment(size_t segmentLowerIndex,int indexModifier) const594 std::vector<Point> Polygon::checkpointsOnSegment(size_t segmentLowerIndex,
595 int indexModifier) const
596 {
597 std::vector<Point> checkpoints;
598 // 0 1 2 3 4 <- vertices on path
599 // +-----+-----+-----+-----+
600 // 0 1 2 3 4 5 6 7 8 <- checkpoints on points & edges
601
602 size_t checkpointLowerValue = 2 * segmentLowerIndex;
603 size_t checkpointUpperValue = checkpointLowerValue + 2;
604 size_t index = 0;
605
606 if (indexModifier > 0)
607 {
608 checkpointLowerValue++;
609 }
610 else if (indexModifier < 0)
611 {
612 checkpointUpperValue--;
613 }
614
615 while (index < checkpointsOnRoute.size())
616 {
617 if ((checkpointsOnRoute[index].first >= checkpointLowerValue) &&
618 (checkpointsOnRoute[index].first <= checkpointUpperValue))
619 {
620 checkpoints.push_back(checkpointsOnRoute[index].second);
621 }
622 ++index;
623 }
624 return checkpoints;
625 }
626
627
628 #define mid(a, b) ((a < b) ? a + ((b - a) / 2) : b + ((a - b) / 2))
629
630
631 // curvedPolyline():
632 // Returns a curved approximation of this multi-segment PolyLine, with
633 // the corners replaced by smooth Bezier curves. curve_amount describes
634 // how large to make the curves.
635 // The ts value for each point in the returned Polygon describes the
636 // drawing operation: 'M' (move) marks the first point, a line segment
637 // is marked with an 'L' and three 'C's (along with the previous point)
638 // describe the control points of a Bezier curve.
639 //
curvedPolyline(const double curve_amount,const bool closed) const640 Polygon Polygon::curvedPolyline(const double curve_amount,
641 const bool closed) const
642 {
643 Polygon simplified = this->simplify();
644
645 Polygon curved;
646 size_t num_of_points = size();
647 if (num_of_points <= 2)
648 {
649 // There is only a single segment, do nothing.
650 curved = *this;
651 curved.ts.push_back('M');
652 curved.ts.push_back('L');
653 return curved;
654 }
655
656 // Build the curved polyline:
657 curved._id = _id;
658 double last_x = 0;
659 double last_y = 0;
660 if (closed)
661 {
662 double x1 = simplified.ps[0].x;
663 double y1 = simplified.ps[0].y;
664 double x2 = simplified.ps[1].x;
665 double y2 = simplified.ps[1].y;
666 shorten_line(x1, y1, x2, y2, SHORTEN_START, curve_amount);
667 curved.ps.push_back(Point(x1, y1));
668 curved.ts.push_back('M');
669 }
670 else
671 {
672 curved.ps.push_back(ps[0]);
673 curved.ts.push_back('M');
674 }
675
676 size_t simpSize = simplified.size();
677 size_t finish = (closed) ? simpSize + 2 : simpSize;
678 for (size_t j = 1; j < finish; ++j)
679 {
680 double x1 = simplified.ps[(simpSize + j - 1) % simpSize].x;
681 double y1 = simplified.ps[(simpSize + j - 1) % simpSize].y;
682 double x2 = simplified.ps[j % simpSize].x;
683 double y2 = simplified.ps[j % simpSize].y;
684
685 double old_x = x1;
686 double old_y = y1;
687
688 unsigned int mode = SHORTEN_BOTH;
689 if (!closed)
690 {
691 if (j == 1)
692 {
693 mode = SHORTEN_END;
694 }
695 else if (j == (size() - 1))
696 {
697 mode = SHORTEN_START;
698 }
699 }
700 shorten_line(x1, y1, x2, y2, mode, curve_amount);
701
702 if (j > 1)
703 {
704 curved.ts.insert(curved.ts.end(), 3, 'C');
705 curved.ps.push_back(Point(mid(last_x, old_x), mid(last_y, old_y)));
706 curved.ps.push_back(Point(mid(x1, old_x), mid(y1, old_y)));
707 curved.ps.push_back(Point(x1, y1));
708 }
709 if (closed && (j == (finish - 1)))
710 {
711 // Close the path.
712 curved.ts.push_back('Z');
713 curved.ps.push_back(Point(x1, y1));
714 break;
715 }
716 curved.ts.push_back('L');
717 curved.ps.push_back(Point(x2, y2));
718
719 last_x = x2;
720 last_y = y2;
721 }
722
723 return curved;
724 }
725
726
Rectangle(const Point & topLeft,const Point & bottomRight)727 Rectangle::Rectangle(const Point& topLeft, const Point& bottomRight)
728 : Polygon(4)
729 {
730 double xMin = std::min(topLeft.x, bottomRight.x);
731 double xMax = std::max(topLeft.x, bottomRight.x);
732 double yMin = std::min(topLeft.y, bottomRight.y);
733 double yMax = std::max(topLeft.y, bottomRight.y);
734
735 ps[0] = Point(xMax, yMin);
736 ps[1] = Point(xMax, yMax);
737 ps[2] = Point(xMin, yMax);
738 ps[3] = Point(xMin, yMin);
739 }
740
741
Rectangle(const Point & centre,const double width,const double height)742 Rectangle::Rectangle(const Point& centre, const double width,
743 const double height)
744 : Polygon(4)
745 {
746 double halfWidth = width / 2.0;
747 double halfHeight = height / 2.0;
748 double xMin = centre.x - halfWidth;
749 double xMax = centre.x + halfWidth;
750 double yMin = centre.y - halfHeight;
751 double yMax = centre.y + halfHeight;
752
753 ps[0] = Point(xMax, yMin);
754 ps[1] = Point(xMax, yMax);
755 ps[2] = Point(xMin, yMax);
756 ps[3] = Point(xMin, yMin);
757 }
758
759
760 }
761
762