c++ 多边形求交集代码（凸多边形与凸多边形交集）

c++ 多边形求交集代码（凸多边形与凸多边形交集）

凸多边形与凹多边形的交集：​​c++ 多边形求交集代码（凸多边形与凹多边形的交集）​​​

凸多边形与凸多边形的交集：​​c++ 多边形求交集代码（凸多边形与凸多边形的交集）​​

/* * 多边形的交，多边形的边一定是要按逆时针方向给出 * 还要判断是凸包还是凹包，调用相应的函数 * 面积并，只要和面积减去交即可 */#include using namespace std;const int maxn = 300;const float eps = 1e-6;int dcmp(float x){ if(x > eps) return 1; return x < -eps ? -1 : 0;}float cross(Point2f a,Point2f b,Point2f c) ///叉积{ return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}Point2f intersection(Point2f a,Point2f b,Point2f c,Point2f d){ Point2f p = a; float t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x)); p.x +=(b.x-a.x)*t; p.y +=(b.y-a.y)*t; return p;}//计算多边形面积float PolygonArea(Point2f p[], int n){ if(n < 3) return 0.0; float s = p[0].y * (p[n - 1].x - p[1].x); p[n] = p[0]; for(int i = 1; i < n; ++ i) s += p[i].y * (p[i - 1].x - p[i + 1].x); return fabs(s * 0.5);}float CPIA(Point2f a[], Point2f b[], int na, int nb)//ConvexPolygonIntersectArea{ Point2f p[20], tmp[20]; int tn, sflag, eflag; a[na] = a[0], b[nb] = b[0]; memcpy(p,b,sizeof(Point2f)*(nb + 1)); for(int i = 0; i < na && nb > 2; i++) { sflag = dcmp(cross(a[i + 1], p[0],a[i])); for(int j = tn = 0; j < nb; j++, sflag = eflag) { if(sflag>=0) tmp[tn++] = p[j]; eflag = dcmp(cross(a[i + 1], p[j + 1],a[i])); if((sflag ^ eflag) == -2) tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]); ///求交点 } memcpy(p, tmp, sizeof(Point) * tn); nb = tn, p[nb] = p[0]; } if(nb < 3) return 0.0; return PolygonArea(p, nb);}float SPIA(Point2f a[], Point2f b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数{ int i, j; Point2f t1[4], t2[4]; float res = 0, num1, num2; a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0]; for(i = 2; i < na; i++) { t1[1] = a[i-1], t1[2] = a[i]; num1 = dcmp(cross(t1[1], t1[2],t1[0])); if(num1 < 0) swap(t1[1], t1[2]); for(j = 2; j < nb; j++) { t2[1] = b[j - 1], t2[2] = b[j]; num2 = dcmp(cross(t2[1], t2[2],t2[0])); if(num2 < 0) swap(t2[1], t2[2]); res += CPIA(t1, t2, 3, 3) * num1 * num2; } } return res;}Point2f p1[maxn], p2[maxn];int n1, n2;int main(){ while(cin>>n1>>n2) { for(int i = 0; i < n1; i++) scanf("%lf%lf", &p1[i].x, &p1[i].y); for(int i = 0; i < n2; i++) scanf("%lf%lf", &p2[i].x, &p2[i].y); float Area = SPIA(p1, p2, n1, n2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。