CUDelaunayTriangulator.h

//
//  CUDelaunayTriangulator.h
//  Cornell University Game Library (CUGL)
//
//  This module is a factory for a Delaunay triangulator.  Delaunay support is
//  not necessary for texture tesselation, but it is useful for applications
//  like HRTF support that require certain geometric guaranties on the
//  triangulation.  In addition, this triangulator can be used to extract the
//  Voronoi diagram as well.
//
//  Because math objects are intended to be on the stack, we do not provide
//  any shared pointer support in this class.
//
//  This implementation is based on the Bowyer-Watson algorithm detailed at
//
//      https://en.wikipedia.org/wiki/Bowyer–Watson_algorithm
//
//  CUGL MIT License:
//      This software is provided 'as-is', without any express or implied
//      warranty.  In no event will the authors be held liable for any damages
//      arising from the use of this software.
//
//      Permission is granted to anyone to use this software for any purpose,
//      including commercial applications, and to alter it and redistribute it
//      freely, subject to the following restrictions:
//
//      1. The origin of this software must not be misrepresented; you must not
//      claim that you wrote the original software. If you use this software
//      in a product, an acknowledgment in the product documentation would be
//      appreciated but is not required.
//
//      2. Altered source versions must be plainly marked as such, and must not
//      be misrepresented as being the original software.
//
//      3. This notice may not be removed or altered from any source distribution.
//
//  Author: Walker White
//  Version: 2/8/18
//
#ifndef __CU_DELAUNAY_TRIANGULATOR_H__
#define __CU_DELAUNAY_TRIANGULATOR_H__
 
#include <cugl/math/CUPoly2.h>
#include <cugl/math/CUVec2.h>
#include <cugl/math/CUVec3.h>
#include <vector>
#include <unordered_map>
 
namespace cugl {
 
class DelaunayTriangulator {
private:
#pragma mark Vertex
 
    class Vertex {
    public:
        Vec2 point;
        Sint64 index;
 
        Vertex() : index(-1) {}
 
        Vertex(const Vec2& p, Sint64 i);
 
        bool operator==(const Vertex& v) const;
 
        bool operator!=(const Vertex& v) const { return !(*this == v); }
 
        bool operator<(const Vertex& v) const;
        
        bool operator> (const Vertex& v) const { return v < *this; }
        
        bool operator<=(const Vertex& v) const { return !(v < *this); }
        
        bool operator>=(const Vertex& v) const { return !(*this < v); }
 
        size_t operator()(const Vertex& v) const;
 
    };
    
    
#pragma mark -
#pragma mark Edge
 
    class Edge {
    public:
        Vertex v1;
        Vertex v2;
        
        Edge() {}
        
        Edge(const Vertex& p1, const Vertex& p2);
        
        bool operator==(const Edge& t) const;
        
        bool operator!=(const Edge& t) const { return !(*this == t); }
        
        size_t operator()(const Edge& t) const;
        
        bool hasVertex(const Vec2& v) const;
 
        bool isDegenerate() const;
    };
    
#pragma mark -
#pragma mark Triangle
 
    class Triangle {
    public:
        Vertex v1;
        Vertex v2;
        Vertex v3;
        bool isbad;
        
        Triangle() : isbad(true) {}
        
        Triangle(const Vertex& p1, const Vertex& p2, const Vertex& p3);
        
        bool operator==(const Triangle& t);
        
        bool operator!=(const Triangle& t) { return !(*this == t); }
        
        size_t operator()(const Triangle& t) const;
 
        bool hasVertex(const Vec2& v);
 
        Vec3 getBarycentric(const Vec2& point) const;
 
        Vec2 getCircleCenter() const;
        
        float getCircleRadius() const;
 
        bool containsInCircle(const Vec2& point) const;
        
        void setBad(bool bad);
 
        bool isBad() const;
        
        bool isDegenerate() const;
        
        bool isExterior() const;
    };
    
#pragma mark -
#pragma mark Delaunay
 
    std::vector<Vec2> _input;
    std::vector<Triangle> _output;
    std::vector<Vec2> _dual;
    std::vector<std::vector<Edge>> _voronoi;
    bool _calculated;
    bool _dualated;
 
public:
    DelaunayTriangulator() {}
    
    DelaunayTriangulator(const std::vector<Vec2>& points) : _calculated(false) { _input = points; }
    
    DelaunayTriangulator(const Poly2& poly) :  _calculated(false) { _input = poly._vertices; }
    
    ~DelaunayTriangulator() {}
    
#pragma mark Initialization
 
    void set(const Poly2& poly) {
        reset();
        _input = poly._vertices;
    }
    
    void set(const std::vector<Vec2>& points) {
        reset();
        _input = points;
    }
    
    void reset() {
        _calculated = false; _dualated = false;
        _output.clear(); _voronoi.clear();
    }
    
    void clear() {
        _calculated = false; _dualated = false;
        _input.clear(); _output.clear(); _voronoi.clear();
    }
    
#pragma mark Calculation
 
    void calculate();
    
    void calculateDual();
    
#pragma mark Materialization
 
    std::vector<unsigned short> getTriangulation() const;
    
    size_t getTriangulation(std::vector<unsigned short>& buffer) const;
    
    Poly2 getPolygon() const;
    
    Poly2* getPolygon(Poly2* buffer) const;
 
    
#pragma mark Voronoization
 
    std::vector<Poly2> getVoronoi() const;
 
    Poly2 getVoronoiCell(size_t index) const;
    
    Poly2* getVoronoiCell(size_t index, Poly2* buffer) const;
    
    Poly2 getVoronoiFrame() const;
    
    Poly2* getVoronoiFrame(Poly2* buffer) const;
 
#pragma mark -
#pragma mark Internal Data Generation
 
    Rect getBoundingBox() const;
    
    void computeDelaunay(const Rect& rect);
 
    void computeVoronoi(const Rect& rect);
    
    void sortCell(size_t index, const Rect& rect);
};
  
    
}
 
#endif /* __CU_DELAUNAY_TRIANGULATOR_H__ */