AlignedBox.h

/*
 * Copyright (C) 2019-2021 HERE Europe B.V.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 * License-Filename: LICENSE
 */
 
#pragma once
 
#include <array>
#include <limits>
 
#include <olp/core/math/Vector.h>
 
namespace olp {
namespace math {
template <typename T,
          int IntegerBits = std::is_integral<T>::value ? sizeof(T) * 8 : 0,
          bool IsSigned = std::numeric_limits<T>::is_signed>
struct OverflowTrait {
  using Type = T;
};
 
template <typename T>
struct OverflowTrait<T, 8, true> {
  using Type = int16_t;
};
 
template <typename T>
struct OverflowTrait<T, 8, false> {
  using Type = uint16_t;
};
 
template <typename T>
struct OverflowTrait<T, 16, true> {
  using Type = int32_t;
};
 
template <typename T>
struct OverflowTrait<T, 16, false> {
  using Type = uint32_t;
};
 
template <typename T>
struct OverflowTrait<T, 32, true> {
  using Type = int64_t;
};
 
template <typename T>
struct OverflowTrait<T, 32, false> {
  using Type = uint64_t;
};
 
template <typename T, unsigned int N>
class AlignedBox {
 public:
  static const unsigned int numCorners = 1 << N;
  static const unsigned int dimensions = N;
 
  using ValueType = T;
  using OverflowType = typename OverflowTrait<T>::Type;
  using VectorType = Vector<ValueType, N>;
  using OverflowVectorType = Vector<OverflowType, N>;
 
  using CornerArrayType =
      typename std::array<VectorType,
                          numCorners>;
 
  AlignedBox();
 
  AlignedBox(const VectorType& min, const VectorType& max);
 
  template <typename OtherT>
  AlignedBox(const AlignedBox<OtherT, N>& other);
 
  void Reset();
 
  void Reset(const VectorType& min, const VectorType& max);
 
  bool Empty() const;
 
  VectorType Center() const;
 
  VectorType Size() const;
 
  const VectorType& Minimum() const;
 
  const VectorType& Maximum() const;
 
  CornerArrayType Corners() const;
  bool Contains(const VectorType& point, T epsilon = T()) const;
 
  bool Contains(const AlignedBox& box) const;
 
  bool Intersects(const AlignedBox& box) const;
 
  VectorType NearestPoint(const VectorType& point) const;
 
  ValueType Distance(const VectorType& point) const;
 
  ValueType Distance2(const VectorType& point) const;
 
  bool operator==(const AlignedBox& box) const;
 
  bool operator!=(const AlignedBox& box) const;
 
 private:
  template <typename U, unsigned int X>
  friend class AlignedBox;
 
