Fast way to find the triangle inside a mesh that encloses a point

Question

I'm running into a performance problem for a task I need to accomplish. One of the bottlenecks at the moment is in getting an interpolated field value from an unstructured grid.

The slow part is, given a 2D point and an unstructured 2D grid, find the mesh points which immediately surround the point. It would be nice to just find the triangle it falls into.

Right now I'm using CGAL, but it's way too slow. With the current implementation, the whole task will take days to complete, running in parallel on a high end CPU.

I believe that the slow part is CGAL::natural_neighbor_coordinates_2.

#ifndef FIELD_INTERPOLATOR_H
#define FIELD_INTERPOLATOR_H

#include "Vec.h"

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Interpolation_traits_2.h>
#include <CGAL/natural_neighbor_coordinates_2.h>
#include <CGAL/interpolation_functions.h>

#include <map>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Delaunay_triangulation_2< Kernel > Delaunay_triangulation;

typedef Kernel::FT FieldType;
typedef Kernel::Point_2 MeshType;

struct FieldInterpolator23 {

    Delaunay_triangulation m_triangulation;

    std::map< MeshType, FieldType, Kernel::Less_xy_2 > m_vX;
    std::map< MeshType, FieldType, Kernel::Less_xy_2 > m_vY;
    std::map< MeshType, FieldType, Kernel::Less_xy_2 > m_vZ;

    typedef CGAL::Data_access< std::map< MeshType, FieldType, Kernel::Less_xy_2 > > ValueAccess;

    FieldInterpolator23() {}

    FieldInterpolator23( const std::vector< TN::Vec2 > & mesh, const std::vector< TN::Vec3 > & field )
    {
        const int N = mesh.size();
        for ( int i = 0; i < N; ++i ) {

            MeshType p( mesh[i].x(), mesh[i].y() );

            m_triangulation.insert( p );
            m_vX.insert( std::make_pair( p, field[i].x() ) );
            m_vY.insert( std::make_pair( p, field[i].y() ) ); 
            m_vZ.insert( std::make_pair( p, field[i].z() ) );                        
        }       
    }

    void set( const std::vector< TN::Vec2 > & mesh, const std::vector< TN::Vec3 > & field ) {

        m_triangulation.clear();
        m_vX.clear();
        m_vY.clear();
        m_vZ.clear();

        const int N = mesh.size();
        for ( int i = 0; i < N; ++i ) {

            MeshType p( mesh[i].x(), mesh[i].y() );

            m_triangulation.insert( p );
            m_vX.insert( std::make_pair( p, field[i].x() ) );
            m_vY.insert( std::make_pair( p, field[i].y() ) );
            m_vZ.insert( std::make_pair( p, field[i].z() ) );
        }
    }

    TN::Vec3 operator() ( TN::Vec2 p ) {

        MeshType pos( p.x(), p.y() );

        std::vector< std::pair< MeshType, FieldType > > coords;

        FieldType norm =
            CGAL::natural_neighbor_coordinates_2( m_triangulation, pos, std::back_inserter( coords ) ).second;

        FieldType resX =
            CGAL::linear_interpolation(
                coords.begin(), 
                coords.end(),
                norm,
                ValueAccess( m_vX )
        );

        FieldType resY =
            CGAL::linear_interpolation(
                coords.begin(), 
                coords.end(),
                norm,
                ValueAccess( m_vY )
        );

        FieldType resZ =
            CGAL::linear_interpolation(
                coords.begin(), 
                coords.end(),
                norm,
                ValueAccess( m_vZ )
        );

        return TN::Vec3( resX, resY, resZ );
    }
};

#endif

Can anyone point me in the direction of an acceptable higher performance solution, either a different library or an algorithm?

Answer 1

CGAL contains an implementation of a Triangulation Hierarchy which

implements a triangulation augmented with a data structure to efficiently answer point location queries. [...] the data structure remains small and achieves fast point location queries on real data.

Its performance is optimal for Delaunay triangulations.

---

         
          ^{Fig. 36.8}

---