精华内容
下载资源
问答
  • alpha shapes提取点云边界特征(C++版本)基于PCL库写的alpha shapes算法,具体实现原理参考:https://blog.csdn.net/qq_36686437/article/details/115168516或者参考论文:[1]刘科. 平面点云边界提取算法研究[D].长沙...
  • Alpha Shapes的演示程序

    2017-09-29 10:04:46
    这是一个Alpha Shapes的测试程序,详细信息请见我的博客:http://blog.csdn.net/mahabharata_
  • PCL实现Alpha Shapes算法

    2021-11-08 19:16:34
    本文所用方法都来自于网络查找,本文借鉴了一下其他博主的文章,在他的基础上实现了Alpha Shapes算法。然后写了一个Alpha Shapes演示程序。 Alpha Shapes演示程序下载 数据: 1、在空白处鼠标单击可以添加数据。 2、...

    说明:

    本文所用方法都来自于网络查找,本文借鉴了一下其他博主的文章,在他的基础上实现了Alpha Shapes算法。然后写了一个Alpha Shapes演示程序。
    Alpha Shapes演示程序下载
    https://download.csdn.net/download/qq_42570058/38588253
    数据:
    1、在空白处鼠标单击可以添加数据。
    2、也可以直接点击随机数据按钮,随机生成50个数据点。
    3、按住Ctrl+Z可以回撤删除最后添加的点。
    参数设置:
    演示程序默认设置半径为30,可以拖动滑条设置半径值,滑条范围(0-200)。
    点击运行AlphaSphaopes按钮即可进行绘制。

    软件使用截图

    在这里插入图片描述

    PCL运行结果

    在这里插入图片描述

    Alpha Shapes算法原理

    实现过程:
    在有限个离散点集S中,存在N个点,这N个点可以组成N*(N-1)条直线,我们可以通过判断该线段是否为边界线提取边界点。边界线判断方式:设定一个半径R,联合每条线段的端点(P1,P2)画圆(显然这种圆有两个),判定圆内没有其他的点,则判定该线段为边界线,P1,P2为边界点。
    具体步骤:
    1、 遍历每条边
    2、 如果判定P1P2长度大于2R,则跳过。
    3、 求圆心坐标(C1,C2)。
    4、 判断任何一个圆内部不包含S中其他点,P1,P2为边界点。
    圆心求解(一定要用向量求解,其他方法很容易出现Bug)。
    1、计算向量v1=P1-P2,线段中点坐标mid,
    2、根据两向量垂直等于0,可以求的n,
    3、根据三角形垂直定理可以求出C1到线段P1P2的长度h,
    4、这样就可以计算出C1,C2坐标C1=mid+nh, C1=mid-nh。
    在这里插入图片描述
    qt中实现的代码
    该函数主要在qt中实现,大部分是从第一个参考文章中直接复制而来,我自己添加了记录圆心边界点(排好序)。看懂了就可以自己在pcl中实现,其实只需要把点类型改了,然后写一个两点之间距离计算就可以实现。

    //该函数从第一个参考文章中直接复制而来,看懂了就可以自己在pcl中实现
    void alphaShapes::process()
    {
    	for (int i = 0; i<m_points.size(); i++)
    	{
    		// k从i+1开始,减少重复计算
    		for (int k = i + 1; k<m_points.size(); k++)
    		{
    			// 跳过距离大于直径的情况
    			if (m_points[i].distanceToPoint(m_points[k])>2 * m_radius)
    				continue;
    
    			// 两个圆心
    			QVector2D c1, c2;
    
    			// 线段中点
    			QVector2D center = 0.5*(m_points[i] + m_points[k]);
    
    			// 方向向量 d = (x,y)
    			QVector2D dir = m_points[i] - m_points[k];
    
    			// 垂直向量 n = (a,b)  a*dir.x+b*dir.y = 0; a = -(b*dir.y/dir.x)
    			QVector2D normal;
    			normal.setY(5);  // 因为未知数有两个,随便给y附一个值5。 
    
    			if (dir.x() != 0)
    				normal.setX(-(normal.y()*dir.y()) / dir.x());
    			else     // 如果方向平行于y轴
    			{
    				normal.setX(1);
    				normal.setY(0);
    			}
    			normal.normalize();   // 法向量单位化
    
    			float len = sqrt(m_radius*m_radius - (0.25*dir.length()*dir.length()));
    			c1 = center + len*normal;
    			c2 = center - len*normal;
    
    			// b1、b2记录是否在圆C1、C2中找到其他点。
    			bool b1 = false, b2 = false;
    			for (int m = 0; m<m_points.size(); m++)
    			{
    				if (m == i || m == k)
    					continue;
    
    				if (b1 != true && m_points[m].distanceToPoint(c1) < m_radius)
    					b1 = true;
    				if (b2 != true && m_points[m].distanceToPoint(c2) < m_radius)
    					b2 = true;
    
    				// 如果都有内部点,不必再继续检查了
    				if (b1 == true && b2 == true)
    					break;
    			}
    
    			MyLine edge;
    			if (b1 != true || b2 != true)
    			{
    
    				edge.p1.setX(m_points[i].x());
    				edge.p1.setY(m_points[i].y());
    				edge.p2.setX(m_points[k].x());
    				edge.p2.setY(m_points[k].y());
    			
    				m_lines.push_back(edge);
    			}
    			if (!b1)
    			{
    				MyCircle c;
    				c.c1.setX(c1.x());
    				c.c1.setY(c1.y());
    				c.radius = m_radius;
    				m_circles.push_back(c);
    			}
    			if (!b2)
    			{
    				MyCircle c;
    				c.c1.setX(c2.x());
    				c.c1.setY(c2.y());
    				c.radius = m_radius;
    				m_circles.push_back(c);
    			}
    		}
    	}
    	takePoint();//获取边界点
    }
    

    参考:
    https://ryuzhihao123.blog.csdn.net/article/details/78130511?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6.highlightwordscore&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6.highlightwordscore

    展开全文
  • 散点轮廓算法——Alpha Shapes

    千次阅读 2020-02-15 23:49:00
    背景 项目原因,需要自动勾勒出一些密集散点的边界,最先想到的是凸包算法,但是明显不符合我的要求,比如我需要求下图(a)中的边界,但是用...Alpha Shapes表示一组无序空间点的边界,这个边界不一定是凸的,也...

    背景

    项目原因,需要自动勾勒出一些密集散点的边界,最先想到的是凸包算法,但是明显不符合我的要求,比如我需要求下图(a)中的边界,但是用凸包算法得到的是(b)中的结果,我们理想的结果是(c)中得到的边界,这时候就要寻求另一种算法。
    示例图片
    在网上查找的过程中接触了Alpha Shapes的概念,发现正好满足我的要求,在此进行记录:
    Alpha Shapes表示一组无序空间点的边界,这个边界不一定是凸的,也不一定是联通的,但是其一定程度上表示了这一组离散点的轮廓。通过调节参数可以使边界更加精细或粗糙。

    算法描述

    最简单的算法

    Alpha Shapes算法思想如下:
    (1)设置一个判别半径R(决定了边界的精细程度,越小越精细);
    (2)假设数据集有n个无序点,过任意两点P1、P2绘制半径为R的圆(排除两点间距离为2R的情况,显然满足要求的圆通常有两个),如果任意一个圆内没有其他数据点,则认为点P1、P2是边界点,其连线P1P2为边界线段。
    (3)n个数据点两两相连共可形成(n*(n-1))/2条线段,逐条进行判断求解。

    优化算法

    上述的算法时间复杂度明显过高,当数据点数目太多时运算效率很低。我们可以通过设置额外的判别条件加快效率:
    (1)当P1P2的长度大于2R时,跳过(一些离群点就可以被排除在外)

    最优算法

    数据点太多时,简化后的计算量还是较大。为了减少计算量,我们可以先先建立所有散点的Delaunay三角网,再从三角网的外边界开始判断。但是建立Delaunay三角网的算法手动实现有困难,暂且搁置,有待日后再进行优化。。。

    展开全文
  • 链接: [Geometry] Alpha Shapes - 原理及我的实现. 结果: 把所有点都连起来了 自己写的C++实现(有问题) struct Edge { Point2f a; Point2f b; }; class AlphaShape { public: void AlphaShapes(const float&...

    网上只找到了matlab的代码,倒是挺简单的

    参考这篇博客

    自己写了个C++的实现,有些问题,还没解决,记录下
    链接: [Geometry] Alpha Shapes - 原理及我的实现.

    结果: 把所有点都连起来了Alt

    自己写的C++实现(有问题)

    struct Edge
    {
    	Point2f a;
    	Point2f b;
    };
    
    class AlphaShape
    {
    public:
    	void AlphaShapes(const float& m_radius, const vector<Point2f> &points, Mat img);
    	vector<Point2f> m_points;  // 点集S
    	vector<Edge> m_edges;   // 边
    private:
    };
    
    float squareDistance(Point2f a, Point2f b) {
    	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
    }
    
    void normalize(Point2f pt)
    {	
    	float x = pt.x;
    	float y = pt.y;
    
    	float flag_x = x > 0 ? 1.0f : -1.0f;
    	float flag_y = y > 0 ? 1.0f : -1.0f;
    
    	pt.x =flag_x* x / (sqrt(x * x + y * y));
    	pt.y = flag_y * y / (sqrt(x * x + y * y));
    }
    
    void AlphaShape::AlphaShapes(const float &m_radius,const vector<Point2f> &points,Mat img)
    {
    	m_points = points;
    	m_edges.clear();
    	
    	for (int i = 0; i < m_points.size(); i++)
    	{
    		// k从i+1开始,减少重复计算
    		for (int k = i + 1; k < m_points.size(); k++)
    		{
    			// 跳过距离大于直径的情况
    			if (squareDistance(m_points[i],m_points[k]) > 2 * m_radius)
    				continue;
    
    			// 两个圆心
    			Point2f c1, c2;
    			
    			// 线段中点
    			Point2f center = 0.5*(m_points[i] + m_points[k]);
    			//bug在这里
    			// 方向向量 d = (x,y)
    			Point2f dir = m_points[i] - m_points[k];
     
    			// 垂直向量 n = (a,b)  a*dir.x+b*dir.y = 0; a = -(b*dir.y/dir.x)
    			Point2f normal;
    			normal.y=1;  // 因为未知数有两个,随便给y附一个值1。 
    
    			if (dir.x != 0)
    				normal.x=-(normal.y*dir.y) / dir.x;
    			else     // 如果方向平行于y轴
    			{
    				normal.x=1;
    				normal.y=0;
    			}
    			normalize(normal);   // 法向量单位化
    
    			float len = sqrt(m_radius*m_radius - (0.25*(dir.x*dir.x+ dir.y*dir.y)));
    			c1 = center + len * normal;
    			c2 = center - len * normal;
    			cout << "第" << i << "和" << k << "个点" << endl;
    			cout << "圆心c1:" << c1.x << " , " << c1.y << endl;
    			cout << "圆心c2:" << c2.x << " , " << c2.y << endl;
    			//test
    			circle(img, c1, m_radius, Scalar(0, 0, 255), 1);
    			circle(img, c2, m_radius, Scalar(0, 0, 255), 1);
    
    			// b1、b2记录是否在圆C1、C2中找到其他点。
    			bool b1 = false, b2 = false;//false:点在圆外;true:点在圆内
    			for (int m = 0; m < m_points.size(); m++)
    			{
    				if (m == i || m == k)
    					continue;
    
    				// 如果都有内部点,不必再继续检查了
    				if (b1 == true || b2 == true)
    					break;
    
    				if (!b1 && squareDistance( m_points[m],c1) < m_radius)
    					b1 = true;
    				if (!b2  && squareDistance(m_points[m], c2) < m_radius)
    					b2 = true;		
    			}
    
    			if (!b1 ||!b2)
    			{
    				Edge edge;
    				edge.a = m_points[i];
    				edge.b = m_points[k];
    
    				m_edges.push_back(edge);
    			}
    
    		}
    	}
    }
    
    int main()
    {
    	Mat image(1000, 1000, CV_8UC3);  //创建一个高200,宽100的灰度图
    	vector<Point2f>pts;
    	pts.push_back({ 400,400 });
    	pts.push_back({ 400,600 });
    	pts.push_back({ 600,400 });
    	pts.push_back({ 600,600 });
    	pts.push_back({ 450,500 });
    
    
    	for (int i = 0; i < pts.size(); i++)
    	{
    		circle(image, pts[i], 2, Scalar(0, 0, 255), 2);
    	}
    
    	AlphaShape alpha;
    	alpha.AlphaShapes(200, pts,image);
    	for (int i = 0; i < alpha.m_edges.size(); i++)
    	{
    		line(image, alpha.m_edges[i].a, alpha.m_edges[i].b, Scalar(0, 255, 0), 2);//bug,除了边缘也画出来了
    		cout << alpha.m_edges[i].a.x << " , " << alpha.m_edges[i].a.y << " - "<< alpha.m_edges[i].b.x << " , " << alpha.m_edges[i].b.y<<endl;
    	}
    	imshow("原图", image);
    
    
    	waitKey(0);
    	return 0;
    
    
    }
    
    展开全文
  • alpha shapes提取边界原理及详细步骤

    千次阅读 2021-01-31 11:08:29
    由Edelsbrunner H提出的alpha shapes算法是一种简单、有效的快速提取边界点算法。其克服了点云边界点形状影响的缺点,可快速准确提取边界点,其原理如下: 如下图所示,对于任意形状的平面点云,若一个半径为a的圆...

    由Edelsbrunner H提出的alpha shapes算法是一种简单、有效的快速提取边界点算法。其克服了点云边界点形状影响的缺点,可快速准确提取边界点,其原理如下:

    如下图所示,对于任意形状的平面点云,若一个半径为a的圆,绕其进行滚动。若滚动圆半径a足够小时,则点云中每一点均为边界点;若适当增大到一定程度,其只在边界点上进行滚动,其滚动的轨迹为点云边界。

     

    (公式4.2中后面应该是x3与y3)

    效果图如下:

          

    参考文献:

    [1]平面点云边界提取算法研究[D].长沙理工大学,2017.

    展开全文
  • python :alpha shapes 算法检测边界点

    千次阅读 2020-11-04 19:31:30
    alpha shapes 算法检测边缘 :param x: 原始点坐标集 x轴 :param y: 原始点坐标集 y轴 :param radius: 圆半径 :return: 边缘点集 """ x = data.x y = data.y count = len(x) i = 0 temp_i = i edge_x = ...
  • Alpha Shapes算法介绍 计算几何中Alpha Shqpes描述欧氏平面有限点集形状的一组分段线性的简单曲线。Alpha Shqpes可以用来从一堆无序的点集中提取边缘
  • [Geometry] Alpha Shapes - 原理及我的实现

    万次阅读 多人点赞 2017-09-29 09:33:17
    其实这段时间我写了很多小程序,但是一直在忙保研的事情就没有时间写文章。... 最近出于一些其他的用途,整理并实现了Alpha shapes,所以拿出来分享一下。首先,这篇博客以及我的程序,是根据Francois Belair写的文...
  • python代码实现alpha shapes平面点云边界特征提取
  • 具有新累积参数的Alpha Shapes算法可用于从凹壳到凸壳的逐渐变化。 表示了两种实现。 其中一个在python 3 ,另一个在cython上cython 。 要执行算法,请运行alfa_example.py 。 您可以在文件夹data找到示例数据集,...
  • 本文将Alpha Shapes 算法应用于隧道二维投影边界提取,详细介绍了Alpha Shapes 边界提取算法的原理。给出了实现代码,并对边界点提取结果进行展示。最后对不同半径 α 得到的边界提取结果进行分析讨论,并得出结论。
  • 阿尔法形状 计算点集的。 例子 var alphaShape = require ( 'alpha-shape' ) var points = [ ] for ( var i = 0 ; i < 10 ; ++ i ) { points . push ( [ Math . random ( ) , Math . random ( ) ] ) } var ...
  • alpha shape 介绍

    2014-07-10 17:50:34
    alpha shape的基本介绍以及寻找convex hull的方法
  • alpha shape算法又称为滚球法,是一种提取边界点的算法。跟凸壳提取相比,alpha shape算法能够了凹包情形,且对多个点云时 能勾勒出多个边界线,这是他的优势。 研究alpha shape算法的博文虽然不多,但也有相当数量...
  • AlphaShapes演示程序

    2021-11-08 20:09:00
    Alpha Shapes演示程序下载 数据: 1、在空白处鼠标单击可以添加数据。 2、也可以直接点击随机数据按钮,随机生成50个数据点。 3、按住Ctrl+Z可以回撤删除最后添加的点。 参数设置: 演示程序默认设置半径为30,可以...
  • Alpha形状工具箱用于生成Alpha形状的工具箱。alpha形状通常用于泛化包含点集的边界多边形。alpha参数定义为值a,使得半径为1/a的圆盘的边可以在一组点的任意两个边成员之间绘制,并且仍然包含所有点。凸面外壳是一个...
  • %使用 alpha 半径 1 计算三维 alpha 形状 plot(shp) axis equal figure(2) % 放弃三维 alpha 形状的小区域 % 通过设置区域阈值来控制 alpha 形状的区域数。 % 创建并绘制一个三维点集。 [x1,y1,z1] = sphere(24); x1...
  • CGAL 凹包(alpha-Shape)

    2021-07-14 17:38:59
    本文转自https://doc.cgal.org/latest/Alpha_shapes_2/index.html。 Introduction Assume we are given a set S of points in 2D or 3D and we would like to have something like “the shape formed by these ...
  • MATLAB Alpha Shape算法检测边缘点

    千次阅读 2018-07-26 15:37:27
    α-shapes的具体算法流程如下: ①从点集PS中任意选择一点P1开始,将与之距离小于2×α的点组成的新的点集PS2 如示意图4.3左图中的所有点,从PS2中任意选取一点P2 ,利用公式(4.1)和(4.2)求出过P1、P2 点的...
  • PCL alpha shapes平面点云边界特征提取

    万次阅读 2021-03-25 09:06:28
    alpha shapes算法用于平面点云的边界特征提取
  • 毕业设计要用Matlab编写Alpha Shape代码实现LiDAR点云边缘点检测,原理流程都知道,但是就是不会编写程序。希望会的人帮帮忙。
  • 最近在项目进行中遇到要提取离散点边界的问题,像我这样的对于matlab不是特别熟练的朋友一开始肯定摸不着头脑,到底选用...关于离散点边界提取的三种方法:1.Convhull 离散点集获得边界2.Alpha Shape算法检测边缘点3...
  • 点云的边界提取

    热门讨论 2012-06-30 17:40:27
    能够将散乱的点云数据边界点及特征点提取出来,并显示。
  • Demo下载地址:http://download.csdn.net/download/qq21497936/10150349 入坑 ... 主窗口为QWidget的子类时,不论设置QPallet和setStyleSheets设置背景图片是无法生效的,但设置颜色却可以生效。...关键代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,257
精华内容 1,302
关键字:

alphashapes