C++ 计算凸包点的最小旋转矩形

RotateRect.h


#include <vector>/**
* @brief 计算点集最小旋转外接矩形
*/
class RotateRect {
public:enum { CALIPERS_MAXHEIGHT = 0, CALIPERS_MINAREARECT = 1, CALIPERS_MAXDIST = 2 };struct Point {float x, y;};using Points = std::vector<Point>;struct Sizef {float width, height;};struct Rect {float left, top, right, bottom;};explicit RotateRect(const Points& pts);const Point& center() const;const Sizef& size() const;float angle() const;
public:void update();Points toPoints() const;Rect getOutLine() const;private:double crossProduct(const Point& A, const Point& B, const Point& C) const;double calculateDistance(const Point& A, const Point& B) const;Points convexHull() const;/* we will use usual cartesian coordinates */void rotatingCalipers(const Point* pts, int n, int mode, float* out) const;private:const Points& m_inputs;Point m_center;//! returns width and height of the rectangleSizef m_size;//! returns the rotation angle. When the angle is 0, 90, 180, 270 etc., the rectangle becomes an up-right rectangle.float m_angle;
};

 RotateRect.cpp


#include "RotateRect.h"
#include <cmath>
#include <assert.h>#ifndef CV_PI
#define CV_PI   3.1415926535897932384626433832795
#endifRotateRect::RotateRect(const RotateRect::Points& pts) : m_inputs(pts), m_angle(0), m_size{ 0, 0 }, m_center{ 0, 0 } {}/** @brief 计算BA与CA之间面积* @param [in] A 点* @param [in] B 点* @param [in] C 点* @returnBA x CA > 0, C在B的逆时针方向,B在C右边BA x CA < 0, C在B的顺时针方向,B在C左边BA x CA = 0, C和B共线,可能正方向,也可能反方向*/
double RotateRect::crossProduct(const RotateRect::Point& A, const RotateRect::Point& B, const RotateRect::Point& C) const {return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}/** @brief 找到x方向最小点为起始点,查找所有点最右边点,到起始点结束* @return 所有凸包点,逆时针方向*/
RotateRect::Points RotateRect::convexHull() const {const auto& points = m_inputs;int n = points.size();if (n <= 3) {return points;}std::vector<Point> hull;int l = 0;for (int i = 1; i < n; i++) {if (points[i].x < points[l].x) {l = i;}}int p = l, q;do {hull.push_back(points[p]);q = (p + 1) % n;for (int i = 0; i < n; i++) {if (crossProduct(points[p], points[i], points[q]) > 0) {q = i;}}p = q;} while (p != l);return hull;
}double RotateRect::calculateDistance(const RotateRect::Point& A, const RotateRect::Point& B) const {return std::sqrt(std::pow(B.x - A.x, 2) + std::pow(B.y - A.y, 2));
}void rotate90CCW(const RotateRect::Point& in, RotateRect::Point& out)
{out.x = -in.y;out.y = in.x;
}void rotate90CW(const RotateRect::Point& in, RotateRect::Point& out)
{out.x = in.y;out.y = -in.x;
}void rotate180(const RotateRect::Point& in, RotateRect::Point& out)
{out.x = -in.x;out.y = -in.y;
}/* return true if first vector is to the right (clockwise) of the second */
bool firstVecIsRight(const RotateRect::Point& vec1, const RotateRect::Point& vec2)
{RotateRect::Point tmp;rotate90CW(vec1, tmp);return tmp.x * vec2.x + tmp.y * vec2.y < 0;
}/** @brief 计算凸包点的最小旋转矩形*//* we will use usual cartesian coordinates */
void RotateRect::rotatingCalipers(const RotateRect::Point* points, int n, int mode, float* out) const
{using Point = RotateRect::Point;float minarea = FLT_MAX;float max_dist = 0;char buffer[32] = {};int i, k;std::vector<float> abuf(n * 3);float* inv_vect_length = abuf.data();Point* vect = (Point*)(inv_vect_length + n);int left = 0, bottom = 0, right = 0, top = 0;int seq[4] = { -1, -1, -1, -1 };Point rot_vect[4];/* rotating calipers sides will always have coordinates(a,b) (-b,a) (-a,-b) (b, -a)*//* this is a first base vector (a,b) initialized by (1,0) */float orientation = 0;float base_a;float base_b = 0;float left_x, right_x, top_y, bottom_y;Point pt0 = points[0];left_x = right_x = pt0.x;top_y = bottom_y = pt0.y;for (i = 0; i < n; i++){double dx, dy;if (pt0.x < left_x)left_x = pt0.x, left = i;if (pt0.x > right_x)right_x = pt0.x, right = i;if (pt0.y > top_y)top_y = pt0.y, top = i;if (pt0.y < bottom_y)bottom_y = pt0.y, bottom = i;Point pt = points[(i + 1) & (i + 1 < n ? -1 : 0)];dx = pt.x - pt0.x;dy = pt.y - pt0.y;vect[i].x = (float)dx;vect[i].y = (float)dy;inv_vect_length[i] = (float)(1. / std::sqrt(dx * dx + dy * dy));pt0 = pt;}// find convex hull orientation{double ax = vect[n - 1].x;double ay = vect[n - 1].y;for (i = 0; i < n; i++){double bx = vect[i].x;double by = vect[i].y;double convexity = ax * by - ay * bx;if (convexity != 0){orientation = (convexity > 0) ? 1.f : (-1.f);break;}ax = bx;ay = by;}assert(orientation != 0);}base_a = orientation;/*****************************************************************************************//*                         init calipers position                                        */seq[0] = bottom;seq[1] = right;seq[2] = top;seq[3] = left;/*****************************************************************************************//*                         Main loop - evaluate angles and rotate calipers               *//* all of edges will be checked while rotating calipers by 90 degrees */for (k = 0; k < n; k++){/* number of calipers edges, that has minimal angle with edge */int main_element = 0;/* choose minimum angle between calipers side and polygon edge by dot product sign */rot_vect[0] = vect[seq[0]];rotate90CW(vect[seq[1]], rot_vect[1]);rotate180(vect[seq[2]], rot_vect[2]);rotate90CCW(vect[seq[3]], rot_vect[3]);for (i = 1; i < 4; i++){if (firstVecIsRight(rot_vect[i], rot_vect[main_element]))main_element = i;}/*rotate calipers*/{//get next baseint pindex = seq[main_element];float lead_x = vect[pindex].x * inv_vect_length[pindex];float lead_y = vect[pindex].y * inv_vect_length[pindex];switch (main_element){case 0:base_a = lead_x;base_b = lead_y;break;case 1:base_a = lead_y;base_b = -lead_x;break;case 2:base_a = -lead_x;base_b = -lead_y;break;case 3:base_a = -lead_y;base_b = lead_x;break;default:assert("main_element should be 0, 1, 2 or 3" && false);}}/* change base point of main edge */seq[main_element] += 1;seq[main_element] = (seq[main_element] == n) ? 0 : seq[main_element];switch (mode){case RotateRect::CALIPERS_MAXHEIGHT:{/* now main element lies on edge aligned to calipers side *//* find opposite element i.e. transform  *//* 0->2, 1->3, 2->0, 3->1                */int opposite_el = main_element ^ 2;float dx = points[seq[opposite_el]].x - points[seq[main_element]].x;float dy = points[seq[opposite_el]].y - points[seq[main_element]].y;float dist;if (main_element & 1)dist = (float)fabs(dx * base_a + dy * base_b);elsedist = (float)fabs(dx * (-base_b) + dy * base_a);if (dist > max_dist)max_dist = dist;}break;case RotateRect::CALIPERS_MINAREARECT:/* find area of rectangle */{float height;float area;/* find vector left-right */float dx = points[seq[1]].x - points[seq[3]].x;float dy = points[seq[1]].y - points[seq[3]].y;/* dotproduct */float width = dx * base_a + dy * base_b;/* find vector left-right */dx = points[seq[2]].x - points[seq[0]].x;dy = points[seq[2]].y - points[seq[0]].y;/* dotproduct */height = -dx * base_b + dy * base_a;area = width * height;if (area <= minarea){float* buf = (float*)buffer;minarea = area;/* leftist point */((int*)buf)[0] = seq[3];buf[1] = base_a;buf[2] = width;buf[3] = base_b;buf[4] = height;/* bottom point */((int*)buf)[5] = seq[0];buf[6] = area;}}break;}                       /*switch */}                           /* for */switch (mode){case RotateRect::CALIPERS_MINAREARECT:{float* buf = (float*)buffer;float A1 = buf[1];float B1 = buf[3];float A2 = -buf[3];float B2 = buf[1];float C1 = A1 * points[((int*)buf)[0]].x + points[((int*)buf)[0]].y * B1;float C2 = A2 * points[((int*)buf)[5]].x + points[((int*)buf)[5]].y * B2;float idet = 1.f / (A1 * B2 - A2 * B1);float px = (C1 * B2 - C2 * B1) * idet;float py = (A1 * C2 - A2 * C1) * idet;out[0] = px;out[1] = py;out[2] = A1 * buf[2];out[3] = B1 * buf[2];out[4] = A2 * buf[4];out[5] = B2 * buf[4];}break;case RotateRect::CALIPERS_MAXHEIGHT:{out[0] = max_dist;}break;}
}void RotateRect::update()
{using Point = RotateRect::Point;std::vector<Point> hull;Point out[3];hull = convexHull();int n = hull.size();const Point* hpoints = &hull[0];if (n > 2){rotatingCalipers(hpoints, n, RotateRect::CALIPERS_MINAREARECT, (float*)out);m_center.x = out[0].x + (out[1].x + out[2].x) * 0.5f;m_center.y = out[0].y + (out[1].y + out[2].y) * 0.5f;m_size.width = (float)std::sqrt((double)out[1].x * out[1].x + (double)out[1].y * out[1].y);m_size.height = (float)std::sqrt((double)out[2].x * out[2].x + (double)out[2].y * out[2].y);m_angle = (float)atan2((double)out[1].y, (double)out[1].x);}else if (n == 2){m_center.x = (hpoints[0].x + hpoints[1].x) * 0.5f;m_center.y = (hpoints[0].y + hpoints[1].y) * 0.5f;double dx = hpoints[1].x - hpoints[0].x;double dy = hpoints[1].y - hpoints[0].y;m_size.width = (float)std::sqrt(dx * dx + dy * dy);m_size.height = 0;m_angle = (float)atan2(dy, dx);}else{if (n == 1)m_center = hpoints[0];}m_angle = (float)(m_angle * 180 / CV_PI);
}RotateRect::Points RotateRect::toPoints() const
{RotateRect::Points pt(4);double _angle = m_angle * CV_PI / 180.;float b = (float)cos(_angle) * 0.5f;float a = (float)sin(_angle) * 0.5f;pt[0].x = m_center.x - a * m_size.height - b * m_size.width;pt[0].y = m_center.y + b * m_size.height - a * m_size.width;pt[1].x = m_center.x + a * m_size.height - b * m_size.width;pt[1].y = m_center.y - b * m_size.height - a * m_size.width;pt[2].x = 2 * m_center.x - pt[0].x;pt[2].y = 2 * m_center.y - pt[0].y;pt[3].x = 2 * m_center.x - pt[1].x;pt[3].y = 2 * m_center.y - pt[1].y;return pt;
}const RotateRect::Point& RotateRect::center() const {return m_center;
}const RotateRect::Sizef& RotateRect::size() const {return m_size;
}float RotateRect::angle() const {return m_angle;
}RotateRect::Rect RotateRect::getOutLine() const {if (m_inputs.empty())return { 0, 0, 0, 0 };using Number = std::numeric_limits<float>;RotateRect::Rect rect{ Number::max(), Number::max(), Number::min(), Number::min() };for (const auto& point : m_inputs) {if (point.x < rect.left)rect.left = point.x;if (point.x > rect.right)rect.right = point.x;if (point.y < rect.top)rect.top = point.y;if (point.y > rect.bottom)rect.bottom = point.y;}return rect;
}

