1 /**
2 * \file
3 * \brief Axis-aligned rectangle
4 *//*
5 * Authors:
6 * Michael Sloan <mgsloan@gmail.com>
7 * Krzysztof Kosiński <tweenk.pl@gmail.com>
8 * Copyright 2007-2011 Authors
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it either under the terms of the GNU Lesser General Public
12 * License version 2.1 as published by the Free Software Foundation
13 * (the "LGPL") or, at your option, under the terms of the Mozilla
14 * Public License Version 1.1 (the "MPL"). If you do not alter this
15 * notice, a recipient may use your version of this file under either
16 * the MPL or the LGPL.
17 *
18 * You should have received a copy of the LGPL along with this library
19 * in the file COPYING-LGPL-2.1; if not, output to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 * You should have received a copy of the MPL along with this library
22 * in the file COPYING-MPL-1.1
23 *
24 * The contents of this file are subject to the Mozilla Public License
25 * Version 1.1 (the "License"); you may not use this file except in
26 * compliance with the License. You may obtain a copy of the License at
27 * http://www.mozilla.org/MPL/
28 *
29 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
31 * the specific language governing rights and limitations.
32 *
33 * Authors of original rect class:
34 * Lauris Kaplinski <lauris@kaplinski.com>
35 * Nathan Hurst <njh@mail.csse.monash.edu.au>
36 * bulia byak <buliabyak@users.sf.net>
37 * MenTaLguY <mental@rydia.net>
38 */
39
40 #ifndef LIB2GEOM_SEEN_GENERIC_RECT_H
41 #define LIB2GEOM_SEEN_GENERIC_RECT_H
42
43 #include <limits>
44 #include <iostream>
45 #include <optional>
46 #include <2geom/coord.h>
47
48 namespace Geom {
49
50 template <typename C>
51 class GenericOptRect;
52
53 /**
54 * @brief Axis aligned, non-empty, generic rectangle.
55 * @ingroup Primitives
56 */
57 template <typename C>
58 class GenericRect
59 : CoordTraits<C>::RectOps
60 {
61 typedef typename CoordTraits<C>::IntervalType CInterval;
62 typedef typename CoordTraits<C>::PointType CPoint;
63 typedef typename CoordTraits<C>::RectType CRect;
64 typedef typename CoordTraits<C>::OptRectType OptCRect;
65 protected:
66 CInterval f[2];
67 public:
68 typedef CInterval D1Value;
69 typedef CInterval &D1Reference;
70 typedef CInterval const &D1ConstReference;
71
72 /// @name Create rectangles.
73 /// @{
74 /** @brief Create a rectangle that contains only the point at (0,0). */
GenericRect()75 GenericRect() { f[X] = f[Y] = CInterval(); }
76 /** @brief Create a rectangle from X and Y intervals. */
GenericRect(CInterval const & a,CInterval const & b)77 GenericRect(CInterval const &a, CInterval const &b) {
78 f[X] = a;
79 f[Y] = b;
80 }
81 /** @brief Create a rectangle from two points. */
GenericRect(CPoint const & a,CPoint const & b)82 GenericRect(CPoint const &a, CPoint const &b) {
83 f[X] = CInterval(a[X], b[X]);
84 f[Y] = CInterval(a[Y], b[Y]);
85 }
86 /** @brief Create rectangle from coordinates of two points. */
GenericRect(C x0,C y0,C x1,C y1)87 GenericRect(C x0, C y0, C x1, C y1) {
88 f[X] = CInterval(x0, x1);
89 f[Y] = CInterval(y0, y1);
90 }
91 /** @brief Create a rectangle from a range of points.
92 * The resulting rectangle will contain all points from the range.
93 * The return type of iterators must be convertible to Point.
94 * The range must not be empty. For possibly empty ranges, see OptRect.
95 * @param start Beginning of the range
96 * @param end End of the range
97 * @return Rectangle that contains all points from [start, end). */
98 template <typename InputIterator>
from_range(InputIterator start,InputIterator end)99 static CRect from_range(InputIterator start, InputIterator end) {
100 assert(start != end);
101 CPoint p1 = *start++;
102 CRect result(p1, p1);
103 for (; start != end; ++start) {
104 result.expandTo(*start);
105 }
106 return result;
107 }
108 /** @brief Create a rectangle from a C-style array of points it should contain. */
from_array(CPoint const * c,unsigned n)109 static CRect from_array(CPoint const *c, unsigned n) {
110 CRect result = GenericRect<C>::from_range(c, c+n);
111 return result;
112 }
113 /** @brief Create rectangle from origin and dimensions. */
from_xywh(C x,C y,C w,C h)114 static CRect from_xywh(C x, C y, C w, C h) {
115 CPoint xy(x, y);
116 CPoint wh(w, h);
117 CRect result(xy, xy + wh);
118 return result;
119 }
120 /** @brief Create rectangle from origin and dimensions. */
from_xywh(CPoint const & xy,CPoint const & wh)121 static CRect from_xywh(CPoint const &xy, CPoint const &wh) {
122 CRect result(xy, xy + wh);
123 return result;
124 }
125 /// Create infinite rectangle.
infinite()126 static CRect infinite() {
127 CPoint p0(std::numeric_limits<C>::min(), std::numeric_limits<C>::min());
128 CPoint p1(std::numeric_limits<C>::max(), std::numeric_limits<C>::max());
129 CRect result(p0, p1);
130 return result;
131 }
132 /// @}
133
134 /// @name Inspect dimensions.
135 /// @{
136 CInterval &operator[](unsigned i) { return f[i]; }
137 CInterval const &operator[](unsigned i) const { return f[i]; }
138 CInterval &operator[](Dim2 d) { return f[d]; }
139 CInterval const &operator[](Dim2 d) const { return f[d]; }
140
141 /** @brief Get the corner of the rectangle with smallest coordinate values.
142 * In 2Geom standard coordinate system, this means upper left. */
min()143 CPoint min() const { CPoint p(f[X].min(), f[Y].min()); return p; }
144 /** @brief Get the corner of the rectangle with largest coordinate values.
145 * In 2Geom standard coordinate system, this means lower right. */
max()146 CPoint max() const { CPoint p(f[X].max(), f[Y].max()); return p; }
147 /** @brief Return the n-th corner of the rectangle.
148 * Returns corners in the direction of growing angles, starting from
149 * the one given by min(). For the standard coordinate system used
150 * in 2Geom (+Y downwards), this means clockwise starting from
151 * the upper left. */
corner(unsigned i)152 CPoint corner(unsigned i) const {
153 switch(i % 4) {
154 case 0: return CPoint(f[X].min(), f[Y].min());
155 case 1: return CPoint(f[X].max(), f[Y].min());
156 case 2: return CPoint(f[X].max(), f[Y].max());
157 default: return CPoint(f[X].min(), f[Y].max());
158 }
159 }
160
161 //We should probably remove these - they're coord sys gnostic
162 /** @brief Return top coordinate of the rectangle (+Y is downwards). */
top()163 C top() const { return f[Y].min(); }
164 /** @brief Return bottom coordinate of the rectangle (+Y is downwards). */
bottom()165 C bottom() const { return f[Y].max(); }
166 /** @brief Return leftmost coordinate of the rectangle (+X is to the right). */
left()167 C left() const { return f[X].min(); }
168 /** @brief Return rightmost coordinate of the rectangle (+X is to the right). */
right()169 C right() const { return f[X].max(); }
170
171 /** @brief Get the horizontal extent of the rectangle. */
width()172 C width() const { return f[X].extent(); }
173 /** @brief Get the vertical extent of the rectangle. */
height()174 C height() const { return f[Y].extent(); }
175 /** @brief Get the ratio of width to height of the rectangle. */
aspectRatio()176 Coord aspectRatio() const { return Coord(width()) / Coord(height()); }
177
178 /** @brief Get rectangle's width and height as a point.
179 * @return Point with X coordinate corresponding to the width and the Y coordinate
180 * corresponding to the height of the rectangle. */
dimensions()181 CPoint dimensions() const { return CPoint(f[X].extent(), f[Y].extent()); }
182 /** @brief Get the point in the geometric center of the rectangle. */
midpoint()183 CPoint midpoint() const { return CPoint(f[X].middle(), f[Y].middle()); }
184
185 /** @brief Compute rectangle's area. */
area()186 C area() const { return f[X].extent() * f[Y].extent(); }
187 /** @brief Check whether the rectangle has zero area. */
hasZeroArea()188 bool hasZeroArea() const { return f[X].isSingular() || f[Y].isSingular(); }
189
190 /** @brief Get the larger extent (width or height) of the rectangle. */
maxExtent()191 C maxExtent() const { return std::max(f[X].extent(), f[Y].extent()); }
192 /** @brief Get the smaller extent (width or height) of the rectangle. */
minExtent()193 C minExtent() const { return std::min(f[X].extent(), f[Y].extent()); }
194
195 /** @brief Clamp point to the rectangle. */
clamp(CPoint const & p)196 CPoint clamp(CPoint const &p) const {
197 CPoint result(f[X].clamp(p[X]), f[Y].clamp(p[Y]));
198 return result;
199 }
200 /** @brief Get the nearest point on the edge of the rectangle. */
nearestEdgePoint(CPoint const & p)201 CPoint nearestEdgePoint(CPoint const &p) const {
202 CPoint result = p;
203 if (!contains(p)) {
204 result = clamp(p);
205 } else {
206 C cx = f[X].nearestEnd(p[X]);
207 C cy = f[Y].nearestEnd(p[Y]);
208 if (std::abs(cx - p[X]) <= std::abs(cy - p[Y])) {
209 result[X] = cx;
210 } else {
211 result[Y] = cy;
212 }
213 }
214 return result;
215 }
216 /// @}
217
218 /// @name Test other rectangles and points for inclusion.
219 /// @{
220 /** @brief Check whether the rectangles have any common points. */
intersects(GenericRect<C> const & r)221 bool intersects(GenericRect<C> const &r) const {
222 return f[X].intersects(r[X]) && f[Y].intersects(r[Y]);
223 }
224 /** @brief Check whether the rectangle includes all points in the given rectangle. */
contains(GenericRect<C> const & r)225 bool contains(GenericRect<C> const &r) const {
226 return f[X].contains(r[X]) && f[Y].contains(r[Y]);
227 }
228
229 /** @brief Check whether the rectangles have any common points.
230 * Empty rectangles will not intersect with any other rectangle. */
231 inline bool intersects(OptCRect const &r) const;
232 /** @brief Check whether the rectangle includes all points in the given rectangle.
233 * Empty rectangles will be contained in any non-empty rectangle. */
234 inline bool contains(OptCRect const &r) const;
235
236 /** @brief Check whether the given point is within the rectangle. */
contains(CPoint const & p)237 bool contains(CPoint const &p) const {
238 return f[X].contains(p[X]) && f[Y].contains(p[Y]);
239 }
240 /// @}
241
242 /// @name Modify the rectangle.
243 /// @{
244 /** @brief Set the minimum X coordinate of the rectangle. */
setLeft(C val)245 void setLeft(C val) {
246 f[X].setMin(val);
247 }
248 /** @brief Set the maximum X coordinate of the rectangle. */
setRight(C val)249 void setRight(C val) {
250 f[X].setMax(val);
251 }
252 /** @brief Set the minimum Y coordinate of the rectangle. */
setTop(C val)253 void setTop(C val) {
254 f[Y].setMin(val);
255 }
256 /** @brief Set the maximum Y coordinate of the rectangle. */
setBottom(C val)257 void setBottom(C val) {
258 f[Y].setMax(val);
259 }
260 /** @brief Set the upper left point of the rectangle. */
setMin(CPoint const & p)261 void setMin(CPoint const &p) {
262 f[X].setMin(p[X]);
263 f[Y].setMin(p[Y]);
264 }
265 /** @brief Set the lower right point of the rectangle. */
setMax(CPoint const & p)266 void setMax(CPoint const &p) {
267 f[X].setMax(p[X]);
268 f[Y].setMax(p[Y]);
269 }
270 /** @brief Enlarge the rectangle to contain the given point. */
expandTo(CPoint const & p)271 void expandTo(CPoint const &p) {
272 f[X].expandTo(p[X]); f[Y].expandTo(p[Y]);
273 }
274 /** @brief Enlarge the rectangle to contain the argument. */
unionWith(CRect const & b)275 void unionWith(CRect const &b) {
276 f[X].unionWith(b[X]); f[Y].unionWith(b[Y]);
277 }
278 /** @brief Enlarge the rectangle to contain the argument.
279 * Unioning with an empty rectangle results in no changes. */
280 void unionWith(OptCRect const &b);
281
282 /** @brief Expand the rectangle in both directions by the specified amount.
283 * Note that this is different from scaling. Negative values will shrink the
284 * rectangle. If <code>-amount</code> is larger than
285 * half of the width, the X interval will contain only the X coordinate
286 * of the midpoint; same for height. */
expandBy(C amount)287 void expandBy(C amount) {
288 expandBy(amount, amount);
289 }
290 /** @brief Expand the rectangle in both directions.
291 * Note that this is different from scaling. Negative values will shrink the
292 * rectangle. If <code>-x</code> is larger than
293 * half of the width, the X interval will contain only the X coordinate
294 * of the midpoint; same for height. */
expandBy(C x,C y)295 void expandBy(C x, C y) {
296 f[X].expandBy(x); f[Y].expandBy(y);
297 }
298 /** @brief Expand the rectangle by the coordinates of the given point.
299 * This will expand the width by the X coordinate of the point in both directions
300 * and the height by Y coordinate of the point. Negative coordinate values will
301 * shrink the rectangle. If <code>-p[X]</code> is larger than half of the width,
302 * the X interval will contain only the X coordinate of the midpoint;
303 * same for height. */
expandBy(CPoint const & p)304 void expandBy(CPoint const &p) {
305 expandBy(p[X], p[Y]);
306 }
307 /// @}
308
309 /// @name Operators
310 /// @{
311 /** @brief Offset the rectangle by a vector. */
312 GenericRect<C> &operator+=(CPoint const &p) {
313 f[X] += p[X];
314 f[Y] += p[Y];
315 return *this;
316 }
317 /** @brief Offset the rectangle by the negation of a vector. */
318 GenericRect<C> &operator-=(CPoint const &p) {
319 f[X] -= p[X];
320 f[Y] -= p[Y];
321 return *this;
322 }
323 /** @brief Union two rectangles. */
324 GenericRect<C> &operator|=(CRect const &o) {
325 unionWith(o);
326 return *this;
327 }
328 GenericRect<C> &operator|=(OptCRect const &o) {
329 unionWith(o);
330 return *this;
331 }
332 /** @brief Test for equality of rectangles. */
333 bool operator==(CRect const &o) const { return f[X] == o[X] && f[Y] == o[Y]; }
334 /// @}
335 };
336
337 /**
338 * @brief Axis-aligned generic rectangle that can be empty.
339 * @ingroup Primitives
340 */
341 template <typename C>
342 class GenericOptRect
343 : public std::optional<typename CoordTraits<C>::RectType>
344 , boost::equality_comparable< typename CoordTraits<C>::OptRectType
345 , boost::equality_comparable< typename CoordTraits<C>::OptRectType, typename CoordTraits<C>::RectType
346 , boost::orable< typename CoordTraits<C>::OptRectType
347 , boost::andable< typename CoordTraits<C>::OptRectType
348 , boost::andable< typename CoordTraits<C>::OptRectType, typename CoordTraits<C>::RectType
349 > > > > >
350 {
351 typedef typename CoordTraits<C>::IntervalType CInterval;
352 typedef typename CoordTraits<C>::OptIntervalType OptCInterval;
353 typedef typename CoordTraits<C>::PointType CPoint;
354 typedef typename CoordTraits<C>::RectType CRect;
355 typedef typename CoordTraits<C>::OptRectType OptCRect;
356 typedef std::optional<CRect> Base;
357 public:
358 typedef CInterval D1Value;
359 typedef CInterval &D1Reference;
360 typedef CInterval const &D1ConstReference;
361
362 /// @name Create potentially empty rectangles.
363 /// @{
GenericOptRect()364 GenericOptRect() : Base() {}
GenericOptRect(GenericRect<C> const & a)365 GenericOptRect(GenericRect<C> const &a) : Base(CRect(a)) {}
GenericOptRect(CPoint const & a,CPoint const & b)366 GenericOptRect(CPoint const &a, CPoint const &b) : Base(CRect(a, b)) {}
GenericOptRect(C x0,C y0,C x1,C y1)367 GenericOptRect(C x0, C y0, C x1, C y1) : Base(CRect(x0, y0, x1, y1)) {}
368 /// Creates an empty OptRect when one of the argument intervals is empty.
GenericOptRect(OptCInterval const & x_int,OptCInterval const & y_int)369 GenericOptRect(OptCInterval const &x_int, OptCInterval const &y_int) {
370 if (x_int && y_int) {
371 *this = CRect(*x_int, *y_int);
372 }
373 // else, stay empty.
374 }
375
376 /** @brief Create a rectangle from a range of points.
377 * The resulting rectangle will contain all points from the range.
378 * If the range contains no points, the result will be an empty rectangle.
379 * The return type of iterators must be convertible to the corresponding
380 * point type (Point or IntPoint).
381 * @param start Beginning of the range
382 * @param end End of the range
383 * @return Rectangle that contains all points from [start, end). */
384 template <typename InputIterator>
from_range(InputIterator start,InputIterator end)385 static OptCRect from_range(InputIterator start, InputIterator end) {
386 OptCRect result;
387 for (; start != end; ++start) {
388 result.expandTo(*start);
389 }
390 return result;
391 }
392 /// @}
393
394 /// @name Check other rectangles and points for inclusion.
395 /// @{
396 /** @brief Check for emptiness. */
empty()397 inline bool empty() const { return !*this; };
398 /** @brief Check whether the rectangles have any common points.
399 * Empty rectangles will not intersect with any other rectangle. */
intersects(CRect const & r)400 bool intersects(CRect const &r) const { return r.intersects(*this); }
401 /** @brief Check whether the rectangle includes all points in the given rectangle.
402 * Empty rectangles will be contained in any non-empty rectangle. */
contains(CRect const & r)403 bool contains(CRect const &r) const { return *this && (*this)->contains(r); }
404
405 /** @brief Check whether the rectangles have any common points.
406 * Empty rectangles will not intersect with any other rectangle.
407 * Two empty rectangles will not intersect each other. */
intersects(OptCRect const & r)408 bool intersects(OptCRect const &r) const { return *this && (*this)->intersects(r); }
409 /** @brief Check whether the rectangle includes all points in the given rectangle.
410 * Empty rectangles will be contained in any non-empty rectangle.
411 * An empty rectangle will not contain other empty rectangles. */
contains(OptCRect const & r)412 bool contains(OptCRect const &r) const { return *this && (*this)->contains(r); }
413
414 /** @brief Check whether the given point is within the rectangle.
415 * An empty rectangle will not contain any points. */
contains(CPoint const & p)416 bool contains(CPoint const &p) const { return *this && (*this)->contains(p); }
417 /// @}
418
419 /// @name Modify the potentially empty rectangle.
420 /// @{
421 /** @brief Enlarge the rectangle to contain the argument.
422 * If this rectangle is empty, after callng this method it will
423 * be equal to the argument. */
unionWith(CRect const & b)424 void unionWith(CRect const &b) {
425 if (*this) {
426 (*this)->unionWith(b);
427 } else {
428 *this = b;
429 }
430 }
431 /** @brief Enlarge the rectangle to contain the argument.
432 * Unioning with an empty rectangle results in no changes.
433 * If this rectangle is empty, after calling this method it will
434 * be equal to the argument. */
unionWith(OptCRect const & b)435 void unionWith(OptCRect const &b) {
436 if (b) unionWith(*b);
437 }
438 /** @brief Leave only the area overlapping with the argument.
439 * If the rectangles do not have any points in common, after calling
440 * this method the rectangle will be empty. */
intersectWith(CRect const & b)441 void intersectWith(CRect const &b) {
442 if (!*this) return;
443 OptCInterval x = (**this)[X] & b[X], y = (**this)[Y] & b[Y];
444 if (x && y) {
445 *this = CRect(*x, *y);
446 } else {
447 *(static_cast<Base*>(this)) = std::nullopt;
448 }
449 }
450 /** @brief Leave only the area overlapping with the argument.
451 * If the argument is empty or the rectangles do not have any points
452 * in common, after calling this method the rectangle will be empty. */
intersectWith(OptCRect const & b)453 void intersectWith(OptCRect const &b) {
454 if (b) {
455 intersectWith(*b);
456 } else {
457 *(static_cast<Base*>(this)) = std::nullopt;
458 }
459 }
460 /** @brief Create or enlarge the rectangle to contain the given point.
461 * If the rectangle is empty, after calling this method it will be non-empty
462 * and it will contain only the given point. */
expandTo(CPoint const & p)463 void expandTo(CPoint const &p) {
464 if (*this) {
465 (*this)->expandTo(p);
466 } else {
467 *this = CRect(p, p);
468 }
469 }
470 /// @}
471
472 /// @name Operators
473 /// @{
474 /** @brief Union with @a b */
475 GenericOptRect<C> &operator|=(OptCRect const &b) {
476 unionWith(b);
477 return *this;
478 }
479 /** @brief Intersect with @a b */
480 GenericOptRect<C> &operator&=(CRect const &b) {
481 intersectWith(b);
482 return *this;
483 }
484 /** @brief Intersect with @a b */
485 GenericOptRect<C> &operator&=(OptCRect const &b) {
486 intersectWith(b);
487 return *this;
488 }
489 /** @brief Test for equality.
490 * All empty rectangles are equal. */
491 bool operator==(OptCRect const &other) const {
492 if (!*this != !other) return false;
493 return *this ? (**this == *other) : true;
494 }
495 bool operator==(CRect const &other) const {
496 if (!*this) return false;
497 return **this == other;
498 }
499 /// @}
500 };
501
502 template <typename C>
unionWith(OptCRect const & b)503 inline void GenericRect<C>::unionWith(OptCRect const &b) {
504 if (b) {
505 unionWith(*b);
506 }
507 }
508 template <typename C>
intersects(OptCRect const & r)509 inline bool GenericRect<C>::intersects(OptCRect const &r) const {
510 return r && intersects(*r);
511 }
512 template <typename C>
contains(OptCRect const & r)513 inline bool GenericRect<C>::contains(OptCRect const &r) const {
514 return !r || contains(*r);
515 }
516
517 template <typename C>
518 inline std::ostream &operator<<(std::ostream &out, GenericRect<C> const &r) {
519 out << "Rect " << r[X] << " x " << r[Y];
520 return out;
521 }
522
523 } // end namespace Geom
524
525 #endif // LIB2GEOM_SEEN_RECT_H
526
527 /*
528 Local Variables:
529 mode:c++
530 c-file-style:"stroustrup"
531 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
532 indent-tabs-mode:nil
533 fill-column:99
534 End:
535 */
536 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
537