实现思路非常简单和直观,本方法针对与二维平面上的凸多边形。多边形顶点坐标数据结构咱就以opencv举例
现有一组凸多边形二维平面坐标数组
//base on opencv
std::vector<cv::Point2f> polygon
- step1 计算凸多边形的质心
计算质心的方法非常简单,就是分区计算x、y坐标的平均值
cv::Point2f centroid = {0.0f, 0.0f};
for(const auto& pt: polygon)
{
centroid.x += pt.x;
centroid.y += pt.y;
}
auto count = polygon.size();
centroid.x = centroid.x / count;
centroid.y = centroid.y / count;
- step2: 将质心作为坐标系原点建立坐标系
以质心坐标作为参考基准,多边形顶点减去质心坐标,就可以将多边形转换为以质心作为原点的坐标表示
for(auto& pt: polygon)
{
auto offset_pt = pt - centroid;
//...下一步处理
}
- step3: 计算每个顶点与质心连线的角度,并基于角度排序
到这一步就很直观了,质心在凸多边形内部,作为坐标系原点。根据顶点的角度排序后,坐标数组自然是成顺时针或逆时针排序的。计算角度的方法我们采用opencv的反三角计算函数
cv::fastAtan2(pt.y, pt.x); //返回值为0-360度的角度值
至于排序,比较方便的方法是基于c++11的lambda表达式特性,写一个匿名函数就可以丢进sort函数里面进行排序,关于根据lambda表达式更多介绍可以参考我这篇笔记使用lambda表达式对自定义对象数组进行排序。下面直接给出代码
auto cmp_angle = [&](cv::Point2f& a, cv::Point2f& b)
{
//将转换坐标系写进匿名函数
auto a_offset = a - centroid;
auto b_offset = b - centroid;
//按角度升序排序(顺时针),若需要逆时针将小于号改为大于号即可
//opencv图像坐标系为如下图,角度升序对应顺时针
//(0,0)----------------------x+-------->
// .
// .
// y+
// .
// V
return cv::fastAtan2(a_offset.y, a_offset.x) < cv::fastAtan2(b_offset.y, b_offset.x);
};
std::sort(polygon.begin(), polygon.end(), cmp_angle);
最后,完整的代码如下
#include "opencv2/opencv.hpp"
//base on opencv
std::vector<cv::Point2f> polygon;
//step1
cv::Point2f centroid = {0.0f, 0.0f};
for(const auto& pt: polygon)
{
centroid.x += pt.x;
centroid.y += pt.y;
}
auto count = polygon.size();
centroid.x = centroid.x / count;
centroid.y = centroid.y / count;
auto cmp_angle = [&](cv::Point2f& a, cv::Point2f& b)
{
//step2
//将转换坐标系写进匿名函数
auto a_offset = a - centroid;
auto b_offset = b - centroid;
//按角度升序排序(顺时针),若需要逆时针将小于号改为大于号即可
//opencv图像坐标系为如下图,角度升序对应顺时针
//(0,0)----------------------x+-------->
// .
// .
// y+
// .
// V
//step3
return cv::fastAtan2(a_offset.y, a_offset.x) < cv::fastAtan2(b_offset.y, b_offset.x);
};
std::sort(polygon.begin(), polygon.end(), cmp_angle);
我们简单测试一下,将以下顺时针数据打乱后输入排序
//顺时针 {12.0, 3.0} { 12.0, 20.0} {0.0, 13.0} {-11.0, 12.0} {-12.0, 0。0} {-11.0, -12.0} {0.0, -15.0}
std::vector<cv::Point2f> polygon;
polygon.push_back({ 12.0f, 20.0f });
polygon.push_back({ 12.0f, 3.0f });
polygon.push_back({ -11.0f, 12.0f });
polygon.push_back({ 0.0f, 13.0f });
polygon.push_back({ 0.0f, -15.0f });
polygon.push_back({ -11.0f, -12.0f });
polygon.push_back({ -12.0f, 0.0f });
测试代码如下:
// polygon vertices sort by angle
// @mango
#include "opencv2/opencv.hpp"
//base on opencv
int main()
{
//顺时针 {12.0, 3.0} { 12.0, 20.0} {0.0, 13.0} {-11.0, 12.0} {-12.0, 0。0} {-11.0, -12.0} {0.0, -15.0}
std::vector<cv::Point2f> polygon;
polygon.push_back({ 12.0f, 20.0f });
polygon.push_back({ 12.0f, 3.0f });
polygon.push_back({ -11.0f, 12.0f });
polygon.push_back({ 0.0f, 13.0f });
polygon.push_back({ 0.0f, -15.0f });
polygon.push_back({ -11.0f, -12.0f });
polygon.push_back({ -12.0f, 0.0f });
//step1
cv::Point2f centroid = { 0.0f, 0.0f };
for (const auto& pt : polygon)
{
centroid.x += pt.x;
centroid.y += pt.y;
}
auto count = polygon.size();
centroid.x = centroid.x / count;
centroid.y = centroid.y / count;
auto cmp_angle = [&](cv::Point2f& a, cv::Point2f& b)
{
//step2
//将转换坐标系写进匿名函数
auto a_offset = a - centroid;
auto b_offset = b - centroid;
//按角度升序排序(顺时针),若需要逆时针将小于号改为大于号即可
//opencv图像坐标系为如下图,角度升序对应顺时针
//(0,0)----------------------x+-------->
// .
// .
// y+
// .
// V
//step3
return cv::fastAtan2(a_offset.y, a_offset.x) < cv::fastAtan2(b_offset.y, b_offset.x);
};
std::sort(polygon.begin(), polygon.end(), cmp_angle);
for (auto& pt : polygon)
{
std::cout << pt << std::endl;
}
return 0;
}
测试结果
[12, 3]
[12, 20]
[0, 13]
[-11, 12]
[-12, 0]
[-11, -12]
[0, -15]
本文由芒果浩明发布,转载请注明出处。
本文链接:https://mangoroom.cn/opencv/sort-polygon-vertices-as-clockwise-or-anticlockwise.html
Windows 10Chrome 109.0.0.0
为什么要选用质点作为坐标系的中心?选择多边形外部的点 为啥不行? 原理是什么呢?谢谢
为了减少轮廓排序可能发生错误的情况,你画一个五角星。用其中一个角的点时钟方向排一下就知道了。
Windows 10Chrome 103.0.5060.114
感谢分享,希望加个微信好友(我的微信:bianzici),我是opencv初学者。
请教一个问题,为什么我用approxPolyDP得到的多边形顶点数据是乱七八糟的?还得我自己写个函数来对它们进行顺时针排序?
注意看看第四个参数close,选闭合看看。算法默认是已经排序的才对