求两条直线交点的面向对象实现
求两条直线交点的面向对象实现
本文介绍了一种面向对象的编程方法来求解两条直线的交点。通过定义点、方向和直线的类，可以清晰地实现算法逻辑，并通过具体的代码示例展示了如何判断直线是否退化、是否平行、是否重合，以及如何计算交点坐标。
输入输出
输入：直线1上的两个点( x 1 , y 1 ) (x_1,y_1)(x1 ,y1 )，( x 2 , y 2 ) (x_2,y_2)(x2 ,y2 )，直线2上的两个点( x 3 , y 3 ) (x_3,y_3)(x3 ,y3 )，( x 4 , y 4 ) (x_4, y_4)(x4 ,y4 )。
输出：
- 直线错误输出：error
- 直线平行输出：parallel
- 直线重合输出：coincide
- 其他情况输出交点坐标保留两位有效数字。
算法流程
下面讲解每一个子流程。
是否有误
有误的情况其实就是直线退化成点，比如对于直线1就是x 1 = = x 2 & & y 1 = = y 2 x1==x2 &&y1==y2x1==x2&&y1==y2，
我们后续在Line中加入isDegenerate方法判断是否是退化点。
是否平行
平行可以通过两条直线的方向向量叉乘得到，如果我们直线用p ⃗ + t d ⃗ \vec{p}+t\vec{d}p +td那么如果这两条直线平行等价于d ⃗ 1 × d ⃗ 2 = 0 \vec{d}_1 \times \vec{d}_2 = 0d1 ×d2 =0
是否重合
重合的话就是在两条直线平行的基础上，判断直线1上的任意点是否在直线2上，如果在的话就是重合。当然也可以通过判断直线1上一点与直线2上的一点定义的直线是否和直线1/直线2平行。
这里主要说下通过判断直线1上的任意点是否在直线2上的方法。
比如判断直线1上的点( x 1 , y 1 ) (x1,y1)(x1,y1)是否在直线2上，首先直线2可以表示为d ⃗ y 2 ( x − x 3 ) = d ⃗ x 2 ( y − y 3 ) \vec{d}_y^2(x-x_3)=\vec{d}_x^2(y-y3)dy2 (x−x3 )=dx2 (y−y3)，那么只需要把( x 1 , y 1 ) (x1,y1)(x1,y1)代入判断等式是否成立即可，下面是这个表示的推导过程。
我们其实可以把直线表示成等式组：
- x 3 + t d ⃗ x 2 = x x_3 + t\vec{d}_x^2=xx3 +tdx2 =x
- y 3 + t d ⃗ y 2 = y y_3 + t\vec{d}_y^2=yy3 +tdy2 =y
那么由上面的等式组其实可以得到t tt的两种表示：
- t = x − x 3 d ⃗ x 2 t = \frac{x - x_3}{\vec{d}_x^2}t=dx2 x−x3
- t = y − y 3 d ⃗ y 2 t = \frac{y-y_3}{\vec{d}_y^2}t=dy2 y−y3
其实把t tt消去就可以得到上面直线表示，但这里需要注意的特殊情况就是d ⃗ x 2 = 0 \vec{d}_x^2=0dx2 =0或d ⃗ y 2 = 0 \vec{d}_y^2=0dy2 =0。
如果d ⃗ x 2 = 0 \vec{d}_x^2=0dx2 =0直线就是一条垂直于x轴的直线，如果d ⃗ y 2 = 0 \vec{d}_y^2=0dy2 =0直线就是一条垂直于y轴的直线。
最终可以得到直线2的表示d ⃗ y 2 ( x − x 3 ) = d ⃗ x 2 ( y − y 3 ) \vec{d}_y^2(x-x_3)=\vec{d}_x^2(y-y3)dy2 (x−x3 )=dx2 (y−y3)。
找到交点
如果前面的判断都没通过，那么这两条直线相交，我们要找到它们的交点。
那么其实就是求解下面的等式组：
也可以表示成矩阵形式
这里的a 1 a_1a1 、a 2 a_2a2 、b 1 b_1b1 、b 2 b_2b2 、c 1 c_1c1 、c 2 c_2c2 、x xx、y yy可以分别表示如下
- a 1 = d ⃗ y 1 a_1=\vec{d}_y^1a1 =dy1
- b 1 = − d ⃗ x 1 b_1=-\vec{d}_x^1b1 =−dx1
- c 1 = d ⃗ y 1 x 1 − d ⃗ x 1 y 1 c_1=\vec{d}_y^1x_1-\vec{d}_x^1y_1c1 =dy1 x1 −dx1 y1
- a 2 = d ⃗ y 2 a_2=\vec{d}_y^2a2 =dy2
- b 2 = − d ⃗ x 2 b_2=-\vec{d}_x^2b2 =−dx2
- c 2 = d ⃗ y 2 x 3 − d ⃗ x 2 y 3 c_2=\vec{d}_y^2x_3-\vec{d}_x^2y_3c2 =dy2 x3 −dx2 y3
这里可以通过克莱姆法则求解：
- 计算系数矩阵的行列式D DD
如果D = 0 D=0D=0，则方程组无唯一解(也就是直线平行或重合) - 计算x xx的行列式D x D_xDx ，用常熟项替换x xx的系数
- 同理计算y yy的行列式D y D_yDy
- 求解x xx和y yy
UML类图
代码
#include <iostream>
#include <iomanip>
using namespace std;
#define Square(x) ((x) * (x))
struct Point
{
double _x, _y;
Point() = delete;
Point(double x, double y) : _x(x), _y(y) {}
Point(const Point& other) : _x(other._x), _y(other._y) {}
double dist(const Point& other) const {
return sqrt(Square(_x - other._x) + Square(_y - other._y));
}
};
struct Direction
{
double _x, _y;
Direction() = delete;
Direction(const Point& pt1, const Point& pt2)
{
const double distance = pt1.dist(pt2);
if (distance == 0.0) // degenerate
{
_x = 0.0;
_y = 0.0;
}
else
{
_x = (pt1._x - pt2._x) / distance;
_y = (pt1._y - pt2._y) / distance;
}
}
double operator^(const Direction& other) const
{
return _x * other._y - _y * other._x;
}
};
struct Line
{
Point _pt;
Direction _dir;
Line() = delete;
Line(const Point& pt1, const Point& pt2) : _pt(pt1), _dir(pt1, pt2) {}
bool isDegenerated() const
{
return _dir._x == 0.0 && _dir._y == 0.0;
}
bool isParallel(const Line& other) const
{
return (_dir ^ other._dir) == 0.0;
}
void findIntersection(const Line& other) const
{
if (isDegenerated() || other.isDegenerated())
{
cout << "error" << endl;
return;
}
if (isParallel(other))
{
// parallel
const double left = other._dir._y * (_pt._x - other._pt._x);
const double right = other._dir._x * (_pt._y - other._pt._y);
if (left == right)
{
// coincident
cout << "coincident" << endl;
}
else {
// just parallel
cout << "parallel" << endl;
}
return;
}
// have intersection
const double a1 = _dir._y;
const double b1 = -_dir._x;
const double c1 = _dir._y * _pt._x - _dir._x * _pt._y;
const double a2 = other._dir._y;
const double b2 = -other._dir._x;
const double c2 = other._dir._y * other._pt._x - other._dir._x * other._pt._y;
const double D = a1 * b2 - a2 * b1;
const double Dx = c1 * b2 - c2 * b1;
const double Dy = a1 * c2 - a2 * c1;
cout << fixed << setprecision(2) << Dx / D << " " << Dy / D << endl;
}
};
int main()
{
// case1: coincident
Point pt1{ 0.0, 0.0 };
Point pt2{ 1.0, 1.0 };
Line line1{ pt1, pt2 };
Point pt3{ 3.0, 3.0 };
Point pt4{ 2.0, 2.0 };
Line line2{ pt3, pt4 };
line1.findIntersection(line2);
// case2: just parallel
Point pt5{ 2.0, 0.0 };
Point pt6{ 3.0, 1.0 };
Line line3{ pt5, pt6 };
line1.findIntersection(line3);
// case3: intersect
Point pt7{ 2.0, 0.0 };
Point pt8{ 3.0, -1.0 };
Line line4{ pt7, pt8 };
line1.findIntersection(line4); // 1.00 1.00
}
参考资料
克拉默法则证明(Cramer’s Rule)