1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2004-2009 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
26 #include <cmath>
27 #include <cfloat>
28 #include <cstdlib>
30 #include "libavoid/geomtypes.h"
31 #include "libavoid/shape.h"
32 #include "libavoid/router.h"
33 #include "libavoid/assertions.h"
36 namespace Avoid
37 {
40 Point::Point() :
41 id(0),
42 vn(kUnassignedVertexNumber)
43 {
44 }
47 Point::Point(const double xv, const double yv) :
48 x(xv),
49 y(yv),
50 id(0),
51 vn(kUnassignedVertexNumber)
52 {
53 }
56 bool Point::operator==(const Point& rhs) const
57 {
58 if ((x == rhs.x) && (y == rhs.y))
59 {
60 return true;
61 }
62 return false;
63 }
66 bool Point::operator!=(const Point& rhs) const
67 {
68 if ((x != rhs.x) || (y != rhs.y))
69 {
70 return true;
71 }
72 return false;
73 }
76 // Just defined to allow std::set<Point>. Not particularly meaningful!
77 bool Point::operator<(const Point& rhs) const
78 {
79 if (x == rhs.x)
80 {
81 return (y < rhs.y);
82 }
83 return (x < rhs.x);
84 }
87 double& Point::operator[](const unsigned int dimension)
88 {
89 COLA_ASSERT((dimension == 0) || (dimension == 1));
90 return ((dimension == 0) ? x : y);
91 }
94 const double& Point::operator[](const unsigned int dimension) const
95 {
96 COLA_ASSERT((dimension == 0) || (dimension == 1));
97 return ((dimension == 0) ? x : y);
98 }
101 ReferencingPolygon::ReferencingPolygon(const Polygon& poly, const Router *router)
102 : PolygonInterface(),
103 _id(poly._id),
104 ps(poly.size())
105 {
106 COLA_ASSERT(router != NULL);
107 for (size_t i = 0; i < poly.size(); ++i)
108 {
109 const Polygon *polyPtr = NULL;
110 for (ShapeRefList::const_iterator sh = router->shapeRefs.begin();
111 sh != router->shapeRefs.end(); ++sh)
112 {
113 if ((*sh)->id() == poly.ps[i].id)
114 {
115 const Polygon& poly = (*sh)->polygon();
116 polyPtr = &poly;
117 break;
118 }
119 }
120 COLA_ASSERT(polyPtr != NULL);
121 ps[i] = std::make_pair(polyPtr, poly.ps[i].vn);
122 }
123 }
126 ReferencingPolygon::ReferencingPolygon()
127 : PolygonInterface()
128 {
129 clear();
130 }
133 void ReferencingPolygon::clear(void)
134 {
135 ps.clear();
136 }
139 bool ReferencingPolygon::empty(void) const
140 {
141 return ps.empty();
142 }
145 size_t ReferencingPolygon::size(void) const
146 {
147 return ps.size();
148 }
151 int ReferencingPolygon::id(void) const
152 {
153 return _id;
154 }
157 const Point& ReferencingPolygon::at(size_t index) const
158 {
159 COLA_ASSERT(index < size());
160 const Polygon& poly = *(ps[index].first);
161 unsigned short poly_index = ps[index].second;
162 COLA_ASSERT(poly_index < poly.size());
164 return poly.ps[poly_index];
165 }
168 void PolygonInterface::getBoundingRect(double *minX, double *minY,
169 double *maxX, double *maxY) const
170 {
171 double progressiveMinX = DBL_MAX;
172 double progressiveMinY = DBL_MAX;
173 double progressiveMaxX = -DBL_MAX;
174 double progressiveMaxY = -DBL_MAX;
176 for (size_t i = 0; i < size(); ++i)
177 {
178 progressiveMinX = std::min(progressiveMinX, at(i).x);
179 progressiveMinY = std::min(progressiveMinY, at(i).y);
180 progressiveMaxX = std::max(progressiveMaxX, at(i).x);
181 progressiveMaxY = std::max(progressiveMaxY, at(i).y);
182 }
184 if (minX)
185 {
186 *minX = progressiveMinX;
187 }
188 if (maxX)
189 {
190 *maxX = progressiveMaxX;
191 }
192 if (minY)
193 {
194 *minY = progressiveMinY;
195 }
196 if (maxY)
197 {
198 *maxY = progressiveMaxY;
199 }
200 }
203 Polygon::Polygon()
204 : PolygonInterface()
205 {
206 clear();
207 }
210 Polygon::Polygon(const int pn)
211 : PolygonInterface(),
212 ps(pn)
213 {
214 }
217 Polygon::Polygon(const PolygonInterface& poly)
218 : PolygonInterface(),
219 _id(poly.id()),
220 ps(poly.size())
221 {
222 for (size_t i = 0; i < poly.size(); ++i)
223 {
224 ps[i] = poly.at(i);
225 }
226 }
229 void Polygon::clear(void)
230 {
231 ps.clear();
232 ts.clear();
233 }
236 bool Polygon::empty(void) const
237 {
238 return ps.empty();
239 }
242 size_t Polygon::size(void) const
243 {
244 return ps.size();
245 }
248 int Polygon::id(void) const
249 {
250 return _id;
251 }
254 const Point& Polygon::at(size_t index) const
255 {
256 COLA_ASSERT(index < size());
258 return ps[index];
259 }
262 static const unsigned int SHORTEN_NONE = 0;
263 static const unsigned int SHORTEN_START = 1;
264 static const unsigned int SHORTEN_END = 2;
265 static const unsigned int SHORTEN_BOTH = SHORTEN_START | SHORTEN_END;
267 // shorten_line():
268 // Given the two endpoints of a line segment, this function adjusts the
269 // endpoints of the line to shorten the line by shorten_length at either
270 // or both ends.
271 //
272 static void shorten_line(double& x1, double& y1, double& x2, double& y2,
273 const unsigned int mode, const double shorten_length)
274 {
275 if (mode == SHORTEN_NONE)
276 {
277 return;
278 }
280 double rise = y1 - y2;
281 double run = x1 - x2;
282 double disty = fabs(rise);
283 double distx = fabs(run);
285 // Handle case where shorten length is greater than the length of the
286 // line segment.
287 if ((mode == SHORTEN_BOTH) &&
288 (((distx > disty) && ((shorten_length * 2) > distx)) ||
289 ((disty >= distx) && ((shorten_length * 2) > disty))))
290 {
291 x1 = x2 = x1 - (run / 2);
292 y1 = y2 = y1 - (rise / 2);
293 return;
294 }
295 else if ((mode == SHORTEN_START) &&
296 (((distx > disty) && (shorten_length > distx)) ||
297 ((disty >= distx) && (shorten_length > disty))))
298 {
299 x1 = x2;
300 y1 = y2;
301 return;
302 }
303 else if ((mode == SHORTEN_END) &&
304 (((distx > disty) && (shorten_length > distx)) ||
305 ((disty >= distx) && (shorten_length > disty))))
306 {
307 x2 = x1;
308 y2 = y1;
309 return;
310 }
312 // Handle orthogonal line segments.
313 if (x1 == x2)
314 {
315 // Vertical
316 int sign = (y1 < y2) ? 1: -1;
318 if (mode & SHORTEN_START)
319 {
320 y1 += (sign * shorten_length);
321 }
322 if (mode & SHORTEN_END)
323 {
324 y2 -= (sign * shorten_length);
325 }
326 return;
327 }
328 else if (y1 == y2)
329 {
330 // Horizontal
331 int sign = (x1 < x2) ? 1: -1;
333 if (mode & SHORTEN_START)
334 {
335 x1 += (sign * shorten_length);
336 }
337 if (mode & SHORTEN_END)
338 {
339 x2 -= (sign * shorten_length);
340 }
341 return;
342 }
344 int xpos = (x1 < x2) ? -1 : 1;
345 int ypos = (y1 < y2) ? -1 : 1;
347 double tangent = rise / run;
349 if (mode & SHORTEN_END)
350 {
351 if (disty > distx)
352 {
353 y2 += shorten_length * ypos;
354 x2 += shorten_length * ypos * (1 / tangent);
355 }
356 else if (disty < distx)
357 {
358 y2 += shorten_length * xpos * tangent;
359 x2 += shorten_length * xpos;
360 }
361 }
363 if (mode & SHORTEN_START)
364 {
365 if (disty > distx)
366 {
367 y1 -= shorten_length * ypos;
368 x1 -= shorten_length * ypos * (1 / tangent);
369 }
370 else if (disty < distx)
371 {
372 y1 -= shorten_length * xpos * tangent;
373 x1 -= shorten_length * xpos;
374 }
375 }
376 }
379 void Polygon::translate(const double xDist, const double yDist)
380 {
381 for (size_t i = 0; i < size(); ++i)
382 {
383 ps[i].x += xDist;
384 ps[i].y += yDist;
385 }
386 }
389 Polygon Polygon::simplify(void) const
390 {
391 Polygon simplified = *this;
392 std::vector<Point>::iterator it = simplified.ps.begin();
393 if (it != simplified.ps.end()) ++it;
395 // Combine collinear line segments into single segments:
396 for (size_t j = 2; j < simplified.size(); )
397 {
398 if (vecDir(simplified.ps[j - 2], simplified.ps[j - 1],
399 simplified.ps[j]) == 0)
400 {
401 // These three points make up two collinear segments, so just
402 // compine them into a single segment.
403 it = simplified.ps.erase(it);
404 }
405 else
406 {
407 ++j;
408 ++it;
409 }
410 }
412 return simplified;
413 }
416 #define mid(a, b) ((a < b) ? a + ((b - a) / 2) : b + ((a - b) / 2))
419 // curvedPolyline():
420 // Returns a curved approximation of this multi-segment PolyLine, with
421 // the corners replaced by smooth Bezier curves. curve_amount describes
422 // how large to make the curves.
423 // The ts value for each point in the returned Polygon describes the
424 // drawing operation: 'M' (move) marks the first point, a line segment
425 // is marked with an 'L' and three 'C's (along with the previous point)
426 // describe the control points of a Bezier curve.
427 //
428 Polygon Polygon::curvedPolyline(const double curve_amount,
429 const bool closed) const
430 {
431 Polygon simplified = this->simplify();
433 Polygon curved;
434 size_t num_of_points = size();
435 if (num_of_points <= 2)
436 {
437 // There is only a single segment, do nothing.
438 curved = *this;
439 curved.ts.push_back('M');
440 curved.ts.push_back('L');
441 return curved;
442 }
444 // Build the curved polyline:
445 curved._id = _id;
446 double last_x = 0;
447 double last_y = 0;
448 if (closed)
449 {
450 double x1 = simplified.ps[0].x;
451 double y1 = simplified.ps[0].y;
452 double x2 = simplified.ps[1].x;
453 double y2 = simplified.ps[1].y;
454 shorten_line(x1, y1, x2, y2, SHORTEN_START, curve_amount);
455 curved.ps.push_back(Point(x1, y1));
456 curved.ts.push_back('M');
457 }
458 else
459 {
460 curved.ps.push_back(ps[0]);
461 curved.ts.push_back('M');
462 }
464 size_t simpSize = simplified.size();
465 size_t finish = (closed) ? simpSize + 2 : simpSize;
466 for (size_t j = 1; j < finish; ++j)
467 {
468 double x1 = simplified.ps[(simpSize + j - 1) % simpSize].x;
469 double y1 = simplified.ps[(simpSize + j - 1) % simpSize].y;
470 double x2 = simplified.ps[j % simpSize].x;
471 double y2 = simplified.ps[j % simpSize].y;
473 double old_x = x1;
474 double old_y = y1;
476 unsigned int mode = SHORTEN_BOTH;
477 if (!closed)
478 {
479 if (j == 1)
480 {
481 mode = SHORTEN_END;
482 }
483 else if (j == (size() - 1))
484 {
485 mode = SHORTEN_START;
486 }
487 }
488 shorten_line(x1, y1, x2, y2, mode, curve_amount);
490 if (j > 1)
491 {
492 curved.ts.insert(curved.ts.end(), 3, 'C');
493 curved.ps.push_back(Point(mid(last_x, old_x), mid(last_y, old_y)));
494 curved.ps.push_back(Point(mid(x1, old_x), mid(y1, old_y)));
495 curved.ps.push_back(Point(x1, y1));
496 }
497 if (closed && (j == (finish - 1)))
498 {
499 // Close the path.
500 curved.ts.push_back('Z');
501 curved.ps.push_back(Point(x1, y1));
502 break;
503 }
504 curved.ts.push_back('L');
505 curved.ps.push_back(Point(x2, y2));
507 last_x = x2;
508 last_y = y2;
509 }
511 return curved;
512 }
515 Rectangle::Rectangle(const Point& topLeft, const Point& bottomRight)
516 : Polygon(4)
517 {
518 double xMin = std::min(topLeft.x, bottomRight.x);
519 double xMax = std::max(topLeft.x, bottomRight.x);
520 double yMin = std::min(topLeft.y, bottomRight.y);
521 double yMax = std::max(topLeft.y, bottomRight.y);
523 ps[0] = Point(xMax, yMin);
524 ps[1] = Point(xMax, yMax);
525 ps[2] = Point(xMin, yMax);
526 ps[3] = Point(xMin, yMin);
527 }
530 Rectangle::Rectangle(const Point& centre, const double width,
531 const double height)
532 {
533 double halfWidth = width / 2.0;
534 double halfHeight = height / 2.0;
535 double xMin = centre.x - halfWidth;
536 double xMax = centre.x + halfWidth;
537 double yMin = centre.y - halfHeight;
538 double yMax = centre.y + halfHeight;
540 ps[0] = Point(xMax, yMin);
541 ps[1] = Point(xMax, yMax);
542 ps[2] = Point(xMin, yMax);
543 ps[3] = Point(xMin, yMin);
544 }
547 }