main.cpp


RotateRect::Points myPoints = { {233, 86}, {322, 106}, {214, 154}, {307, 176}, {286, 209}, {331, 183}, {346, 319}, {392, 294}, {356, 346}, {419, 311}, {419, 311}, {778, 1031}, {840, 995} };RotateRect myRotateRect(myPoints);myRotateRect.update();

 


创作不易,小小的支持一下吧!

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

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

相关文章

微服务SpringCloud ES分布式全文搜索引擎简介 下载安装及简单操作入门

Elasticsearch ES简介 Elasticsearch&#xff08;简称ES&#xff09;是一个开源的分布式搜索和分析引擎&#xff0c;常用于全文搜索、日志存储和分析等场景。它构建在Apache Lucene搜索引擎库之上&#xff0c;提供了一个分布式的多租户能力&#xff0c;支持大规模的数据处理。…

网络编程5----初识http

1.1 请求和响应的格式 http协议和前边学过的传输层、网络层协议不同&#xff0c;它是“一问一答”形式的&#xff0c;所以要分为请求和响应两部分看待&#xff0c;同时&#xff0c;请求和响应的格式是不同的&#xff0c;我们来具体介绍一下。 1.1.1 请求 在介绍请求之前&…

将自己md文件发布到自己的博客园实现文件的持久化存储

