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