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 */
25 //! @file geomtypes.h
26 //! @brief Contains the interface for various geometry types and classes.
29 #ifndef AVOID_GEOMTYPES_H
30 #define AVOID_GEOMTYPES_H
32 #include <vector>
33 #include <utility>
36 namespace Avoid
37 {
40 //! @brief The Point class defines a point in the plane.
41 //!
42 //! Points consist of an x and y value. They may also have an ID and vertex
43 //! number associated with them.
44 //!
45 class Point
46 {
47 public:
48 //! @brief Default constructor.
49 //!
50 Point();
51 //! @brief Standard constructor.
52 //!
53 //! @param[in] xv The x position of the point.
54 //! @param[in] yv The y position of the point.
55 //!
56 Point(const double xv, const double yv);
58 //! @brief Comparison operator. Returns true if at same position.
59 //!
60 //! @param[in] rhs The point to compare with this one.
61 //! @return The result of the comparison.
62 //!
63 bool operator==(const Point& rhs) const;
64 //! @brief Comparison operator. Returns true if at different positions.
65 //!
66 //! @param[in] rhs The point to compare with this one.
67 //! @return The result of the comparison.
68 //!
69 bool operator!=(const Point& rhs) const;
70 //! @brief Comparison operator. Returns true if less-then rhs point.
71 //!
72 //! @note This operator is not particularly useful, but is defined
73 //! to allow std::set<Point>.
74 //!
75 //! @param[in] rhs The point to compare with this one.
76 //! @return The result of the comparison.
77 //!
78 bool operator<(const Point& rhs) const;
80 //! @brief Returns the x or y value of the point, given the dimension.
81 //!
82 //! @param[in] dimension The dimension: 0 for x, 1 for y.
83 //! @return The component of the point in that dimension.
84 double& operator[](const unsigned int dimension);
85 const double& operator[](const unsigned int dimension) const;
87 //! The x position.
88 double x;
89 //! The y position.
90 double y;
91 //! The ID associated with this point.
92 unsigned int id;
93 //! The vertex number associated with this point.
94 unsigned short vn;
96 };
99 //! Constant value representing an unassigned vertex number.
100 //!
101 static const unsigned short kUnassignedVertexNumber = 8;
104 //! @brief A vector, represented by the Point class.
105 //!
106 typedef Point Vector;
109 //! @brief A common interface used by the Polygon classes.
110 //!
111 class PolygonInterface
112 {
113 public:
114 //! @brief Constructor.
115 PolygonInterface() { }
116 //! @brief Destructor.
117 virtual ~PolygonInterface() { }
118 //! @brief Resets this to the empty polygon.
119 virtual void clear(void) = 0;
120 //! @brief Returns true if this polygon is empty.
121 virtual bool empty(void) const = 0;
122 //! @brief Returns the number of points in this polygon.
123 virtual size_t size(void) const = 0;
124 //! @brief Returns the ID value associated with this polygon.
125 virtual int id(void) const = 0;
126 //! @brief Returns a specific point in the polygon.
127 //! @param[in] index The array index of the point to be returned.
128 virtual const Point& at(size_t index) const = 0;
129 //! @brief Returns the bounding rectangle that contains this polygon.
130 //!
131 //! If a NULL pointer is passed for any of the arguments, then that
132 //! value is ignored and not returned.
133 //!
134 //! @param[out] minX The left hand side of the bounding box.
135 //! @param[out] minY The top of the bounding box.
136 //! @param[out] maxX The right hand side of the bounding box.
137 //! @param[out] maxY The bottom of the bounding box.
138 void getBoundingRect(double *minX, double *minY,
139 double *maxX, double *maxY) const;
140 };
143 //! @brief A line between two points.
144 //!
145 class Edge
146 {
147 public:
148 //! The first point.
149 Point a;
150 //! The second point.
151 Point b;
152 };
155 //! @brief A bounding box, represented with an Edge between top-left and
156 //! bottom-right corners.
157 //!
158 typedef Edge BBox;
161 class Router;
162 class ReferencingPolygon;
165 //! @brief A dynamic Polygon, to which points can be easily added and removed.
166 //!
167 //! @note The Rectangle class can be used as an easy way of constructing a
168 //! square or rectangular polygon.
169 //!
170 class Polygon : public PolygonInterface
171 {
172 public:
173 //! @brief Constructs an empty polygon (with zero points).
174 Polygon();
175 //! @brief Constructs a new polygon with n points.
176 //!
177 //! A rectangle would be comprised of four point. An n segment
178 //! PolyLine (represented as a Polygon) would be comprised of n+1
179 //! points. Whether a particular Polygon is closed or not, depends
180 //! on whether it is a Polygon or Polyline. Shape polygons are always
181 //! considered to be closed, meaning the last point joins back to the
182 //! first point.
183 //!
184 //! @param[in] n Number of points in the polygon.
185 //!
186 Polygon(const int n);
187 //! @brief Constructs a new polygon from an existing Polygon.
188 //!
189 //! @param[in] poly An existing polygon to copy the new polygon from.
190 //!
191 Polygon(const PolygonInterface& poly);
192 //! @brief Resets this to the empty polygon.
193 void clear(void);
194 //! @brief Returns true if this polygon is empty.
195 bool empty(void) const;
196 //! @brief Returns the number of points in this polygon.
197 size_t size(void) const;
198 //! @brief Returns the ID value associated with this polygon.
199 int id(void) const;
200 //! @brief Returns a specific point in the polygon.
201 //! @param[in] index The array index of the point to be returned.
202 const Point& at(size_t index) const;
203 //! @brief Returns a simplified Polyline, where all collinear line
204 //! segments have been collapsed down into single line
205 //! segments.
206 //!
207 //! @return A new polyline with a simplified representation.
208 //!
209 Polygon simplify(void) const;
210 //! @brief Returns a curved approximation of this multi-segment
211 //! PolyLine, with the corners replaced by smooth Bezier
212 //! curves.
213 //!
214 //! This function does not do any further obstacle avoidance with the
215 //! curves produced. Hence, you would usually specify a curve_amount
216 //! in similar size to the space buffer around obstacles in the scene.
217 //! This way the curves will cut the corners around shapes but still
218 //! run within this buffer space.
219 //!
220 //! @param curve_amount Describes the distance along the end of each
221 //! line segment to turn into a curve.
222 //! @param closed Describes whether the Polygon should be
223 //! treated as closed. Defaults to false.
224 //! @return A new polyline (polygon) representing the curved path.
225 //! Its points represent endpoints of line segments and
226 //! Bezier spline control points. The Polygon::ts vector for
227 //! this returned polygon is populated with a character for
228 //! each point describing its type.
229 //! @sa ts
230 Polygon curvedPolyline(const double curve_amount,
231 const bool closed = false) const;
232 //! @brief Translates the polygon position by a relative amount.
233 //!
234 //! @param[in] xDist Distance to move polygon in the x dimension.
235 //! @param[in] yDist Distance to move polygon in the y dimension.
236 void translate(const double xDist, const double yDist);
238 //! @brief An ID for the polygon.
239 int _id;
240 //! @brief A vector of the points that make up the Polygon.
241 std::vector<Point> ps;
242 //! @brief If used, denotes whether the corresponding point in ps is
243 //! a move-to operation or a Bezier curve-to.
244 //!
245 //! Each character describes the drawing operation for the
246 //! corresponding point in the ps vector. Possible values are:
247 //! - 'M': A moveto operation, marks the first point;
248 //! - 'L': A lineto operation, is a line from the previous point to
249 //! the current point; or
250 //! - 'C': A curveto operation, three consecutive 'C' points
251 //! (along with the previous point) describe the control points
252 //! of a Bezier curve.
253 //! - 'Z': Closes the path (used for cluster boundaries).
254 //!
255 //! @note This vector will currently only be populated for polygons
256 //! returned by curvedPolyline().
257 std::vector<char> ts;
258 };
261 //! @brief A multi-segment line, represented with the Polygon class.
262 //!
263 typedef Polygon PolyLine;
266 //! @brief A Polygon which just references its points from other Polygons.
267 //!
268 //! This type of Polygon is used to accurately represent cluster boundaries
269 //! made up from the corner points of shapes.
270 //!
271 class ReferencingPolygon : public PolygonInterface
272 {
273 public:
274 ReferencingPolygon();
275 ReferencingPolygon(const Polygon& poly, const Router *router);
276 void clear(void);
277 bool empty(void) const;
278 size_t size(void) const;
279 int id(void) const;
280 const Point& at(size_t index) const;
282 int _id;
283 std::vector<std::pair<const Polygon *, unsigned short> > ps;
284 };
287 //! @brief A Rectangle, a simpler way to define the polygon for square or
288 //! rectangular shapes.
289 //!
290 class Rectangle : public Polygon
291 {
292 public:
293 //! @brief Constructs a rectangular polygon given two opposing
294 //! corner points.
295 //!
296 //! @param[in] topLeft The first corner point of the rectangle.
297 //! @param[in] bottomRight The opposing corner point of the rectangle.
298 //!
299 Rectangle(const Point& topLeft, const Point& bottomRight);
301 //! @brief Constructs a rectangular polygon given the centre, width
302 //! and height.
303 //!
304 //! @param[in] centre The centre of the rectangle, specified as
305 //! a point.
306 //! @param[in] width The width of the rectangle.
307 //! @param[in] height The height of the rectangle.
308 //!
309 Rectangle(const Point& centre, const double width, const double height);
310 };
313 }
315 #endif