//參考 //http://dev.gameres.com/Program/Abstract/Geometry.htm //http://zhan.renren.com/jisuanjihe?from=template&checked=true /* toolbox: Geometry algorithm toolbox author: alaclp email: alaclp@qq.com publish date: 2015⑴⑴6 */ #include <iostream> #include <stdio.h> #include <math.h> using namespace std; //預(yù)定義 #define Min(x, y) ((x) < (y) ? (x) : (y)) #define Max(x, y) ((x) > (y) ? (x) : (y)) //點(diǎn)對(duì)象 typedef struct Point { double x, y; //構(gòu)造函數(shù) Point(double x, double y) : x(x), y(y) {} //無(wú)參數(shù)時(shí)的構(gòu)造函數(shù) Point() : x(0), y(0) {} //獲得到點(diǎn)pt的距離 double distance(const Point& pt) { return sqrt( (x - pt.x) * (x - pt.x) + (y - pt.y) * (y - pt.y)); } //判斷兩點(diǎn)是不是同1個(gè)點(diǎn) bool equal(const Point& pt) { return ((x - pt.x) == 0) && (y - pt.y == 0); } } Point; //線段對(duì)象 typedef struct PartLine { Point pa, pb; double length; PartLine() { length = 0; } //構(gòu)造函數(shù) PartLine(Point pa, Point pb) : pa(pa), pb(pb) { length = sqrt((pa.x - pb.x) * (pa.x - pb.x) + (pa.y - pb.y) * (pa.y - pb.y)); } void assign(const PartLine& pl) { pa = pl.pa; pb = pl.pb; length = pl.length; } //利用叉積計(jì)算點(diǎn)到線段的垂直距離 //注意：此結(jié)果距離有正負(fù)之分 //若pc點(diǎn)在線段的逆時(shí)針?lè)较颍瑒t距離為正;否則，距離為副值 double getDistantToPoint(Point pc) { double area = crossProd(pc) / 2; return area * 2 / length; /* 利用海倫公式計(jì)算 PartLine pl1(this->pa, pc), pl2(this->pb, pc); double l1 = this->length, l2 = pl1.length, l3 = pl2.length; double s = (l1 + l2 + l3) / 2; //海倫公式 double area = sqrt(s * (s - l1) * (s - l2) * (s - l3)); return area * 2 / l1; */ } //向量的叉積 /* 計(jì)算向量的叉積（ABxAC A(x1,y1) B(x2,y2) C(x3,y3)）是計(jì)算行列式 | x1-x0 y1-y0 | | x2-x0 y2-y0 | 的結(jié)果(向量的叉積 AB X AC) */ //計(jì)算AB與AC的叉積---叉積的絕對(duì)值是兩向量所構(gòu)成平行4邊形的面積 double crossProd(Point& pc) { //計(jì)算ab X ac return (pb.x - pa.x) * (pc.y - pa.y) - (pb.y - pa.y) * (pc.x - pa.x); } //判斷兩線段是不是相交 bool isIntersected(PartLine& pl) { double d1, d2, d3, d4, d5, d6; d1 = pl.crossProd(pb); d2 = pl.crossProd(pa); d3 = crossProd(pl.pa); d4 = crossProd(pl.pb); d5 = crossProd(pl.pa); d6 = crossProd(pl.pb); //printf("%f %f %f %f %f %f ", d1, d2, d3, d4, d5, d6); bool cond1 = d1 * d2 <= 0, //pb和pa在pl的兩側(cè)或線段或線段的延長(zhǎng)線上 cond2 = d3 * d4 <= 0, //pl.pa和pl.pb在this的兩側(cè)或線段或線段的延長(zhǎng)線上 cond3 = d5 != 0, //pl.pa不在線段和延長(zhǎng)線上 cond4 = d6 != 0; //pl.pb不在線段和延長(zhǎng)線上 return cond1 && cond2 && cond3 && cond4; } //判斷兩線段是不是平行 bool isParallel(PartLine& pl) { double v1 = crossProd(pl.pa), v2 = crossProd(pl.pb); return (v1 == v2) && (v1 != 0); } //沿pa點(diǎn)旋轉(zhuǎn)theta PartLine rotateA(double theta) { float nx = pa.x +(pb.x - pa.x) * cos(theta) - (pb.y - pa.y) * sin(theta), ny = pa.y + (pb.x - pa.x) * sin(theta) + (pb.y - pa.y) * cos(theta); return PartLine(pa, Point(nx, ny)); } //沿pb點(diǎn)旋轉(zhuǎn)theta PartLine rotateB(double theta) { float nx = pb.x +(pa.x - pb.x) * cos(theta) - (pa.y - pb.y) * sin(theta), ny = pb.y + (pa.x - pb.x) * sin(theta) + (pa.y - pb.y) * cos(theta); return PartLine(Point(nx, ny), pb); } //判斷兩線段是不是堆疊或共線 bool inSameLine(PartLine& pl) { double v1 = crossProd(pl.pa), v2 = crossProd(pl.pb); if (v1 != v2) return false; if (v1 != 0) return false; return true; } //獲得兩線段的相交點(diǎn)---如果不相交返回valid=false //如果多個(gè)交點(diǎn)，給出正告 Point getCrossPoint(PartLine& pl, bool& valid) { valid = false; if (!isIntersected(pl)) { //不相交 return Point(); } if ( inSameLine(pl) ) { //有交點(diǎn)且共線 if ( pa.equal(pl.pa) ) { valid = true; return pa; } if ( pa.equal(pl.pb) ) { valid = true; return pa; } if ( pb.equal(pl.pa) ) { valid = true; return pb; } if ( pb.equal(pl.pb) ) { valid = true; return pb; } //多個(gè)焦點(diǎn) cout << "毛病：計(jì)算交點(diǎn)結(jié)果數(shù)量為無(wú)窮" << endl; valid = false; return Point(); } //相交 Point pt1, pt2, pt3, result; pt1 = pa; pt2 = pb; pt3.x = (pt1.x + pt2.x) / 2; pt3.y = (pt1.y + pt2.y) / 2; double L1 = pl.crossProd(pt1), L2 = pl.crossProd(pt2), L3 = pl.crossProd(pt3); printf("%f %f %f=%f ", L1, L2, L3, L1 + L2); while(fabs(L1) > 1e⑺ || fabs(L2) > 1e⑺) { valid = true; if (fabs(L1) < fabs(L2)) pt2 = pt3; else pt1 = pt3; pt3.x = (pt1.x + pt2.x) / 2; pt3.y = (pt1.y + pt2.y) / 2; result = pt3; L1 = pl.crossProd(pt1), L2 = pl.crossProd(pt2), L3 = pl.crossProd(pt3); printf("%f %f %f=%f ", L1, L2, L3, L1 - L2); } return pt3; } //獲得線段上離pt最近的點(diǎn) Point getNearestPointToPoint(Point& pt) { Point pt1, pt2, pt3, result; pt1 = pa; pt2 = pb; pt3.x = (pt1.x + pt2.x) / 2; pt3.y = (pt1.y + pt2.y) / 2; double L1 = pt1.distance(pt), L2 = pt2.distance(pt), L3 = pt3.distance(pt); if (L1 == L2) return pt3; while(fabs(L1 - L2) > 1e⑺) { if (L1 < L2) pt2 = pt3; else pt1 = pt3; pt3.x = (pt1.x + pt2.x) / 2; pt3.y = (pt1.y + pt2.y) / 2; result = pt3; L1 = pt1.distance(pt); L2 = pt2.distance(pt); L3 = pt3.distance(pt); //printf("%f %f %f=%f ", L1, L2, L3, L1 - L2); } return result; } //獲得1個(gè)點(diǎn)在線段上的鏡像點(diǎn) Point getMirrorPoint(Point& pc) { } } PartLine; int main(void) { Point p1(0, 0), p2(1, 1), p3(0, 1.1), p4(0.5, 0.5+1e⑴0), p5(0.5, 0.5⑴e⑴0), np; PartLine pl1(p1, p2), pl2(p3, p4), pl3(p3, p5); cout << pl1.getDistantToPoint(p3) << endl; cout << "線段1和2相交？" << pl1.isIntersected(pl2) << endl; np = pl1.getNearestPointToPoint(p5); cout << "最近點(diǎn):" << np.x << ", " << np.y << endl; bool isvalid; np = pl1.getCrossPoint(pl3, isvalid); cout << "兩線段的相交點(diǎn)：" << (isvalid ? "有效":"無(wú)效") << "=" << np.x << ", " << np.y << endl; PartLine plx = pl1.rotateA(M_PI / 2); printf("旋轉(zhuǎn)90度后：%f %f %f %f ", plx.pa.x, plx.pa.y, plx.pb.x, plx.pb.y); return 0; }