CDTUtils.h

Go to the documentation of this file.

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

 
#ifndef CDT_obwOaxOTdAWcLNTlNnaq
#define CDT_obwOaxOTdAWcLNTlNnaq
 
#ifdef CDT_DONT_USE_BOOST_RTREE
// CDT_DONT_USE_BOOST_RTREE was replaced with CDT_USE_BOOST
typedef char CDT_DONT_USE_BOOST_RTREE__was__replaced__with__CDT_USE_BOOST[-1];
#endif
 
// #define CDT_USE_STRONG_TYPING // strong type checks on indices
 
// check if c++11 is supported
#if __cplusplus >= 201103L || (defined(_MSC_VER) && _MSC_VER >= 1900)
#define CDT_CXX11_IS_SUPPORTED
#elif !defined(__cplusplus) && !defined(_MSC_VER)
typedef char couldnt_parse_cxx_standard[-1]; 
#endif
 
// 'noexcept' is only available since c++11 and its c++98 spelling 'throw()'
// is in turn removed in c++20
#ifdef CDT_CXX11_IS_SUPPORTED
#define CDT_NOEXCEPT noexcept
#else
#define CDT_NOEXCEPT throw()
#endif
 
// Functions defined outside the class need to be 'inline'
// if CDT is configured to be used as header-only library:
// single-definition rule is violated otherwise
#ifdef CDT_USE_AS_COMPILED_LIBRARY
#define CDT_INLINE_IF_HEADER_ONLY
#include "cdt_export.h" // automatically generated by CMake
#else
#define CDT_INLINE_IF_HEADER_ONLY inline
#define CDT_EXPORT
#endif
 
#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <queue>
#include <vector>
 
#ifdef M_PI
#define CDT_M_PI M_PI
#else
#define CDT_M_PI 3.14159265358979323846
#endif
 
#ifdef CDT_USE_STRONG_TYPING
#include <boost/serialization/strong_typedef.hpp>
#endif
 
// use fall-backs for c++11 features
#ifdef CDT_CXX11_IS_SUPPORTED
 
#include <array>
#include <functional>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
 
#ifdef CDT_DISABLE_EXCEPTIONS
#include <exception>
#endif
 
namespace CDT
{
using std::array;
using std::get;
using std::make_tuple;
using std::tie;
using std::to_string;
using std::tuple;
using std::unordered_map;
using std::unordered_set;
} // namespace CDT
 
#else
#include <boost/array.hpp>
#include <boost/functional/hash.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
namespace CDT
{
using boost::array;
using boost::get;
using boost::make_tuple;
using boost::tie;
using boost::tuple;
using boost::unordered_map;
using boost::unordered_set;
 
template <typename T>
std::string to_string(const T& value)
{
    return boost::lexical_cast<std::string>(value);
}
} // namespace CDT
#endif

#ifdef _MSC_VER
#define CDT_ENSURE_PRECISE_MATH \
    __pragma(float_control(push)) \
    __pragma(float_control(precise, on)) \
    __pragma(fp_contract(off))
#elif defined(__clang__)
#define CDT_ENSURE_PRECISE_MATH \
    _Pragma("float_control(push)") \
    _Pragma("float_control(precise, on)") \
    _Pragma("clang fp contract(off)")
#elif defined(__GNUC__)
#define CDT_ENSURE_PRECISE_MATH \
    _Pragma("GCC push_options") \
    _Pragma("GCC optimize(\"no-fast-math\")") \
    _Pragma("GCC optimize(\"fp-contract=off\")")
#else
#define CDT_ENSURE_PRECISE_MATH _Pragma("STDC FP_CONTRACT OFF")
#endif

#if defined(_MSC_VER)
#define CDT_RESTORE_MATH_SETTINGS __pragma(float_control(pop))
#elif defined(__clang__)
#define CDT_RESTORE_MATH_SETTINGS _Pragma("float_control(pop)")
#elif defined(__GNUC__)
#define CDT_RESTORE_MATH_SETTINGS _Pragma("GCC pop_options")
#else
#define CDT_RESTORE_MATH_SETTINGS _Pragma("STDC FP_CONTRACT DEFAULT")
#endif

