CUSimpleTriangulator.h

//
//  CUSimpleTriangulator.h
//  Cornell University Game Library (CUGL)
//
//  This module is a factory for a very lightweight triangulator.  While we
//  do have access to the very powerful Pol2Tri, that API has a lot of overhead
//  with it.  If you polygon is simple (no holes or self-intersections), this
//  is good enough for you.
//
//  Because math objects are intended to be on the stack, we do not provide
//  any shared pointer support in this class.
//
//  This implementation is largely inspired by the LibGDX implementation from
//  Nicolas Gramlich, Eric Spits, Thomas Cate, and Nathan Sweet.
//
//  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: 6/22/16
 
#ifndef __CU_SIMPLE_TRIANGULATOR_H__
#define __CU_SIMPLE_TRIANGULATOR_H__
 
#include <cugl/math/CUPoly2.h>
#include <cugl/math/CUVec2.h>
#include <vector>
 
namespace cugl {
    
class SimpleTriangulator {
#pragma mark Values
private:
    enum VertexType {
        CONCAVE    = -1,
        TANGENTIAL = 0,
        CONVEX     = 1
    };
 
    std::vector<Vec2> _input;
    std::vector<VertexType> _types;
    std::vector<unsigned short> _naive;
    std::vector<unsigned short> _output;
    bool _calculated;
 
    
#pragma mark -
#pragma mark Constructors
public:
    SimpleTriangulator() {}
 
    SimpleTriangulator(const std::vector<Vec2>& points) : _calculated(false) { _input = points; }
 
    SimpleTriangulator(const Poly2& poly) :  _calculated(false) { _input = poly._vertices; }
 
    ~SimpleTriangulator() {}
 
#pragma mark -
#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;
        _output.clear(); _naive.clear(); _types.clear();
    }
    
    void clear() {
        _calculated = false;
        _input.clear(); _output.clear(); _naive.clear(); _types.clear();
    }
    
#pragma mark -
#pragma mark Calculation
 
    void calculate();
    
#pragma mark -
#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 -
#pragma mark Internal Data Generation
private:
    VertexType computeSpannedAreaType(const Vec2& p1, const Vec2& p2, const Vec2& p3);
    
    bool areVerticesClockwise (const std::vector<Vec2>& vertices);
    
    void cutEarTip(int earTipIndex);
    
    bool isEarTip (int earTipIndex);
    
    int findEarTip();
    
    VertexType classifyVertex (int index);
    
    void computeTriangulation();
    
    void trimColinear();
    
};
 
}
 
#endif /* __CU_SIMPLE_TRIANGULATOR_H__ */