Алгоритм C ++ для сортировки соединенных треугольников в группы

У меня есть треугольная сетка, которая имеет различные группы треугольников, например группа из 15 соединенных треугольников, за которой следует другая группа (не связанная с первым) из 25 треугольников. Число групп соединенных треугольников произвольно, а сами группы могут быть любого размера (от 1 до чего угодно). Мне нужно назначить каждой вершине треугольника индекс, указывающий, к какой группе связанных треугольников он принадлежит. Итак, в приведенном выше примере я бы дал вершинам, которые составляют группу из 15 треугольников, индекс 0, а вершинам, которые составляют группу из 25 треугольников, индекс 1 (и т. Д.).

Код ниже очень медленный, когда я передаю ему массив из более чем 70 000 треугольников, но работает. У кого-нибудь есть понимание областей кода, где я могу найти наиболее эффективные оптимизации?

int _tmain(int argc, _TCHAR* argv[])
{
//test array of vertex indices - each triple is a discrete triangle
int vv[21] = {0,1,2, 2,3,4, 4,5,6, 7,8,9, 9,10,11, 0,99,80, 400, 401, 402};

//setup the initial arrays prior to the while loop
std::vector<int> active_points;
std::vector<vector<int>> groups;
std::vector<int> active_triplets(&vv[0], &vv[0]+21);

//put the first three triangle points into active points
active_points.push_back(active_triplets[0]);
active_points.push_back(active_triplets[1]);
active_points.push_back(active_triplets[2]);

int group_index = 0;

//put these initial points in the first group
std::vector<int> v;
v.push_back(active_points[0]);
v.push_back(active_points[1]);
v.push_back(active_points[2]);
groups.push_back(v);

//remove the first triangle points from the triplets array
std::vector<int>::iterator it = active_triplets.begin();
active_triplets.erase(it, it+3);

while (active_triplets.size() > 0)
{
//once we've exhausted the first group of connections
//we move on the next connected set of triangles
if (active_points.size() == 0)
{
group_index++;
active_points.push_back(active_triplets[0]);
active_points.push_back(active_triplets[1]);
active_points.push_back(active_triplets[2]);

std::vector<int> v;
for (std::vector<int>::iterator it = active_points.begin(); it != active_points.end(); ++it)
{
v.push_back(*it);
}
groups.push_back(v);

std::vector<int>::iterator it = active_triplets.begin();
active_triplets.erase(it,it+3);
}

//create a vector to store the 'connected' points of the current active points
//I don't think I can modify any of the existing vectors as I iterate over them
std::vector<int> temp_active_points;
//start check this group of three vertices
for  (std::vector<int>::iterator it = active_points.begin(); it != active_points.end(); ++it)
{
std::vector<int> polys_to_delete;
for  (std::vector<int>::iterator it_a = active_triplets.begin(); it_a != active_triplets.end();++it_a)
{
if (*it == *it_a)
{
//which triangle do we hit? put all points in temp_active_points.
//Once a vertex matches with another vertex we work out the other
//connected points in that triangle from that single connection

int offset = it_a - active_triplets.begin();
int mod = (it_a - active_triplets.begin())  % 3;
polys_to_delete.push_back(offset - mod);
if (mod == 1)
{
temp_active_points.push_back(active_triplets.at((offset - 1)));
temp_active_points.push_back(active_triplets.at((offset + 1)));
}
else if (mod ==  2)
{
temp_active_points.push_back(active_triplets.at((offset - 2)));
temp_active_points.push_back(active_triplets.at((offset - 1)));
}
else
{
temp_active_points.push_back(active_triplets.at((offset + 1)));
temp_active_points.push_back(active_triplets.at((offset + 2)));
}
}
}
int offset_subtraction = 0;
for  (std::vector<int>::iterator it = polys_to_delete.begin(); it != polys_to_delete.end(); ++it)
{
std::vector<int>::iterator it_a = active_triplets.begin();
active_triplets.erase(it_a + (*it - offset_subtraction),  it_a + (*it - offset_subtraction) + 3);
offset_subtraction += 3;
}
}
for (std::vector<int>::iterator it = temp_active_points.begin(); it != temp_active_points.end(); ++it)
{
groups[group_index].push_back(*it);
}
//remove duplicates
std::sort( temp_active_points.begin(), temp_active_points.end() );
temp_active_points.erase( std::unique( temp_active_points.begin(), temp_active_points.end() ), temp_active_points.end() );
active_points = temp_active_points;
temp_active_points.clear();
}
for (std::vector<vector<int>>::iterator it = groups.begin(); it != groups.end(); ++it)
{
for (std::vector<int>::iterator it_sub = (*it).begin(); it_sub != (*it).end(); ++it_sub)
{
std::cout <<  it - groups.begin() << ' ' << *it_sub << '\n';
}
}
}

