判断两个线段(注意是线段不是射线或直线)是否相交的计算几何算法在《算法导论》第三版33.1节有详细的文字描述还配有图示,这里就不赘述了.阅读以下代码前需要深刻理解scalarProduct(标量积,点积)和vectorProduct(矢量积叉积)的含义和应用.代码中pointOnLine函数用于判断点是否在线段上,parallel函数用于判断两线段是否平行,intersect函数最终用于判断两线段是否相交…C代码#includeiostream#includeutilityusingnamespacestd;structLineSegment{pairint,intfirst;pairint,intsecond;LineSegment(intlfirst,intlsecond,intrfirst,intrsecond):first({lfirst,lsecond}),second({rfirst,rsecond}){}};intscalarProduct(intx1,inty1,intx2,inty2){returnx1*x2y1*y2;}intvectorProduct(intx1,inty1,intx2,inty2){returnx1*y2-x2*y1;}boolpointOnLine(constpairint,intpoint,constLineSegmentline){if(vectorProduct(point.first-line.first.first,point.second-line.first.second,line.second.first-line.first.first,line.second.second-line.first.second)!0){returnfalse;}if(scalarProduct(point.first-line.first.first,point.second-line.first.second,point.first-line.second.first,point.second-line.second.second)0){returnfalse;}returntrue;}boolparallel(constLineSegmentline1,constLineSegmentline2){if(vectorProduct(line1.second.first-line1.first.first,line1.second.second-line1.first.second,line2.second.first-line2.first.first,line2.second.second-line2.first.second)0){returntrue;}returnfalse;}boolcross(constLineSegmentline1,constLineSegmentline2){intvector_product1vectorProduct(line1.first.first-line2.first.first,line1.first.second-line2.first.second,line2.second.first-line2.first.first,line2.second.second-line2.first.second);intvector_product2vectorProduct(line1.second.first-line2.first.first,line1.second.second-line2.first.second,line2.second.first-line2.first.first,line2.second.second-line2.first.second);if(vector_product10vector_product20||vector_product10vector_product20){returntrue;}returnfalse;}boolintersect(constLineSegmentline1,constLineSegmentline2){if(pointOnLine(line1.first,line2)||pointOnLine(line1.second,line2)){returntrue;}if(pointOnLine(line2.first,line1)||pointOnLine(line2.second,line1)){returntrue;}if(parallel(line1,line2)){returnfalse;}if(cross(line1,line2)cross(line2,line1)){returntrue;}returnfalse;}intmain(){LineSegmentleft(3,6,5,4);LineSegmentright(3,4,4,1);if(intersect(left,right)){cout相交;}else{cout不相交;}coutendl;return0;}