CGAL Delauny Triangulation 的优化，因为 C++ 非常慢

Question

我正在尝试用大约 400.000 点的数据集制作一个 delauny 三角形，我设法做到了，它给了我大约 19 秒的时间，但后来我想用 1000 万点制作一个三角测量，19 秒是这么少的点太长了，我的问题是你推荐我组装德劳尼三角形效率更高吗？

我读到，分段进行三角测量要短得多，但我不知道如何连接生成的网格。

关于如何优化或更有效地组装 delauny 三角剖分有什么建议吗？

// Compares the result of several interpolation methods

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/Random.h>
#include <CGAL/squared_distance_2.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 <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
#include <CGAL/Origin.h>

#include <cassert>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::FT                                         Coord_type;
typedef K::Vector_2                                   Vector;
typedef K::Point_2                                    Point;

typedef CGAL::Delaunay_triangulation_2<K>             Delaunay_triangulation;
typedef CGAL::Interpolation_traits_2<K>               Traits;

typedef std::vector< std::pair<Point, Coord_type> >   Coordinate_vector;
typedef std::map<Point, Coord_type, K::Less_xy_2>     Point_value_map;
typedef std::map<Point, Vector, K::Less_xy_2 >       Point_vector_map;


void readExcelCSV(std::vector<Point>& points, std::vector<Point>& pointsInterpolation, Point_value_map& values, Delaunay_triangulation& T) {
    std::ifstream file("datos.csv");
    std::ifstream filePoints("datosforInterpolation.csv");

    if (!file || !filePoints) {
        std::cerr << "Error in Open File." << std::endl;
        return;
    }


    std::string line;

    int cont = 0;
    while (std::getline(file, line)) {
        std::stringstream ss(line);
        std::string value;
        std::vector<double> row;
        
        for (int idx = 0; idx < 3; idx++)
        {
            std::getline(ss, value, ',');
            row.push_back(std::stod(value));
        }
       
        points.push_back(Point(row[0], row[1]));
        T.insert(points[cont]);
        Coord_type value2 = row[2];
        values.insert(std::make_pair(points[cont], value2));
        cont++;
    }
    cont = 0;
    while (std::getline(filePoints, line)) {
        std::stringstream ss(line);
        std::string value;
        std::vector<double> row;

        for (int idx = 0; idx < 3; idx++)
        {
            std::getline(ss, value, ',');
            row.push_back(std::stod(value));
        }

        pointsInterpolation.push_back(Point(row[0], row[1]));
        cont++;
    }

    filePoints.close();
    file.close();
    
};

int main()
{
    std::vector<Point> points;
    std::vector<Point> pointsInterpolation;
    Delaunay_triangulation T;

    Point_value_map values;
    Point_vector_map gradients;
    
    std::cout << "Go to read File csv..." << std::endl;
    readExcelCSV(points, pointsInterpolation,values, T);
    std::cout << "Read Excel and build delauny triangulation" << std::endl;
    
    //variables for statistics:
    std::pair<Coord_type, bool> res;
    Coord_type  l_total = Coord_type(0),
       l_value(l_total);
   

    //interpolation + error statistics
    for (int i = 0; i < pointsInterpolation.size(); i++) {
        std::cout << "point " << i << std::endl;
        Coord_type x(pointsInterpolation[i].x());
        Coord_type y(pointsInterpolation[i].y());

        
        std::cout << pointsInterpolation[i].x() << " " << pointsInterpolation[i].y()<< std::endl;
        //Coordinate_vector:
        std::vector< std::pair< Point, Coord_type > > coords;
        Coord_type norm =
            CGAL::natural_neighbor_coordinates_2(T, pointsInterpolation[i],
                std::back_inserter(coords)).second;

        assert(norm > 0);
        if (coords.empty()) {
             std::cout << pointsInterpolation[i].x() << " " << pointsInterpolation[i].y() <<" Not valid coords" << std::endl;
             continue;
        }
        //linear interpolant:
        l_value = CGAL::linear_interpolation(coords.begin(), coords.end(),
            norm,
            CGAL::Data_access<Point_value_map>(values));
       
        std::cout << pointsInterpolation[i].x() << " " << pointsInterpolation[i].y() << " " << l_value << std::endl;
    }
    
    return EXIT_SUCCESS;
}

我展示的代码是根据我在官方 CGAL 文档中找到的示例代码改编的。我将留下下面的链接供参考。 CGAL 6.0 - 2D 和曲面函数插值

我尝试读取 csv 文件，将其保存到向量中，关闭文件，然后使用该向量构建网格，但它并没有对网格构建时间产生重大变化。

Answer 1

我做了很多研究，并成功通过一个非常简单的更改来优化代码。 为了澄清，所花费的是进行三角测量，我没有考虑读取分开的文件（只有几秒钟）所需的时间。

解决方案： 在函数 readExcelCSV 中，我更改了第一个 while 循环，以便在读取文件时不将点添加到变量 T 中，而是稍后将它们添加到变量点中，一旦循环完成，立即插入所有点，结果代码如下。

std::string line;

int cont = 0;
while (std::getline(file, line)) {
    std::stringstream ss(line);
    std::string value;
    std::vector<double> row;
        
    for (int idx = 0; idx < 3; idx++)
    {
        std::getline(ss, value, ',');
        row.push_back(std::stod(value));
    }
       
    points.push_back(Point(row[0], row[1]));
    Coord_type value2 = row[2];
    values.insert(std::make_pair(points[cont], value2));
    cont++;
}
T.insert(points.begin(),points.end());

这将处理三角形所需的时间从 18 秒缩短到 >1 秒。

我正在使用CGAL 6.0

我在以下链接的评论中找到了答案：CGAL Triangulation：非常慢的点插入