凸包算法-判断凸多边形是否相交.doc

/*凸包算法 判断凸多边形是否相交 */#include #include #include #define MaxNode 100015#define INF 99999999int stackMaxNode;int top;typedef struct TPoint double x; double y;TPoint;TPoint black2005, white2005;TPoint p0;typedef struct TPloygon TPoint p2005; int n;TPolygon;TPolygon covtexb, covtexw;typedef struct TSegment TPoint p1; TPoint p2;TSegment;void swap(TPoint point, int i, int j) TPoint tmp; tmp = pointi; pointi = pointj; pointj = tmp;double max(double x, double y) /比较两个数的大小，返回大的数 if(x y) return x; else return y; double min(double x, double y) /比较两个数的大小，返回小的数 if(x y) return x; else return y; double multi(TPoint p1, TPoint p2, TPoint p0) return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);double distanc(TPoint p1, TPoint p2) return sqrt(p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);int cmp(const void *a, const void *b) TPoint *c = (TPoint *)a; TPoint *d = (TPoint *)b; double k = multi(*c, *d, p0); if(k = distanc(*d, p0) return 1; else return -1; void grahamScan(TPoint point, int n) /Graham扫描求凸包 int i, u; /将最左下的点调整到p0的位置 u = 0; for(i = 1;i = n - 1;i+) if(pointi.y pointu.y) | (pointi.y = pointu.y & pointi.x pointu.x) u = i; swap(point, 0, u); p0 = point0; /将平p1到pn - 1按按极角排序，可采用快速排序 qsort(point + 1, n - 1, sizeof(point0), cmp); for(i = 0;i = 2;i+) stacki = i; top = 2; for(i = 3;i = 0) if(top = 0)break; top-; top+; stacktop = i; bool isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2) /判断线段是否相交 /1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交 /2.跨立试验 if( (max(s1.x, e1.x) = min(s2.x, e2.x) & (max(s2.x, e2.x) = min(s1.x, e1.x) & (max(s1.y, e1.y) = min(s2.y, e2.y) & (max(s2.y, e2.y) = min(s1.y, e1.y) & (multi(s2, e1, s1) * multi(e1, e2, s1) = 0) & (multi(s1, e2, s2) * multi(e2, e1, s2) = 0) ) return true; return false; bool Intersect(TSegment L1, TSegment L2) /线段l1与l2相交而且不在端点上时，返回true /判断线段是否相交 /1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交 TPoint s1 = L1.p1; TPoint e1 = L1.p2; TPoint s2 = L2.p1; TPoint e2 = L2.p2; /2.跨立试验 if( (max(s1.x, e1.x) = min(s2.x, e2.x) & (max(s2.x, e2.x) = min(s1.x, e1.x) & (max(s1.y, e1.y) = min(s2.y, e2.y) & (max(s2.y, e2.y) = min(s1.y, e1.y) & (multi(s2, e1, s1) * multi(e1, e2, s1) = 0) & (multi(s1, e2, s2) * multi(e2, e1, s2) = 0) ) return true; return false; bool Online(TSegment L, TPoint p) /p在L上(不在端点)时返回true /1.在L所在的直线上 /2.在L为对角线的矩形中 double dx, dy, dx1, dy1; dx = L.p2.x - L.p1.x; dy = L.p2.y - L.p1.y; dx1 = p.x - L.p1.x; dy1 = p.y - L.p1.y; if(dx * dy1 - dy * dx1 != 0) return false; /叉积 if(dx1 * (dx1 - dx) 0 | dy1 * (dy1 - dy) 0) return true; return false; bool same1(TSegment L, TPoint p1, TPoint p2) /判断p1, p2是否在L的同侧 if(multi(p1, L.p2, L.p1) * multi(L.p2, p2, L.p1) 0) return true; return false; bool Inside(TPoint q, TPolygon polygon) int c, i, n; TSegment L1, L2; c = 0; n = polygon.n; L1.p1 = q; L1.p2 = q; L1.p2.x = INF; /* （1）相交 1.pi和pi+1在L的两侧 2.pi和pi+2在L的同侧 3.pu和pi+3在L的同侧或异侧 */ for(i = 0;i polygon.n;i+) L2.p1 = polygon.pi; L2.p2 = polygon.p(i + 1) % n; if(Intersect(L1, L2) c+; continue; if(!Online(L1, polygon.p(i + 1) % n) continue; if(!Online(L1, polygon.p(i + 2) % n) & !same1(L1, polygon.pi, polygon.p(i + 2) % n) c+; continue; if(Online(L1, polygon.p(i + 2) % n) & !same1(L1, polygon.pi, polygon.p(i + 3) % n) c+; if(c % 2 = 0) return false; else return true;int covtexintet() int i, j, s, t; for(i = 0;i covtexb.n;i+) for(j =i + 1;j covtexb.n;j+) for(s = 0;s covtexw.n;s+) for(t = s + 1;t covtexw.n;t+) if(isIntersected(covtexb.pi, covtexb.pj, covtexw.ps,covtexw.pt) return 0; if(Inside(covtexb.pcovtexb.n - 1, covtexw) | Inside(covtexw.pcovtexw.n - 1, covtexb) return 0; else return 1; int main() int i, d, t1, t2, p, test = 1; double x1, y1, x2, y2; while(scanf(%d%d, &d, &p) & d & p) if(test != 1) printf(n); t1 = 0; for(i = 0;i d;i+) scanf(%lf%lf%lf%lf,&x1, &y1, &x2, &y2); blackt1.x = x1; blackt1.y = y1; t1+; blackt1.x = x2; blackt1.y = y2; t1+; blackt1.x = x1; blackt1.y = y2; t1+; blackt1.x = x2; blackt1.y = y1; t2 = 0; for(i = 0;i p;i+) scanf(%lf%lf%lf%lf, &x1, &y1, &x2, &y2); whitet2.x = x1; whitet2.y = y1; t2+; whitet2.x = x2; whitet2.y = y2; t2+; whitet2.x = x1; whitet2.y = y2; t2+; whitet2.x = x2; whitet2.y = y1; grahamScan(black, t1 + 1); for(i = 0;i = top;i+) covtexb.pi.x = blackstacki.x; covtexb.pi.y = blackstacki.y; covtexb.n = top + 1; grahamScan(white, t2 + 1); for(i = 0;i = top;i+) covtexw.pi.x = whitestacki.x; covtexw.pi.y = whi