MonotonePartition.cpp

//
// Created by Ryan.Zurrin001 on 12/16/2021.
//
#include "MonotonePartition.h"

#include <set>
#include <map>
#include <algorithm>

using namespace rez;

enum class VERTEX_CATEGORY {
    START,
    END,
    REGULAR,
    SPLIT,
    MERGE,
    INVALID
};

VERTEX_CATEGORY categorize_vertex(Vertex2dDCEL* vertex)
{
    Vertex2dDCEL* v_prev = vertex->incident_edge->prev->origin;
    Vertex2dDCEL* v_next = vertex->incident_edge->next->origin;

    // Need vertex beside the given one to get the dicission. Return INVALID if one is missing
    if (!v_prev || !v_next)
        return VERTEX_CATEGORY::INVALID;

    Point2d p_prev = v_prev->point;
    Point2d p = vertex->point;
    Point2d p_next = v_next->point;

    bool is_left = left(p_prev, p, p_next);

    if (p[Y_] > p_prev[Y_] && p[Y_] > p_next[Y_])
    {
        if (is_left)
            return VERTEX_CATEGORY::START;
        else
            return VERTEX_CATEGORY::SPLIT;
    }
    else if (p[Y_] < p_prev[Y_] && p[Y_] < p_next[Y_])
    {
        if (is_left)
            return VERTEX_CATEGORY::END;
        else
            return VERTEX_CATEGORY::MERGE;
    }
    else
    {
        return VERTEX_CATEGORY::REGULAR;
    }
}

struct Vertex2dDCELWrapper {
    Vertex2dDCEL* vert;
    VERTEX_CATEGORY category;
};

struct Edge2dDCELWrapper {
    Edge2dDCEL* edge;
    Vertex2dDCELWrapper helper;

    Edge2dDCELWrapper(Edge2dDCEL* _edge, Vertex2dDCELWrapper& _helper) {
        edge = _edge;
        helper = _helper;
        orgin = edge->origin->point;
        dest = edge->twin->origin->point;
    }

    const float computeX(const Point2d& point) const {
        float _deno = (dest[Y_] - orgin[Y_]);
        float _x = point[X_];
        if (_deno != 0) {
            _x = (point[Y_] - orgin[Y_]) * (dest[X_] - orgin[X_]) / _deno + orgin[X_];
        }
        return _x;
    }

private:
    Point2d orgin, dest;
};

struct Vertex2DWrapperSort {
    bool operator()(Vertex2dDCELWrapper& current, Vertex2dDCELWrapper& ref) {
        auto cur_pnt = current.vert->point;
        auto ref_pnt = ref.vert->point;
        if ((cur_pnt[Y_] > ref_pnt[Y_])
            || (cur_pnt[Y_] == ref_pnt[Y_]) && (cur_pnt[X_] < ref_pnt[X_]))
        {
            return true;
        }
        return false;
    }
};

struct SweepLineComparator {
    Point2d* point;
    SweepLineComparator(Point2d* _point) {
        point = _point;
    }

    bool operator()(const Edge2dDCELWrapper* _ref1, const Edge2dDCELWrapper* _ref2) const {
        return _ref1->computeX(*point) < _ref2->computeX(*point);
    }
};

// TODO : Check the posibility of Refactoring the code to remove duplicate lines

static void handle_start_vertices(Vertex2dDCELWrapper& vertex
        , std::set<Edge2dDCELWrapper*, SweepLineComparator>& sweep_line
        , std::map<Edge2dDCEL*, Edge2dDCELWrapper*>& edge_mapper, Polygon2d* poly)
{
    Edge2dDCELWrapper* edge = new Edge2dDCELWrapper(vertex.vert->incident_edge, vertex);
    sweep_line.insert(edge);
    edge_mapper.insert(std::pair<Edge2dDCEL*, Edge2dDCELWrapper*>(vertex.vert->incident_edge, edge));
}

