initializeWithCustomGrid

Ciao, In my application, the coordinate grid for tessellation initialisation can have inconsistently spaced points for rows and columns. To give an idea, opposite sides of the grid could have the same number of intervals, but different values. As a result, each node would be the intersection of the i-th row and j-th column of the intervals, as the yellow point in the image.

To generalise this behaviour, I wrote two functions that could be integrated into the library. The actual input is the vector of points defining the grid, plus you need to know the number of columns (xres). The vector is the linearization of the grid, so its interval [0,... xres*yres] expands to the grid: 0	…	xres
xres+1	…	xres*2
…	…	…
xres*(yres-1)	…	xres*yres

The implementation is the following (surely you can do way better than me):

namespace CDT::detail {
/**
 * Generate grid vertices given of a vector of points defining the grid nodes coordinates
 *
 * @tparam OutputVertIt output vertices iterator
 * @tparam OutputTriIt output triangles iterator
 * @tparam TCoordIter iterator dereferencing to [X,Y] coordinate
 * @param outFirst the beginning of the destination range
 * @param first beginning of [X,Y] coordinates range
 * @param last end [X,Y] coordinates range
 * @param xres the x resolution (number of grid columns)
 */

template <
  typename T,
  typename OutputVertIt,
  typename OutputTriIt,
  typename TCoordIter>
void generateCustomGridVertices(
  OutputVertIt outVertsFirst,
  OutputTriIt outTrisFirst,
  const TCoordIter first,
  const TCoordIter last,
  const std::size_t xres
)
{
  const std::size_t res = std::distance( first, last );
  const std::size_t yres = res / (xres + 1) - 1;

  TCoordIter iter = first;
  for( std::size_t i = 0; iter != last; ++iter, ++i ) {
    *outVertsFirst++ = V2d<T>::make( (*iter)[0], (*iter)[1] );
    size_t ix = i % yres;
    size_t iy = i % xres;
    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) );
    }
#ifdef CDT_CXX11_IS_SUPPORTED
    * outTrisFirst++ = std::move( vTris.front( ) );
#else
    * outTrisFirst++ = vTris;
#endif
  }
}

/**
 * Make a triangulation that uses a custom grid triangles instead of
 * super-triangle. Irregular grid is given by the nodes coordinates.
 *
 * @tparam T type of vertex coordinates (e.g., float, double)
 * @tparam TNearPointLocator class providing locating near point for efficiently
 * inserting new points.
 * @tparam TCoordIter iterator dereferencing to [X,Y] coordinate
 * @param first beginning of [X,Y] coordinates range
 * @param last end [X,Y] coordinates range
 * @param xres the x resolution (number of grid columns)
 * @param out triangulation to initialize with grid super-geometry
 */
template <
  typename T,
  typename TNearPointLocator,
  typename TCoordIter>
  void initializeWithCustomGrid(
    const TCoordIter first,
    const TCoordIter last,
    const std::size_t xres,
    Triangulation<T, TNearPointLocator>& out )
{
  const std::size_t res = std::distance( first, last );
  const std::size_t yres = res / (xres + 1) - 1;
  out.triangles.reserve( xres * yres * 2 );
  out.vertices.reserve( (xres + 1) * (yres + 1) );
  out.VertTrisInternal( ).reserve( (xres + 1) * (yres + 1) );
  detail::generateCustomGridVertices<T>(
    std::back_inserter( out.vertices ),
    std::back_inserter( out.VertTrisInternal( ) ),
    first,
    last,
    xres);
  detail::generateGridTriangles(
    std::back_inserter( out.triangles ),
    static_cast<IndexSizeType>(xres),
    static_cast<IndexSizeType>(yres) );
  out.initializedWithCustomSuperGeometry( );
}
}

artem-ogre / CDT

initializeWithCustomGrid #164