triangle2triangle-Test.zip_三角形相交_两个三角形_平面相交

#include<iostream> using namespace std; #include"Point2D.h" #include"Segment.h" #include"Triangle2D.h" int WhichSide(Triangle&tri,Point2D&D,Point2D vert) { int positive=0,negtive=0; float t; for(int i=0;i<3;i++) { t=D.Dot(tri.GetVertex(i)-vert); if(t>0)positive++; if(t<0) negtive++; if(positive&&negtive)return 0; } return (positive?1:-1); } //判断三角形是否相交 bool TestIntersection(Triangle &tri0,Triangle &tri1) { int i0,i1; Point2D D,edge; //判断三角形tri1在tri0的正向 for(i0=0,i1=2;i0<3;i1=i0,i0++) { edge=tri0.GetVertex(i0)-tri0.GetVertex(i1); D=edge.Perp(); if(WhichSide(tri1,D,tri0.GetVertex(i0))>0) { return false; } } //判断三角形tri0在tri1的正向 for(i0=0,i1=2;i0<3;i1=i0,i0++) { edge=tri1.GetVertex(i0)-tri1.GetVertex(i1); D=edge.Perp(); if(WhichSide(tri0,D,tri1.GetVertex(i0))>0) { return false; } } return true; } void ClipConvexPolygonAgainstLine ( Point2D rkN, float fC, int& riQuantity, Point2D akV[6]) { // The input vertices are assumed to be in counterclockwise order. The // ordering is an invariant of this function. // test on which side of line the vertices are int iPositive = 0, iNegative = 0, iPIndex = -1; float afTest[6]; int i; for (i = 0; i < riQuantity; i++) { afTest[i] = rkN.Dot(akV[i]) - fC; if (afTest[i] > (float)0.0) { iPositive++; if (iPIndex < 0) { iPIndex = i; } } else if (afTest[i] < (float)0.0) { iNegative++; } } if (iPositive > 0) { if (iNegative > 0) { // line transversely intersects polygon Point2D akCV[6]; int iCQuantity = 0, iCur, iPrv; float fT; if (iPIndex > 0) { // first clip vertex on line iCur = iPIndex; iPrv = iCur-1; fT = afTest[iCur]/(afTest[iCur] - afTest[iPrv]); akCV[iCQuantity++] = akV[iCur]+(akV[iPrv]-akV[iCur])*fT; // vertices on positive side of line while (iCur < riQuantity && afTest[iCur] > (float)0.0) { akCV[iCQuantity++] = akV[iCur++]; } // last clip vertex on line if (iCur < riQuantity) { iPrv = iCur-1; } else { iCur = 0; iPrv = riQuantity - 1; } fT = afTest[iCur]/(afTest[iCur] - afTest[iPrv]); akCV[iCQuantity++] = akV[iCur]+(akV[iPrv]-akV[iCur])*fT; } else // iPIndex is 0 { // vertices on positive side of line iCur = 0; while (iCur < riQuantity && afTest[iCur] > (float)0.0) { akCV[iCQuantity++] = akV[iCur++]; } // last clip vertex on line iPrv = iCur-1; fT = afTest[iCur]/(afTest[iCur] - afTest[iPrv]); akCV[iCQuantity++] = akV[iCur]+(akV[iPrv]-akV[iCur])*fT; // skip vertices on negative side while (iCur < riQuantity && afTest[iCur] <= (float)0.0) { iCur++; } // first clip vertex on line if (iCur < riQuantity) { iPrv = iCur-1; fT = afTest[iCur]/(afTest[iCur] - afTest[iPrv]); akCV[iCQuantity++] = akV[iCur]+(akV[iPrv]-akV[iCur])*fT; // vertices on positive side of line while (iCur < riQuantity && afTest[iCur] > (float)0.0) { akCV[iCQuantity++] = akV[iCur++]; } } else { // iCur = 0 iPrv = riQuantity - 1; fT = afTest[0]/(afTest[0] - afTest[iPrv]); akCV[iCQuantity++] = akV[0]+(akV[iPrv]-akV[0])*fT; } } riQuantity = iCQuantity; for(int i=0;i<riQuantity;i++) { akV[i]=akCV[i]; } } // else polygon fully on positive side of line, nothing to do } else { // polygon does not intersect positive side of line, clip all riQuantity = 0; } } bool Find (Triangle &tri0,Triangle &tri1,Point2D *cross,int& crossnum) { // The potential intersection is initialized to triangle1. The set of // vertices is refined based on clipping against each edge of triangle0. crossnum = 3; // cross[6]={Point2D(0,0)}; for (int i = 0; i < 3; i++) { cross[i] = tri1.GetVertex(i); } for (int i1 = 2, i0 = 0; i0 < 3; i1 = i0, i0++) { // clip against edge <V0[i1],V0[i0]> Point2D edge=tri0.GetVertex(i1)-tri0.GetVertex(i0); Point2D kN=edge.Perp(); float fC = kN.Dot(tri0.GetVertex(i1)); ClipConvexPolygonAgainstLine(kN,fC,crossnum,cross); if (crossnum == 0) { // triangle completely clipped, no intersection occurs return false; } } return true; } int main() { Point2D p1(0,0),p2(1,0),p3(2,0),p4(3,0),p5(0,1),p6(0,2),p7(0,3),p8(1,1),p9(2,1); int crossnum; Point2D cross[6]; Triangle tri0(p1,p2,p5),tri1(p3,p4,p7); bool bok1=TestIntersection(tri0,tri1); if(bok1) { bool bok2=Find(tri0,tri1,cross,crossnum); cout<<crossnum<<endl; for(int i=0;i<crossnum;i++) cout<<cross[i]<<endl; } return 0; }