实现思路非常简单和直观，本方法针对与二维平面上的凸多边形。多边形顶点坐标数据结构咱就以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
