kev/Drawer/Module/GeoSigmaDraw/UndecidedZone.h

#pragma once

#include <cassert>
#include "DrawOperator/Mesh.h"
#include "DrawModel/Dimension2D.h"
#include "DrawOperator/unordered_dense.h"
#include "Util.h"
#include "clipper2/clipper.h"

/**
 * <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
 */
class UndecidedZone
{
public:

	UndecidedZone(CMesh* pMesh)
		: m_pMesh(pMesh)
	{
		m_pMesh->GetNumber(m_numx, m_numy);
		m_pMesh->GetDelt(m_dx, m_dy);
		m_pDfg = m_pMesh->GetDfg();
	}

	/**
	 * <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Χ<EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD>ͨ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
	 *
	 * \param zMin	z ֵ<EFBFBD><EFBFBD>Сֵ
	 * \param zMax	z ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ
	 * \return
	 */
	std::vector<std::unique_ptr<CCurveEx>> ComputeRegions(double zMin, double zMax) const
	{
		std::vector<std::unique_ptr<CCurveEx>> result;
		Regions regions = FindAllRegions(zMin, zMax);

		for (const Region& region : regions)
		{
			auto regionResult = ComputeRegion(region);
			result.insert(result.end(), std::make_move_iterator(regionResult.begin()), std::make_move_iterator(regionResult.end()));
		}

		return result;
	}

	/**
	 * <EFBFBD><EFBFBD>ȡָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Χ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±꣬<EFBFBD><EFBFBD>ͨ<EFBFBD>Ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>
	 * 
	 * \param zMin
	 * \param zMax
	 * \return 
	 */
	std::vector<std::vector<std::pair<int, int>>> FindAllRegions(double zMin, double zMax) const
	{
		if (zMin > zMax)
		{
			return {};
		}

		if (IsZOutofMesh(zMin, zMax))
		{
			return {};
		}

		auto pred = [this, zMin, zMax](int x, int y)
			{
				double z = m_pDfg->Value(x, y);
				return InRange(z, zMin, zMax);
			};

		return FindAllRegions(pred);
	}

private:
	using Point = std::pair<int, int>;
	using Region = std::vector<Point>;
	using Regions = std::vector<Region>;
	using Pred = std::function<bool(int x, int y)>;

	/**
	 * <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͨ<EFBFBD>Ľڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Χ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
	 * 
	 * \param region
	 * \return 
	 */
	std::vector<std::unique_ptr<CCurveEx>> ComputeRegion(const Region& region) const
	{
		struct PointHash
		{
			size_t operator()(const std::pair<int, int>& p) const
			{
				return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
			}
		};

		struct Edge
		{
			Point p1, p2;
			void normalize()
			{
				if (p1 > p2) std::swap(p1, p2);
			}
			bool operator==(const Edge& other) const
			{
				return p1 == other.p1 && p2 == other.p2;
			}
		};

		struct EdgeHash
		{
			size_t operator()(const Edge& e) const
			{
				return std::hash<int>()(e.p1.first) ^ (std::hash<int>()(e.p1.second) << 1) ^
					   (std::hash<int>()(e.p2.first) << 2) ^ (std::hash<int>()(e.p2.second) << 3);
			}
		};

		std::unordered_map<Edge, int, EdgeHash> edgeCount;

		// 1. ͳ<><CDB3><EFBFBD><EFBFBD><EFBFBD>б߳<D0B1><DFB3>ִ<EFBFBD><D6B4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>߹<EFBFBD><DFB9><EFBFBD>ÿ<EFBFBD><C3BF><EFBFBD><EFBFBD><EFBFBD>ӣ<EFBFBD>
		for (const Point& pt : region)
		{
			int x = pt.first;
			int y = pt.second;

			std::array<Edge, 4> edges = {
				Edge{{x, y}, {x + 1, y}},       // bottom
				Edge{{x + 1, y}, {x + 1, y + 1}}, // right
				Edge{{x + 1, y + 1}, {x, y + 1}}, // top
				Edge{{x, y + 1}, {x, y}}        // left
			};

			for (auto& edge : edges)
			{
				edge.normalize();
				edgeCount[edge]++;
			}
		}

		// 2. ֻ<><D6BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD>εıߣ<C4B1><DFA3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߣ<EFBFBD>
		std::unordered_map<Point, std::vector<Edge>, PointHash> pointToEdges;
		std::unordered_set<Edge, EdgeHash> boundaryEdges;

		for (const auto& [edge, count] : edgeCount)
		{
			if (count == 1)
			{
				pointToEdges[edge.p1].push_back(edge);
				pointToEdges[edge.p2].push_back(edge);
				boundaryEdges.insert(edge);
			}
		}

		// 3. <20>ӱ߽<D3B1><DFBD><EFBFBD>׷<EFBFBD>ٹ<EFBFBD><D9B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܶ<EFBFBD><DCB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Σ<EFBFBD>
		std::vector<std::unique_ptr<CCurveEx>> result;
		std::unordered_set<Edge, EdgeHash> visited;

		while (!boundaryEdges.empty())
		{
			// <20><>ѡһ<D1A1><D2BB>δʹ<CEB4>ñ߿<C3B1>ʼ׷<CABC><D7B7>
			Edge startEdge = *boundaryEdges.begin();
			Point current = startEdge.p1;

			std::vector<Point> contour;
			contour.push_back(current);
			visited.insert(startEdge);
			boundaryEdges.erase(startEdge);

			Point next = startEdge.p2;
			contour.push_back(next);

			while (next != current)
			{
				const auto& edges = pointToEdges[next];
				bool found = false;

				for (const Edge& e : edges)
				{
					if (visited.count(e) == 0)
					{
						Point other = (e.p1 == next) ? e.p2 : e.p1;
						contour.push_back(other);
						visited.insert(e);
						boundaryEdges.erase(e);
						next = other;
						found = true;
						break;
					}
				}

				if (!found) break; // <20><><EFBFBD>պϾ<D5BA><CFBE>˳<EFBFBD>
			}

			// 4. ת<><D7AA> contour <20><>ʵ<EFBFBD><CAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϵ<EFBFBD><CFB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD> CCurveEx
			if (contour.size() >= 3)
			{
				auto curve = std::make_unique<CCurveEx>();
				curve->Create(static_cast<int>(contour.size()));

				for (size_t i = 0; i < contour.size(); ++i)
				{
					curve->x[i] = m_pMesh->left + contour[i].first * m_dx;
					curve->y[i] = m_pMesh->bottom + contour[i].second * m_dy;
				}
				result.push_back(std::move(curve));
			}
		}

		return result;
	}

