前言
在我初涉编程世界的时候，Python是我的初恋。它的语法简洁明了，易于上手，也能快速上手。我记得那时候，然而，随着时间的推移，我发现Python在处理一些复杂任务时，效率低下的问题开始显现。于是，毫无疑问我选择了C++。我开始用C++重新实现那些曾经用Python完成的任务。结果出乎我的意料，C++的效率竟然比Python高出许多。这让我有些惊讶，也有些尴尬。我曾经以为Python是我的最佳伴侣，现在我说吃了细粮后怎么能咽的下粗糠！
问题
在图像处理任务中有一个经典任务：电子围栏。电子围栏，顾名思义就是在视频画面中出现绘制一个多边形的区域，该区域的边数应该是为 >=3,当目标出现在视频画面中的时候触碰到围栏时候或者在围栏里面则进行告警。
在进行目标检测时常见的为矩形，矩形的坐标形式是Xmin, Ymin, Xmax, Ymax，多边形的坐标形式为 [(x1,y1), (x2,y2), (x3,y3) ...] 这里我们需要判断这两个多边形是否存在交集
Python解决
使用Python的话针对上述任务经过调用研究，可以直接调用现成的shapely.geometry库进行运算，我们构建isRectangleAndPolygonIntersect 函数可以直接把目标框的坐标与电子围栏的坐标输入到对应位置调用库函数即可直接得出目标区域与电子围栏区域是否存在交集。
ini
复制代码
import time from shapely.geometry import Polygon, box def isRectangleAndPolygonIntersect(label, warn): # 创建矩形坐标域对象 rect = box(label[0], label[1], label[2], label[3]) # 创建多边形对象 polygon = Polygon(warn) if rect.intersects(polygon): return 1 # 相交 else: return 0 # 不相交 if __name__ == "__main__": label = [0,0,2,2] warn = [(3,3),(10,3),(10,10),(3,10)] t1 = time.time() for i in range(1000000): isRectangleAndPolygonIntersect(label, warn) print(time.time() - t1)
C++解决
相较于Python使用C++就没有那么多库进行调用（可能是自己知道的库较少的缘故），这就需要自己从底层逻辑中进行分析得到判断矩形和多边形是否存在交集：
- 矩形与多边形相交则必定存在矩形内的点在多边形区域内；
- 矩形内的区域点可以很好使用for循环得到；
- 可以通过射线法判断某点是否在多边形内；
射线法基本原理
在上述逻辑里有一个基础知识点：射线法。下面为大家介绍其基本原理： 从待检测点P出发，沿任意方向（通常选择水平方向以简化计算）绘制一条射线（无限长直线），穿过整个平面。 计算这条射线与多边形各边的交点数目（包括边界上的交点，但不包括在多边形顶点处的重复交点）。根据交点数目的奇偶性来判断点P的位置：
- 若交点数目为奇数，则点P位于多边形内部；
- 若交点数目为偶数，则点P位于多边形外部。
ini
复制代码
#include <iostream> #include <vector> #include <time.h> //#include <algorithm> using namespace std; //定义电子围栏的坐标点 struct Point { int x; int y; }; //定义目标检测框的坐标点 struct Box { int xmin; int ymin; int xmax; int ymax; }; // 获取目标检测狂的坐标 Box get_box(int xmin, int ymin, int xmax, int ymax) { Box label_box = {xmin, ymin, xmax, ymax }; return label_box; } //获取电子围栏坐标 vector<Point> get_warn_box() { vector<Point> warn_box = { {3, 3},{10,3},{10,10},{3,10} }; return warn_box; } //射线法求某点是否在多边形区域内 bool isPointInPolygon(const Point& p, const vector<Point>& polygon) { int n = polygon.size(); int count = 0; for (int i = 0; i < n; ++i) { Point p1 = polygon[i]; Point p2 = polygon[(i + 1) % n]; if (p1.y == p2.y) continue; if (p.y < min(p1.y, p2.y)) continue; if (p.y >= max(p1.y, p2.y)) continue; double x = (double)(p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x; if (x > p.x) count++; } return count % 2 == 1; } // 判定是否非相离状态 bool isRectangleAndPolygonIntersect(const Box& label_box, const vector<Point>& warn_box) { Point p; bool isRect = false; for (int x = label_box.xmin; x <= label_box.xmax; ++x) { for (int y = label_box.ymin; y <= label_box.ymax; ++y) { p = { x, y }; isRect = isPointInPolygon(p, warn_box); if (isRect) break; } if (isRect) break; } return isRect; } int main() { Box label_box; //定义 Box label_box 常量 label_box = get_box(0, 0, 2, 2); //调用函数得到 vector<Point> warn_box; warn_box = get_warn_box(); clock_t start, finish; start = clock(); /* cout << "warn_box: "; for (const auto& point : warn_box) { cout << "(" << point.x << ", " << point.y << ") "; } cout << endl; */ for (int x = 0; x <= 1000000; x++) { bool isRect; isRect = isRectangleAndPolygonIntersect(label_box, warn_box); } finish = clock(); cout << endl << "the time cost is:" << double(finish - start) / CLOCKS_PER_SEC << endl; return 0; }
比对
通过上述的Python代码和C++代码我们可以明显得到二者的矩形坐标与多边形坐标是一样的，二者循环次数也是一样的
- Python代码运行一百万次的平均耗时为39.5秒
- C++代码运行一百万次的平均耗时为0.535秒
老天爷！这是什么概念？我的表情就像上面的杰克版。请你不要告诉我python还能优化，使用python的人员无非就是图它的方便能快速找到对应的轮子函数进行计算加速开发速度，有优化的时间用来写C++不香么。泪目，在相同的设备中运行，C++ 的运行速度比Python运行速度快了73.8倍。我在Python中丢的面子被我用C++找回来了。重新拾回了男人的尊严！
