c++ 多边形求交集代码(凸多边形与凹多边形的交集)
多边形求交集cpp代码
凸多边形与凹多边形的交集:c++ 多边形求交集代码(凸多边形与凹多边形的交集)
凸多边形与凸多边形的交集:c++ 多边形求交集代码(凸多边形与凸多边形的交集)
#include "stdafx.h"#include #include #include using namespace std;using namespace cv;#define FREESPACENUM 64//计算多边形面积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);}int pointLineRelationship(int pt1x,int pt1y, int pt2x, int pt2y, int &pt0x, int &pt0y){ //iValue=0,点在分割线上,iValue>0,点在直线Pt3顺时针那侧,iValue<0,点在直线Pt3逆时针那侧, return((pt2y - pt1y) * pt0x + (pt1x - pt2x) * pt0y + (pt2x*pt1y - pt1x*pt2y));}bool intersect(int pt1x, int pt1y, int pt2x, int pt2y, int pt3x, int pt3y, int pt4x, int pt4y, int &ptNodex, int &ptNodey){ int ax = pt2x - pt1x, ay = pt2y - pt1y; int bx = pt3x - pt4x, by = pt3y - pt4y; int cx = pt1x - pt3x, cy = pt1y - pt3y; float fDenominator = ay * bx - ax * by; if (fDenominator == 0) return false; float fReciprocal = 1 / fDenominator; float na = (by * cx - bx * cy) * fReciprocal; ptNodex = ax * na + pt1x; ptNodey = ay * na + pt1y; if (na < 0 || na > 1) return true; float nb = (ax * cy - ay * cx) * fReciprocal; if (nb < 0 || nb > 1) return true; return true;}int main(){ Mat img = imread("7487939.jpg"); // init park vector> parkList(6); parkList[0] = {160,180,140,90,24,89,23,171 }; parkList[1] = {192,458,188,368,27,362,10,480}; parkList[2] = {451,173,444,332,617,318,621,199}; parkList[3] = {439,372,429,478,620,446,632,320}; parkList[4] = {427,490,358,500,336,616,476,616}; parkList[5] = {248,505,158,486,118,612,236,620}; for (vector park: parkList) { cv::line(img,Point2i(park[0], park[1]), Point2i(park[2], park[3]), Scalar(0, 0,255),2,8); cv::line(img, Point2i(park[2], park[3]), Point2i(park[4], park[5]), Scalar(0, 0, 255), 2, 8); cv::line(img, Point2i(park[4], park[5]), Point2i(park[6], park[7]), Scalar(0, 0, 255), 2, 8); cv::line(img, Point2i(park[6], park[7]), Point2i(park[0], park[1]), Scalar(0, 0, 255), 2, 8); } // init freespace vector leftFreespace, rightFreespace, backFreespace; for (int i=0;i=0;--i) { pParkSet[0] = Point2f(parkList[i][0], parkList[i][1]); pParkSet[1] = Point2f(parkList[i][2], parkList[i][3]); pParkSet[2] = Point2f(parkList[i][4], parkList[i][5]); pParkSet[3] = Point2f(parkList[i][6], parkList[i][7]); fParkArea = PolygonArea(pParkSet,4); poly_j_begin = -1, poly_j_end = -1; min_x = min(min(parkList[i][0], parkList[i][2]), min(parkList[i][4], parkList[i][6])); max_x = max(max(parkList[i][0], parkList[i][2]), max(parkList[i][4], parkList[i][6])); min_y = min(min(parkList[i][1], parkList[i][3]), min(parkList[i][5], parkList[i][7])); max_y = max(max(parkList[i][1], parkList[i][3]), max(parkList[i][5], parkList[i][7])); min_x_p0167 = min(parkList[i][0], parkList[i][6]); max_x_p0167 = max(parkList[i][0], parkList[i][6]); min_y_p0167 = min(parkList[i][1], parkList[i][7]); max_y_p0167 = max(parkList[i][1], parkList[i][7]); min_x_p0123 = min(parkList[i][0], parkList[i][2]); max_x_p0123 = max(parkList[i][0], parkList[i][2]); min_y_p0123 = min(parkList[i][1], parkList[i][3]); max_y_p0123 = max(parkList[i][1], parkList[i][3]); min_x_p2345 = min(parkList[i][2], parkList[i][4]); max_x_p2345 = max(parkList[i][2], parkList[i][4]); min_y_p2345 = min(parkList[i][3], parkList[i][5]); max_y_p2345 = max(parkList[i][3], parkList[i][5]); min_x_p4567 = min(parkList[i][4], parkList[i][6]); max_x_p4567 = max(parkList[i][4], parkList[i][6]); min_y_p4567 = min(parkList[i][5], parkList[i][7]); max_y_p4567 = max(parkList[i][5], parkList[i][7]); pPolygonIndex = 0; for (int j=0;j=leftFreespace[j].x&& min_y <=leftFreespace[j].y&& max_y >=leftFreespace[j].y) { n_flag = 0; //cout <= cross_x_p0167 && min_y_p0167 <= cross_y_p0167 && max_y_p0167 >= cross_y_p0167 && min_x_freespace <= cross_x_p0167&& max_x_freespace >= cross_x_p0167 && min_y_freespace <= cross_y_p0167&& max_y_freespace >= cross_y_p0167) { cout<<"p0167 ===== "<< cross_x_p0167 << " " << cross_y_p0167 << endl; n_flag = 1; pPolygonSet[pPolygonIndex] = Point2f(cross_x_p0167, cross_y_p0167); pPolygonSetAttribute[pPolygonIndex] = n_flag; ++pPolygonIndex; } //01-23 intersect(parkList[i][0], parkList[i][1], parkList[i][2], parkList[i][3], leftFreespace[j].x, leftFreespace[j].y,leftFreespace[j + 1].x, leftFreespace[j + 1].y, cross_x_p0123, cross_y_p0123); //01-23边有交点 if (min_x_p0123 <= cross_x_p0123&& max_x_p0123 >= cross_x_p0123 && min_y_p0123 <= cross_y_p0123 && max_y_p0123 >= cross_y_p0123 && min_x_freespace <= cross_x_p0123 && max_x_freespace >= cross_x_p0123 && min_y_freespace <= cross_y_p0123 && max_y_freespace >= cross_y_p0123) { cout << "p0123 ===== " << cross_x_p0123 << " " << cross_y_p0123 << endl; n_flag = 2; pPolygonSet[pPolygonIndex] = Point2f(cross_x_p0123, cross_y_p0123); pPolygonSetAttribute[pPolygonIndex] = n_flag; ++pPolygonIndex; } //23-45 intersect(parkList[i][2], parkList[i][3], parkList[i][4], parkList[i][5], leftFreespace[j].x, leftFreespace[j].y,leftFreespace[j + 1].x, leftFreespace[j + 1].y, cross_x_p2345, cross_y_p2345); //23-45边有交点 if (min_x_p2345 <= cross_x_p2345 && max_x_p2345 >= cross_x_p2345 && min_y_p2345 <= cross_y_p2345 && max_y_p2345 >= cross_y_p2345 && min_x_freespace <= cross_x_p2345 && max_x_freespace >= cross_x_p2345 && min_y_freespace <= cross_y_p2345 && max_y_freespace >= cross_y_p2345) { cout << "p2345 ===== " << cross_x_p2345 << " " << cross_y_p2345 << endl; n_flag = 3; pPolygonSet[pPolygonIndex] = Point2f(cross_x_p2345, cross_y_p2345); pPolygonSetAttribute[pPolygonIndex] = n_flag; ++pPolygonIndex; } //45-67 intersect(parkList[i][4], parkList[i][5], parkList[i][6], parkList[i][7], leftFreespace[j].x, leftFreespace[j].y,leftFreespace[j + 1].x, leftFreespace[j + 1].y, cross_x_p4567, cross_y_p4567); //45-67边有交点 if (min_x_p4567 <= cross_x_p4567 && max_x_p4567 >= cross_x_p4567 && min_y_p4567 <= cross_y_p4567 && max_y_p4567 >= cross_y_p4567 && min_x_freespace <= cross_x_p4567 && max_x_freespace >= cross_x_p4567 && min_y_freespace <= cross_y_p4567 && max_y_freespace >= cross_y_p4567) { cout << "p4567 ===== " << cross_x_p4567 << " " << cross_y_p4567 << endl; n_flag = 4; pPolygonSet[pPolygonIndex] = Point2f(cross_x_p4567, cross_y_p4567); pPolygonSetAttribute[pPolygonIndex] = n_flag; ++pPolygonIndex; } if (n_flag<1) { pPolygonSet[pPolygonIndex] = Point2f(leftFreespace[j].x, leftFreespace[j].y); pPolygonSetAttribute[pPolygonIndex] = n_flag; ++pPolygonIndex; } } // end if }// end for poly_j_begin = pPolygonSetAttribute[0]; poly_j_end = pPolygonSetAttribute[pPolygonIndex-1]; if (poly_j_begin>-1&& poly_j_end>-1) { if (poly_j_begin == 1) { if (poly_j_end == 2) { pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 3) { pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 4) { pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } } else if (poly_j_begin == 2) { if (poly_j_end == 1) { pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 3) { pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 4) { pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } } else if (poly_j_begin == 3) { if (poly_j_end == 1) { pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 2) { pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 4) { pPolygonSet[pPolygonIndex] = pParkSet[3]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } } else { if (poly_j_end == 1) { pPolygonSet[pPolygonIndex] = pParkSet[0]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 2) { pPolygonSet[pPolygonIndex] = pParkSet[1]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } else if (poly_j_end == 3) { pPolygonSet[pPolygonIndex] = pParkSet[2]; pPolygonSetAttribute[pPolygonIndex] = -1; ++pPolygonIndex; } } } cout << "***************" << endl; /*for (int n=0;n
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
暂时没有评论,来抢沙发吧~