上传markdown文件到博客园 目录 【0】需求原因【1】功能【2】环境【最佳实践测试】 &#xff08;1&#xff09;查看 Typora 设置&#xff08;2&#xff09;配置 pycnblog 配置文件 config.yaml&#xff08;3&#xff09;运行 pycnblog 中的文件 cnblog_markdown.cmd&#xff0…

自杀行为的神经生物学认识

自杀行为的神经生物学认识 编译 李升伟 隐藏在自杀行为背后的大脑生化机制正引领人类对自杀的认识从黑暗步入光明。科学家希望未来这些机制能带来更好的治疗和预防策略。 基斯 • 范希林根&#xff08;Cornelis Van Heeringen&#xff09;第一次遇见瓦莱丽&#xff08; Va…

Java用文件流mask文本文件某些特定字段

思路 在Java中&#xff0c;如果你想要掩码&#xff08;mask&#xff09;文本文件中的某些特定字段&#xff0c;你可以按照以下步骤进行&#xff1a; 读取文本文件内容。找到并识别需要掩码的字段。用特定的掩码字符&#xff08;如星号*&#xff09;替换这些字段。将修改后的内…

Leetcode Hot100之双指针

1. 移动零 题目描述 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。解题思路 双指针遍历一遍即可解决: 我们定义了两个指针 i 和 j&#xf…

