首页 > 编程语言 >α-shape算法曲面重建

α-shape算法曲面重建

时间:2024-11-07 12:19:11浏览次数:3  
标签:曲面 剖分 算法 外接圆 shape pcl 三角形 Delaunay

目录

1 原理介绍

α-shape 的基础概念

数学公式推导

2.1 外接圆半径

2.2 根据 α 参数筛选三角形

2.3 构建 α-shape

2.4 参数调整与优化

3 α-shape 的构建步骤

4 示例代码

        取点云的凹边界是计算几何中的一个经典问题。凹边界与凸边界不同,它能捕捉到数据的细节和凹形结构。在点云处理中,凹边界提取用于描述点云的外形。以下是关于凹边界提取的详细介绍:

1 原理介绍

        凹边界提取的基本思想是找到一个边界,该边界可以包围点云中的所有点,同时允许凹陷,以更紧密地拟合点云的形状。凹边界的计算通常基于一个参数,该参数决定了边界的细节程度。常用的方法包括 α-球体(α-shape)方法。

α-shape 的基础概念

  1. Delaunay 三角剖分: 给定一个点集,Delaunay 三角剖分是该点集的一个三角剖分,其特点是任何一个三角形的外接圆的内部不包含其他点。Delaunay 三角剖分是构建 α-shape 的基础。

  2. α-ball: α-ball 是指半径为 α 的球体。在二维情况下,这个球体是一个圆。在 α-shape 方法中,我们使用 α-ball 来确定哪些边和面(在三维中)属于 α-shape。

  3. α-shape: 对于给定的点集和 α 值,α-shape 是由 Delaunay 三角剖分中的一部分边和面构成的多边形或多面体。具体而言,如果一个三角形的外接圆半径小于 α,则该三角形在 α-shape 中被保留。

数学公式推导

2.1 外接圆半径

        给定一个三角形,其顶点为 A(x1,y1), B(x2,y2), C(x3,y3),我们可以计算三角形的三条边的长度:

外接圆半径 R 可以通过三角形的边长及其面积来计算。公式如下:

其中 a,b,c 是三角形的三条边的长度,A 是三角形的面积,计算方法如下:

是三角形的半周长

2.2 根据 α 参数筛选三角形

  • α 参数: 这是一个用户定义的参数,控制 α-shape 的细节程度。α 值越小,保留的细节越多。

  • 筛选过程:

    • 遍历 Delaunay 三角剖分中的每个三角形。
    • 如果三角形的外接圆半径小于或等于 α,则保留该三角形;否则,去除。
  • 结果: 通过这种筛选,我们将只保留那些满足 α 条件的三角形或四面体,它们构成 α-shape 的基本单元。

2.3 构建 α-shape

  • 连接: 将保留的三角形或四面体连接起来构成一个多边形或多面体,即 α-shape。

  • 拓扑结构: 保证这些单元之间的拓扑连接性,以形成一个封闭的形状。

2.4 参数调整与优化

  • α 参数调整: 根据具体需求调整 α 值,观察 α-shape 的变化。较小的 α 值可能生成更复杂的形状,而较大的 α 值则更接近于凸包。

  • 优化: 通过优化算法或启发式方法找到最佳 α 值,使得生成的 α-shape 能够最准确地描述点集的结构。

3 α-shape 的构建步骤

  1. 计算 Delaunay 三角剖分: Delaunay 三角剖分的性质是对于任意一个三角形,其外接圆内不包含任何其他点。这一性质使得 Delaunay 三角剖分在构建 α-shape 时非常有效,因为我们可以通过简单地遍历三角形并计算其外接圆半径来决定是否保留这个三角形。

  2. 计算外接圆半径: 对于 Delaunay 三角剖分中的每个三角形,计算其外接圆半径 R。

  3. 筛选三角形: 遍历所有的三角形,保留那些外接圆半径 R≤α 的三角形。这是因为较小的 α 值会去除那些包含较多空洞的三角形,而较大的 α 值会保留更多的细节。

  4. 生成 α-shape: 使用保留下来的三角形生成 α-shape,即为最终的凹边界。

4 示例代码

#include <pcl/io/pcd_io.h>
#include <pcl/io/obj_io.h>
#include <pcl/point_types.h>
#include <pcl/surface/concave_hull.h>
#include <pcl/visualization/pcl_visualizer.h>

