如何对std::vector<cv::Point2i>类型点集进行顺时针排序？

核心思路 #

要实现点的顺时针排序，核心是基于点相对于参考中心的极角来排序。我们选所有点的质心（平均坐标）作为参考中心，它能代表点集的整体位置。在OpenCV的坐标系（原点左上角，x轴向右，y轴向下）中，顺时针方向对应极角从小到大的顺序，按极角递增排序就能得到顺时针排列的点集。

具体实现步骤 #

1. 计算点集的质心 #

质心是所有点的x、y坐标平均值，代码如下：

#include <vector>
#include <opencv2/core.hpp>

cv::Point2i computeCentroid(const std::vector<cv::Point2i>& points) {
    int sumX = 0, sumY = 0;
    for (const auto& p : points) {
        sumX += p.x;
        sumY += p.y;
    }
    // 整数除法适配Point2i的整数类型
    return cv::Point2i(sumX / points.size(), sumY / points.size());
}

2. 执行排序 #

直接使用std::sort结合lambda表达式实现极角比较，逻辑更紧凑：

#include <algorithm>
#include <cmath>

// 假设你的点集是x_y
if (x_y.size() <= 1) {
    // 点数量不足，无需排序
    return;
}

cv::Point2i centroid = computeCentroid(x_y);

std::sort(x_y.begin(), x_y.end(), [centroid](const cv::Point2i& a, const cv::Point2i& b) {
    // 计算单个点相对于质心的极角，转换到0~2π范围
    auto calculateAngle = [&centroid](const cv::Point2i& p) {
        int dx = p.x - centroid.x;
        int dy = p.y - centroid.y;
        // atan2(dy, dx)返回-π~π的弧度值
        double angle = std::atan2(dy, dx);
        // 转换为0~2π，避免负数打乱排序顺序
        return angle < 0 ? angle + 2 * M_PI : angle;
    };

    // 极角小的点排在前面，对应屏幕坐标系的顺时针顺序
    return calculateAngle(a) < calculateAngle(b);
});

关键细节说明 #

• 坐标系适配：OpenCV的y轴向下，与数学坐标系相反，atan2(dy, dx)计算的极角递增顺序正好对应屏幕上的顺时针方向。
• 极角范围处理：将atan2返回的-π_π转换为02π，避免负数导致排序逻辑出错。
• 边界防护：先判断点集大小，避免空集或单点集的无效操作。

内容的提问来源于stack exchange，提问作者user19190785