凸多边形顶点顺逆时针排序

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