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

实现思路非常简单和直观，本方法针对与二维平面上的凸多边形。多边形顶点坐标数据结构咱就以opencv举例现有一组凸多边形二维平面坐标数组

1
2


//base on opencv
std::vector<cv::Point2f> polygon

step1 计算凸多边形的质心

计算质心的方法非常简单，就是分区计算x、y坐标的平均值

1
2
3
4
5
6
7
8
9


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: 将质心作为坐标系原点建立坐标系

以质心坐标作为参考基准，多边形顶点减去质心坐标，就可以将多边形转换为以质心作为原点的坐标表示

1
2
3
4
5


for(auto& pt: polygon)
{
    auto offset_pt = pt - centroid;
    //...下一步处理
}

step3: 计算每个顶点与质心连线的角度，并基于角度排序

到这一步就很直观了，质心在凸多边形内部，作为坐标系原点。根据顶点的角度排序后，坐标数组自然是成顺时针或逆时针排序的。计算角度的方法我们采用opencv的反三角计算函数

1

cv::fastAtan2(pt.y, pt.x); //返回值为0-360度的角度值

至于排序，比较方便的方法是基于c++11的lambda表达式特性，写一个匿名函数就可以丢进sort函数里面进行排序，关于根据lambda表达式更多介绍可以参考我这篇笔记使用lambda表达式对自定义对象数组进行排序。下面直接给出代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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);

最后，完整的代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#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);

我们简单测试一下，将以下顺时针数据打乱后输入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


//顺时针 {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 });

测试代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


// 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;
}

测试结果

1
2
3
4
5
6
7


[12, 3]
[12, 20]
[0, 13]
[-11, 12]
[-12, 0]
[-11, -12]
[0, -15]

本文由芒果浩明发布，转载请注明出处。本文链接：https://blog.mangoeffect.net/opencv/sort-polygon-vertices-as-clockwise-or-anticlockwise.html

微信公众号