.. _program_listing_file_libtcod_bresenham.hpp: Program Listing for File bresenham.hpp ====================================== |exhale_lsh| :ref:`Return to documentation for file ` (``libtcod/bresenham.hpp``) .. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS .. code-block:: cpp /* 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 #include #include #include #include "bresenham.h" // clang-format off class TCODLIB_API TCODLineListener { public : virtual bool putPoint(int x,int y) = 0; virtual ~TCODLineListener() {} }; 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; 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_