---

#include <SFML/Graphics.hpp>
#include <vector>
#include <cmath>
#include <iostream>

struct Point
{
    float x, y;

    Point() = default;

    Point(float X, float Y)
        : x(X), y(Y)
    {
    }

    Point operator+(const Point& other) const
    {
        return {x + other.x, y + other.y};
    }

    Point operator-(const Point& other) const
    {
        return {x - other.x, y - other.y};
    }

    Point operator*(float v) const
    {
        return {x * v, y * v};
    }
};

float cross(const Point& a, const Point& b)
{
    return a.x * b.y - a.y * b.x;
}

bool segmentIntersection(
    Point p1,
    Point p2,
    Point q1,
    Point q2,
    Point& intersection)
{
    Point r = p2 - p1;
    Point s = q2 - q1;

    float rxs = cross(r, s);

    if (fabs(rxs) < 1e-6f)
        return false;

    float t = cross(q1 - p1, s) / rxs;
    float u = cross(q1 - p1, r) / rxs;

    if (t >= 0 && t <= 1 && u >= 0 && u <= 1)
    {
        intersection = p1 + r * t;
        return true;
    }

    return false;
}

bool inside(Point p, sf::FloatRect rect)
{
    return p.x >= rect.left &&
           p.x <= rect.left + rect.width &&
           p.y >= rect.top &&
           p.y <= rect.top + rect.height;
}

std::vector<Point> clipPolygon(
    const std::vector<Point>& poly,
    sf::FloatRect rect)
{
    std::vector<Point> output = poly;

    auto clipEdge = [&](auto insideFunc, auto intersectFunc)
    {
        std::vector<Point> input = output;
        output.clear();

        if (input.empty())
            return;

        Point S = input.back();

        for (auto& E : input)
        {
            bool Ein = insideFunc(E);
            bool Sin = insideFunc(S);

            if (Ein)
            {
                if (!Sin)
                    output.push_back(intersectFunc(S, E));

                output.push_back(E);
            }
            else if (Sin)
            {
                output.push_back(intersectFunc(S, E));
            }

            S = E;
        }
    };

    clipEdge(
        [&](Point p)
        {
            return p.x >= rect.left;
        },
        [&](Point s, Point e)
        {
            float t = (rect.left - s.x) / (e.x - s.x);
            return Point(
                rect.left,
                s.y + (e.y - s.y) * t);
        });

    clipEdge(
        [&](Point p)
        {
            return p.x <= rect.left + rect.width;
        },
        [&](Point s, Point e)
        {
            float x = rect.left + rect.width;
            float t = (x - s.x) / (e.x - s.x);

            return Point(
                x,
                s.y + (e.y - s.y) * t);
        });

    clipEdge(
        [&](Point p)
        {
            return p.y >= rect.top;
        },
        [&](Point s, Point e)
        {
            float t = (rect.top - s.y) / (e.y - s.y);

            return Point(
                s.x + (e.x - s.x) * t,
                rect.top);
        });

    clipEdge(
        [&](Point p)
        {
            return p.y <= rect.top + rect.height;
        },
        [&](Point s, Point e)
        {
            float y = rect.top + rect.height;
            float t = (y - s.y) / (e.y - s.y);

            return Point(
                s.x + (e.x - s.x) * t,
                y);
        });

    return output;
}

sf::ConvexShape makeShape(
    const std::vector<Point>& pts,
    sf::Color color)
{
    sf::ConvexShape shape;
    shape.setPointCount(pts.size());

    for (size_t i = 0; i < pts.size(); ++i)
    {
        shape.setPoint(i, sf::Vector2f(pts[i].x, pts[i].y));
    }

    shape.setFillColor(sf::Color::Transparent);
    shape.setOutlineThickness(2);
    shape.setOutlineColor(color);

    return shape;
}

int main()
{
    sf::RenderWindow window(
        sf::VideoMode(1000, 700),
        "Weiler-Atherton");

    std::vector<Point> plus =
    {
        {300, 100},
        {400, 100},
        {400, 250},
        {550, 250},
        {550, 350},
        {400, 350},
        {400, 500},
        {300, 500},
        {300, 350},
        {150, 350},
        {150, 250},
        {300, 250}
    };

    sf::FloatRect clipRect(250, 180, 300, 220);

    bool dragging = false;
    sf::Vector2f dragOffset;

    while (window.isOpen())
    {
        sf::Event event;

        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();

            if (event.type == sf::Event::MouseButtonPressed)
            {
                if (event.mouseButton.button == sf::Mouse::Left)
                {
                    sf::Vector2f mouse(
                        event.mouseButton.x,
                        event.mouseButton.y);

                    if (clipRect.contains(mouse))
                    {
                        dragging = true;

                        dragOffset =
                            mouse -
                            sf::Vector2f(
                                clipRect.left,
                                clipRect.top);
                    }
                }
            }

            if (event.type == sf::Event::MouseButtonReleased)
            {
                dragging = false;
            }

            if (event.type == sf::Event::MouseMoved)
            {
                if (dragging)
                {
                    clipRect.left =
                        event.mouseMove.x - dragOffset.x;

                    clipRect.top =
                        event.mouseMove.y - dragOffset.y;
                }
            }

            if (event.type == sf::Event::KeyPressed)
            {
                if (event.key.code == sf::Keyboard::Delete)
                {
                    clipRect = sf::FloatRect(0,0,0,0);
                }
            }
        }

        auto clipped = clipPolygon(plus, clipRect);

        window.clear(sf::Color::White);

        auto originalShape =
            makeShape(plus, sf::Color::Blue);

        window.draw(originalShape);

        if (clipRect.width > 0 && clipRect.height > 0)
        {
            sf::RectangleShape rectShape(
                sf::Vector2f(
                    clipRect.width,
                    clipRect.height));

            rectShape.setPosition(
                clipRect.left,
                clipRect.top);

            rectShape.setFillColor(
                sf::Color::Transparent);

            rectShape.setOutlineThickness(2);

            rectShape.setOutlineColor(
                sf::Color::Red);

            window.draw(rectShape);
        }

        if (!clipped.empty())
        {
            auto clippedShape =
                makeShape(clipped, sf::Color::Green);

            clippedShape.setFillColor(
                sf::Color(0,255,0,80));

            window.draw(clippedShape);
        }

        window.display();
    }

    return 0;
}