recti.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>  // for std::sort
#include <optional>   // for std::optional, std::nullopt
#include <vector>     // for std::vector
 
#include "interval.hpp"  // for Interval
#include "point.hpp"     // for Point
 
namespace recti {
 
    template <typename T> struct Rectangle : Point<Interval<T>> {
        constexpr Rectangle(Interval<T> xcoord, Interval<T> ycoord) noexcept
            : Point<Interval<T>>{std::move(xcoord), std::move(ycoord)} {}
 
        constexpr Rectangle(
            Point<Interval<T>> base) noexcept  // Note: intentionally allow implicit conversion
            : Point<Interval<T>>{std::move(base)} {}
 
        constexpr auto ll() const -> Point<T> { return {this->xcoord().lb(), this->ycoord().lb()}; }
 
        constexpr auto ur() const -> Point<T> { return {this->xcoord().ub(), this->ycoord().ub()}; }
 
        constexpr auto area() const -> T {
            return this->xcoord().length() * this->ycoord().length();
        }
    };
 
    template <typename T> struct HSegment : Point<Interval<T>, T> {
        constexpr HSegment(Interval<T> xcoord, T ycoord) noexcept
            : Point<Interval<T>, T>{std::move(xcoord), std::move(ycoord)} {}
 
        constexpr HSegment(
            Point<Interval<T>, T> base) noexcept  // Note: intentionally allow implicit conversion
            : Point<Interval<T>, T>{std::move(base)} {}
    };
 
    template <typename T> struct VSegment : Point<T, Interval<T>> {
        constexpr VSegment(T xcoord, Interval<T> ycoord) noexcept
            : Point<T, Interval<T>>{std::move(xcoord), std::move(ycoord)} {}
 
        constexpr VSegment(
            Point<T, Interval<T>> base) noexcept  // Note: intentionally allow implicit conversion
            : Point<T, Interval<T>>{std::move(base)} {}
    };
 
    template <typename Container> constexpr auto detect_overlap(const Container& rectangles)
        -> std::optional<
            std::pair<typename Container::value_type, typename Container::value_type>> {
        using RectT = typename Container::value_type;
        using T = typename RectT::value_type;  // Extract the underlying type (int)
 
        if (rectangles.size() < 2) {
            return std::nullopt;
        }
 
        using Event = std::tuple<T, int, size_t>;
        std::vector<Event> events;
 
        size_t idx = 0;
        for (const auto& rect : rectangles) {
            if (rect.xcoord().is_invalid() || rect.ycoord().is_invalid()) {
                ++idx;
                continue;
            }
            events.emplace_back(rect.xcoord().lb(), 1, idx);
            events.emplace_back(rect.xcoord().ub(), -1, idx);
            ++idx;
        }
 
        std::sort(events.begin(), events.end(),
                  [](const Event& a, const Event& b) { return std::get<0>(a) < std::get<0>(b); });
 
        std::vector<std::pair<size_t, Interval<T>>> active;
 
        for (const auto& [x, event_type, rect_idx] : events) {
            const auto& rect = rectangles[rect_idx];
 
            if (event_type == 1) {
                for (const auto& [other_idx, other_y] : active) {
                    if (rect.ycoord().overlaps(other_y)) {
                        return std::make_optional(std::make_pair(rect, rectangles[other_idx]));
                    }
                }
                active.emplace_back(rect_idx, rect.ycoord());
            } else {
                for (size_t i = 0; i < active.size(); ++i) {
                    if (active[i].first == rect_idx) {
                        // O(1) removal: swap with back and pop
                        active[i] = active.back();
                        active.pop_back();
                        break;
                    }
                }
            }
        }
 
        return std::nullopt;
    }
 
}  // namespace recti