浏览器(Browser):轻量级浏览器,高效浏览新体验

在可的哥桌面&#xff08;Codigger Desktop&#xff09;&#xff0c;我们始终秉持创新精神&#xff0c;致力于提供卓越的用户体验。如今&#xff0c;我们激动地宣布一项全新功能的发布——轻量级浏览器Browser。这款浏览器的推出&#xff0c;正是我们对用户体验追求的再次体现&…

使用自签名 TLS 将 Dremio 连接到 MinIO

Dremio 是一个开源的分布式分析引擎&#xff0c;为数据探索、转换和协作提供简单的自助服务界面。Dremio 的架构建立在 Apache Arrow&#xff08;一种高性能列式内存格式&#xff09;之上&#xff0c;并利用 Parquet 文件格式实现高效存储。有关 Dremio 的更多信息&#xff0c;…

从艳彩山水到艳彩艺术 薛永年:郭泰来艳彩艺术填补了中国美术史的空白

薛永年先生 自6月12日开展以来&#xff0c;郭泰来现代艺术大展杭州如火如荼地进行着&#xff0c;吸引了众多艺术爱好者和专业人士前往。毫不夸张地说&#xff0c;总统和清洁工人都能在他的作品中找到自己心中的那一块共振带并与之产生强烈的共鸣&#xff0c;这便是郭泰来先生的…

目标跟踪算法(bytetrack)-tensorrt部署教程

一、本机安装python环境 conda create -n bytetrace_env python=3.8 activate bytetrace_env conda install pytorch torchvision cudatoolkit=10.1 -c检测GPU是否可用,不可用不行 import torch print(torch.cuda.is_available())安装bytetrack git clone https://github.c…

