1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9
10#ifndef EIGEN_ALIGNEDBOX_H
11#define EIGEN_ALIGNEDBOX_H
12
13namespace Eigen {
14
15/** \geometry_module \ingroup Geometry_Module
16  *
17  *
18  * \class AlignedBox
19  *
20  * \brief An axis aligned box
21  *
22  * \param _Scalar the type of the scalar coefficients
23  * \param _AmbientDim the dimension of the ambient space, can be a compile time value or Dynamic.
24  *
25  * This class represents an axis aligned box as a pair of the minimal and maximal corners.
26  */
27template <typename _Scalar, int _AmbientDim>
28class AlignedBox
29{
30public:
31EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(_Scalar,_AmbientDim)
32  enum { AmbientDimAtCompileTime = _AmbientDim };
33  typedef _Scalar                                   Scalar;
34  typedef NumTraits<Scalar>                         ScalarTraits;
35  typedef DenseIndex                                Index;
36  typedef typename ScalarTraits::Real               RealScalar;
37  typedef typename ScalarTraits::NonInteger      NonInteger;
38  typedef Matrix<Scalar,AmbientDimAtCompileTime,1>  VectorType;
39
40  /** Define constants to name the corners of a 1D, 2D or 3D axis aligned bounding box */
41  enum CornerType
42  {
43    /** 1D names */
44    Min=0, Max=1,
45
46    /** Added names for 2D */
47    BottomLeft=0, BottomRight=1,
48    TopLeft=2, TopRight=3,
49
50    /** Added names for 3D */
51    BottomLeftFloor=0, BottomRightFloor=1,
52    TopLeftFloor=2, TopRightFloor=3,
53    BottomLeftCeil=4, BottomRightCeil=5,
54    TopLeftCeil=6, TopRightCeil=7
55  };
56
57
58  /** Default constructor initializing a null box. */
59  inline explicit AlignedBox()
60  { if (AmbientDimAtCompileTime!=Dynamic) setEmpty(); }
61
62  /** Constructs a null box with \a _dim the dimension of the ambient space. */
63  inline explicit AlignedBox(Index _dim) : m_min(_dim), m_max(_dim)
64  { setEmpty(); }
65
66  /** Constructs a box with extremities \a _min and \a _max. */
67  template<typename OtherVectorType1, typename OtherVectorType2>
68  inline AlignedBox(const OtherVectorType1& _min, const OtherVectorType2& _max) : m_min(_min), m_max(_max) {}
69
70  /** Constructs a box containing a single point \a p. */
71  template<typename Derived>
72  inline explicit AlignedBox(const MatrixBase<Derived>& a_p)
73  {
74    const typename internal::nested<Derived,2>::type p(a_p.derived());
75    m_min = p;
76    m_max = p;
77  }
78
79  ~AlignedBox() {}
80
81  /** \returns the dimension in which the box holds */
82  inline Index dim() const { return AmbientDimAtCompileTime==Dynamic ? m_min.size()-1 : Index(AmbientDimAtCompileTime); }
83
84  /** \deprecated use isEmpty */
85  inline bool isNull() const { return isEmpty(); }
86
87  /** \deprecated use setEmpty */
88  inline void setNull() { setEmpty(); }
89
90  /** \returns true if the box is empty. */
91  inline bool isEmpty() const { return (m_min.array() > m_max.array()).any(); }
92
93  /** Makes \c *this an empty box. */
94  inline void setEmpty()
95  {
96    m_min.setConstant( ScalarTraits::highest() );
97    m_max.setConstant( ScalarTraits::lowest() );
98  }
99
100  /** \returns the minimal corner */
101  inline const VectorType& (min)() const { return m_min; }
102  /** \returns a non const reference to the minimal corner */
103  inline VectorType& (min)() { return m_min; }
104  /** \returns the maximal corner */
105  inline const VectorType& (max)() const { return m_max; }
106  /** \returns a non const reference to the maximal corner */
107  inline VectorType& (max)() { return m_max; }
108
109  /** \returns the center of the box */
110  inline const CwiseUnaryOp<internal::scalar_quotient1_op<Scalar>,
111                            const CwiseBinaryOp<internal::scalar_sum_op<Scalar>, const VectorType, const VectorType> >
112  center() const
113  { return (m_min+m_max)/2; }
114
115  /** \returns the lengths of the sides of the bounding box.
116    * Note that this function does not get the same
117    * result for integral or floating scalar types: see
118    */
119  inline const CwiseBinaryOp< internal::scalar_difference_op<Scalar>, const VectorType, const VectorType> sizes() const
120  { return m_max - m_min; }
121
122  /** \returns the volume of the bounding box */
123  inline Scalar volume() const
124  { return sizes().prod(); }
125
126  /** \returns an expression for the bounding box diagonal vector
127    * if the length of the diagonal is needed: diagonal().norm()
128    * will provide it.
129    */
130  inline CwiseBinaryOp< internal::scalar_difference_op<Scalar>, const VectorType, const VectorType> diagonal() const
131  { return sizes(); }
132
133  /** \returns the vertex of the bounding box at the corner defined by
134    * the corner-id corner. It works only for a 1D, 2D or 3D bounding box.
135    * For 1D bounding boxes corners are named by 2 enum constants:
136    * BottomLeft and BottomRight.
137    * For 2D bounding boxes, corners are named by 4 enum constants:
138    * BottomLeft, BottomRight, TopLeft, TopRight.
139    * For 3D bounding boxes, the following names are added:
140    * BottomLeftCeil, BottomRightCeil, TopLeftCeil, TopRightCeil.
141    */
142  inline VectorType corner(CornerType corner) const
143  {
144    EIGEN_STATIC_ASSERT(_AmbientDim <= 3, THIS_METHOD_IS_ONLY_FOR_VECTORS_OF_A_SPECIFIC_SIZE);
145
146    VectorType res;
147
148    Index mult = 1;
149    for(Index d=0; d<dim(); ++d)
150    {
151      if( mult & corner ) res[d] = m_max[d];
152      else                res[d] = m_min[d];
153      mult *= 2;
154    }
155    return res;
156  }
157
158  /** \returns a random point inside the bounding box sampled with
159   * a uniform distribution */
160  inline VectorType sample() const
161  {
162    VectorType r;
163    for(Index d=0; d<dim(); ++d)
164    {
165      if(!ScalarTraits::IsInteger)
166      {
167        r[d] = m_min[d] + (m_max[d]-m_min[d])
168             * internal::random<Scalar>(Scalar(0), Scalar(1));
169      }
170      else
171        r[d] = internal::random(m_min[d], m_max[d]);
172    }
173    return r;
174  }
175
176  /** \returns true if the point \a p is inside the box \c *this. */
177  template<typename Derived>
178  inline bool contains(const MatrixBase<Derived>& a_p) const
179  {
180    typename internal::nested<Derived,2>::type p(a_p.derived());
181    return (m_min.array()<=p.array()).all() && (p.array()<=m_max.array()).all();
182  }
183
184  /** \returns true if the box \a b is entirely inside the box \c *this. */
185  inline bool contains(const AlignedBox& b) const
186  { return (m_min.array()<=(b.min)().array()).all() && ((b.max)().array()<=m_max.array()).all(); }
187
188  /** Extends \c *this such that it contains the point \a p and returns a reference to \c *this. */
189  template<typename Derived>
190  inline AlignedBox& extend(const MatrixBase<Derived>& a_p)
191  {
192    typename internal::nested<Derived,2>::type p(a_p.derived());
193    m_min = m_min.cwiseMin(p);
194    m_max = m_max.cwiseMax(p);
195    return *this;
196  }
197
198  /** Extends \c *this such that it contains the box \a b and returns a reference to \c *this. */
199  inline AlignedBox& extend(const AlignedBox& b)
200  {
201    m_min = m_min.cwiseMin(b.m_min);
202    m_max = m_max.cwiseMax(b.m_max);
203    return *this;
204  }
205
206  /** Clamps \c *this by the box \a b and returns a reference to \c *this. */
207  inline AlignedBox& clamp(const AlignedBox& b)
208  {
209    m_min = m_min.cwiseMax(b.m_min);
210    m_max = m_max.cwiseMin(b.m_max);
211    return *this;
212  }
213
214  /** Returns an AlignedBox that is the intersection of \a b and \c *this */
215  inline AlignedBox intersection(const AlignedBox& b) const
216  {return AlignedBox(m_min.cwiseMax(b.m_min), m_max.cwiseMin(b.m_max)); }
217
218  /** Returns an AlignedBox that is the union of \a b and \c *this */
219  inline AlignedBox merged(const AlignedBox& b) const
220  { return AlignedBox(m_min.cwiseMin(b.m_min), m_max.cwiseMax(b.m_max)); }
221
222  /** Translate \c *this by the vector \a t and returns a reference to \c *this. */
223  template<typename Derived>
224  inline AlignedBox& translate(const MatrixBase<Derived>& a_t)
225  {
226    const typename internal::nested<Derived,2>::type t(a_t.derived());
227    m_min += t;
228    m_max += t;
229    return *this;
230  }
231
232  /** \returns the squared distance between the point \a p and the box \c *this,
233    * and zero if \a p is inside the box.
234    * \sa exteriorDistance()
235    */
236  template<typename Derived>
237  inline Scalar squaredExteriorDistance(const MatrixBase<Derived>& a_p) const;
238
239  /** \returns the squared distance between the boxes \a b and \c *this,
240    * and zero if the boxes intersect.
241    * \sa exteriorDistance()
242    */
243  inline Scalar squaredExteriorDistance(const AlignedBox& b) const;
244
245  /** \returns the distance between the point \a p and the box \c *this,
246    * and zero if \a p is inside the box.
247    * \sa squaredExteriorDistance()
248    */
249  template<typename Derived>
250  inline NonInteger exteriorDistance(const MatrixBase<Derived>& p) const
251  { return internal::sqrt(NonInteger(squaredExteriorDistance(p))); }
252
253  /** \returns the distance between the boxes \a b and \c *this,
254    * and zero if the boxes intersect.
255    * \sa squaredExteriorDistance()
256    */
257  inline NonInteger exteriorDistance(const AlignedBox& b) const
258  { return internal::sqrt(NonInteger(squaredExteriorDistance(b))); }
259
260  /** \returns \c *this with scalar type casted to \a NewScalarType
261    *
262    * Note that if \a NewScalarType is equal to the current scalar type of \c *this
263    * then this function smartly returns a const reference to \c *this.
264    */
265  template<typename NewScalarType>
266  inline typename internal::cast_return_type<AlignedBox,
267           AlignedBox<NewScalarType,AmbientDimAtCompileTime> >::type cast() const
268  {
269    return typename internal::cast_return_type<AlignedBox,
270                    AlignedBox<NewScalarType,AmbientDimAtCompileTime> >::type(*this);
271  }
272
273  /** Copy constructor with scalar type conversion */
274  template<typename OtherScalarType>
275  inline explicit AlignedBox(const AlignedBox<OtherScalarType,AmbientDimAtCompileTime>& other)
276  {
277    m_min = (other.min)().template cast<Scalar>();
278    m_max = (other.max)().template cast<Scalar>();
279  }
280
281  /** \returns \c true if \c *this is approximately equal to \a other, within the precision
282    * determined by \a prec.
283    *
284    * \sa MatrixBase::isApprox() */
285  bool isApprox(const AlignedBox& other, RealScalar prec = ScalarTraits::dummy_precision()) const
286  { return m_min.isApprox(other.m_min, prec) && m_max.isApprox(other.m_max, prec); }
287
288protected:
289
290  VectorType m_min, m_max;
291};
292
293
294
295template<typename Scalar,int AmbientDim>
296template<typename Derived>
297inline Scalar AlignedBox<Scalar,AmbientDim>::squaredExteriorDistance(const MatrixBase<Derived>& a_p) const
298{
299  const typename internal::nested<Derived,2*AmbientDim>::type p(a_p.derived());
300  Scalar dist2(0);
301  Scalar aux;
302  for (Index k=0; k<dim(); ++k)
303  {
304    if( m_min[k] > p[k] )
305    {
306      aux = m_min[k] - p[k];
307      dist2 += aux*aux;
308    }
309    else if( p[k] > m_max[k] )
310    {
311      aux = p[k] - m_max[k];
312      dist2 += aux*aux;
313    }
314  }
315  return dist2;
316}
317
318template<typename Scalar,int AmbientDim>
319inline Scalar AlignedBox<Scalar,AmbientDim>::squaredExteriorDistance(const AlignedBox& b) const
320{
321  Scalar dist2(0);
322  Scalar aux;
323  for (Index k=0; k<dim(); ++k)
324  {
325    if( m_min[k] > b.m_max[k] )
326    {
327      aux = m_min[k] - b.m_max[k];
328      dist2 += aux*aux;
329    }
330    else if( b.m_min[k] > m_max[k] )
331    {
332      aux = b.m_min[k] - m_max[k];
333      dist2 += aux*aux;
334    }
335  }
336  return dist2;
337}
338
339/** \defgroup alignedboxtypedefs Global aligned box typedefs
340  *
341  * \ingroup Geometry_Module
342  *
343  * Eigen defines several typedef shortcuts for most common aligned box types.
344  *
345  * The general patterns are the following:
346  *
347  * \c AlignedBoxSizeType where \c Size can be \c 1, \c 2,\c 3,\c 4 for fixed size boxes or \c X for dynamic size,
348  * and where \c Type can be \c i for integer, \c f for float, \c d for double.
349  *
350  * For example, \c AlignedBox3d is a fixed-size 3x3 aligned box type of doubles, and \c AlignedBoxXf is a dynamic-size aligned box of floats.
351  *
352  * \sa class AlignedBox
353  */
354
355#define EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, Size, SizeSuffix)    \
356/** \ingroup alignedboxtypedefs */                                 \
357typedef AlignedBox<Type, Size>   AlignedBox##SizeSuffix##TypeSuffix;
358
359#define EIGEN_MAKE_TYPEDEFS_ALL_SIZES(Type, TypeSuffix) \
360EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, 1, 1) \
361EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, 2, 2) \
362EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, 3, 3) \
363EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, 4, 4) \
364EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, Dynamic, X)
365
366EIGEN_MAKE_TYPEDEFS_ALL_SIZES(int,                  i)
367EIGEN_MAKE_TYPEDEFS_ALL_SIZES(float,                f)
368EIGEN_MAKE_TYPEDEFS_ALL_SIZES(double,               d)
369
370#undef EIGEN_MAKE_TYPEDEFS_ALL_SIZES
371#undef EIGEN_MAKE_TYPEDEFS
372
373} // end namespace Eigen
374
375#endif // EIGEN_ALIGNEDBOX_H
376