  VectorType minimum_;
  VectorType maximum_;
};
 
#ifndef NDEBUG
template <typename T>
bool CheckAddOperationOverflow(T a, T b) {
  return ((a > 0) && (b > 0) && (a > (std::numeric_limits<T>::max() - b))) ||
         ((a < 0) && (b < 0) && (a < (std::numeric_limits<T>::min() - b)));
}
#endif
 
using AlignedBox3d =
    AlignedBox<double, 3>;
 
template <typename T, unsigned int N>
AlignedBox<T, N>::AlignedBox()
    : minimum_(std::numeric_limits<T>::max()),
      maximum_(std::numeric_limits<T>::lowest()) {}
 
template <typename T, unsigned int N>
template <typename OtherT>
AlignedBox<T, N>::AlignedBox(const AlignedBox<OtherT, N>& other)
    : minimum_(other.min()), maximum_(other.max()) {}
 
template <typename T, unsigned int N>
AlignedBox<T, N>::AlignedBox(const VectorType& min, const VectorType& max)
    : minimum_(min), maximum_(max) {}
 
template <typename T, unsigned int N>
void AlignedBox<T, N>::Reset() {
  minimum_ = VectorType(std::numeric_limits<T>::max());
  maximum_ = VectorType(std::numeric_limits<T>::lowest());
}
 
template <typename T, unsigned int N>
void AlignedBox<T, N>::Reset(const VectorType& min, const VectorType& max) {
  minimum_ = min;
  maximum_ = max;
}
 
template <typename T, unsigned int N>
typename AlignedBox<T, N>::VectorType AlignedBox<T, N>::Center() const {
#ifndef NDEBUG
  // Checks for possible 64-bit integer overflows or underflows.
  if (std::numeric_limits<OverflowType>::is_integer &&
      sizeof(OverflowType) * 8 == 64) {
    for (unsigned dim = 0; dim < dimensions; ++dim) {
      if (CheckAddOperationOverflow<OverflowType>(maximum_[dim],
                                                  minimum_[dim])) {
        // DEBUG_ASSERT( false );
        return VectorType(0);
      }
    }
  }
#endif
 
  return VectorType(
      (OverflowVectorType(maximum_) + OverflowVectorType(minimum_)) /
      OverflowVectorType(2));
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::Empty() const {
  Vector3<bool> result = maximum_.LessThan(minimum_);
  return result.x || result.y || result.z;
}
 
template <typename T, unsigned int N>
typename AlignedBox<T, N>::VectorType AlignedBox<T, N>::Size() const {
  return Empty() ? VectorType(0) : maximum_ - minimum_;
}
 
template <typename T, unsigned int N>
const typename AlignedBox<T, N>::VectorType& AlignedBox<T, N>::Minimum() const {
  return minimum_;
}
 
template <typename T, unsigned int N>
const typename AlignedBox<T, N>::VectorType& AlignedBox<T, N>::Maximum() const {
  return maximum_;
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::Contains(const VectorType& point, T epsilon) const {
  if (Empty()) {
    return false;
  }
 
  for (unsigned dim = 0; dim < dimensions; dim++) {
    if (minimum_[dim] - epsilon > point[dim] ||
        maximum_[dim] + epsilon < point[dim])
      return false;
  }
 
  return true;
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::Contains(const AlignedBox& box) const {
  if (Empty()) {
    return false;
  }
 
  for (unsigned dim = 0; dim < dimensions; ++dim) {
    if (box.minimum_[dim] < minimum_[dim] ||
        box.maximum_[dim] > maximum_[dim]) {
      return false;
    }
  }
 
  return true;
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::Intersects(const AlignedBox& box) const {
  if (Empty()) {
    return false;
  }
 
  const VectorType& otherMin = box.Minimum();
  const VectorType& otherMax = box.Maximum();
  for (unsigned dim = 0; dim < dimensions; dim++) {
    if ((maximum_[dim] < otherMin[dim]) || (minimum_[dim] > otherMax[dim]))
      return false;
  }
 
  return true;
}
 
template <typename T, unsigned int N>
auto AlignedBox<T, N>::Distance(const VectorType& point) const -> ValueType {
  return static_cast<ValueType>(sqrt(distance2(point)));
}
 
template <typename T, unsigned int N>
auto AlignedBox<T, N>::Distance2(const VectorType& point) const -> ValueType {
  T distance2 = 0;
  for (unsigned dim = 0; dim < dimensions; dim++) {
    if (point[dim] < minimum_[dim]) {
      T dimDistance = minimum_[dim] - point[dim];
      distance2 += dimDistance * dimDistance;
    } else if (point[dim] > maximum_[dim]) {
      T dimDistance = point[dim] - maximum_[dim];
      distance2 += dimDistance * dimDistance;
    }
  }
 
  return distance2;
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::operator==(const AlignedBox& box) const {
  //
  // If either box is empty, checks which ones are
  // empty.
  //
  bool thisEmpty = Empty();
  bool otherEmpty = box.Empty();
  if (thisEmpty || otherEmpty) {
    return thisEmpty == otherEmpty;
  }
 
  return minimum_ == box.Minimum() && maximum_ == box.Maximum();
}
 
template <typename T, unsigned int N>
bool AlignedBox<T, N>::operator!=(const AlignedBox& box) const {
  return !(*this == box);
}
 
}  // namespace math
}  // namespace olp