#ifdef CDT_ENSURE_PRECISE_MATH_IN_CONSTRUCTIONS
#define CDT_ENSURE_PRECISE_MATH_FOR_CONSTRUCTIONS CDT_ENSURE_PRECISE_MATH
#define CDT_RESTORE_MATH_SETTINGS_FOR_CONSTRUCTIONS CDT_RESTORE_MATH_SETTINGS
#else
#define CDT_ENSURE_PRECISE_MATH_FOR_CONSTRUCTIONS
#define CDT_RESTORE_MATH_SETTINGS_FOR_CONSTRUCTIONS
#endif
 
namespace CDT
{
 
template <typename T>
void handleException(const T& error)
{
#ifdef CDT_DISABLE_EXCEPTIONS
    std::terminate();
#else
    throw error;
#endif
}

template <typename T>
array<T, 3> arr3(const T& v0, const T& v1, const T& v2)
{
    const array<T, 3> out = {v0, v1, v2};
    return out;
}

template <typename T>
array<T, 3> arr3(const T& v)
{
    const array<T, 3> out = {v, v, v};
    return out;
}

template <typename T>
struct CDT_EXPORT V2d
{
    T x; 
    T y; 

    V2d()
        : x(T(0))
        , y(T(0))
    {}

    V2d(const T x, const T y)
        : x(x)
        , y(y)
    {}
};

template <typename T>
const T& getX_V2d(const V2d<T>& v)
{
    return v.x;
}

template <typename T>
const T& getY_V2d(const V2d<T>& v)
{
    return v.y;
}

template <typename T>
bool operator==(const CDT::V2d<T>& lhs, const CDT::V2d<T>& rhs)
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

template <typename T>
bool operator!=(const CDT::V2d<T>& lhs, const CDT::V2d<T>& rhs)
{
    return !(lhs == rhs);
}
 
#ifdef CDT_USE_64_BIT_INDEX_TYPE
typedef unsigned long long IndexSizeType;
#else
typedef unsigned int IndexSizeType;
#endif
 
#ifdef CDT_USE_STRONG_TYPING
BOOST_STRONG_TYPEDEF(unsigned char, Index);
BOOST_STRONG_TYPEDEF(IndexSizeType, VertInd);
BOOST_STRONG_TYPEDEF(IndexSizeType, TriInd);
#else
typedef unsigned char Index;
typedef IndexSizeType VertInd;
typedef IndexSizeType TriInd;
#endif

const static Index invalidIndex(std::numeric_limits<Index>::max());
const static IndexSizeType
    invalidIndexSizeType(std::numeric_limits<IndexSizeType>::max());
const static IndexSizeType nSuperTriVerts(3);
const static TriInd noNeighbor(invalidIndexSizeType);
const static VertInd noVertex(invalidIndexSizeType);
 
typedef std::vector<TriInd> TriIndVec;  
typedef array<VertInd, 3> VerticesArr3; 
typedef array<TriInd, 3> NeighborsArr3; 

template <typename T>
struct CDT_EXPORT Box2d
{
    V2d<T> min; 
    V2d<T> max; 

    Box2d()
        : min(std::numeric_limits<T>::max(), std::numeric_limits<T>::max())
        , max(-std::numeric_limits<T>::max(), -std::numeric_limits<T>::max())
    {}

    Box2d<T>& envelopPoint(const V2d<T>& p)
    {
        return envelopPoint(p.x, p.y);
    }

    Box2d<T>& envelopPoint(const T x, const T y)
    {
        min.x = std::min(x, min.x);
        max.x = std::max(x, max.x);
        min.y = std::min(y, min.y);
        max.y = std::max(y, max.y);
        return *this;
    }

    template <
        typename TVertexIter,
        typename TGetVertexCoordX,
        typename TGetVertexCoordY>
    Box2d<T>& envelopPoints(
        TVertexIter first,
        TVertexIter last,
        TGetVertexCoordX getX,
        TGetVertexCoordY getY)
    {
        for(; first != last; ++first)
        {
            envelopPoint(getX(*first), getY(*first));
        }
        return *this;
    }

