问题描述：已知两个多边形Poly1和Poly2，分别由点集C1={P1,P2,…,Pm}和C2={Q1,Q2,…,Qn}表示，求这两个多边形的交集。
算法思想：
两个多边形相交后，其顶点要么是两个多边形边的交点，要么是在多边形内部的点。
算法步骤：
1.计算两个多边形每条边之间的交点。
2.计算包含在多边形内部的点。
3.将交点和多边形内部的点，按逆时针(或顺时针)排序，得出最终的点集。
代码基本实现如下：
1 typedef struct Point
2 {
3 int x;
4 int y;
5 }Point;
6 bool PolygonClip(const vector &poly1,const vector &poly2, std::vector &interPoly)
7 {
8 if (poly1.size() < 3 || poly2.size() < 3)
9 {
10 return false;
11 }
12
13 long x,y;
14 //计算多边形交点
15 for (int i = 0;i < poly1.size();i++)
16 {
17 int poly1_next_idx = (i + 1) % poly1.size();
18 for (int j = 0;j < poly2.size();j++)
19 {
20 int poly2_next_idx = (j + 1) % poly2.size();
21 if (GetCrossPoint(poly1[i],poly1[poly1_next_idx],
22 poly2[j],poly2[poly2_next_idx],
23 x,y))
24 {
25 interPoly.push_back(cv::Point(x,y));
26 }
27 }
28 }
29
30 //计算多边形内部点
31 for(int i = 0;i < poly1.size();i++)
32 {
33 if (IsPointInpolygon(poly2,poly1[i]))
34 {
35 interPoly.push_back(poly1[i]);
36 }
37 }
38 for (int i = 0;i < poly2.size();i++)
39 {
40 if (IsPointInpolygon(poly1,poly2[i]))
41 {
42 interPoly.push_back(poly2[i]);
43 }
44 }
45
46 if(interPoly.size() 代码分析：求多边形交集，主要由计算多边形交点、计算多边形内部点、点集排序三部分组成，主要由以下三个函数完成。参考资料：
Original: https://www.cnblogs.com/xmphoenix/p/4508454.html
Author: 深海的小鱼儿
Title: 【计算几何】多边形交集
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/534080/
转载文章受原作者版权保护。转载请注明原作者出处！