bresenham.hpp

Go to the documentation of this file.

/* BSD 3-Clause License
 *
 * Copyright © 2008-2025, Jice and the libtcod contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the copyright holder nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
#pragma once
#ifndef TCOD_BRESENHAM_HPP_
#define TCOD_BRESENHAM_HPP_
 
#include <array>
#include <functional>
#include <iterator>
#include <vector>
 
#include "bresenham.h"

 
class TCODLIB_API TCODLineListener {
 public:
  virtual bool putPoint(int x, int y) = 0;
  virtual ~TCODLineListener() {}
};
// clang-format off
class TCODLIB_API TCODLine {
public :
  static void init(int xFrom, int yFrom, int xTo, int yTo);

  static bool step(int *xCur, int *yCur);

  static bool line(int xFrom, int yFrom, int xTo, int yTo, TCODLineListener *listener);
};
// clang-format on
namespace tcod {

class BresenhamLine {
 public:
  using Point2 = std::array<int, 2>;
  using iterator_category = std::random_access_iterator_tag;
  using value_type = Point2;
  using difference_type = int;
  using pointer = void;
  using reference = value_type;
  explicit BresenhamLine(Point2 begin, Point2 end) noexcept
      : origin_{begin},
        dest_{end},
        index_{0},
        index_end_{get_delta_x() + 1},
        cursor_{0, 0},
        y_error_{-get_delta_x() / 2} {}

  explicit BresenhamLine(Point2 begin, Point2 end, int error) noexcept
      : origin_{begin},
        dest_{end},
        index_{0},
        index_end_{get_delta_x() + 1},
        cursor_{0, 0},
        y_error_{error > 0 ? error % get_delta_x() - get_delta_x() : error % get_delta_x()} {}
 
  inline BresenhamLine& operator++() noexcept {
    ++index_;
    return *this;
  }
  inline BresenhamLine operator++(int) noexcept {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  inline BresenhamLine& operator--() noexcept {
    --index_;
    return *this;
  }
  inline BresenhamLine operator--(int) noexcept {
    auto tmp = *this;
    --(*this);
    return tmp;
  }
  inline value_type operator[](int index) noexcept { return bresenham_get(index_ + index); }
  inline value_type operator*() noexcept { return (*this)[0]; }
  inline constexpr bool operator==(const BresenhamLine& rhs) const noexcept { return index_ == rhs.index_; }
  inline constexpr bool operator!=(const BresenhamLine& rhs) const noexcept { return !(*this == rhs); }
  inline constexpr difference_type operator-(const BresenhamLine& rhs) const noexcept { return index_ - rhs.index_; }

  inline BresenhamLine adjust_range(int shift_begin, int shift_end) const noexcept {
    BresenhamLine new_data{*this};
    new_data.index_ += shift_begin;
    new_data.index_end_ += shift_end;
    new_data.index_end_ = std::max(new_data.index_, new_data.index_end_);
    return new_data;
  }

  inline BresenhamLine without_start() const noexcept { return adjust_range(1, 0); }
  inline BresenhamLine without_end() const noexcept { return adjust_range(0, -1); }
  inline BresenhamLine without_endpoints() const noexcept { return adjust_range(1, -1); }
  inline BresenhamLine begin() const noexcept { return {*this}; }
  inline BresenhamLine end() const noexcept {
    return BresenhamLine{origin_, dest_, index_end_, index_end_, cursor_, y_error_};
  }
 
 private:
  struct Matrix {
    inline Point2 transform(const Point2& cursor) const noexcept {
      return {ax + cursor.at(0) * xx + cursor.at(1) * yx, ay + cursor.at(0) * xy + cursor.at(1) * yy};
    }
    int ax;  // Affine transformation on X.
    int ay;  // Affine transformation on Y.
    int_fast8_t xx;  // Index to world X.
    int_fast8_t xy;  // Index to world Y.
    int_fast8_t yx;  // Cursor Y to world X.
    int_fast8_t yy;  // Cursor Y to world Y.
  };
  inline Matrix get_matrix() const noexcept { return get_matrix(origin_, dest_); }
  static Matrix get_matrix(const Point2& origin, const Point2& dest) noexcept {
    const int delta_x = dest.at(0) - origin.at(0);
    const int delta_y = dest.at(1) - origin.at(1);
    Matrix matrix{
        origin.at(0),
        origin.at(1),
        1,
        0,
        0,
        1,
    };
    if (delta_x < 0) matrix.xx = -1;
    if (delta_y < 0) matrix.yy = -1;
    if (std::abs(delta_y) > std::abs(delta_x)) {
      std::swap(matrix.xx, matrix.yx);
      std::swap(matrix.xy, matrix.yy);
    }
    return matrix;
  }
  explicit BresenhamLine(Point2 begin, Point2 end, int index_begin, int index_end, Point2 cursor, int error) noexcept
      : origin_{begin}, dest_{end}, index_{index_begin}, index_end_{index_end}, cursor_{cursor}, y_error_{error} {}
  inline Point2 get_normalized_delta() const noexcept { return get_normalized_delta(origin_, dest_); }
  static Point2 get_normalized_delta(const Point2& origin, const Point2& dest) noexcept {
    return std::abs(dest.at(0) - origin.at(0)) > std::abs(dest.at(1) - origin.at(1))
               ? Point2{std::abs(dest.at(0) - origin.at(0)), std::abs(dest.at(1) - origin.at(1))}
               : Point2{std::abs(dest.at(1) - origin.at(1)), std::abs(dest.at(0) - origin.at(0))};
  }
  inline int get_delta_x() const noexcept { return get_normalized_delta().at(0); }
  inline BresenhamLine& bresenham_next() {
    const Point2 delta = get_normalized_delta();
    y_error_ += delta.at(1);
    if (y_error_ > 0) {
      ++cursor_.at(1);
      y_error_ -= delta.at(0);
    };
    ++cursor_.at(0);
    return *this;
  }
  inline BresenhamLine& bresenham_prev() {
    const Point2 delta = get_normalized_delta();
    y_error_ -= delta.at(1);
    if (y_error_ <= -delta.at(0)) {
      --cursor_.at(1);
      y_error_ += delta.at(0);
    };
    --cursor_.at(0);
    return *this;
  }
  inline Point2 bresenham_get(int index) {
    while (cursor_.at(0) < index) bresenham_next();
    while (cursor_.at(0) > index) bresenham_prev();
    return get_matrix().transform(cursor_);
  }
  Point2 origin_;  // Starting point.
  Point2 dest_;  // Ending point.
  int index_;  // The starting index returned by `begin`.
  int index_end_;  // The past-the-end index returned by `end`.
  Point2 cursor_;  // Normalized Bresenham low-slope position.  First axis acts as the current index.
  int y_error_;  // Fractional difference between Y indexes.  Is always `-delta[0] < err <= 0`.
};

}  // namespace tcod
#endif  // TCOD_BRESENHAM_HPP_