OpenCV结构分析与形状描述符（21）计算包围给定点集的最小面积三角形函数minEnclosingTriangle()的使用

embedded/2024/9/23 15:16:14/

操作系统：ubuntu22.04
OpenCV版本：OpenCV4.9
IDE:Visual Studio Code
编程语言：C++11

算法描述

找到一个包围二维点集的最小面积三角形，并返回其面积。

该函数找到一个包围给定的二维点集的最小面积三角形，并返回其面积。给定的二维点集的输出结果如下面的图所示。二维点用红色表示，包围的三角形用黄色表示：
在这里插入图片描述
该算法的实现基于 O’Rourke 的 206和 Klee 与 Laskowski 的 144论文。O’Rourke 提供了一个 θ(n) 的算法来寻找具有 n 个顶点的二维凸多边形的最小包围三角形。由于 minEnclosingTriangle 函数接收一个二维点集作为输入，因此需要一个额外的预处理步骤来计算该二维点集的凸包。凸包（convexHull）函数的时间复杂度是 O(nlog(n))，这比 θ(n) 要高。因此，该函数的总体复杂度是 O(nlog(n))

函数原型

double cv::minEnclosingTriangle	
(InputArray 	points,OutputArray 	triangle 
)

参数

参数points 输入的二维点向量，深度为 CV_32S 或 CV_32F，存储在 std::vector<> 或 Mat 中。
参数triangle 输出的三维点向量，定义三角形的三个顶点。OutputArray 的深度必须为 CV_32F。

返回值

返回的是三角形的面积

代码示例


#include <iostream>
#include <opencv2/opencv.hpp>
#include <vector>int main()
{// 创建一个空白的图像cv::Mat image = cv::Mat::zeros( 300, 300, CV_8UC3 );// 构造一个包含多个点的向量std::vector< cv::Point2f > points;points.push_back( cv::Point2f( 100, 100 ) );points.push_back( cv::Point2f( 150, 90 ) );points.push_back( cv::Point2f( 150, 140 ) );points.push_back( cv::Point2f( 200, 100 ) );points.push_back( cv::Point2f( 150, 150 ) );points.push_back( cv::Point2f( 160, 155 ) );points.push_back( cv::Point2f( 100, 200 ) );points.push_back( cv::Point2f( 200, 200 ) );// 定义输出变量std::vector< cv::Point2f > triangle;// 计算最小面积三角形cv::minEnclosingTriangle( points, triangle );// 计算三角形的面积float area = cv::contourArea( triangle );// 绘制点集for ( const auto& pt : points ){cv::circle( image, pt, 3, cv::Scalar( 0, 0, 255 ), -1 );  // 绘制红色的小圆圈表示点}// 将 Point2f 转换为 Pointstd::vector< cv::Point > triangleInt;for ( const auto& pt : triangle ){triangleInt.push_back( cv::Point( static_cast< int >( pt.x ), static_cast< int >( pt.y ) ) );}// 将单个点向量转换为 polylines 所需的向量的向量形式std::vector< std::vector< cv::Point > > allTriangles;allTriangles.push_back( triangleInt );// 绘制最小面积三角形if ( triangle.size() == 3 ){cv::polylines( image, allTriangles, true, cv::Scalar( 0, 255, 255 ), 2 );  // 绘制黄色的三角形}// 显示图像cv::imshow( "Min Enclosing Triangle", image );cv::waitKey( 0 );// 输出三角形的面积std::cout << "Area of the enclosing triangle: " << area << std::endl;return 0;
}