0.15元1.5Mhz-1.3A同步整流BUCK降压DCDC芯片MT3410(MT3410LB)

前言 国产同步整流DCDC&#xff0c;参考价格约0.15元。 特征 高效率&#xff1a;高达 96% 1.5MHz恒定频率操作 1.3A 输出电流 无需肖特基二极管 2.3V至7V输入电压范围 输出电压低至 0.6V PFM 模式可在轻负载下实现高效率 压差操作中的100%占空比 低静态电流&#xff1a;35μ…

网络爬虫设置代理服务器

目录 1&#xff0e;获取代理 IP 2&#xff0e;设置代理 IP 3. 检测代理 IP 的有效性 4. 处理异常 如果希望在网络爬虫程序中使用代理服务器&#xff0c;就需要为网络爬虫程序设置代理服务器。 设置代理服务器一般分为获取代理 IP 、设置代理 IP 两步。接下来&#xff0c;分…

【数据库备份完整版】物理备份、逻辑备份,mysqldump、mysqlbinlog的备份方法

【数据库备份完整版】物理备份、逻辑备份&#xff0c;mysqldump、mysqlbinlog的备份方法 一、物理备份二、逻辑备份1.mysqldump和binlog备份的方式&#xff1a;2.mysqldump完整备份与恢复数据2.1 mysqldump概念2.2 mysqldump备份2.3 数据恢复2.4 **使用 Cron 自动执行备份**2.5…

机器学习:人工智能的子领域之一

引言 人工智能&#xff08;AI&#xff09;已经成为现代科技的重要组成部分&#xff0c;推动了许多领域的创新与进步。在人工智能的诸多子领域中&#xff0c;机器学习&#xff08;ML&#xff09;无疑是最关键和最具影响力的一个。机器学习通过自动分析和学习数据中的模式&#x…

机器学习算法的电影推荐系统以及票房预测系统

一、实验概述 1. 实验目标 本项目希望基于电影数据集&#xff0c;依据电影的简介、关键词、预算、票房、用户评分等特征来对电影进行分析&#xff0c;并完成以下任务&#xff1a; 对电影特征的可视化分析对电影票房的预测多功能个性化的电影推荐算法 2. 数据集 针对票房预…

湖南科技大学24计算机考研情况,软工学硕考数二,分数线290分,录取均分321分!

湖南科技大学&#xff08;Hunan University of Science and Technology&#xff09;坐落在伟人故里、人文圣地湘潭&#xff0c;处于长株潭核心区域&#xff0c;比邻湘潭九华经济技术开发区&#xff08;国家级&#xff09;&#xff0c;是应急管理部、国家国防科技工业局与湖南省…

自监督分类网络:创新的端到端学习方法

现代人工智能的快速发展中&#xff0c;分类任务的高效解决方案一直备受关注。今天&#xff0c;我们向大家介绍一种名为Self-Classifier的全新自监督端到端分类学习方法。由Elad Amrani、Leonid Karlinsky和Alex Bronstein团队开发&#xff0c;Self-Classifier通过优化同一样本的…

探索C嘎嘎的奇妙世界:第十六关---STL(vector的练习)

1.只出现一次的数字 我们可以使用异或运算来解决这个问题&#xff1a; 异或运算有一个重要的性质&#xff1a;两个相同的数进行异或运算结果为 0&#xff0c;任何数与 0 异或结果为其本身。对于数组中的元素&#xff0c;依次进行异或运算&#xff0c;出现两次的元素异…

智谱API调用

一、智谱API 文心一言api 千帆大模型平台 申请和使用 智谱AI开放平台 登录智谱AI开放平台&#xff0c;点击右上角的开发者工作台&#xff0c;然后查看自己的API glm-4 接口 conda create -n zhipuai python3.10 -y 二、如何使用 这边的介绍是根据官方文档的接口文档来进行介绍…

postman 工具下载安装使用教程_postman安装

本文讲解的是postman工具下载、Postman安装步骤、postman下载、postman安装教程。Postman是一款流行的API测试工具&#xff0c;它提供了一个用户友好的界面&#xff0c;用于发送和测试API请求&#xff0c;并且可以轻松地按需管理和组织请求。 这使得开发人员和测试人员能够更高…