c++ - 获取顶点索引以保存三角剖分

Question

我想将 triangulation_2D 保存为下一种格式:

v x1 y1
v x2 y2
...
f v11 v12 v13
f v21 v22 v23
...

其中 v11 v12 ... 是已经保存的点的索引，这里我使用的是:(CDT 是一个 Triangulation_2，_Point 是一个 point_2)

std::vector<_Point> meshpoints;
int find_index(_Point p)
{
    bool trouv = false;
    unsigned i = 0;
    while(i < meshpoints.size() && !trouv)
    {
        if(p.x() == meshpoints.at(i).x() && p.y() == meshpoints.at(i).y()) trouv = true;
        else i++;
    }
    if(trouv) return i;
    return -1;
}

void save_triangulation(CDT triangulation, std::string link = "unkown.txt")
{
    std::cout << "Saving IVGE . . ." ;
    std::ofstream triangulation_file(link);

    for(CDT::Vertex_iterator vertex = triangulation.vertices_begin() ; vertex != triangulation.vertices_end() ; vertex++)
        meshpoints.push_back(vertex->point());

    for(unsigned i = 0 ; i < meshpoints.size() ; i++)
        triangulation_file << "v " << std::setprecision(15) << meshpoints.at(i) << std::endl;

    for(CDT::Face_iterator c = triangulation.faces_begin(); c != triangulation.faces_end(); c++)
    {
        triangulation_file << "f " << find_indice(c->vertex(0)->point()) << " " << find_indice(c->vertex(1)->point()) << " " << find_indice(c->vertex(2)->point()) <<std::endl;
    }
    std::cout << " Done\n" ;
}

我的问题是:是否有任何方法可以优化 find_index，因为我有一个超过 2M 点的三角剖分。

我改变了输出文件的格式，这里是新格式:
v x1 y1
v x2 y2
...
f v11 v12 v13 a11 a12 a13
f v21 v22 v23 a21 a22 a23
...

其中 a12 ... 是三角形邻居。函数变为:

std::ofstream Ivge_file(link);
unsigned Vertx_index = 0;
Ivge_file << std::setprecision(15);
for(CDT::Vertex_iterator vertex = IVGE.vertices_begin() ; vertex != IVGE.vertices_end() ; vertex++)
{
    Triangulation::Vertex_handle vertx_h = vertex;
    vertx_h->info() = Vertx_index;
    Vertx_index++;
    Ivge_file << "v " << vertex->point() << std::endl;
}

int id=0;
for(CDT::Face_iterator c = IVGE.faces_begin(); c != IVGE.faces_end(); c++,id++)
    c->info()._Id = id;

for(CDT::Face_iterator c = IVGE.faces_begin(); c != IVGE.faces_end(); c++)
    Ivge_file << "f " << c->vertex(0)->info() << " " << c->vertex(1)->info() << " " << c->vertex(2)->info() << " " << c->neighbor(0)->info()._Id << " " << c->neighbor(1)->info()._Id << " " << c->neighbor(2)->info()._Id << std::endl;

Answer 1

我改变了输出文件的格式，这里是新格式:
v x1 y1
v x2 y2
...
f v11 v12 v13 a11 a12 a13
f v21 v22 v23 a21 a22 a23
...

其中 a12 ... 是三角形邻居。函数变为:

std::ofstream Ivge_file(link);
unsigned Vertx_index = 0;
Ivge_file << std::setprecision(15);
for(CDT::Vertex_iterator vertex = IVGE.vertices_begin() ; vertex != IVGE.vertices_end() ; vertex++)
{
    Triangulation::Vertex_handle vertx_h = vertex;
    vertx_h->info() = Vertx_index;
    Vertx_index++;
    Ivge_file << "v " << vertex->point() << std::endl;
}

int id=0;
for(CDT::Face_iterator c = IVGE.faces_begin(); c != IVGE.faces_end(); c++,id++)
    c->info()._Id = id;

for(CDT::Face_iterator c = IVGE.faces_begin(); c != IVGE.faces_end(); c++)
    Ivge_file << "f " << c->vertex(0)->info() << " " << c->vertex(1)->info() << " " << c->vertex(2)->info() << " " << c->neighbor(0)->info()._Id << " " << c->neighbor(1)->info()._Id << " " << c->neighbor(2)->info()._Id << std::endl;