CDT.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_lNrmUayWQaIR5fxnsg9B
#define CDT_lNrmUayWQaIR5fxnsg9B
 
#include "CDTUtils.h"
#include "Triangulation.h"
 
#include "remove_at.hpp"
 
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iterator>
#include <memory>
#include <vector>

namespace CDT
{


typedef unsigned short LayerDepth;
typedef LayerDepth BoundaryOverlapCount;

typedef std::vector<TriIndVec> VerticesTriangles;


CDT_EXPORT VerticesTriangles
calculateTrianglesByVertex(const TriangleVec& triangles, VertInd verticesSize);

struct CDT_EXPORT DuplicatesInfo
{
    std::vector<std::size_t> mapping;    
    std::vector<std::size_t> duplicates; 
};

template <
    typename T,
    typename TVertexIter,
    typename TGetVertexCoordX,
    typename TGetVertexCoordY>
DuplicatesInfo FindDuplicates(
    TVertexIter first,
    TVertexIter last,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY);

template <typename TVertex, typename TAllocator>
void RemoveDuplicates(
    std::vector<TVertex, TAllocator>& vertices,
    const std::vector<std::size_t>& duplicates);

template <typename T>
CDT_EXPORT DuplicatesInfo RemoveDuplicates(std::vector<V2d<T> >& vertices);

template <
    typename TEdgeIter,
    typename TGetEdgeVertexStart,
    typename TGetEdgeVertexEnd,
    typename TMakeEdgeFromStartAndEnd>
void RemapEdges(
    TEdgeIter first,
    TEdgeIter last,
    const std::vector<std::size_t>& mapping,
    TGetEdgeVertexStart getStart,
    TGetEdgeVertexEnd getEnd,
    TMakeEdgeFromStartAndEnd makeEdge);

CDT_EXPORT void
RemapEdges(std::vector<Edge>& edges, const std::vector<std::size_t>& mapping);

template <
    typename T,
    typename TVertex,
    typename TGetVertexCoordX,
    typename TGetVertexCoordY,
    typename TVertexAllocator,
    typename TEdgeIter,
    typename TGetEdgeVertexStart,
    typename TGetEdgeVertexEnd,
    typename TMakeEdgeFromStartAndEnd>
DuplicatesInfo RemoveDuplicatesAndRemapEdges(
    std::vector<TVertex, TVertexAllocator>& vertices,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY,
    TEdgeIter edgesFirst,
    TEdgeIter edgesLast,
    TGetEdgeVertexStart getStart,
    TGetEdgeVertexEnd getEnd,
    TMakeEdgeFromStartAndEnd makeEdge);

template <typename T>
CDT_EXPORT DuplicatesInfo RemoveDuplicatesAndRemapEdges(
    std::vector<V2d<T> >& vertices,
    std::vector<Edge>& edges);

CDT_EXPORT EdgeUSet extractEdgesFromTriangles(const TriangleVec& triangles);

CDT_EXPORT unordered_map<Edge, EdgeVec>
EdgeToPiecesMapping(const unordered_map<Edge, EdgeVec>& pieceToOriginals);

template <typename T>
unordered_map<Edge, std::vector<VertInd> > EdgeToSplitVertices(
    const unordered_map<Edge, EdgeVec>& edgeToPieces,
    const std::vector<V2d<T> >& vertices);


 
} // namespace CDT
 
//*****************************************************************************
// Implementations of template functionlity
//*****************************************************************************
// hash for CDT::V2d<T>
#ifdef CDT_CXX11_IS_SUPPORTED
namespace std
#else
namespace boost
#endif
{
template <typename T>
struct hash<CDT::V2d<T> >
{
    size_t operator()(const CDT::V2d<T>& xy) const
    {
#ifdef CDT_CXX11_IS_SUPPORTED
        typedef std::hash<T> Hasher;
#else
        typedef boost::hash<T> Hasher;
#endif
        return Hasher()(xy.x) ^ Hasher()(xy.y);
    }
};
} // namespace std
 
