# 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与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;
}

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