summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/adaptagrams/libavoid/geomtypes.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/adaptagrams/libavoid/geomtypes.cpp')
-rw-r--r--src/3rdparty/adaptagrams/libavoid/geomtypes.cpp761
1 files changed, 761 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/geomtypes.cpp b/src/3rdparty/adaptagrams/libavoid/geomtypes.cpp
new file mode 100644
index 0000000..4987834
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libavoid/geomtypes.cpp
@@ -0,0 +1,761 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ *
+ * Copyright (C) 2004-2014 Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * Licensees holding a valid commercial license may use this file in
+ * accordance with the commercial license agreement provided with the
+ * library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s): Michael Wybrow
+*/
+
+
+#include <cmath>
+#include <cfloat>
+#include <cstdlib>
+#include <algorithm>
+
+#include "libavoid/geomtypes.h"
+#include "libavoid/shape.h"
+#include "libavoid/router.h"
+#include "libavoid/assertions.h"
+
+
+namespace Avoid
+{
+
+
+Point::Point() :
+ id(0),
+ vn(kUnassignedVertexNumber)
+{
+}
+
+
+Point::Point(const double xv, const double yv) :
+ x(xv),
+ y(yv),
+ id(0),
+ vn(kUnassignedVertexNumber)
+{
+}
+
+
+bool Point::operator==(const Point& rhs) const
+{
+ if ((x == rhs.x) && (y == rhs.y))
+ {
+ return true;
+ }
+ return false;
+}
+
+
+bool Point::operator!=(const Point& rhs) const
+{
+ if ((x != rhs.x) || (y != rhs.y))
+ {
+ return true;
+ }
+ return false;
+}
+
+
+bool Point::equals(const Point& rhs, double epsilon) const
+{
+ if ( (fabs(x - rhs.x) < epsilon) && (fabs(y - rhs.y) < epsilon) )
+ {
+ return true;
+ }
+ return false;
+}
+
+
+// Just defined to allow std::set<Point>. Not particularly meaningful!
+bool Point::operator<(const Point& rhs) const
+{
+ if (x == rhs.x)
+ {
+ return (y < rhs.y);
+ }
+ return (x < rhs.x);
+}
+
+
+double& Point::operator[](const size_t dimension)
+{
+ COLA_ASSERT((dimension == 0) || (dimension == 1));
+ return ((dimension == 0) ? x : y);
+}
+
+
+const double& Point::operator[](const size_t dimension) const
+{
+ COLA_ASSERT((dimension == 0) || (dimension == 1));
+ return ((dimension == 0) ? x : y);
+}
+
+Point Point::operator+(const Point& rhs) const
+{
+ return Point(x + rhs.x, y + rhs.y);
+}
+
+
+Point Point::operator-(const Point& rhs) const
+{
+ return Point(x - rhs.x, y - rhs.y);
+}
+
+
+ReferencingPolygon::ReferencingPolygon(const Polygon& poly, const Router *router)
+ : PolygonInterface(),
+ _id(poly._id),
+ psRef(poly.size()),
+ psPoints(poly.size())
+{
+ COLA_ASSERT(router != nullptr);
+ for (size_t i = 0; i < poly.size(); ++i)
+ {
+ if (poly.ps[i].id == 0)
+ {
+ // Can't be referenced, so just make a copy of the point.
+ psRef[i] = std::make_pair((Polygon *) nullptr,
+ kUnassignedVertexNumber);
+ psPoints[i] = poly.ps[i];
+ }
+ else
+ {
+ const Polygon *polyPtr = nullptr;
+ for (ObstacleList::const_iterator sh = router->m_obstacles.begin();
+ sh != router->m_obstacles.end(); ++sh)
+ {
+ if ((*sh)->id() == poly.ps[i].id)
+ {
+ const Polygon& poly = (*sh)->polygon();
+ polyPtr = &poly;
+ break;
+ }
+ }
+ COLA_ASSERT(polyPtr != nullptr);
+ psRef[i] = std::make_pair(polyPtr, poly.ps[i].vn);
+ }
+ }
+}
+
+
+ReferencingPolygon::ReferencingPolygon()
+ : PolygonInterface()
+{
+ clear();
+}
+
+
+void ReferencingPolygon::clear(void)
+{
+ psRef.clear();
+ psPoints.clear();
+}
+
+
+bool ReferencingPolygon::empty(void) const
+{
+ return psRef.empty();
+}
+
+
+size_t ReferencingPolygon::size(void) const
+{
+ return psRef.size();
+}
+
+
+int ReferencingPolygon::id(void) const
+{
+ return _id;
+}
+
+
+const Point& ReferencingPolygon::at(size_t index) const
+{
+ COLA_ASSERT(index < size());
+
+ if (psRef[index].first != nullptr)
+ {
+ const Polygon& poly = *(psRef[index].first);
+ unsigned short poly_index = psRef[index].second;
+ COLA_ASSERT(poly_index < poly.size());
+
+ return poly.ps[poly_index];
+ }
+ else
+ {
+ return psPoints[index];
+ }
+}
+
+
+Box PolygonInterface::offsetBoundingBox(double offset) const
+{
+ Box bBox;
+ bBox.min.x = DBL_MAX;
+ bBox.min.y = DBL_MAX;
+ bBox.max.x = -DBL_MAX;
+ bBox.max.y = -DBL_MAX;
+
+ for (size_t i = 0; i < size(); ++i)
+ {
+ bBox.min.x = std::min(bBox.min.x, at(i).x);
+ bBox.min.y = std::min(bBox.min.y, at(i).y);
+ bBox.max.x = std::max(bBox.max.x, at(i).x);
+ bBox.max.y = std::max(bBox.max.y, at(i).y);
+ }
+
+ // Add buffer space.
+ bBox.min.x -= offset;
+ bBox.min.y -= offset;
+ bBox.max.x += offset;
+ bBox.max.y += offset;
+
+ return bBox;
+}
+
+double Box::length(size_t dimension) const
+{
+ if (dimension == 0)
+ {
+ return (max.x - min.x);
+ }
+ return (max.y - min.y);
+}
+
+double Box::width(void) const
+{
+ return (max.x - min.x);
+}
+
+double Box::height(void) const
+{
+ return (max.y - min.y);
+}
+
+Polygon::Polygon()
+ : PolygonInterface(),
+ _id(0)
+{
+ clear();
+}
+
+
+Polygon::Polygon(const int pn)
+ : PolygonInterface(),
+ _id(0),
+ ps(pn)
+{
+}
+
+
+Polygon::Polygon(const PolygonInterface& poly)
+ : PolygonInterface(),
+ _id(poly.id()),
+ ps(poly.size())
+{
+ for (size_t i = 0; i < poly.size(); ++i)
+ {
+ ps[i] = poly.at(i);
+ }
+}
+
+
+Polygon PolygonInterface::boundingRectPolygon(void) const
+{
+ Box boundingBox = offsetBoundingBox(0.0);
+
+ return Rectangle(boundingBox.min, boundingBox.max);
+}
+
+static Point unitNormalForEdge(const Point &pt1, const Point &pt2)
+{
+ if (pt2 == pt1)
+ {
+ return Point(0, 0);
+ }
+ double dx = pt2.x - pt1.x;
+ double dy = pt2.y - pt1.y;
+ double f = 1.0 / std::sqrt((dx * dx) + (dy * dy));
+ dx *= f;
+ dy *= f;
+ return Point(dy, -dx);
+}
+
+Polygon PolygonInterface::offsetPolygon(double offset) const
+{
+ Polygon newPoly;
+ newPoly._id = id();
+ if (offset == 0)
+ {
+ for (size_t i = 0; i < size(); ++i)
+ {
+ newPoly.ps.push_back(at(i));
+ }
+ return newPoly;
+ }
+
+ size_t numOfEdges = size();
+ std::vector<Vector> normals(numOfEdges);
+ for (size_t i = 0; i < numOfEdges; ++i)
+ {
+ normals[i] = unitNormalForEdge(at(i), at((i + 1) % numOfEdges));
+ }
+
+ size_t j = numOfEdges - 1;
+ for (size_t i = 0; i < numOfEdges; ++i)
+ {
+ double R = 1 + ((normals[i].x * normals[j].x) +
+ (normals[i].y * normals[j].y));
+ if (((normals[j].x * normals[i].y) - (normals[i].x * normals[j].y)) *
+ offset >= 0)
+ {
+ double q = offset / R;
+ Point pt = Point(at(i).x + (normals[j].x + normals[i].x) * q,
+ at(i).y + (normals[j].y + normals[i].y) * q);
+
+ pt.id = id();
+ pt.vn = newPoly.size();
+ newPoly.ps.push_back(pt);
+ }
+ else
+ {
+ Point pt1 = Point(at(i).x + normals[j].x * offset,
+ at(i).y + normals[j].y * offset);
+ Point pt2 = at(i);
+ Point pt3 = Point(at(i).x + normals[i].x * offset,
+ at(i).y + normals[i].y * offset);
+
+ pt1.id = id();
+ pt1.vn = newPoly.size();
+ newPoly.ps.push_back(pt1);
+
+ pt2.id = id();
+ pt2.vn = newPoly.size();
+ newPoly.ps.push_back(pt2);
+
+ pt3.id = id();
+ pt3.vn = newPoly.size();
+ newPoly.ps.push_back(pt3);
+ }
+ j = i;
+ }
+
+ return newPoly;
+}
+
+void Polygon::clear(void)
+{
+ ps.clear();
+ ts.clear();
+}
+
+
+bool Polygon::empty(void) const
+{
+ return ps.empty();
+}
+
+
+size_t Polygon::size(void) const
+{
+ return ps.size();
+}
+
+
+int Polygon::id(void) const
+{
+ return _id;
+}
+
+
+const Point& Polygon::at(size_t index) const
+{
+ COLA_ASSERT(index < size());
+
+ return ps[index];
+}
+
+void Polygon::setPoint(size_t index, const Point& point)
+{
+ COLA_ASSERT(index < size());
+
+ ps[index] = point;
+}
+
+
+static const unsigned int SHORTEN_NONE = 0;
+static const unsigned int SHORTEN_START = 1;
+static const unsigned int SHORTEN_END = 2;
+static const unsigned int SHORTEN_BOTH = SHORTEN_START | SHORTEN_END;
+
+// shorten_line():
+// Given the two endpoints of a line segment, this function adjusts the
+// endpoints of the line to shorten the line by shorten_length at either
+// or both ends.
+//
+static void shorten_line(double& x1, double& y1, double& x2, double& y2,
+ const unsigned int mode, const double shorten_length)
+{
+ if (mode == SHORTEN_NONE)
+ {
+ return;
+ }
+
+ double rise = y1 - y2;
+ double run = x1 - x2;
+ double disty = fabs(rise);
+ double distx = fabs(run);
+
+ // Handle case where shorten length is greater than the length of the
+ // line segment.
+ if ((mode == SHORTEN_BOTH) &&
+ (((distx > disty) && ((shorten_length * 2) > distx)) ||
+ ((disty >= distx) && ((shorten_length * 2) > disty))))
+ {
+ x1 = x2 = x1 - (run / 2);
+ y1 = y2 = y1 - (rise / 2);
+ return;
+ }
+ else if ((mode == SHORTEN_START) &&
+ (((distx > disty) && (shorten_length > distx)) ||
+ ((disty >= distx) && (shorten_length > disty))))
+ {
+ x1 = x2;
+ y1 = y2;
+ return;
+ }
+ else if ((mode == SHORTEN_END) &&
+ (((distx > disty) && (shorten_length > distx)) ||
+ ((disty >= distx) && (shorten_length > disty))))
+ {
+ x2 = x1;
+ y2 = y1;
+ return;
+ }
+
+ // Handle orthogonal line segments.
+ if (x1 == x2)
+ {
+ // Vertical
+ int sign = (y1 < y2) ? 1: -1;
+
+ if (mode & SHORTEN_START)
+ {
+ y1 += (sign * shorten_length);
+ }
+ if (mode & SHORTEN_END)
+ {
+ y2 -= (sign * shorten_length);
+ }
+ return;
+ }
+ else if (y1 == y2)
+ {
+ // Horizontal
+ int sign = (x1 < x2) ? 1: -1;
+
+ if (mode & SHORTEN_START)
+ {
+ x1 += (sign * shorten_length);
+ }
+ if (mode & SHORTEN_END)
+ {
+ x2 -= (sign * shorten_length);
+ }
+ return;
+ }
+
+ int xpos = (x1 < x2) ? -1 : 1;
+ int ypos = (y1 < y2) ? -1 : 1;
+
+ double tangent = rise / run;
+
+ if (mode & SHORTEN_END)
+ {
+ if (disty > distx)
+ {
+ y2 += shorten_length * ypos;
+ x2 += shorten_length * ypos * (1 / tangent);
+ }
+ else if (disty < distx)
+ {
+ y2 += shorten_length * xpos * tangent;
+ x2 += shorten_length * xpos;
+ }
+ }
+
+ if (mode & SHORTEN_START)
+ {
+ if (disty > distx)
+ {
+ y1 -= shorten_length * ypos;
+ x1 -= shorten_length * ypos * (1 / tangent);
+ }
+ else if (disty < distx)
+ {
+ y1 -= shorten_length * xpos * tangent;
+ x1 -= shorten_length * xpos;
+ }
+ }
+}
+
+
+void Polygon::translate(const double xDist, const double yDist)
+{
+ for (size_t i = 0; i < size(); ++i)
+ {
+ ps[i].x += xDist;
+ ps[i].y += yDist;
+ }
+}
+
+
+Polygon Polygon::simplify(void) const
+{
+ // Copy the PolyLine.
+ Polygon simplified = *this;
+
+ std::vector<std::pair<size_t, Point> >& checkpoints =
+ simplified.checkpointsOnRoute;
+ bool hasCheckpointInfo = !(checkpoints.empty());
+
+ std::vector<Point>::iterator it = simplified.ps.begin();
+ if (it != simplified.ps.end()) ++it;
+
+ // Combine collinear line segments into single segments:
+ for (size_t j = 2; j < simplified.size(); )
+ {
+ if (vecDir(simplified.ps[j - 2], simplified.ps[j - 1],
+ simplified.ps[j]) == 0)
+ {
+ // These three points make up two collinear segments, so just
+ // combine them into a single segment.
+ it = simplified.ps.erase(it);
+
+ if (hasCheckpointInfo)
+ {
+ // 0 1 2 3 4 <- vertices on path
+ // +-----+-----+-----+-----+
+ // 0 1 2 3 4 5 6 7 8 <- checkpoints on points & edges
+ // |
+ // \_ deletedPointValue = 4
+ //
+ // If 1-2-3 is collinear then we want to end up with
+ //
+ // 0 1 2 3
+ // +-----+-----------+-----+
+ // 0 1 2 3 3 3 4 5 6
+ //
+ //
+ //
+ size_t deletedPointValue = (j - 1) - 1;
+ for (size_t i = 0; i < checkpoints.size(); ++i)
+ {
+ if (checkpoints[i].first == deletedPointValue)
+ {
+ checkpoints[i].first -= 1;
+ }
+ else if (checkpoints[i].first > deletedPointValue)
+ {
+ checkpoints[i].first -= 2;
+ }
+ }
+ }
+ }
+ else
+ {
+ ++j;
+ ++it;
+ }
+ }
+
+ return simplified;
+}
+
+std::vector<Point> Polygon::checkpointsOnSegment(size_t segmentLowerIndex,
+ int indexModifier) const
+{
+ std::vector<Point> checkpoints;
+ // 0 1 2 3 4 <- vertices on path
+ // +-----+-----+-----+-----+
+ // 0 1 2 3 4 5 6 7 8 <- checkpoints on points & edges
+
+ size_t checkpointLowerValue = 2 * segmentLowerIndex;
+ size_t checkpointUpperValue = checkpointLowerValue + 2;
+ size_t index = 0;
+
+ if (indexModifier > 0)
+ {
+ checkpointLowerValue++;
+ }
+ else if (indexModifier < 0)
+ {
+ checkpointUpperValue--;
+ }
+
+ while (index < checkpointsOnRoute.size())
+ {
+ if ((checkpointsOnRoute[index].first >= checkpointLowerValue) &&
+ (checkpointsOnRoute[index].first <= checkpointUpperValue))
+ {
+ checkpoints.push_back(checkpointsOnRoute[index].second);
+ }
+ ++index;
+ }
+ return checkpoints;
+}
+
+
+#define mid(a, b) ((a < b) ? a + ((b - a) / 2) : b + ((a - b) / 2))
+
+
+// curvedPolyline():
+// Returns a curved approximation of this multi-segment PolyLine, with
+// the corners replaced by smooth Bezier curves. curve_amount describes
+// how large to make the curves.
+// The ts value for each point in the returned Polygon describes the
+// drawing operation: 'M' (move) marks the first point, a line segment
+// is marked with an 'L' and three 'C's (along with the previous point)
+// describe the control points of a Bezier curve.
+//
+Polygon Polygon::curvedPolyline(const double curve_amount,
+ const bool closed) const
+{
+ Polygon simplified = this->simplify();
+
+ Polygon curved;
+ size_t num_of_points = size();
+ if (num_of_points <= 2)
+ {
+ // There is only a single segment, do nothing.
+ curved = *this;
+ curved.ts.push_back('M');
+ curved.ts.push_back('L');
+ return curved;
+ }
+
+ // Build the curved polyline:
+ curved._id = _id;
+ double last_x = 0;
+ double last_y = 0;
+ if (closed)
+ {
+ double x1 = simplified.ps[0].x;
+ double y1 = simplified.ps[0].y;
+ double x2 = simplified.ps[1].x;
+ double y2 = simplified.ps[1].y;
+ shorten_line(x1, y1, x2, y2, SHORTEN_START, curve_amount);
+ curved.ps.push_back(Point(x1, y1));
+ curved.ts.push_back('M');
+ }
+ else
+ {
+ curved.ps.push_back(ps[0]);
+ curved.ts.push_back('M');
+ }
+
+ size_t simpSize = simplified.size();
+ size_t finish = (closed) ? simpSize + 2 : simpSize;
+ for (size_t j = 1; j < finish; ++j)
+ {
+ double x1 = simplified.ps[(simpSize + j - 1) % simpSize].x;
+ double y1 = simplified.ps[(simpSize + j - 1) % simpSize].y;
+ double x2 = simplified.ps[j % simpSize].x;
+ double y2 = simplified.ps[j % simpSize].y;
+
+ double old_x = x1;
+ double old_y = y1;
+
+ unsigned int mode = SHORTEN_BOTH;
+ if (!closed)
+ {
+ if (j == 1)
+ {
+ mode = SHORTEN_END;
+ }
+ else if (j == (size() - 1))
+ {
+ mode = SHORTEN_START;
+ }
+ }
+ shorten_line(x1, y1, x2, y2, mode, curve_amount);
+
+ if (j > 1)
+ {
+ curved.ts.insert(curved.ts.end(), 3, 'C');
+ curved.ps.push_back(Point(mid(last_x, old_x), mid(last_y, old_y)));
+ curved.ps.push_back(Point(mid(x1, old_x), mid(y1, old_y)));
+ curved.ps.push_back(Point(x1, y1));
+ }
+ if (closed && (j == (finish - 1)))
+ {
+ // Close the path.
+ curved.ts.push_back('Z');
+ curved.ps.push_back(Point(x1, y1));
+ break;
+ }
+ curved.ts.push_back('L');
+ curved.ps.push_back(Point(x2, y2));
+
+ last_x = x2;
+ last_y = y2;
+ }
+
+ return curved;
+}
+
+
+Rectangle::Rectangle(const Point& topLeft, const Point& bottomRight)
+ : Polygon(4)
+{
+ double xMin = std::min(topLeft.x, bottomRight.x);
+ double xMax = std::max(topLeft.x, bottomRight.x);
+ double yMin = std::min(topLeft.y, bottomRight.y);
+ double yMax = std::max(topLeft.y, bottomRight.y);
+
+ ps[0] = Point(xMax, yMin);
+ ps[1] = Point(xMax, yMax);
+ ps[2] = Point(xMin, yMax);
+ ps[3] = Point(xMin, yMin);
+}
+
+
+Rectangle::Rectangle(const Point& centre, const double width,
+ const double height)
+ : Polygon(4)
+{
+ double halfWidth = width / 2.0;
+ double halfHeight = height / 2.0;
+ double xMin = centre.x - halfWidth;
+ double xMax = centre.x + halfWidth;
+ double yMin = centre.y - halfHeight;
+ double yMax = centre.y + halfHeight;
+
+ ps[0] = Point(xMax, yMin);
+ ps[1] = Point(xMax, yMax);
+ ps[2] = Point(xMin, yMax);
+ ps[3] = Point(xMin, yMin);
+}
+
+
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-03 16:16:29 +0000