最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • C++实现常用的平面计算几何问题求解

    通过封装经常使用的点、线段类型,并提供点、线间的相互关系运算,为计算几何工具库的编写提供基础框架。

    代码以下:(代码正确性仍需测试,谨慎使用)

    //参考
    //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;

    //预定义
    #define Min(x, y) ((x) < (y) ? (x) : (y))
    #define Max(x, y) ((x) > (y) ? (x) : (y))

    //点对象
    typedef struct Point {
    double x, y;
    //构造函数
    Point(double x, double y) : x(x), y(y) {}
    //无参数时的构造函数
    Point() : x(0), y(0) {}
    //获得到点pt的距离
    double distance(const Point& pt) {
    return sqrt( (x – pt.x) * (x – pt.x) + (y – pt.y) * (y – pt.y));
    }
    //判断两点是不是同1个点
    bool equal(const Point& pt) {
    return ((x – pt.x) == 0) && (y – pt.y == 0);
    }
    } Point;

    //线段对象
    typedef struct PartLine {
    Point pa, pb;
    double length;

    PartLine() {
    length = 0;
    }

    //构造函数
    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;
    }

    //利用叉积计算点到线段的垂直距离
    //注意:此结果距离有正负之分
    //若pc点在线段的逆时针方向,则距离为正;否则,距离为副值
    double getDistantToPoint(Point pc) {
    double area = crossProd(pc) / 2;
    return area * 2 / length;
    /* 利用海伦公式计算
    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;
    */
    }

    //向量的叉积
    /* 计算向量的叉积(ABxAC A(x1,y1) B(x2,y2) C(x3,y3))是计算行列式
    | x1-x0 y1-y0 |
    | x2-x0 y2-y0 |
    的结果(向量的叉积 AB X AC)
    */
    //计算AB与AC的叉积—叉积的绝对值是两向量所构成平行4边形的面积
    double crossProd(Point& pc) {
    //计算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的两侧或线段或线段的延长线上
    cond2 = d3 * d4 <= 0, //pl.pa和pl.pb在this的两侧或线段或线段的延长线上
    cond3 = d5 != 0, //pl.pa不在线段和延长线上
    cond4 = d6 != 0; //pl.pb不在线段和延长线上
    return cond1 && cond2 && cond3 && cond4;
    }

    //判断两线段是不是平行
    bool isParallel(PartLine& pl) {
    double v1 = crossProd(pl.pa),
    v2 = crossProd(pl.pb);
    return (v1 == v2) && (v1 != 0);
    }

    //沿pa点旋转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点旋转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;
    }

    //获得两线段的相交点—如果不相交返回valid=false
    //如果多个交点,给出正告
    Point getCrossPoint(PartLine& pl, bool& valid) {
    valid = false;
    if (!isIntersected(pl)) { //不相交
    return Point();
    }
    if ( inSameLine(pl) ) { //有交点且共线
    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; }
    //多个焦点
    cout << "毛病:计算交点结果数量为无穷" << 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最近的点
    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个点在线段上的镜像点
    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 << "最近点:" << np.x << ", " << np.y << endl;
    bool isvalid;
    np = pl1.getCrossPoint(pl3, isvalid);
    cout << "两线段的相交点:" << (isvalid ? "有效":"无效") << "=" << np.x << ", " << np.y << endl;
    PartLine plx = pl1.rotateA(M_PI / 2);
    printf("旋转90度后:%f %f %f %f
    ", plx.pa.x, plx.pa.y, plx.pb.x, plx.pb.y);
    return 0;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » C++实现常用的平面计算几何问题求解

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级