    Box2d<T>& envelopPoints(const std::vector<V2d<T> >& vertices)
    {
        return envelopPoints(
            vertices.begin(), vertices.end(), getX_V2d<T>, getY_V2d<T>);
    }
};

struct CDT_EXPORT Edge
{
    Edge(const VertInd iV1, const VertInd iV2)
        : m_vertices(
              iV1 < iV2 ? std::make_pair(iV1, iV2) : std::make_pair(iV2, iV1))
    {}

    bool operator==(const Edge& other) const
    {
        return m_vertices == other.m_vertices;
    }

    bool operator!=(const Edge& other) const
    {
        return !(this->operator==(other));
    }

    bool operator<(const Edge& other) const
    {
        return m_vertices < other.m_vertices;
    }

    VertInd v1() const
    {
        return m_vertices.first;
    }

    VertInd v2() const
    {
        return m_vertices.second;
    }

    const std::pair<VertInd, VertInd>& verts() const
    {
        return m_vertices;
    }
 
private:
    std::pair<VertInd, VertInd> m_vertices;
};

inline VertInd edge_get_v1(const Edge& e)
{
    return e.v1();
}

inline VertInd edge_get_v2(const Edge& e)
{
    return e.v2();
}

inline Edge edge_make(VertInd iV1, VertInd iV2)
{
    return Edge(iV1, iV2);
}
 
typedef std::vector<Edge> EdgeVec;                
typedef std::queue<Edge> EdgeQueue;               
typedef std::queue<TriInd> TriIndQueue;           
typedef unordered_set<Edge> EdgeUSet;             
typedef unordered_set<TriInd> TriIndUSet;         
typedef unordered_map<TriInd, TriInd> TriIndUMap; 

/*
 *      v3
 *      /\
 *   n3/  \n2
 *    /____\
 *  v1  n1  v2
 */
struct CDT_EXPORT Triangle
{
    VerticesArr3 vertices;   
    NeighborsArr3 neighbors; 

    Triangle()
        : vertices(arr3(noVertex))
        , neighbors(arr3(noNeighbor))
    {}

    Triangle(const VerticesArr3& vertices, const NeighborsArr3& neighbors)
        : vertices(vertices)
        , neighbors(neighbors)
    {}

    std::pair<TriInd, VertInd> next(const VertInd i) const
    {
        assert(vertices[0] == i || vertices[1] == i || vertices[2] == i);
        if(vertices[0] == i)
        {
            return std::make_pair(neighbors[0], vertices[1]);
        }
        if(vertices[1] == i)
        {
            return std::make_pair(neighbors[1], vertices[2]);
        }
        return std::make_pair(neighbors[2], vertices[0]);
    }

    std::pair<TriInd, VertInd> prev(const VertInd i) const
    {
        assert(vertices[0] == i || vertices[1] == i || vertices[2] == i);
        if(vertices[0] == i)
            return std::make_pair(neighbors[2], vertices[2]);
        if(vertices[1] == i)
            return std::make_pair(neighbors[0], vertices[0]);
        return std::make_pair(neighbors[1], vertices[1]);
    }

