bresenham.hpp

Go to the documentation of this file.

// Copyright 2023 Ekumen, Inc.
//
// 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.
 
#ifndef BELUGA_ALGORITHM_RAYCASTING_BRESENHAM_HPP
#define BELUGA_ALGORITHM_RAYCASTING_BRESENHAM_HPP
 
#include <cstdint>
#include <utility>
 
#include <range/v3/view/all.hpp>
#include <range/v3/view/take_while.hpp>
 
#include <Eigen/Core>
 
namespace beluga {
 
class Bresenham2i {
 public:
  enum Variant : std::uint8_t {
    kStandard = 0,  
    kModified       
  };
 
 
  template <class Vector2, typename Integer = typename Vector2::Scalar>
  class Line : public ranges::view_interface<Line<Vector2, Integer>> {
   public:
    class iterator {  // NOLINT(readability-identifier-naming)
     public:
      struct sentinel {
        bool operator==(const iterator& other) const { return other == *this; }
 
        bool operator!=(const iterator& other) const { return !(other == *this); }
      };
 
      using iterator_category = std::forward_iterator_tag;
 
      using difference_type = std::ptrdiff_t;
 
      using value_type = Vector2;
 
      using pointer = Vector2*;
 
      using reference = Vector2&;
 
      iterator() = default;
 
      explicit iterator(const Line* line) : current_point_(line->p0_), x_(line->p0_.x()), y_(line->p0_.y()) {
        xspan_ = line->p1_.x() - line->p0_.x();
        xstep_ = static_cast<decltype(xspan_)>(1);
        if (xspan_ < 0) {
          xspan_ = -xspan_;
          xstep_ = -xstep_;
        }
 
        yspan_ = line->p1_.y() - line->p0_.y();
        ystep_ = static_cast<decltype(yspan_)>(1);
        if (yspan_ < 0) {
          yspan_ = -yspan_;
          ystep_ = -ystep_;
        }
 
        if (xspan_ < yspan_) {
          using std::swap;
          swap(x_, y_);
          swap(xspan_, yspan_);
          swap(xstep_, ystep_);
          reversed_ = true;
        }
 
        dxspan_ = 2 * xspan_;
        dyspan_ = 2 * yspan_;
 
        error_ = prev_error_ = xspan_;
        modified_ = line->variant_ == Bresenham2i::kModified;
      }
 
      iterator operator++(int) {
        iterator other = *this;
        this->operator++();
        return other;
      }
 
      iterator& operator++() {
        if (checks_ == 0) {
          if (++step_ > xspan_) {
            return *this;
          }
          x_ += xstep_;
          error_ += dyspan_;
          ++checks_;
          if (error_ > dxspan_) {
            y_ += ystep_;
            error_ -= dxspan_;
            if (modified_) {
              ++checks_;
              ++checks_;
            }
          }
        }
 
        if (checks_ > 1) {
          if (checks_ > 2) {
            --checks_;
            if (error_ + prev_error_ <= dxspan_) {
              step_to(x_, y_ - ystep_);
              return *this;
            }
          }
 
          --checks_;
          if (error_ + prev_error_ >= dxspan_) {
            step_to(x_ - xstep_, y_);
            return *this;
          }
        }
 
        --checks_;
        step_to(x_, y_);
        prev_error_ = error_;
        return *this;
      }
 
      const Vector2& operator*() const { return current_point_; }
 
      const Vector2* operator->() const { return &current_point_; }
 
      bool operator==(const iterator& other) const {
        return x_ == other.x_ && y_ == other.y_ && xstep_ == other.xstep_ && ystep_ == other.ystep_ &&
               xspan_ == other.xspan_ && yspan_ == other.yspan_ && step_ == other.step_ && checks_ == other.checks_ &&
               modified_ == other.modified_ && reversed_ == other.reversed_;
      }
 
      bool operator!=(const iterator& other) const { return !(*this == other); }
 
      bool operator==(const sentinel&) const { return step_ > xspan_; }
 
      bool operator!=(const sentinel& other) const { return !(*this == other); }
 
     private:
      void step_to(Integer x, Integer y) {
        if (reversed_) {
          using std::swap;
          swap(x, y);
        }
        current_point_.x() = x;
        current_point_.y() = y;
      }
 
      Vector2 current_point_{};
      Integer x_{}, y_{};
      Integer xspan_{}, yspan_{};
      Integer dxspan_, dyspan_{};
      Integer xstep_{}, ystep_{}, step_{};
      Integer prev_error_{}, error_{};
 
      std::size_t checks_{0};
      bool modified_{false};
      bool reversed_{false};
    };
 
    Line() = default;
 
 
    explicit Line(Vector2 p0, Vector2 p1, Variant variant)
        : p0_(std::move(p0)), p1_(std::move(p1)), variant_(variant) {}
 
    [[nodiscard]] auto begin() const { return Line::iterator{this}; }
 
    [[nodiscard]] auto end() const { return typename Line::iterator::sentinel{}; }
 
   private:
    friend class iterator;
 
    Vector2 p0_{};
    Vector2 p1_{};
    Variant variant_{};
  };
 
  Bresenham2i() noexcept = default;
 
  Bresenham2i(const Bresenham2i&) noexcept = default;
 
  Bresenham2i(Bresenham2i&&) noexcept = default;
 
  Bresenham2i& operator=(const Bresenham2i&) noexcept = default;
 
  Bresenham2i& operator=(Bresenham2i&&) noexcept = default;
 
  explicit Bresenham2i(Variant variant) noexcept : variant_(variant) {}
 
 
  template <class Vector2i = Eigen::Vector2i>
  auto operator()(Vector2i p0, Vector2i p1) const {
    return Line{std::move(p0), std::move(p1), variant_};
  }
 
 private:
  Variant variant_{};
};
 
}  // namespace beluga
 
#endif