	Clipper2Lib::PathD CreatePathD(const Point& point) const
	{
		double left = m_pMesh->left + point.first * m_dx;
		double bottom = m_pMesh->bottom + point.second * m_dy;
		double right = left + m_dx;
		double top = bottom + m_dy;

		return Clipper2Lib::PathD{ {left, top}, { right, top}, {right, bottom}, {left, bottom} };
	}

	std::unique_ptr<CCurveEx> CreateCurveEx(const Clipper2Lib::PathD& path) const
	{
		assert(!path.empty());

		auto pCurve = std::make_unique<CCurveEx>();
		pCurve->Create(static_cast<int>(path.size()) + 1);

		size_t i = 0;
		for (; i < path.size(); i++)
		{
			pCurve->x[i] = path[i].x;
			pCurve->y[i] = path[i].y;
		}
		pCurve->x[i] = path[0].x;
		pCurve->y[i] = path[0].y;

		return pCurve;
	}

	Regions FindAllRegions(Pred pred) const
	{
		Regions regions;

		std::vector<std::vector<bool>> visited(m_numx, std::vector<bool>(m_numy, false));

		for (int i = 0; i < m_numx; i++)
		{
			for (int j = 0; j < m_numy; j++)
			{
				if (!visited[i][j] && pred(i, j))
				{
					regions.push_back(Bfs(i, j, visited, pred));
				}
			}
		}

		return regions;
	}

	std::vector<Point> Bfs(int x, int y, std::vector<std::vector<bool>>& visited, Pred pred) const
	{
		std::queue<Point> q;
		std::vector<Point> region;

		// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
		std::vector<int> dx = { -1, 1, 0, 0 };
		std::vector<int> dy = { 0, 0, -1, 1 };

		q.push({ x, y });
		visited[x][y] = true;

		while (!q.empty())
		{
			Point p = q.front();
			q.pop();
			region.push_back(p);

			for (int d = 0; d < 4; d++)
			{
				int ni = p.first + dx[d];
				int nj = p.second + dy[d];

				if ((ni >= 0 && ni < m_numx) && (nj >= 0 && nj < m_numy))
				{
					if (pred(ni, nj) && !visited[ni][nj])
					{
						visited[ni][nj] = true;
						q.push({ ni, nj });
					}
				}
			}
		}

		return region;
	}

	bool IsZOutofMesh(double zMin, double zMax) const
	{
		double mZmin = 0.0;
		double mZmax = 0.0;
		m_pMesh->GetM(mZmin, mZmax);
		return (zMin >= mZmax || zMax <= mZmin);
	}

	CMesh* m_pMesh = nullptr;
	CDimension2D* m_pDfg = nullptr;
	double m_dx = 0.0;
	double m_dy = 0.0;
	long m_numx = 0;
	long m_numy = 0;
};