src/libavoid/geomtypes.cpp

   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 */
  24
  25
  26 #include <cmath>
  27 #include <cfloat>
  28 #include <cstdlib>
  29
  30 #include "libavoid/geomtypes.h"
  31 #include "libavoid/shape.h"
  32 #include "libavoid/router.h"
  33 #include "libavoid/assertions.h"
  34
  35
  36 namespace Avoid
  37 {
  38
  39
  40 Point::Point() :
  41     id(0),
  42     vn(kUnassignedVertexNumber)
  43 {
  44 }
  45
  46
  47 Point::Point(const double xv, const double yv) :
  48     x(xv),
  49     y(yv),
  50     id(0),
  51     vn(kUnassignedVertexNumber)
  52 {
  53 }
  54
  55
  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 }
  64
  65
  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 }
  74
  75
  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 }
  85
  86
  87 double& Point::operator[](const unsigned int dimension)
  88 {
  89     COLA_ASSERT((dimension == 0) || (dimension == 1));
  90     return ((dimension == 0) ? x : y);
  91 }
  92
  93
  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 }
  99
 100
 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 }
 124
 125
 126 ReferencingPolygon::ReferencingPolygon()
 127     : PolygonInterface()
 128 {
 129     clear();
 130 }
 131
 132
 133 void ReferencingPolygon::clear(void)
 134 {
 135     ps.clear();
 136 }
 137
 138
 139 bool ReferencingPolygon::empty(void) const
 140 {
 141     return ps.empty();
 142 }
 143
 144
 145 size_t ReferencingPolygon::size(void) const
 146 {
 147     return ps.size();
 148 }
 149
 150
 151 int ReferencingPolygon::id(void) const
 152 {
 153     return _id;
 154 }
 155
 156
 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());
 163
 164     return poly.ps[poly_index];
 165 }
 166
 167
 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;
 175
 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     }
 183
 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 }
 201
 202
 203 Polygon::Polygon()
 204     : PolygonInterface()
 205 {
 206     clear();
 207 }
 208
 209
 210 Polygon::Polygon(const int pn)
 211     : PolygonInterface(),
 212       ps(pn)
 213 {
 214 }
 215
 216
 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 }
 227
 228
 229 void Polygon::clear(void)
 230 {
 231     ps.clear();
 232     ts.clear();
 233 }
 234
 235
 236 bool Polygon::empty(void) const
 237 {
 238     return ps.empty();
 239 }
 240
 241
 242 size_t Polygon::size(void) const
 243 {
 244     return ps.size();
 245 }
 246
 247
 248 int Polygon::id(void) const
 249 {
 250     return _id;
 251 }
 252
 253
 254 const Point& Polygon::at(size_t index) const
 255 {
 256     COLA_ASSERT(index < size());
 257
 258     return ps[index];
 259 }
 260
 261
 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;
 266
 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     }
 279
 280     double rise = y1 - y2;
 281     double run = x1 - x2;
 282     double disty = fabs(rise);
 283     double distx = fabs(run);
 284
 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     }
 311
 312     // Handle orthogonal line segments.
 313     if (x1 == x2)
 314     {
 315         // Vertical
 316         int sign = (y1 < y2) ? 1: -1;
 317
 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;
 332
 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     }
 343
 344     int xpos = (x1 < x2) ? -1 : 1;
 345     int ypos = (y1 < y2) ? -1 : 1;
 346
 347     double tangent = rise / run;
 348
 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     }
 362
 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 }
 377
 378
 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 }
 387
 388
 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;
 394
 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     }
 411
 412     return simplified;
 413 }
 414
 415
 416 #define mid(a, b) ((a < b) ? a + ((b - a) / 2) : b + ((a - b) / 2))
 417
 418
 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();
 432
 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     }
 443
 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     }
 463
 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;
 472
 473         double old_x = x1;
 474         double old_y = y1;
 475
 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);
 489
 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));
 506
 507         last_x = x2;
 508         last_y = y2;
 509     }
 510
 511     return curved;
 512 }
 513
 514
 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);
 522
 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 }
 528
 529
 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;
 539
 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 }
 545
 546
 547 }
 548