#include <cmath>
#include "geometry.h"

inline bool _collide(const vec2f *p, const vec2f *A, const vec2f *B, const vec2f *C) noexcept;
inline bool _triangleOk(const vec2f **, uint32_t index, uint32_t count, std::vector<vec2f> &) noexcept;
inline float _angle(const vec2f **, uint32_t index, uint32_t count, float modAngle = 0) noexcept;

namespace render::utils
{

void triangulate(const std::vector<vec2f> &vertices, std::vector<vec2f> &out) noexcept
{
    uint32_t count = vertices.size();
    const vec2f **vertData = new const vec2f *[count];

    uint32_t index = 0;
    for (const vec2f &vert : vertices)
        vertData[index++] = &vert;

    while (count >= 3)
    {
        uint32_t leftIndex = 0;
        for (uint32_t i = 1; i < count; i++)
        {
            if (vertData[i]->x < vertData[leftIndex]->x)
                leftIndex = i;
        }

        if (_triangleOk(vertData, leftIndex, count, out))
        {
            count--;
            vertData[leftIndex] = vertData[count];
            continue;
        }

        float modAngle = _angle(vertData, leftIndex, count);
        float lastAngle = _angle(vertData, count - 1, count, modAngle);

        for (uint32_t i = 0; i < count; i++)
        {
            if (i == leftIndex)
                continue;
            float angle = _angle(vertData, i, count, modAngle);
            if (angle <= lastAngle)
                if (_triangleOk(vertData, i, count, out))
                {
                    count--;
                    vertData[leftIndex] = vertData[count];
                    break;
                }
            lastAngle = angle;
        }
    }
}

} // namespace render::utils

inline bool _triangleOk(const vec2f **verts, uint32_t index, uint32_t count, std::vector<vec2f> &out) noexcept
{
    uint32_t prev = index - 1, next = index + 1;

    if (!index)
        prev = count - 1;
    else if (next == count)
        next = 0;

    for (uint32_t i = 0; i < count; i++)
    {
        if (i == index || i == next || i == prev)
            continue;

        if (_collide(verts[i], verts[index], verts[prev], verts[next]))
            return false;
    }

    out.push_back(*verts[prev]);
    out.push_back(*verts[index]);
    out.push_back(*verts[next]);

    return true;
}

inline bool _collide(const vec2f *p, const vec2f *A, const vec2f *B, const vec2f *C) noexcept
{
    vec3f r(
        (A->x - p->x) * (B->y - A->y) - (B->x - A->x) * (A->y - p->y),
        (B->x - p->x) * (C->y - B->y) - (C->x - B->x) * (B->y - p->y),
        (C->x - p->x) * (A->y - C->y) - (A->x - C->x) * (C->y - p->y));

    return ((r.x < 0 && r.y < 0 && r.z < 0) || (r.x == 0 && r.y == 0 && r.z == 0) || (r.x > 0 && r.y > 0 && r.z > 0));
}

inline float _angle(const vec2f **verts, uint32_t index, uint32_t count, float modAngle) noexcept
{
    uint32_t next = index + 1;

    if (next == count)
        next = 0;

    vec2f temp = (*verts[next]) - (*verts[index]);
    return atan2(temp.x, temp.y) - modAngle;
}
