C++ 代码：使用最小生成树连接 PLY 点云文件中的点

#include #include #include #include #include

using namespace std;

// 定义点的数据结构 struct Point { float x, y, z; };

// 定义边的数据结构 struct Edge { int p1, p2; float weight; };

// 定义比较函数 struct Compare { bool operator()(const Edge& e1, const Edge& e2) { return e1.weight > e2.weight; } };

// 读取PLY文件，返回点云数据 vector readPLY(const char* filename) { vector points;

ifstream file(filename, ios::in);
string line;

// 读取头部信息
while (getline(file, line)) {
    if (line == "end_header") {
        break;
    }
}

// 读取点数据
while (getline(file, line)) {
    Point p;
    sscanf(line.c_str(), "%f %f %f", &p.x, &p.y, &p.z);
    points.push_back(p);
}

file.close();

return points;

}

// 计算两个点之间的距离 float distance(const Point& p1, const Point& p2) { float dx = p1.x - p2.x; float dy = p1.y - p2.y; float dz = p1.z - p2.z; return sqrt(dx * dx + dy * dy + dz * dz); }

// 计算最小生成树，返回边的集合 vector minimumSpanningTree(const vector& points) { int n = points.size(); vector edges; priority_queue<Edge, vector, Compare> pq;

// 构建边的集合
for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
        Edge e;
        e.p1 = i;
        e.p2 = j;
        e.weight = distance(points[i], points[j]);
        pq.push(e);
    }
}

// 计算最小生成树
vector<int> parent(n);
for (int i = 0; i < n; ++i) {
    parent[i] = i;
}
int count = 0;
while (count < n - 1 && !pq.empty()) {
    Edge e = pq.top();
    pq.pop();
    int p1 = e.p1;
    int p2 = e.p2;
    int parent1 = parent[p1];
    int parent2 = parent[p2];
    while (parent1 != parent[parent1]) {
        parent1 = parent[parent1];
    }
    while (parent2 != parent[parent2]) {
        parent2 = parent[parent2];
    }
    if (parent1 != parent2) {
        edges.push_back(e);
        ++count;
        parent[parent1] = parent2;
    }
}

return edges;

}

// 将点云数据和边的集合输出为PLY文件 void writePLY(const char* filename, const vector& points, const vector& edges) { ofstream file(filename, ios::out); file << "ply" << endl; file << "format ascii 1.0" << endl; file << "element vertex " << points.size() << endl; file << "property float x" << endl; file << "property float y" << endl; file << "property float z" << endl; file << "element edge " << edges.size() << endl; file << "property int vertex1" << endl; file << "property int vertex2" << endl; file << "end_header" << endl; for (const Point& p : points) { file << p.x << " " << p.y << " " << p.z << endl; } for (const Edge& e : edges) { file << e.p1 << " " << e.p2 << endl; } file.close(); }

// 将边的集合转换为线段集合 vector<pair<Point, Point>> edgesToSegments(const vector& points, const vector& edges) { vector<pair<Point, Point>> segments; for (const Edge& e : edges) { Point p1 = points[e.p1]; Point p2 = points[e.p2]; segments.push_back(make_pair(p1, p2)); } return segments; }

int main(int argc, char** argv) { // 读取PLY文件 vector points = readPLY("input.ply");

// 计算最小生成树
vector<Edge> edges = minimumSpanningTree(points);

// 将点云数据和边的集合输出为PLY文件
writePLY("output.ply", points, edges);

// 将边的集合转换为线段集合
vector<pair<Point, Point>> segments = edgesToSegments(points, edges);

// 输出线段集合
for (const auto& segment : segments) {
    cout << "(" << segment.first.x << ", " << segment.first.y << ", " << segment.first.z << ") - ";
    cout << "(" << segment.second.x << ", " << segment.second.y << ", " << segment.second.z << ")" << endl;
}

return 0;

}