ContourTrace.hpp

#pragma once
 
#include "../utils/Common.hpp"
 
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <span>
#include <stdexcept>
#include <utility>
#include <vector>
 
namespace mmcfilters {
 
class ContourTraceComputation;
namespace contours::detail {
class ContourTraceTraversal;
}
 
enum class ContourSide : uint8_t { North = 0, West = 1, East = 2, South = 3 };
 
enum class ContourBoundaryKind : uint8_t { External, Internal };
 
struct ContourEdge {
    PixelId pixel = InvalidPixel;
    ContourSide side = ContourSide::North;
 
    friend bool operator==(const ContourEdge&, const ContourEdge&) = default;
};
 
struct ContourBoundary {
    ContourBoundaryKind kind = ContourBoundaryKind::External;
    uint32_t edgeOffset = 0;
    uint32_t edgeCount = 0;
    int doubledSignedArea = 0;
};
 
namespace contours::detail {
 
[[nodiscard]] inline int packContourEdge(PixelId pixel, ContourSide side) {
    return (4 * pixel) + static_cast<int>(side);
}
 
[[nodiscard]] inline ContourEdge unpackContourEdge(int packedEdge) {
    if (packedEdge < 0) {
        return {};
    }
    return ContourEdge{packedEdge / 4, static_cast<ContourSide>(packedEdge & 3)};
}
 
} // namespace contours::detail
 
class ContourEdgeRange {
  public:
    class iterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = ContourEdge;
        using difference_type = std::ptrdiff_t;
        using pointer = void;
        using reference = value_type;
 
        iterator() = default;
 
        explicit iterator(const int* packedEdge) : packedEdge_(packedEdge) {}
 
        [[nodiscard]] value_type operator*() const { return contours::detail::unpackContourEdge(*packedEdge_); }
 
        iterator& operator++() {
            ++packedEdge_;
            return *this;
        }
 
        iterator operator++(int) {
            iterator previous(*this);
            ++(*this);
            return previous;
        }
 
        friend bool operator==(const iterator&, const iterator&) = default;
 
      private:
        const int* packedEdge_ = nullptr;
    };
 
    ContourEdgeRange() = default;
 
    explicit ContourEdgeRange(std::span<const int> packedEdges) : packedEdges_(packedEdges) {}
 
    [[nodiscard]] iterator begin() const { return iterator(packedEdges_.data()); }
 
    [[nodiscard]] iterator end() const {
        return packedEdges_.empty() ? begin() : iterator(packedEdges_.data() + packedEdges_.size());
    }
 
    [[nodiscard]] bool empty() const noexcept { return packedEdges_.empty(); }
 
    [[nodiscard]] std::size_t size() const noexcept { return packedEdges_.size(); }
 
  private:
    std::span<const int> packedEdges_; 
};
 
class ContourPixelRange {
  public:
    class iterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = PixelId;
        using difference_type = std::ptrdiff_t;
        using pointer = void;
        using reference = value_type;
 
        iterator() = default;
 
        explicit iterator(ContourEdgeRange::iterator edgeIterator) : edgeIterator_(edgeIterator) {}
 
        [[nodiscard]] value_type operator*() const { return (*edgeIterator_).pixel; }
 
        iterator& operator++() {
            ++edgeIterator_;
            return *this;
        }
 
        iterator operator++(int) {
            iterator previous(*this);
            ++(*this);
            return previous;
        }
 
        friend bool operator==(const iterator&, const iterator&) = default;
 
      private:
        ContourEdgeRange::iterator edgeIterator_; 
    };
 
    ContourPixelRange() = default;
 
    explicit ContourPixelRange(ContourEdgeRange edges) : edges_(edges) {}
 
    [[nodiscard]] iterator begin() const { return iterator(edges_.begin()); }
 
    [[nodiscard]] iterator end() const { return iterator(edges_.end()); }
 
    [[nodiscard]] bool empty() const noexcept { return edges_.empty(); }
 
    [[nodiscard]] std::size_t size() const noexcept { return edges_.size(); }
 
  private:
    ContourEdgeRange edges_; 
};
 
class ContourTrace;
 
class ContourTraceView {
  public:
    ContourTraceView() = default;
 
    [[nodiscard]] std::span<const ContourBoundary> boundaries() const noexcept { return boundaries_; }
 
    [[nodiscard]] ContourBoundary externalBoundary() const {
        const ContourBoundary* external = nullptr;
        for (const ContourBoundary& boundary : boundaries_) {
            if (boundary.kind != ContourBoundaryKind::External) {
                continue;
            }
            if (external != nullptr) {
                throw std::logic_error("ContourTraceView::externalBoundary requires exactly one external boundary.");
            }
            external = &boundary;
        }
        if (external == nullptr) {
            throw std::logic_error("ContourTraceView::externalBoundary requires exactly one external boundary.");
        }
        return *external;
    }
 
    [[nodiscard]] ContourEdgeRange edges() const noexcept { return ContourEdgeRange(packedEdges_); }
 
    [[nodiscard]] ContourEdgeRange boundaryEdges(const ContourBoundary& boundary) const {
        return ContourEdgeRange(boundarySpan(boundary));
    }
 
    [[nodiscard]] ContourPixelRange boundaryPixels(const ContourBoundary& boundary) const {
        return ContourPixelRange(boundaryEdges(boundary));
    }
 
  private:
    friend class ContourTrace;
    friend class ContourTraceComputation;
    friend class contours::detail::ContourTraceTraversal;
 
    ContourTraceView(std::span<const int> packedEdges, std::span<const ContourBoundary> boundaries)
        : packedEdges_(packedEdges), boundaries_(boundaries) {}
 
    [[nodiscard]] std::span<const int> boundarySpan(const ContourBoundary& boundary) const {
        const std::size_t offset = boundary.edgeOffset;
        const std::size_t count = boundary.edgeCount;
        if (offset > packedEdges_.size() || count > packedEdges_.size() - offset) {
            throw std::invalid_argument("ContourBoundary does not belong to this contour trace.");
        }
        return packedEdges_.subspan(offset, count);
    }
 
    std::span<const int> packedEdges_;                    
    std::span<const ContourBoundary> boundaries_;         
};
 
class ContourTrace {
  public:
    ContourTrace() = default;
 
    explicit ContourTrace(ContourTraceView trace)
        : packedEdges_(trace.packedEdges_.begin(), trace.packedEdges_.end()),
          boundaries_(trace.boundaries_.begin(), trace.boundaries_.end()) {}
 
    [[nodiscard]] std::span<const ContourBoundary> boundaries() const noexcept { return view().boundaries(); }
 
    [[nodiscard]] ContourBoundary externalBoundary() const { return view().externalBoundary(); }
 
    [[nodiscard]] ContourEdgeRange edges() const noexcept { return view().edges(); }
 
    [[nodiscard]] ContourEdgeRange boundaryEdges(const ContourBoundary& boundary) const { return view().boundaryEdges(boundary); }
 
    [[nodiscard]] ContourPixelRange boundaryPixels(const ContourBoundary& boundary) const { return view().boundaryPixels(boundary); }
 
    [[nodiscard]] ContourTraceView view() const noexcept { return ContourTraceView(packedEdges_, boundaries_); }
 
  private:
    friend class ContourTraceComputation;
 
    ContourTrace(std::vector<int> packedEdges, std::vector<ContourBoundary> boundaries)
        : packedEdges_(std::move(packedEdges)), boundaries_(std::move(boundaries)) {}
 
    std::vector<int> packedEdges_;                
    std::vector<ContourBoundary> boundaries_;     
};
 
} // namespace mmcfilters