delaunay_triangulation.hpp

#include <vector>
#include <array>
#include <glm/glm.hpp>

struct TriangleAdj {
    std::array<int, 3> vertices;
    std::array<int, 3> adjacencies;

    TriangleAdj() : vertices{0, 0, 0}, adjacencies{-1, -1, -1} {}
};

struct DelaunayResult {
    std::vector<glm::vec2> points;
    std::vector<TriangleAdj> triangles;
};

bool point_within_triangle(const glm::vec2 &p, const glm::vec2 &a, const glm::vec2 &b, const glm::vec2 &c);

std::pair<float, glm::vec2> normalize_points(std::vector<glm::vec2> &points);

// using binning
void sort_points_by_spatial_proximity(std::vector<glm::vec2> &points);

// find which triangle contains a point
int find_containing_triangle(const glm::vec2 &p, int start_idx, const std::vector<glm::vec2> &points,
                             const std::vector<TriangleAdj> &triangles);

bool in_circumcircle(const glm::vec2 &p, const glm::vec2 &v1, const glm::vec2 &v2, const glm::vec2 &v3);

DelaunayResult delaunay_triangulate(std::vector<glm::vec2> points);