我有一个三角形网格，它具有不同的三角形组，例如一组 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;
}
}