问题描述：已知两个多边形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() <= 0)
47 return false;
48
49 //点集排序
50 ClockwiseSortPoints(interPoly);
51 return true;
52 }
按照这个代码写的程序结果似乎不正确,方便给予指导?
当点和点重合，点和边重合，边和边重合，多边形和多边形重合的时候，你就掉坑里了。