用c++写一个点云最小生成树
时间: 2023-07-22 21:11:21 浏览: 46
好的,以下是用 C++ 实现点云最小生成树的代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point {
double x, y, z;
int id;
};
struct Edge {
int u, v;
double w;
};
bool cmp(const Edge &a, const Edge &b) {
return a.w < b.w;
}
class UnionFind {
public:
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int Find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = Find(parent[x]);
}
bool Union(int x, int y) {
int px = Find(x);
int py = Find(y);
if (px == py) {
return false;
}
if (rank[px] < rank[py]) {
parent[px] = py;
}
else if (rank[px] > rank[py]) {
parent[py] = px;
}
else {
parent[px] = py;
++rank[py];
}
return true;
}
private:
vector<int> parent;
vector<int> rank;
};
class PointCloud {
public:
PointCloud() {}
void AddPoint(const Point &p) {
p.id = points.size();
points.push_back(p);
}
void BuildEdges() {
int n = points.size();
edges.reserve(n * (n - 1) / 2);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
double dx = points[i].x - points[j].x;
double dy = points[i].y - points[j].y;
double dz = points[i].z - points[j].z;
double w = sqrt(dx * dx + dy * dy + dz * dz);
edges.push_back({ i, j, w });
}
}
sort(edges.begin(), edges.end(), cmp);
}
vector<Edge> FindMST() {
UnionFind uf(points.size());
vector<Edge> mst;
for (const auto &e : edges) {
if (uf.Union(e.u, e.v)) {
mst.push_back(e);
}
if (mst.size() == points.size() - 1) {
break;
}
}
return mst;
}
private:
vector<Point> points;
vector<Edge> edges;
};
int main() {
PointCloud cloud;
cloud.AddPoint({ 0, 0, 0 });
cloud.AddPoint({ 1, 0, 0 });
cloud.AddPoint({ 0, 1, 0 });
cloud.AddPoint({ 0, 0, 1 });
cloud.BuildEdges();
auto mst = cloud.FindMST();
for (const auto &e : mst) {
cout << e.u << " - " << e.v << " : " << e.w << endl;
}
return 0;
}
```
这个程序实现了一个简单的点云类,其中包含点的坐标和编号,以及最小生成树的边和权重。它使用 Kruskal 算法来查找最小生成树,使用并查集来维护连通性。