判斷兩個(gè)線段(注意是線段不是射線或直線)是否相交的計(jì)算幾何算法在《算法導(dǎo)論》第三版33.1節(jié)有詳細(xì)的文字描述還配有圖示,這里就不贅述了.閱讀以下代碼前需要深刻理解scalarProduct(標(biāo)量積,點(diǎn)積)和vectorProduct(矢量積叉積)的含義和應(yīng)用.代碼中pointOnLine函數(shù)用于判斷點(diǎn)是否在線段上,parallel函數(shù)用于判斷兩線段是否平行,intersect函數(shù)最終用于判斷兩線段是否相交…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;}