InitializeWithGrid.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_HmXGv083vZCrT3OXASD9
#define CDT_HmXGv083vZCrT3OXASD9
 
#include <CDT.h>
#include <CDTUtils.h>
 
#include <algorithm>
#include <cstddef>
#include <iterator>
#include <vector>
 
namespace CDT
{
namespace detail
{

template <
    typename OutputVertIt,
    typename OutputTriIt,
    typename TXCoordIter,
    typename TYCoordIter>
void generateGridVertices(
    OutputVertIt outVertsFirst,
    OutputTriIt outTrisFirst,
    const TXCoordIter xfirst,
    const TXCoordIter xlast,
    const TYCoordIter yfirst,
    const TYCoordIter ylast)
{
    typedef typename std::iterator_traits<TXCoordIter>::value_type T;
    const std::size_t xres = std::distance(xfirst, xlast) - 1;
    const std::size_t yres = std::distance(yfirst, ylast) - 1;
 
    TXCoordIter yiter = yfirst;
    for(std::size_t iy = 0; yiter != ylast; ++yiter, ++iy)
    {
        TXCoordIter xiter = xfirst;
        for(std::size_t ix = 0; xiter != xlast; ++xiter, ++ix)
        {
            *outVertsFirst++ = V2d<T>(*xiter, *yiter);
            const std::size_t i = iy * xres + ix;
            TriIndVec vTris;
            vTris.reserve(6);
            // left-up
            if(ix > 0 && iy < yres)
            {
                vTris.push_back(static_cast<TriInd>(2 * (i - 1)));
                vTris.push_back(static_cast<TriInd>(2 * (i - 1) + 1));
            }
            // right-up
            if(ix < xres && iy < yres)
            {
                vTris.push_back(static_cast<TriInd>(2 * i));
            }
            // left-down
            if(ix > 0 && iy > 0)
            {
                vTris.push_back(static_cast<TriInd>(2 * (i - xres - 1) + 1));
            }
            // right-down
            if(ix < xres && iy > 0)
            {
                vTris.push_back(static_cast<TriInd>(2 * (i - xres)));
                vTris.push_back(static_cast<TriInd>(2 * (i - xres) + 1));
            }
            // note: only one adjacent triangle per vertex is stored
            *outTrisFirst++ = vTris.front();
        }
    }
}

template <typename OutputIt>
void generateGridTriangles(
    OutputIt outFirst,
    const IndexSizeType xres,
    const IndexSizeType yres)
{
    for(IndexSizeType iy = 0; iy < yres; ++iy)
    {
        for(IndexSizeType ix = 0; ix < xres; ++ix)
        {
            // 2___3           v3
            // |\  |           /\
            // | \ |        n3/  \n2
            // |__\|         /____\
            // 0   1       v1  n1  v2
            const IndexSizeType i = iy * xres + ix;
            const IndexSizeType iv = iy * (xres + 1) + ix;
            const VertInd vv[4] = {
                VertInd(iv),
                VertInd(iv + 1),
                VertInd(iv + xres + 1),
                VertInd(iv + xres + 2)};
            {
                const Triangle t(
                    arr3(vv[0], vv[1], vv[2]),
                    arr3(
                        TriInd(iy ? 2 * i - xres * 2 + 1 : noNeighbor),
                        TriInd(2 * i + 1),
                        TriInd(ix ? 2 * i - 1 : noNeighbor)));
                *outFirst++ = t;
            }
            {
                const Triangle t(
                    arr3(vv[1], vv[3], vv[2]),
                    arr3(
                        TriInd(ix < xres - 1 ? 2 * i + 2 : noNeighbor),
                        TriInd(iy < yres - 1 ? 2 * i + xres * 2 : noNeighbor),
                        TriInd(2 * i)));
                *outFirst++ = t;
            }
        }
    }
}
 
} // namespace detail

template <typename T, typename TNearPointLocator>
void initializeWithRegularGrid(
    const T xmin,
    const T xmax,
    const T ymin,
    const T ymax,
    const std::size_t xres,
    const std::size_t yres,
    Triangulation<T, TNearPointLocator>& out)
{
    std::vector<T> xcoords;
    std::vector<T> ycoords;
    xcoords.reserve(xres + 1);
    ycoords.reserve(yres + 1);
    const T xstep = (xmax - xmin) / xres;
    T x = xmin;
    for(std::size_t ix = 0; ix <= xres; ++ix, x += xstep)
        xcoords.push_back(x);
    const T ystep = (ymax - ymin) / yres;
    T y = ymin;
    for(std::size_t iy = 0; iy <= yres; ++iy, y += ystep)
        ycoords.push_back(y);
 
    return initializeWithIrregularGrid(
        xcoords.begin(), xcoords.end(), ycoords.begin(), ycoords.end(), out);
}

template <
    typename T,
    typename TNearPointLocator,
    typename TXCoordIter,
    typename TYCoordIter>
void initializeWithIrregularGrid(
    const TXCoordIter xfirst,
    const TXCoordIter xlast,
    const TYCoordIter yfirst,
    const TYCoordIter ylast,
    Triangulation<T, TNearPointLocator>& out)
{
    const std::size_t xres = std::distance(xfirst, xlast) - 1;
    const std::size_t yres = std::distance(yfirst, ylast) - 1;
    out.triangles.reserve(xres * yres * 2);
    out.vertices.reserve((xres + 1) * (yres + 1));
    out.VertTrisInternal().reserve((xres + 1) * (yres + 1));
    detail::generateGridVertices(
        std::back_inserter(out.vertices),
        std::back_inserter(out.VertTrisInternal()),
        xfirst,
        xlast,
        yfirst,
        ylast);
    detail::generateGridTriangles(
        std::back_inserter(out.triangles),
        static_cast<IndexSizeType>(xres),
        static_cast<IndexSizeType>(yres));
    out.initializedWithCustomSuperGeometry();
}
 
} // namespace CDT
 
#endif