// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// contours.hpp — 輪郭検出
//
// Suzuki-Abe 簡略版 border following アルゴリズム。
// 二値画像 (0 = 背景, 非ゼロ = 前景) から外部輪郭を抽出。

#ifndef CALX_IMAGE_IMGPROC_CONTOURS_HPP
#define CALX_IMAGE_IMGPROC_CONTOURS_HPP

#include <image/Image.hpp>
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <utility>
#include <vector>

namespace calx::image {

    /// 輪郭を表す点列
    struct Contour {
        std::vector<std::pair<int, int>> points;  // (y, x)
    };

    namespace detail_contours {

        // 8 近傍の方向 (時計回り): 右, 右下, 下, 左下, 左, 左上, 上, 右上
        inline constexpr int dy8[8] = { 0,  1,  1,  1,  0, -1, -1, -1 };
        inline constexpr int dx8[8] = { 1,  1,  0, -1, -1, -1,  0,  1 };

        /// 1 つの輪郭を追跡 (Moore boundary tracing)
        /// @param visited  訪問済みフラグ (H x W)
        /// @param bin      二値画像データ
        /// @param H, W     画像サイズ
        /// @param startY, startX  輪郭開始点
        /// @param startDir 開始方向
        inline Contour traceContour(std::vector<std::vector<bool>>& visited,
                                    const std::vector<std::vector<int>>& bin,
                                    int H, int W,
                                    int startY, int startX, int startDir) {
            Contour c;
            int y = startY, x = startX;
            int dir = startDir;
            bool first = true;

            do {
                c.points.emplace_back(y, x);
                visited[y][x] = true;

                // 次の前景ピクセルを探す (反時計回りに回転して探索)
                int searchDir = (dir + 6) % 8;  // 前の方向の左 90° から開始
                bool found = false;
                for (int i = 0; i < 8; ++i) {
                    int d = (searchDir + i) % 8;
                    int ny = y + dy8[d];
                    int nx = x + dx8[d];
                    if (ny >= 0 && ny < H && nx >= 0 && nx < W && bin[ny][nx] != 0) {
                        dir = d;
                        y = ny;
                        x = nx;
                        found = true;
                        break;
                    }
                }
                if (!found) break;  // 孤立点

                if (first) first = false;
            } while (y != startY || x != startX);

            return c;
        }

    } // namespace detail_contours

    /// 二値画像から外部輪郭を検出
    /// @param binaryImg  二値画像 (1ch, 0 = 背景, 非ゼロ = 前景)
    /// @return           輪郭のリスト
    template<typename T>
    std::vector<Contour> findContours(const Image<T>& binaryImg) {
        assert(binaryImg.numChannels() >= 1);

        int H = static_cast<int>(binaryImg.height());
        int W = static_cast<int>(binaryImg.width());

        // 二値化してコピー
        std::vector<std::vector<int>> bin(H, std::vector<int>(W, 0));
        const auto& ch = binaryImg.channel(0);
        for (int y = 0; y < H; ++y)
            for (int x = 0; x < W; ++x)
                bin[y][x] = (ch(y, x) > T{0}) ? 1 : 0;

        std::vector<std::vector<bool>> visited(H, std::vector<bool>(W, false));
        std::vector<Contour> contours;

        // ラスタスキャンで輪郭開始点を探す
        for (int y = 0; y < H; ++y) {
            for (int x = 0; x < W; ++x) {
                if (bin[y][x] == 0 || visited[y][x]) continue;

                // 外部輪郭の開始条件: 左隣が背景 (または左端)
                if (x == 0 || bin[y][x - 1] == 0) {
                    auto c = detail_contours::traceContour(
                        visited, bin, H, W, y, x, 0);
                    if (!c.points.empty())
                        contours.push_back(std::move(c));
                } else {
                    visited[y][x] = true;
                }
            }
        }
        return contours;
    }

    /// 輪郭面積 (Shoelace formula)
    inline double contourArea(const Contour& c) {
        if (c.points.size() < 3) return 0;
        double area = 0;
        size_t n = c.points.size();
        for (size_t i = 0; i < n; ++i) {
            size_t j = (i + 1) % n;
            auto [y0, x0] = c.points[i];
            auto [y1, x1] = c.points[j];
            area += static_cast<double>(x0) * y1 - static_cast<double>(x1) * y0;
        }
        return std::abs(area) * 0.5;
    }

    /// 輪郭の弧長 (周囲長)
    inline double arcLength(const Contour& c) {
        if (c.points.size() < 2) return 0;
        double len = 0;
        size_t n = c.points.size();
        for (size_t i = 0; i < n; ++i) {
            size_t j = (i + 1) % n;
            double dy = c.points[j].first  - c.points[i].first;
            double dx = c.points[j].second - c.points[i].second;
            len += std::sqrt(dy * dy + dx * dx);
        }
        return len;
    }

    /// バウンディングボックス {x, y, w, h}
    inline std::array<int, 4> boundingRect(const Contour& c) {
        if (c.points.empty()) return {0, 0, 0, 0};
        int minY = c.points[0].first,  maxY = minY;
        int minX = c.points[0].second, maxX = minX;
        for (auto& [y, x] : c.points) {
            minY = std::min(minY, y); maxY = std::max(maxY, y);
            minX = std::min(minX, x); maxX = std::max(maxX, x);
        }
        return {minX, minY, maxX - minX + 1, maxY - minY + 1};
    }

} // namespace calx::image

#endif // CALX_IMAGE_IMGPROC_CONTOURS_HPP