int main(int argc, char** argv)
{
    // 创建一个指向 pcl::PointCloud<pcl::PointXYZ> 的共享指针,用于存储输入点云
    pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);

    // 从 PCD 文件中加载点云数据
    pcl::io::loadPCDFile<pcl::PointXYZ>("bunny.pcd", *cloud);

    // 创建一个指向 pcl::PointCloud<pcl::PointXYZ> 的共享指针,用于存储凹包结果
    pcl::PointCloud<pcl::PointXYZ>::Ptr surface_hull(new pcl::PointCloud<pcl::PointXYZ>);

    // 创建 ConcaveHull 对象,用于计算凹包
    pcl::ConcaveHull<pcl::PointXYZ> cavehull;
    cavehull.setInputCloud(cloud);  // 设置输入点云
    cavehull.setAlpha(0.003);       // 设置 α 参数,控制凹包的细节程度

    // 用于存储多边形的顶点信息
    std::vector<pcl::Vertices> polygons;

    // 计算凹包并将结果存储到 surface_hull 和 polygons 中
    cavehull.reconstruct(*surface_hull, polygons);

    // 创建一个用于存储多边形网格的对象
    pcl::PolygonMesh mesh;
    cavehull.reconstruct(mesh); // 重建面要素到 mesh


    // 创建一个 PCL 可视化器,用于显示凹包结果
    pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer("hull"));
    viewer->setWindowName("Surface Reconstruction");

    // 在可视化器中添加多边形网格
    viewer->addPolygonMesh<pcl::PointXYZ>(surface_hull, polygons, "polyline");

    // 开始视图循环,直到窗口关闭
     // 主循环
    while (!viewer->wasStopped()) 
    {
        viewer->spinOnce(0);
    }


    return 0;
}

标签:曲面,剖分,算法,外接圆,shape,pcl,三角形,Delaunay
From: https://blog.csdn.net/twnkie/article/details/143494063

相关文章

  • Java深度优先搜索(DFS)算法实现
    标题:Java深度优先搜索(DFS)算法实现引言:深度优先搜索(Depth-FirstSearch,DFS)是一种常用的图遍历算法,它通过递归地遍历图中的每个顶点,来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。算法思想:深度优先搜索算法的基本思想是先访问一个......
  • c++ Kruskal 最小生成树 (MST) 算法(Kruskal’s Minimum Spanning Tree (MST) Algorith
            对于加权、连通、无向图,最小生成树(MST)或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。Kruskal算法简介:        在这里,我们将讨论Kruskal算法来查找给定加权图的MST。         在Kruskal算法中,按升序对给定图的所有......
  • 常考的排序算法
    冒泡排序#include<iostream>#include<string>usingnamespacestd;//voidShellsort(intA[],intn)//{//   intd,i,j;//   for(d=n/2;d>=1;d=d/2)//   {//      for(i=d+1;i<=n;i++)//      {//     ......
  • JavaScript Kruskal 最小生成树 (MST) 算法(Kruskal’s Minimum Spanning Tree (MST) A
             对于加权、连通、无向图,最小生成树(MST)或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。Kruskal算法简介:        在这里,我们将讨论Kruskal算法来查找给定加权图的MST。         在Kruskal算法中,按升序对给定图的所......
  • 基于springboot框架在线生鲜商城推荐系统 java实现个性化生鲜/农产品购物商城推荐网站
    基于springboot框架在线生鲜商城推荐系统java实现个性化生鲜/农产品购物商城推荐网站爬虫、数据分析、排行榜基于协同过滤算法推荐、基于流行度热点推荐、平均加权混合推荐机器学习、大数据、深度学习OnlineShopRecommendEx一、项目简介1、开发工具和使用技术IDEA,jdk......
  • 【算法学习】反悔贪心
    前言反悔贪心,先选择局部最优,当不断向后更新时发现前面的决策在现在来看并不优就进行调整过去决策进行局部最优,可以说反悔贪心一步步扩宽自己的视野从而明白过去的错误。、如果动态规划是将各种削苹果的方式都展示出来的话,那反悔贪心就是削一下补回来一点再削。当然反悔贪心的题......
  • C语言数据结构--详细讲解算法复杂度
    C语言数据结构-算法复杂度前言一、时间复杂度1.大O渐进表示法2时间复杂度的计算二、空间复杂度1.什么是空间复杂度2时间复杂度的计算总结前言我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时,这个过程就......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • 算法笔记——马拉核弹(Mana Nuclear)
    0x00摘要“马拉核弹”算法由SXHT同学(2009~今)发明,并在2024年11月于某不知名学校机房内正式公布。该算法基于1975年发明的Manacher算法,并将其推广至对称正方形问题。原文链接与密码:sunxuhetai2009。关键词:Manacher算法信息学对称正方形0x01缘由先来看这道题目:......
  • Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构
    1.数据结构和算法简介程序可以理解为:程序=数据结构+算法概述/目的:都可以提高程序的效率(性能)数据结构指的是存储,组织数据的方式.算法指的是为了解决实际业务问题而思考思路和方法,就叫:算法.2.算法的5大特性介绍概述:为了解决实际业务问题,......