После комментариев Питера я переделал код с помощью коллеги. Намного быстрее, используя карту:

#include "stdafx.h"#include <iostream>     // std::cout
#include <algorithm>    // std::set_difference, std::sort
#include <vector>       // std::vector
#include <set>       // std::vector
#include <cmath>
#include <map>

using namespace std;

// the global vertex indices
int numIndices;
int* indices;

class Triangle
{
public:
explicit Triangle(int positionIndex_) : added(false), positionIndex(positionIndex_) {}

int positionIndex; // positinon of the first index of this triangle in the global vert array (which is in  3's)

// only valid with 0, 1, 2
int getIndex(int i) { return indices[positionIndex + i];}

bool isNeighbour(Triangle* other)
{
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (getIndex(i) == other->getIndex(j))
return true;
return false;
}

bool isAdded() const{return added;}
void setAdded(){ added = true;}

int getNeighbourCount() const{ return neighbours.size(); }
Triangle* getNeighbour(int i) const{ return neighbours[i];}
void AddNeighbour(Triangle* neighbour)
{
neighbours.push_back(neighbour);//changed to set
}

private:
std::vector<Triangle*> neighbours;//changed to set
bool added;
};

std::vector<Triangle*> triangles;

void createAllTriangles()
{
for (int i = 0; i < numIndices; i += 3)
triangles.push_back(new Triangle(i));

//must delete all these pointers created with new
}

void setupAllNeighboursA()
{
std::map<int,std::set<int>> vertex_to_tris;
for (int i = 0; i < numIndices; i += 3)
{
vertex_to_tris[indices[i]].insert(i);
vertex_to_tris[indices[i+1]].insert(i);
vertex_to_tris[indices[i+2]].insert(i);
}

int n = triangles.size();
for (int i = 0; i < n; ++i)
{
Triangle* t = triangles[i];
std::set<int> temp_neighbours;
for (int j = 0; j < 3; ++j)
{
int test_index = t->getIndex(j);
for (std::set<int>::iterator it = vertex_to_tris[test_index].begin(); it != vertex_to_tris[test_index].end(); ++it)
{
if (*it != i) temp_neighbours.insert(*it/3);//divide by 3 to get the 'actual' tri index
}
}

for (std::set<int>::iterator it = temp_neighbours.begin(); it != temp_neighbours.end(); ++it)
{
Triangle* other = triangles[*it];
t->AddNeighbour(other);
}
}
}

class Island
{
public:
void recursiveAdd(Triangle* t)
{
AddAndSetAdded(t);
for(int i = 0; i < t->getNeighbourCount(); i++)
if ( ! t->getNeighbour(i)->isAdded() )
recursiveAdd(t->getNeighbour(i));
}
std::set<Triangle*> children;
private:
void AddAndSetAdded(Triangle* t)
{
t->setAdded();
children.insert(t);
}
};

std::vector<Island*> island_list;

void createIslands()
{
for (int i = 0; i < int(triangles.size()); ++i)
{
Triangle* t = triangles[i];
if( ! t->isAdded() )
{
Island* island = new Island;
island->recursiveAdd(t);
island_list.push_back(island);
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
indices = vv;
numIndices = 73728;
createAllTriangles();
setupAllNeighboursA();
createIslands();

for (int x = 0; x < int(island_list.size()); x++)
{
std::cout << "Island Index: " << x << endl;
std::cout << island_list[x]->children.size() << endl;
}
}