利用C++实现RANSAC拟合多条直线并提出符合要求的直线，标准库和手写（不使用任何库、链表方式）两种方法

**背景：**2D/3D激光雷达扫描的点云数据，拟合直线做分析，实现总共有三种方法：
（1）PCL点云库实现
（2）利用标准库手写
（3）不使用任何库，链表方式实现
使用手写实现的主要目的是因为程序可能会在性能一般的单片机（不支持库）上跑。

第一种方式可看本人激光雷达处理系列中一篇文章：https://blog.csdn.net/qq_37967853/article/details/133946558?spm=1001.2014.3001.5502
接下来主要介绍另外两种方法：

1.标准库手写

struct Point {double x;double y;
};
// 定义拟合直线的模型
struct Line {double slope;double intercept;
};// 计算两点之间的距离
double distance(Point p1, Point p2) {double dx = p2.x - p1.x;double dy = p2.y - p1.y;return sqrt(dx * dx + dy * dy);
}

constexpr double TOLERANCE = 1.0; // 用于计算直线拟合的容差值
constexpr int MAX_ITERATIONS = 100; // RANSAC算法的最大迭代次数
constexpr int MIN_POINTS = 5; // 拟合直线所需的最小点数
constexpr int MIN_INLIERS = 20; // 拟合直线所需的最小内点数
// 生成随机数
double generateRandomNumber(double min, double max) {return min + static_cast<double>(std::rand()) / (RAND_MAX / (max - min));
}
// RANSAC拟合直线
Line ransac(const std::vector<Point>& points) {std::srand(std::time(nullptr)); // 初始化随机种子Line bestLine;int bestInliers = 0;for (int i = 0; i < MAX_ITERATIONS; ++i) {// 随机选择两个点int index1 = std::rand() % points.size();int index2 = std::rand() % points.size();while (index2 == index1) {index2 = std::rand() % points.size();}const Point& p1 = points[index1];const Point& p2 = points[index2];// 计算直线参数double slope = (p2.y - p1.y) / (p2.x - p1.x);double intercept = p1.y - slope * p1.x;// 统计内点数int inliers = 0;for (const Point& p : points) {double d = std::abs(p.y - slope * p.x - intercept);if (d < TOLERANCE) {++inliers;}}// 更新最优直线if (inliers > bestInliers && inliers >= MIN_INLIERS) {bestInliers = inliers;bestLine.slope = slope;bestLine.intercept = intercept;}}return bestLine;
}

int main() {std::srand(std::time(nullptr)); // 初始化随机种子// 生成随机点std::vector<Point> points;for (int i = 0; i < 100; ++i) {double x = generateRandomNumber(-10.0, 10.0);double y = 2.0 * x + generateRandomNumber(-1.0, 1.0); // 两条直线的斜率分别为2和-2points.push_back({ x, y });}std::vector<Point> points1;for (int i = 0; i < 100; ++i) {double x = generateRandomNumber(-10.0, 10.0);double y = -2.0 * x + generateRandomNumber(-1.0, 1.0); // 两条直线的斜率分别为2和-2points1.push_back({ x, y });}points.insert(points.end(), points1.begin(), points1.end());// RANSAC拟合直线std::vector<Line> lines;while (points.size() >= MIN_POINTS) {Line line = ransac(points);lines.push_back(line);// 从数据中移除拟合的内点std::vector<Point> remainingPoints;for (const Point& p : points) {double d = std::abs(p.y - line.slope * p.x - line.intercept);if (d >= TOLERANCE) {remainingPoints.push_back(p);}}points = remainingPoints;}// 输出拟合结果for (int i = 0; i < lines.size(); i++) {std::cout << "拟合直线 " << i + 1 << " 方程：y = " << lines[i].slope << "x + " << lines[i].intercept << std::endl;}return 0;
}

结果：
在这里插入图片描述

2.不使用任何库，利用链表数据结构

std只是用来处理随机数生成的，算法部分没使用。详细实现看代码注释

using namespace std;
//点数据
struct Node {double x;double y;Node* next;
};
//直线参数
struct LineNode {double slope;double intercept;LineNode* next;
};