namespace CDT
{
 
//-----
// API
//-----
template <
    typename T,
    typename TVertexIter,
    typename TGetVertexCoordX,
    typename TGetVertexCoordY>
DuplicatesInfo FindDuplicates(
    TVertexIter first,
    TVertexIter last,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY)
{
    typedef unordered_map<V2d<T>, std::size_t> PosToIndex;
    PosToIndex uniqueVerts;
    const std::size_t verticesSize = std::distance(first, last);
    DuplicatesInfo di = {
        std::vector<std::size_t>(verticesSize), std::vector<std::size_t>()};
    for(std::size_t iIn = 0, iOut = iIn; iIn < verticesSize; ++iIn, ++first)
    {
        typename PosToIndex::const_iterator it;
        bool isUnique;
        tie(it, isUnique) = uniqueVerts.insert(
            std::make_pair(V2d<T>(getX(*first), getY(*first)), iOut));
        if(isUnique)
        {
            di.mapping[iIn] = iOut++;
            continue;
        }
        di.mapping[iIn] = it->second; // found a duplicate
        di.duplicates.push_back(iIn);
    }
    return di;
}
 
template <typename TVertex, typename TAllocator>
void RemoveDuplicates(
    std::vector<TVertex, TAllocator>& vertices,
    const std::vector<std::size_t>& duplicates)
{
    vertices.erase(
        remove_at(
            vertices.begin(),
            vertices.end(),
            duplicates.begin(),
            duplicates.end()),
        vertices.end());
}
 
template <
    typename TEdgeIter,
    typename TGetEdgeVertexStart,
    typename TGetEdgeVertexEnd,
    typename TMakeEdgeFromStartAndEnd>
void RemapEdges(
    TEdgeIter first,
    const TEdgeIter last,
    const std::vector<std::size_t>& mapping,
    TGetEdgeVertexStart getStart,
    TGetEdgeVertexEnd getEnd,
    TMakeEdgeFromStartAndEnd makeEdge)
{
    for(; first != last; ++first)
    {
        *first = makeEdge(
            static_cast<VertInd>(mapping[getStart(*first)]),
            static_cast<VertInd>(mapping[getEnd(*first)]));
    }
}
 
template <
    typename T,
    typename TVertex,
    typename TGetVertexCoordX,
    typename TGetVertexCoordY,
    typename TVertexAllocator,
    typename TEdgeIter,
    typename TGetEdgeVertexStart,
    typename TGetEdgeVertexEnd,
    typename TMakeEdgeFromStartAndEnd>
DuplicatesInfo RemoveDuplicatesAndRemapEdges(
    std::vector<TVertex, TVertexAllocator>& vertices,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY,
    const TEdgeIter edgesFirst,
    const TEdgeIter edgesLast,
    TGetEdgeVertexStart getStart,
    TGetEdgeVertexEnd getEnd,
    TMakeEdgeFromStartAndEnd makeEdge)
{
    const DuplicatesInfo di =
        FindDuplicates<T>(vertices.begin(), vertices.end(), getX, getY);
    RemoveDuplicates(vertices, di.duplicates);
    RemapEdges(edgesFirst, edgesLast, di.mapping, getStart, getEnd, makeEdge);
    return di;
}
 
template <typename T>
unordered_map<Edge, std::vector<VertInd> > EdgeToSplitVertices(
    const unordered_map<Edge, EdgeVec>& edgeToPieces,
    const std::vector<V2d<T> >& vertices)
{
    typedef std::pair<VertInd, T> VertCoordPair;
    struct ComparePred
    {
        bool operator()(const VertCoordPair& a, const VertCoordPair& b) const
        {
            return a.second < b.second;
        }
    } comparePred;
 
    unordered_map<Edge, std::vector<VertInd> > edgeToSplitVerts;
    typedef unordered_map<Edge, EdgeVec>::const_iterator It;
    for(It e2pIt = edgeToPieces.begin(); e2pIt != edgeToPieces.end(); ++e2pIt)
    {
        const Edge& e = e2pIt->first;
        const T dX = vertices[e.v2()].x - vertices[e.v1()].x;
        const T dY = vertices[e.v2()].y - vertices[e.v1()].y;
        const bool isX = std::abs(dX) >= std::abs(dY); // X-coord longer
        const bool isAscending =
            isX ? dX >= 0 : dY >= 0; // Longer coordinate ascends
        const EdgeVec& pieces = e2pIt->second;
        std::vector<VertCoordPair> splitVerts;
        // size is:  2[ends] + (pieces - 1)[split vertices] = pieces + 1
        splitVerts.reserve(pieces.size() + 1);
        typedef EdgeVec::const_iterator EIt;
        for(EIt pieceIt = pieces.begin(); pieceIt != pieces.end(); ++pieceIt)
        {
            const array<VertInd, 2> vv = {pieceIt->v1(), pieceIt->v2()};
            typedef array<VertInd, 2>::const_iterator VIt;
            for(VIt v = vv.begin(); v != vv.end(); ++v)
            {
                const T c = isX ? vertices[*v].x : vertices[*v].y;
                splitVerts.push_back(std::make_pair(*v, isAscending ? c : -c));
            }
        }
        // sort by longest coordinate
        std::sort(splitVerts.begin(), splitVerts.end(), comparePred);
        // remove duplicates
        splitVerts.erase(
            std::unique(splitVerts.begin(), splitVerts.end()),
            splitVerts.end());
        assert(splitVerts.size() > 2); // 2 end points with split vertices
        std::pair<Edge, std::vector<VertInd> > val =
            std::make_pair(e, std::vector<VertInd>());
        val.second.reserve(splitVerts.size());
        typedef typename std::vector<VertCoordPair>::const_iterator SEIt;
        for(SEIt it = splitVerts.begin() + 1; it != splitVerts.end() - 1; ++it)
        {
            val.second.push_back(it->first);
        }
        edgeToSplitVerts.insert(val);
    }
    return edgeToSplitVerts;
}
 
} // namespace CDT
 
#ifndef CDT_USE_AS_COMPILED_LIBRARY
#include "CDT.hpp"
#endif
 
#endif // header-guard