面试题: 用C++实现多边形IOU计算_c++计算iou

题目

实现多边形 IOU 计算

题解思路

1. 将两个多边形的顶点进行排序和连接，得到两个多边形的边界
2. 计算两个多边形的交集面积，可以使用 Sutherland-Hodgman 算法将两个边界进行裁剪得到交集多边形
3. 计算两个多边形的并集面积，可以直接将两个多边形边界进行裁剪，并根据裁剪后的多边形组合得到并集多边形
4. 最终的 IOU 值可以通过交集面积与并集面积之比来计算得到。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};

typedef vector<Point> Polygon;

double cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}

double area(const Polygon& p) {
double a = 0;
for (int i = 0; i < p.size(); i++) {
int j = (i + 1) % p.size();
a += cross(p[i], p[j]);
}
return a / 2;
}

Polygon clip(const Polygon& p, const Point& a, const Point& b) {
Polygon q;
for (int i = 0; i < p.size(); i++) {
int j = (i + 1) % p.size();
if (cross(b - a, p[i] - a) >= 0) q.push_back(p[i]);
if (cross(b - a, p[i] - a) * cross(b - a, p[j] - a) < 0) {
q.push_back(Point((cross(b - a, p[j] - a) * p[i].x - cross(b - a, p[i] - a) * p[j].x) /
(cross(b - a, p[j] - a) - cross(b - a, p[i] - a)),
(cross(b - a, p[j] - a) * p[i].y - cross(b - a, p[i] - a) * p[j].y) /
(cross(b - a, p[j] - a) - cross(b - a, p[i] - a))));
}
}
return q;
}

Polygon intersection(const Polygon& p, const Polygon& q) {
Polygon r = q;
for (int i = 0; i < p.size(); i++) {
int j = (i + 1) % p.size();
r = clip(r, p[j], p[i]);
}
return r;
}

Polygon join(const Polygon& p, const Polygon& q) {
int pi = 0, qi = 0;
Polygon r;
while (pi < p.size() || qi < q.size()) {
if (pi == p.size()) r.push_back(q[qi++]);
else if (qi == q.size()) r.push_back(p[pi++]);
else if (p[pi].y < q[qi].y) r.push_back(p[pi++]);
else if (p[pi].y > q[qi].y) r.push_back(q[qi++]);
else if (p[pi].x < q[qi].x) r.push_back(p[pi++]);
else r.push_back(q[qi++]);
}
return r;
}

double iou(const Polygon& p, const Polygon& q) {
Polygon r = intersection(p, q);
double inter = area(r);
double uni = area(join(p, q));
return inter / uni;
}

int main() {
// test
Polygon p;
p.push_back(Point(0, 0));
p.push_back(Point(1, 0));
p.push_back(Point(1, 1));
p.push_back(Point(0, 1));
Polygon q;
q.push_back(Point(0.5, 0.5));
q.push_back(Point(1.5, 0.5));
q.push_back(Point(1.5, 1.5));
q.push_back(Point(0.5, 1.5));
cout << iou(p, q) << endl; // should output 0.25
return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87