    bool containsVertex(const VertInd i) const
    {
        return std::find(vertices.begin(), vertices.end(), i) != vertices.end();
    }
};
 
typedef std::vector<Triangle> TriangleVec; 

CDT_EXPORT Index ccw(Index i);

CDT_EXPORT Index cw(Index i);

struct CDT_EXPORT PtTriLocation
{
    enum Enum
    {
        Inside,
        Outside,
        OnEdge1,
        OnEdge2,
        OnEdge3,
        OnVertex,
    };
};

CDT_EXPORT bool isOnEdge(PtTriLocation::Enum location);

CDT_EXPORT Index edgeNeighbor(PtTriLocation::Enum location);

struct CDT_EXPORT PtLineLocation
{
    enum Enum
    {
        Left,
        Right,
        OnLine,
    };
};

template <typename T>
CDT_EXPORT T orient2D(const V2d<T>& p, const V2d<T>& v1, const V2d<T>& v2);

template <typename T>
CDT_EXPORT PtLineLocation::Enum locatePointLine(
    const V2d<T>& p,
    const V2d<T>& v1,
    const V2d<T>& v2,
    T orientationTolerance = T(0));

template <typename T>
CDT_EXPORT PtLineLocation::Enum
classifyOrientation(T orientation, T orientationTolerance = T(0));

template <typename T>
CDT_EXPORT PtTriLocation::Enum locatePointTriangle(
    const V2d<T>& p,
    const V2d<T>& v1,
    const V2d<T>& v2,
    const V2d<T>& v3);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoNbr(Index vertIndex);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoVrt(Index neighborIndex);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
opposedTriangleInd(const VerticesArr3& vv, VertInd iVert);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
edgeNeighborInd(const VerticesArr3& vv, VertInd iVedge1, VertInd iVedge2);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
opposedVertexInd(const NeighborsArr3& nn, TriInd iTopo);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
vertexInd(const VerticesArr3& vv, VertInd iV);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd
opposedTriangle(const Triangle& tri, VertInd iVert);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd
edgeNeighbor(const Triangle& tri, VertInd iVedge1, VertInd iVedge2);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY VertInd
opposedVertex(const Triangle& tri, TriInd iTopo);

template <typename T>
CDT_EXPORT bool isInCircumcircle(
    const V2d<T>& p,
    const V2d<T>& v1,
    const V2d<T>& v2,
    const V2d<T>& v3);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY bool
verticesShareEdge(const TriIndVec& aTris, const TriIndVec& bTris);

template <typename T>
CDT_EXPORT T distance(const V2d<T>& a, const V2d<T>& b);

template <typename T>
CDT_EXPORT T distanceSquared(const V2d<T>& a, const V2d<T>& b);

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY bool
touchesSuperTriangle(const Triangle& t);
 
namespace detail
{

template <typename T>
bool isEncroachingOnEdge(
    const V2d<T>& v,
    const V2d<T>& edgeStart,
    const V2d<T>& edgeEnd);

template <typename T>
T doubledArea(const V2d<T>& a, const V2d<T>& b, const V2d<T>& c);

template <typename T>
T sineOfSmallestAngle(const V2d<T>& a, const V2d<T>& b, const V2d<T>& c);
 
} // namespace detail

template <typename T>
CDT_EXPORT T area(const V2d<T>& a, const V2d<T>& b, const V2d<T>& c);

template <typename T>
CDT_EXPORT V2d<T> circumcenter(V2d<T> a, V2d<T> b, V2d<T> c);

template <typename T>
CDT_EXPORT T smallestAngle(const V2d<T>& a, const V2d<T>& b, const V2d<T>& c);

template <typename T>
CDT_EXPORT T degToRad(T degrees);
 
} // namespace CDT
 
#ifndef CDT_USE_AS_COMPILED_LIBRARY
#include "CDTUtils.hpp"
#endif
 
//*****************************************************************************
// Specialize hash functions
//*****************************************************************************
#ifdef CDT_CXX11_IS_SUPPORTED
namespace std
#else
namespace boost
#endif
{
 
#ifdef CDT_USE_STRONG_TYPING

template <>
struct hash<CDT::VertInd>
{
    std::size_t operator()(const CDT::VertInd& vi) const
    {
        return std::hash<std::size_t>()(vi.t);
    }
};

template <>
struct hash<CDT::TriInd>
{
    std::size_t operator()(const CDT::TriInd& vi) const
    {
        return std::hash<std::size_t>()(vi.t);
    }
};
 
#endif // CDT_USE_STRONG_TYPING

template <>
struct hash<CDT::Edge>
{
    std::size_t operator()(const CDT::Edge& e) const
    {
        return hashEdge(e);
    }
 
private:
    static void hashCombine(std::size_t& seed, const CDT::VertInd& key)
    {
#ifdef CDT_CXX11_IS_SUPPORTED
        typedef std::hash<CDT::VertInd> Hasher;
#else
        typedef boost::hash<CDT::VertInd> Hasher;
#endif
        seed ^= Hasher()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
 
    static std::size_t hashEdge(const CDT::Edge& e)
    {
        std::size_t seed(0);
        hashCombine(seed, e.v1());
        hashCombine(seed, e.v2());
        return seed;
    }
};
 
} // namespace std/boost
 
#endif // header guard