C++语言实现一些基本算法(两点距离、点是否在直线上、点与直线的关系、两直线的夹角、两直线的交点、两个举行的重合面积等等)

#include <math.h> #include <vector> #include <memory.h> #include <iostream> #include <qdebug.h> using namespace std; #define PI 3.141592653 struct QUICKSORT { int iIndex; float fAngle; QUICKSORT(int iIndex, float fAngle) { this->iIndex = iIndex; this->fAngle = fAngle; } QUICKSORT() {memset(this, 0, sizeof(*this));} }; //定义点结构体 struct myPoint { int x; //点的x坐标 int y; //点的y坐标 myPoint(){memset(this, 0, sizeof(*this));} myPoint(int x, int y) { this->x = x; this->y = y; } bool operator==(const myPoint &other) const { return (this->x == other.x && this->y == other.y); } }; /******************************************************************** * 函数名称 : segmentLength * 函数功能 : 求两点的长度(勾股定理) * 输入参数1: pt1 第一个点 * 输入参数2: pt2 第二个点 * 输出参数: 无 * 返回参数: pt1到pt2的距离 * 日 期: 2018年09月13日 * 作 者: mark-plus ********************************************************************/ float segmentLength(const myPoint &pt1, const myPoint &pt2) { float x = fabs(pt1.x - pt2.x); float y = fabs(pt1.y - pt2.y); float fLength = sqrt((x * x + y * y)); return fLength; } /******************************************************************** * 函数名称 : pointOnSegment * 函数功能 : 判断点是否在线段上 * 输入参数1: pt1 线段的第一个点 * 输入参数2: pt2 线段的第二个点 * 输入参数3: ptNode　需要判断的点 * 输出参数: 无 * 返回参数: true:点ptNode在线段上　false:点ptNode在在线段上 * 日 期: 2018年09月13日 * 作 者: mark-plus ********************************************************************/ bool pointOnSegment(const myPoint &pt1, const myPoint &pt2, const myPoint &ptNode) { float a = segmentLength(pt1, pt2); float b= segmentLength(pt1, ptNode); float c= segmentLength(pt2, ptNode); if (a == (b +c)) return true; else return false; } /******************************************************************** * 函数名称 : pointOnSegmentOutSide * 函数功能 : 判断某个点是否在线段外 * 输入参数1: pt1 线段的第一个点 * 输入参数2: pt2 线段的第二个点 * 输入参数3: ptNode　需要判断的点 * 输出参数: 无 * 返回参数: true:点ptNode在线外　false:点ptNode在线上 * 日 期: 2018年09月13日 * 作 者: mark-plus ********************************************************************/ bool pointOnSegmentOutSide(const myPoint pt1, const myPoint pt2, const myPoint ptNode) { float a = segmentLength(pt1, pt2); float b= segmentLength(pt1, ptNode); float c= segmentLength(pt2, ptNode); if (b > a || c > a) return false; else return true; } /******************************************************************** * 函数名称 : intersect * 函数功能 : 求两直线的交点（参考了Qt里面两直线求交点的算法） * 输入参数1: pt1　直线１的第１个点 * 输入参数2: pt2　直线１的第２点 * 输入参数3: pt3　直线２的第１个点 * 输入参数4: pt4　直线２的第２个点 * 输出参数: ptNode　直线１和直线２的交点 * 返回参数: true:直线１和直线２有交点　false：true:直线１和直线２没有交点 * 日 期: 2018年09月13日 * 作 者: mark-plus ********************************************************************/ bool intersect(const myPoint &pt1, const myPoint &pt2, const myPoint &pt3, const myPoint &pt4, myPoint &ptNode) { myPoint a(pt2.x - pt1.x, pt2.y - pt1.y); myPoint b(pt3.x - pt4.x, pt3.y - pt4.y); myPoint c(pt1.x - pt3.x, pt1.y - pt3.y); float fDenominator = a.y * b.x - a.x * b.y; if (fDenominator == 0) return false; float fReciprocal = 1 / fDenominator; float na = (b.y * c.x - b.x * c.y) * fReciprocal; ptNode = myPoint(a.x * na + pt1.x, a.y * na + pt1.y); if (na < 0 || na > 1) return true; float nb = (a.x * c.y - a.y * c.x) * fReciprocal; if (nb < 0 || nb > 1) return true; return true; } /******************************************************************** * 函数名称 : triangleArea * 函数功能 : 三点求三角形的面积(海伦公式) * 输入参数1: pt1　三角形的第１个点 * 输入参数2: pt2　三角形的第２个点 * 输入参数3: pt3　三角形的第３个点 * 输出参数: 无 * 返回参数:三角形的面积 * 日 期: 2018年09月13日 * 作 者: mark-plus ********************************************************************/ float triangleArea(const myPoint &pt1, const myPoint &pt2, const myPoint &pt3) { float a = segmentLength(pt1, pt2);//三角形的a边 float b = segmentLength(pt2, pt3);//三角形的b边 float c = segmentLength(pt3, pt1);//三角形的c边 float p = (a + b + c) / 2;//三角形的周长一半 float fArea = sqrt((p * (p - a) * (p - b) * (p - c)));//用海伦公式计算三角形面积 return fArea; } // 功能：判断点是否与多边形的关系(const vector<myPoint> vPointF, const myPoint &pt) // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： // myPoint pt 指定的某个点 // vector<myPoint> vPointF多边形的各个顶点坐标（首末点可以不一致） /******************************************************************** * 函数名称 : containsPointPolygon * 函数功能 : 判断点(pt)是否在多边形内(vPointF) * 输入参数1: vPointF 多边形的四个顶点，顶点要顺序放置(A-B-C-D-A) * 输入参数2: pt 需要判断的点 * 输出参数 : 无 * 返回参数 : 0:在多边形外　1:在多变形内　2:在多变形的边上 * 日 期 : 2018年09月13日 * 作 者 : mark-plus ********************************************************************/ int containsPointPolygon(const vector<myPoint> &vPointF, const myPoint &pt) { if (vPointF.size() == 0) return 0; int nCross = 0; int nCount = vPointF.size(); for (int i = 0; i < nCount; i++) { myPoint p1 = vPointF[i]; myPoint p2 = vPointF[(i + 1) % nCount]; if (pointOnSegment(p1, p2, pt)) return 2; //相交点刚好在边上 // 求解 y=p.y 与 p1p2 的交点 if (p1.y == p2.y) continue; //p1p2 与 y=p0.y平行 if (pt.y < min(p1.y, p2.y)) continue; //交点在p1p2延长线上 if (pt.y >= max(p1.y, p2.y)) continue; //交点在p1p2延长线上 // 求交点的x坐标 float x = ((pt.y - p1.y) * (p2.x - p1.x)) / (p2.y - p1.y) + p1.x; if (x > pt.x) nCross++; // 只统计单边交点 } // 单边交点为偶数，点在多边形之外 --- return ((nCross & 1) == 1); } /******************************************************************** * 函数名称 : pointLineRelationship * 函数功能 : 判断点与直线的关系 * 输入参数1: pt1　直线的第１个点 * 输入参数2: pt2　直线的第２个点 * 输入参数3: ptNode　需要判断的点 * 输出参数　: 无 * 返回参数　:　0：点在直线上　大于0：点在直线Pt3顺时针那侧　小于：0,点在直线Pt3逆时针那侧， * 日 期　: 2018年09月13日 * 作 者　: mark-plus ********************************************************************/ int pointLineRelationship(const myPoint &pt1, const myPoint &pt2, myPoint &ptNode) { //iValue=0,点在分割线上，iValue>0,点在直线Pt3顺时针那侧，iValue<0,点在直线Pt3逆时针那侧， int iRet = ((pt2.y - pt1.y) * ptNode.x + (pt1.x-pt2.x) * ptNode.y + (pt2.x*pt1.y - pt1.x*pt2.y)); return iRet; } /******************************************************************** * 函数名称 : line2LineAnge * 函数功能 : 求两直线的夹角(小于90) * 输入参数1: pt1　直线1的第１个点 * 输入参数2: pt