//计算两点x之间最大值（横向最远）
//寻找链表中x的极值
double findMaxDist(Node* head) {double xmax=0;double xmin=0;Node* current = head;while (current != nullptr) {if ( current->x < xmin) {xmin = current->x;}if (current->x > xmax) {xmax = current->x;}current = current->next;}return xmax - xmin;
}
//释放链表内存，在链表使用结束
template<typename T>
void deleteNodeList(T* head) {while (head != nullptr) {T* temp = head;head = head->next;delete temp;}
}
template<typename T>
void deleteArryNodeList(T* lines[]) {// 释放数组链表中的内存int size = sizeof(lines) / sizeof(lines[0]);for (int i = 0; i < size; i++) {if (lines[i] != nullptr) {deleteNodeList(lines[i]);}}
}
//向链表末尾添加数据
void addNode(Node*& head, double x, double y) {if (head == nullptr) {Node* node = new Node;node->x = x;node->y = y;node->next = nullptr;head = node;}else {Node* temp1 = head;while (temp1->next != nullptr) {temp1 = temp1->next;}temp1->next = new Node;temp1->next->x = x;temp1->next->y = y;temp1->next->next = nullptr;}}
//向链表末尾添加数据
void addLineNode(LineNode*& head, double slope, double intercept) {if (head == nullptr) {LineNode* node = new LineNode;node->slope = slope;node->intercept = intercept;node->next = nullptr;head = node;}else {LineNode* temp1 = head;while (temp1->next != nullptr) {temp1 = temp1->next;}temp1->next = new LineNode;temp1->next->slope = slope;temp1->next->intercept = intercept;temp1->next->next = nullptr;}}
//合并链表
//将链表1加在链表2后面，顺序不变
void appendList(Node*& list1, Node* list2) {if (list1 == nullptr) {list1 = list2;}else {Node* temp = list1;while (temp->next != nullptr) {temp = temp->next;}temp->next = list2;}
}
//链表1赋值替换链表2
void replaceList(Node* list1, Node*& list2) {// 释放链表 list2 的内存while (list2 != nullptr) {Node* temp = list2;list2 = list2->next;delete temp;}// 复制链表 list1 的节点到 list2Node* current = list1;Node* head_1 = nullptr;//head_1为head_1链表的头节点地址while (current != nullptr) {Node* newNode = new Node;newNode->x = current->x;newNode->y = current->y;newNode->next = nullptr;if (head_1 == nullptr) {head_1 = newNode;}else {Node* temp = head_1;while (temp->next != nullptr) {//循环遍历head_1链表（中已存放的newNode）temp = temp->next;//找到末尾的空地址}temp->next = newNode;//新newNode数据添加到已存放的newNode末尾}current = current->next;}list2 = head_1;//将head_1链表首地址赋值给list2首地址，指针的值复制
}
//计算链表size
template<typename T>
int getListSize(T*& head) {int size = 0;T* current = head;while (current != nullptr) {size++;current = current->next;}return size;
}
// 从链表中随机选择节点
Node* getRandomNode(Node* head) {int length = getListSize(head);// 生成随机数种子std::srand(static_cast<unsigned int>(std::time(nullptr)));// 生成随机索引int randomIndex = std::rand() % length;Node* current = head;for (int i = 0; i < randomIndex; i++) {current = current->next;}return current;
}
template<typename T>
void printList(T* head) {T* temp = head;while (temp != nullptr) {std::cout << "(" << temp->x << ", " << temp->y << ") ";temp = temp->next;}std::cout << std::endl;
}
// 获取链表中特定索引位置的指针
Node* getValueAtIndex(Node* head, int index) {Node* temp = head;int currentIndex = 0;while (temp != nullptr) {if (currentIndex == index) {return temp; // 返回节点的值（或你想要获取的值）}temp = temp->next;currentIndex++;}return nullptr;// 如果索引超出链表长度，可以根据具体情况进行错误处理// 在此示例中，我们返回一个默认值 -1.0/*return -1.0;*/
}
constexpr double TOLERANCE = 2.0; // 用于计算直线拟合的容差值
constexpr int MAX_ITERATIONS = 100; // RANSAC算法的最大迭代次数
constexpr int MIN_POINTS = 15; // 拟合直线所需的最小点数
constexpr int MIN_INLIERS = 20; // 拟合直线所需的最小内点数// 生成随机数
double generateRandomNumber(double min, double max) {return min + static_cast<double>(std::rand()) / (RAND_MAX / (max - min));
}// RANSAC拟合直线
LineNode* ransac(Node*& points) {std::srand(std::time(nullptr)); // 初始化随机种子//Line bestLine;LineNode* bestLine = nullptr;int bestInliers = 0;int size = getListSize(points);for (int i = 0; i < MAX_ITERATIONS; ++i) {//随机从链表中选择两个不相同的点，生成随机数种子//生成随机索引int randomIndex1 = std::rand() % size;Node* randomNode1 = getValueAtIndex(points, randomIndex1);int randomIndex2 = std::rand() % size;while (randomIndex1 == randomIndex2) {randomIndex2 = std::rand() % size;}Node* randomNode2 = getValueAtIndex(points, randomIndex2);// 统计内点数int inliers = 0;double slope = 0;double intercept = 0;// 计算直线参数if (randomNode1 != nullptr && randomNode2 != nullptr) {slope = (randomNode2->y - randomNode1->y) / (randomNode2->x - randomNode1->x);intercept = randomNode1->y - slope * randomNode1->x;Node* current = points;   while (current != nullptr) {double d = std::abs(current->y - slope * current->x - intercept);if (d < TOLERANCE) {++inliers;}current = current->next;}// 内点数最多的直线，更新最优直线if (inliers > bestInliers && inliers >= MIN_INLIERS) {bestInliers = inliers;addLineNode(bestLine, slope, intercept);}}}cout << "bestInliers:" << bestInliers << endl;return bestLine;
}

int main() {std::srand(std::time(nullptr)); // 初始化随机种子// 生成随机点Node* points = nullptr;for (int i = 0; i < 100; ++i) {double x = generateRandomNumber(-10.0, 10.0);double y = 2.0 * x + generateRandomNumber(-1.0, 1.0); // 两条直线的斜率分别为2和-2addNode(points, x, y);}Node* points1 = nullptr;for (int i = 0; i < 100; ++i) {double x = generateRandomNumber(-10.0, 10.0);double y = -2.0 * x + generateRandomNumber(-1.0, 1.0); // 两条直线的斜率分别为2和-2addNode(points1, x, y);}appendList(points, points1);printList(points);//线段最长的double max_line_length = 0;//循环计数int index = 0;//符合墙面线要求的索引，方便求出符合要求的直线int model_index=0;//RANSAC拟合直线,假设提前知道在一百条以内LineNode* lines[100];int points_Size = 0;points_Size=getListSize(points);while (points_Size >= MIN_POINTS) {//循环条件        cout << "points变化size"<<index<<":" << points_Size << endl;LineNode* line = ransac(points);//如果拟合不出直线则退出if (line==nullptr) {break;}cout << "best" << line->slope << " " << line->intercept << endl;lines[index]=line;//外点，从数据中移除拟合的内点Node* remainingPoints = nullptr;//内点，提取内点Node* interiorPoint = nullptr;for (Node* current = points; current!=nullptr ; current=current->next){double d = std::abs(current->y - line->slope * current->x - line->intercept);if (d >= TOLERANCE) {addNode(remainingPoints, current->x, current->y);}else {addNode(interiorPoint, current->x, current->y);}}int interiorPoint_Size = getListSize(interiorPoint);cout << "内点数目" << interiorPoint_Size << endl;int remainingPoints_Size = getListSize(remainingPoints);cout << "外点数目" << remainingPoints_Size<< endl;//寻找内点中最大和最小的点double maxdist=findMaxDist(interiorPoint);cout << "横向最大距离" << maxdist << endl;//内点求满足一定范围斜率且横向长度最长的//if (-tan(45)<line->slope<tan(45) && maxdist> max_line_length) {//        max_line_length = maxdist;//        model_index = index;//}//计算符合条件的直线方程if (0 < abs(line->slope) && maxdist> max_line_length) {max_line_length = maxdist;model_index = index;}//若没有外点则退出循环if (remainingPoints==nullptr) {break;}replaceList(remainingPoints,points);cout << "------------" << endl;points_Size = getListSize(points);index++;}std::cout << "目标直线方程：y = " << lines[model_index]->slope << "x + " << lines[model_index]->intercept << std::endl;//清除链表内存，即使没有通过newdeleteNodeList(points);deleteNodeList(points1);deleteArryNodeList(lines);

结果：
在这里插入图片描述
**注意：**对于第二种方法，实现过程中一定要注意指针为空的情况，指针为空时会报错：读取访问权限错误。另外拟合直线时，一定要对数据有初步认识，最好先去除离群点再来拟合，容差设置尤为关键，太小可能会拟合不出直线，太大会导致得到的直线不准确。

以上代码均为本人手敲加调试实现，完成不易，转载或引用请注明出处。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/178271.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

最新ssl证书申请与安装配置2024版

最新ssl证书申请与安装配置2024版

最新ssl证书申请与安装配置2024版 目录 最新ssl证书申请与安装配置2024版 1、申请腾讯云ssl证书 2、ssl证书所属域名的验证 2.1、确保你的web服务正常访问“域名”及其子域“www.域名” 2.2、国内或国外均能访问 2.3、.txt文件访问验证 2.4、验证域名 3、下载签发的ss…
阅读更多...
视频编码转换技巧：视频批量转码H264转H265，高效且顺畅

视频编码转换技巧：视频批量转码H264转H265，高效且顺畅

随着数字媒体的广泛应用&#xff0c;视频编码转换已成为一种普遍的需求。不同的视频格式和编码标准使得在不同设备上播放视频成为可能&#xff0c;同时也带来了兼容性和传输效率的问题。本文讲解引用云炫AI智剪使视频编码转换技巧&#xff0c;即批量将H264编码转换为H265编码&a…
阅读更多...
算法通过村第十八关-回溯|青铜笔记|什么叫回溯（后篇）

算法通过村第十八关-回溯|青铜笔记|什么叫回溯（后篇）

文章目录 前言回溯热身问题输出二叉树的所有路径&#xff1a;路径总和问题&#xff1a; 总结 前言 提示&#xff1a;今夜思量千条路&#xff0c;明朝依旧卖豆腐。 --谚语 回溯是非常重要的算法思想之一&#xff0c;主要解决一些暴力枚举也搞不定的问题&#xff08;这里埋个坑&a…
阅读更多...
使用 Python 进行自然语言处理第 5 部分：文本分类

使用 Python 进行自然语言处理第 5 部分：文本分类

一、说明 关于文本分类&#xff0c;文章已经很多&#xff0c;本文这里有实操代码&#xff0c;明确而清晰地表述这种过程&#xff0c;是实战工程师所可以参照和依赖的案例版本。 本文是 2023 年 1 月的 WomenWhoCode 数据科学跟踪活动提供的会议系列文章中的一篇。 之前的文章在…
阅读更多...
使用虚拟合成数据训练对象检测模型

使用虚拟合成数据训练对象检测模型

监督式机器学习 &#xff08;ML&#xff09; 彻底改变了人工智能&#xff0c;并催生了众多创新产品。然而&#xff0c;对于监督式机器学习&#xff0c;总是需要更大、更复杂的数据集&#xff0c;而收集这些数据集的成本很高。如何确定标签质量&#xff1f;如何确保数据代表生产…
阅读更多...
100量子比特启动实用化算力标准！玻色量子重磅发布相干光量子计算机

100量子比特启动实用化算力标准！玻色量子重磅发布相干光量子计算机

2023年5月16日&#xff0c;北京玻色量子科技有限公司&#xff08;以下简称“玻色量子”&#xff09;在北京正大中心成功召开了2023年首场新品发布会&#xff0c;重磅发布了自研100量子比特相干光量子计算机——“天工量子大脑”。 就在3个月前&#xff0c;因“天工量子大脑”在…
阅读更多...
关于idea使用的一些操作设置

关于idea使用的一些操作设置

关于idea使用的一些操作设置 1. 常用的一下设置1.1 快捷键相关1.2 配置自动生成注释&#xff08;类、方法等&#xff09;1.3 maven项目相关1.4 常见其他的一些操作设置 2. IntelliJ IDEA 取消param注释中参数报错提示3. idea同时打开多个文件&#xff0c;导航栏不隐藏、自动换行…
阅读更多...
1m照片手机怎么拍？这样操作真的很简单！

1m照片手机怎么拍？这样操作真的很简单！

在生活中&#xff0c;使用手机拍照时&#xff0c;会发现拍摄的照片比较大&#xff0c;而自己的拍摄需求并不需要很清晰的照片&#xff0c;只需要保留照片里的内容信息&#xff0c;那么&#xff0c;1m以内的照片怎么拍&#xff1f;下面介绍了三种方法。 方法一&#xff1a;调整手…
阅读更多...
DBA笔记（1）

DBA笔记（1）

目录 1、rpm yum 命令的使用&#xff0c;参数的含义 rpm命令&#xff1a; yum命令&#xff1a; 2、上传镜像至虚拟机搭建本地yum源 3、chown chomd 命令每一个参数的含义 chown命令&#xff1a; chmod命令&#xff1a; 4、fdisk partd 硬盘分区命令用法 fdisk命令&am…
阅读更多...
windows搭建Cobalt strike

windows搭建Cobalt strike

使用cobaltstrike 3.14版本 window10搭建服务器 默认端口可以修改的 window10搭建客户端 双击客服端bat运行连接 监听器 windows/beacon为内置监听器&#xff0c;包括dns、http、https、smb、tcp、extc2六种方式的监听器&#xff1b;windows/foreign为外部监听器 wndows/be…
阅读更多...
2023最新ChatGPT商业运营系统源码+支持GPT4/支持ai绘画+支持Midjourney绘画

2023最新ChatGPT商业运营系统源码+支持GPT4/支持ai绘画+支持Midjourney绘画

一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…
阅读更多...
蓝桥白皮书16.0版——2、蓝桥等考介绍及代报名方式、报名时间

蓝桥白皮书16.0版——2、蓝桥等考介绍及代报名方式、报名时间

等级考试综述 蓝桥等考全称为“蓝桥青少年信息技术等级考试” 。等级考试聚焦学生学习过程的跟 踪评价 &#xff0c;以考促学 &#xff0c;标准化中小学校教学、校外机构培训和家长学生自学的学习目标及学习进程。 等级考试命题原则 等级考试各组别考试范围是掌握该组别编程知识…
阅读更多...
【Java|golang】2103. 环和杆---位运算

【Java|golang】2103. 环和杆---位运算

总计有 n 个环&#xff0c;环的颜色可以是红、绿、蓝中的一种。这些环分别穿在 10 根编号为 0 到 9 的杆上。 给你一个长度为 2n 的字符串 rings &#xff0c;表示这 n 个环在杆上的分布。rings 中每两个字符形成一个 颜色位置对 &#xff0c;用于描述每个环&#xff1a; 第 …
阅读更多...
ANGR初识

ANGR初识

首页&#xff1a; https://angr.io 项目存储库&#xff1a; GitHub - angr/angr: A powerful and user-friendly binary analysis platform! 文档&#xff1a; https://docs.angr.io API 文档&#xff1a; angr documentation 练习项目&#xff1a; https://github.com/angr/an…
阅读更多...
MSQL系列(十一) Mysql实战-Inner Join算法底层原理及驱动表选择

MSQL系列(十一) Mysql实战-Inner Join算法底层原理及驱动表选择

Mysql实战-Inner Join算法驱动表选择 前面我们讲解了BTree的索引结构&#xff0c;及Mysql的存储引擎MyISAM和InnoDB,也详细讲解下 left Join的底层驱动表 选择, 并且初步了解 Inner join是Mysql 主动选择优化的驱动表&#xff0c;知道索引要建立在被驱动表上 那么对于Inner j…
阅读更多...
“排队领奖，购物狂欢！开启全新商业模式

“排队领奖，购物狂欢！开启全新商业模式

欢迎来到这个充满惊喜的商业模式——工会排队奖励模式&#xff01;在这个时代&#xff0c;你是否感到购物和消费的乐趣被平淡无奇的模式所限制&#xff1f;那么&#xff0c;这个全新的商业模式将带你进入一个充满刺激和惊喜的世界&#xff01; 想象一下&#xff0c;当你购物时&…
阅读更多...
AutoX.js - openCV多分辨率找图

AutoX.js - openCV多分辨率找图

AutoX.js - openCV多分辨率找图 一、起因 AutoXjs 中有两个找图相关的方法 findImage 和 matchTemplate&#xff0c;之前一直没发现什么问题&#xff0c;但最近在一次测试找图时&#xff0c;明明大图和模板图的轮廓都清晰&#xff0c;却怎么也找不到图&#xff0c;降低阈值参…
阅读更多...
C语言 每日一题 11

C语言 每日一题 11

1.使用函数求素数和 本题要求实现一个判断素数的简单函数、以及利用该函数计算给定区间内素数和的函数。 素数就是只能被1和自身整除的正整数。注意&#xff1a;1不是素数&#xff0c;2是素数。 函数接口定义&#xff1a; int prime(int p); int PrimeSum(int m, int n); 其中…
阅读更多...
云原生环境下JAVA应用容器JVM内存如何配置？—— 筑梦之路

云原生环境下JAVA应用容器JVM内存如何配置？—— 筑梦之路

Docker环境下的JVM参数非定值配置 —— 筑梦之路_docker jvm设置-CSDN博客 之前简单地记录过一篇&#xff0c;这里在之前的基础上更加细化一下。 场景说明 使用Java开发且设置的JVM堆空间过小时&#xff0c;程序会出现系统内存不足OOM&#xff08;Out of Memory&#xff09;的…
阅读更多...
Java实验二类编程实验

Java实验二类编程实验

1.编写一个代表三角形的类&#xff08;Triangle.java&#xff09;。 其中&#xff0c;三条边a,b,c&#xff08;数据类型为double类型&#xff09;为三角形的属性&#xff0c;该类封装有求三角形的面积和周长的方法。分别针对三条边为3、4、5和7、8、9的两个三角形进行测试&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023