static void handle_end_vertices(Vertex2dDCELWrapper& vertex
        , std::set<Edge2dDCELWrapper*, SweepLineComparator>& sweep_line
        , std::map<Edge2dDCEL*, Edge2dDCELWrapper*>& edge_mapper, Polygon2d* poly)
{
    auto edge_wrapper = edge_mapper[vertex.vert->incident_edge->prev];
    auto found = sweep_line.find(edge_wrapper);
    auto helper = (*found)->helper;
    if (helper.category == VERTEX_CATEGORY::MERGE)
        poly->split(vertex.vert, helper.vert);
    sweep_line.erase(found);
}

static void handle_split_vertices(Vertex2dDCELWrapper& vertex
        , std::set<Edge2dDCELWrapper*, SweepLineComparator>& sweep_line
        , std::map<Edge2dDCEL*, Edge2dDCELWrapper*>& edge_mapper, Polygon2d* poly)
{
    Edge2dDCELWrapper* edge = new Edge2dDCELWrapper(vertex.vert->incident_edge, vertex);
    auto found = sweep_line.lower_bound(edge);
    Edge2dDCELWrapper* ej;
    if (found == sweep_line.end()) {
        if (sweep_line.size() > 0) {
            ej = *(--found);
            poly->split(vertex.vert, ej->helper.vert);
            ej->helper = vertex;
        }
    }
    else if (found != sweep_line.begin())
    {
        ej = *(--found);
        poly->split(vertex.vert, ej->helper.vert);
        ej->helper = vertex;
    }
    sweep_line.insert(edge);
    edge_mapper.insert(std::pair<Edge2dDCEL*, Edge2dDCELWrapper*>(vertex.vert->incident_edge, edge));
}

static void handle_merge_vertices(Vertex2dDCELWrapper& vertex
        , std::set<Edge2dDCELWrapper*, SweepLineComparator>& sweep_line
        , std::map<Edge2dDCEL*, Edge2dDCELWrapper*>& edge_mapper, Polygon2d* poly)
{
    auto edge_wrapper = edge_mapper[vertex.vert->incident_edge->prev];
    if (edge_wrapper->helper.category == VERTEX_CATEGORY::MERGE) {
        poly->split(vertex.vert, edge_wrapper->helper.vert);
    }

    auto found = sweep_line.find(edge_wrapper);
    if (found != sweep_line.end())
        sweep_line.erase(found);

    Edge2dDCELWrapper* edge = new Edge2dDCELWrapper(vertex.vert->incident_edge, vertex);
    found = sweep_line.lower_bound(edge);
    Edge2dDCELWrapper* ej;
    if (found == sweep_line.end()) {
        if (sweep_line.size() > 0) {
            ej = *(--found);
            if (ej->helper.category == VERTEX_CATEGORY::MERGE)
                poly->split(vertex.vert, ej->helper.vert);
            ej->helper = vertex;
        }
    }
    else if (found != sweep_line.begin())
    {
        ej = *(--found);
        if (ej->helper.category == VERTEX_CATEGORY::MERGE)
            poly->split(vertex.vert, ej->helper.vert);
        ej->helper = vertex;
    }
}

