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
 
// 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 <vector>
 
#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 <tuple>
#include <unordered_map>
#include <unordered_set>
namespace CDT
{
using std::array;
using std::get;
using std::make_tuple;
using std::tie;
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/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;
} // namespace CDT
#endif
 
namespace CDT
{
 
template <typename T>
struct CDT_EXPORT V2d
{
    T x; 
    T y; 
 
    static V2d make(T x, T 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;
}
 
#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 IndexSizeType
    invalidIndex(std::numeric_limits<IndexSizeType>::max());
const static TriInd noNeighbor(invalidIndex);
const static VertInd noVertex(invalidIndex);
 
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; 
 
    void envelopPoint(const V2d<T>& p)
    {
        envelopPoint(p.x, p.y);
    }
    void 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);
    }
};
 
template <
    typename T,
    typename TVertexIter,
    typename TGetVertexCoordX,
    typename TGetVertexCoordY>
Box2d<T> envelopBox(
    TVertexIter first,
    TVertexIter last,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY)
{
    const T max = std::numeric_limits<T>::max();
    Box2d<T> box = {{max, max}, {-max, -max}};
    for(; first != last; ++first)
    {
        box.envelopPoint(getX(*first), getY(*first));
    }
    return box;
}
 
template <typename T>
CDT_EXPORT Box2d<T> envelopBox(const std::vector<V2d<T> >& vertices);
 
struct CDT_EXPORT Edge
{
    Edge(VertInd iV1, VertInd iV2);
    bool operator==(const Edge& other) const;
    bool operator!=(const Edge& other) const;
    VertInd v1() const;
    VertInd v2() const;
    const std::pair<VertInd, VertInd>& verts() const;
 
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 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; 
 
    static Triangle
    make(const array<VertInd, 3>& vertices, const array<TriInd, 3>& neighbors)
    {
        Triangle t = {vertices, neighbors};
        return t;
    }
 
    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_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_INLINE_IF_HEADER_ONLY bool touchesSuperTriangle(const Triangle& t);
 
} // 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)
    {
        const std::pair<CDT::VertInd, CDT::VertInd>& vv = e.verts();
        std::size_t seed1(0);
        hashCombine(seed1, vv.first);
        hashCombine(seed1, vv.second);
        std::size_t seed2(0);
        hashCombine(seed2, vv.second);
        hashCombine(seed2, vv.first);
        return std::min(seed1, seed2);
    }
};
} // namespace std/boost
 
#endif // header guard