| 15 | |
| 16 | |
| 17 | universe* segment_graph(int num_vertices, int num_edges, edge* edges, float c) { |
| 18 | std::sort(edges, edges + num_edges); // sort edges by weight |
| 19 | universe* u = new universe(num_vertices); // make a disjoint-set forest |
| 20 | // threshold for each vertex |
| 21 | float* threshold = new float[num_vertices]; |
| 22 | // set initial threshold |
| 23 | for (int i = 0; i < num_vertices; i++) { |
| 24 | threshold[i] = c; |
| 25 | } |
| 26 | // for each edge, in non-decreasing weight order |
| 27 | for (int i = 0; i < num_edges; i++) { |
| 28 | edge* pedge = &edges[i]; |
| 29 | // components conected by this edge = initially 2 vertices |
| 30 | int a = u->find(pedge->a); |
| 31 | int b = u->find(pedge->b); |
| 32 | if (a != b) { |
| 33 | if ((pedge->w <= threshold[a]) && (pedge->w <= threshold[b])) { |
| 34 | // join components |
| 35 | u->join(a, b); |
| 36 | a = u->find(a); |
| 37 | // update threshold for a = edge weight + kthr / |a| |
| 38 | threshold[a] = pedge->w + (c / u->size(a)); |
| 39 | } |
| 40 | } |
| 41 | } |
| 42 | delete[] threshold; |
| 43 | return u; |
| 44 | } |
| 45 | |
| 46 | |
| 47 | vector<int> segment_mesh(MeshDataf mesh, const float kthr, const int segMinVerts, std::map<std::pair<int, int>, int>& connectivity) { |
no test coverage detected