static void handle_regular_vertices(Vertex2dDCELWrapper& vertex
        , std::set<Edge2dDCELWrapper*, SweepLineComparator>& sweep_line
        , std::map<Edge2dDCEL*, Edge2dDCELWrapper*>& edge_mapper, Polygon2d* poly)
{
    // Check whether the interior of the polygon lies right to vertex point
    auto prev_y = vertex.vert->incident_edge->prev->origin->point[Y_];
    auto current_y = vertex.vert->point[Y_];
    auto next_y = vertex.vert->incident_edge->next->origin->point[Y_];

    Edge2dDCELWrapper* edge = new Edge2dDCELWrapper(vertex.vert->incident_edge, vertex);

    if (prev_y >= current_y && current_y >= next_y) {
        auto edge_wrapper = edge_mapper[vertex.vert->incident_edge->prev];
        if (edge_wrapper->helper.category == VERTEX_CATEGORY::MERGE) {
            poly->split(vertex.vert, edge_wrapper->helper.vert);
        }

        auto found = sweep_line.find(edge_wrapper);
        if (found != sweep_line.end())
            sweep_line.erase(found);

        sweep_line.insert(edge);
        edge_mapper.insert(std::pair<Edge2dDCEL*, Edge2dDCELWrapper*>(vertex.vert->incident_edge,
                                                                      edge));
    }
    else {
        auto found = sweep_line.lower_bound(edge);
        Edge2dDCELWrapper* ej;
        if (found == sweep_line.end()) {
            if (sweep_line.size() > 0) {
                ej = *(--found);
                if (ej->helper.category == VERTEX_CATEGORY::MERGE)
                    poly->split(vertex.vert, ej->helper.vert);
                ej->helper = vertex;
            }
        }
        else if (found != sweep_line.begin())
        {
            ej = *(found--);
            if (ej->helper.category == VERTEX_CATEGORY::MERGE)
                poly->split(vertex.vert, ej->helper.vert);
            ej->helper = vertex;
        }
    }
}


void rez::get_monotone_polygons(Polygon2d* poly, std::vector<Polygon2d*>& mono_polies)
{
    std::vector<Vertex2dDCELWrapper> vertices;
    for (auto vertex : poly->getVertexList()) {
        vertices.push_back(Vertex2dDCELWrapper{ vertex,categorize_vertex(vertex) });
    }

    std::sort(vertices.begin(), vertices.end(), Vertex2DWrapperSort());

    Point2d* sweep_point = new Point2d();
    sweep_point->assign(X_, vertices[0].vert->point[X_]);
    sweep_point->assign(Y_, vertices[0].vert->point[Y_]);

    SweepLineComparator comp(sweep_point);
    std::set<Edge2dDCELWrapper*, SweepLineComparator> sweep_line(comp);
    std::map<Edge2dDCEL*, Edge2dDCELWrapper*> edge_mapping;

    for (auto vertex : vertices)
    {
        sweep_point->assign(X_, vertex.vert->point[X_]);
        sweep_point->assign(Y_, vertex.vert->point[Y_]);

        switch (vertex.category)
        {
            case VERTEX_CATEGORY::START:
                handle_start_vertices(vertex, sweep_line, edge_mapping, poly);
                break;
            case VERTEX_CATEGORY::END:
                handle_end_vertices(vertex, sweep_line, edge_mapping, poly);
                break;
            case VERTEX_CATEGORY::REGULAR:
                handle_regular_vertices(vertex, sweep_line, edge_mapping, poly);
                break;
            case VERTEX_CATEGORY::SPLIT:
                handle_split_vertices(vertex, sweep_line, edge_mapping, poly);
                break;
            case VERTEX_CATEGORY::MERGE:
                handle_merge_vertices(vertex, sweep_line, edge_mapping, poly);
                break;
            case VERTEX_CATEGORY::INVALID:
                break;
        }
    }

    std::vector<std::vector<Point2d>> polygon_pieces_vertices;

    for (auto face_ptr : poly->getFaceList()) {
        auto first_edge_ptr = face_ptr->outer;
        if (first_edge_ptr) {
            std::vector<Point2d> vertices;
            vertices.push_back(first_edge_ptr->origin->point);

            auto next_edge_ptr = first_edge_ptr->next;
            while (next_edge_ptr != first_edge_ptr) {
                vertices.push_back(next_edge_ptr->origin->point);
                next_edge_ptr = next_edge_ptr->next;
            }

            polygon_pieces_vertices.push_back(vertices);
        }
    }

    for (auto vertices : polygon_pieces_vertices)
        mono_polies.push_back(new Polygon2d(vertices));
}