一、问题描述
已知两条线段P1P2和Q1Q2，判断P1P2和Q1Q2是否相交，若相交，求出交点。
两条线段的位置关系可以分为三类：
[1] 有重合部分;
[2] 无重合部分但有交点;
[3] 无交点。
注意：这里讨论的是两条线段是否相交，而非两条直线相交。
二、算法的步骤
2.1 快速排斥实验
设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，如果R和T不相交，则两线段不相交。
2.2 跨立实验
如果两线段相交，则两线段必然相互跨立对方。
若P1P2跨立Q1Q2，则矢量(P1-Q1)和(P2-Q1)位于矢量(Q2-Q1)的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。
若Q1Q2跨立P1P2，则矢量(Q1-P1)和(Q2-P1)位于矢量(P2-P1)的两侧，即( Q1 - P1 ) × ( P2 - P1 ) * ( Q2 - P1 ) × ( P2 - P1 ) < 0。
排斥实验和跨立实验的示例如下图所示。
2.3 计算交点
当判定两条线段相交后，可以进行交点的求解，求交点可以用平面几何方法，列点斜式方程来完成。但由于点斜式方程难以处理斜率为0的特殊情况，不方便求解。因而，参用向量法求解交点。
设交点为(x0,y0)，则下列方程组成立：
根据以上方程组，消除参数k1和k2，得到如下方程：
然后求解(x0,y0)，结果如下所示：
2.4 代码实现
线段相交判断/
//排斥实验
bool IsRectCross(const cv::Point &p1, const cv::Point &p2, const cv::Point &q1, const cv::Point &q2)
{
bool ret = min(p1.x, p2.x) <= max(q1.x, q2.x) &&
min(q1.x, q2.x) <= max(p1.x, p2.x) &&
min(p1.y, p2.y) <= max(q1.y, q2.y) &&
min(q1.y, q2.y) <= max(p1.y, p2.y);
return ret;
}
//跨立判断
bool IsLineSegmentCross(const cv::Point &pFirst1, const cv::Point &pFirst2, const cv::Point &pSecond1, const cv::Point &pSecond2)
{
long line1, line2;
line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
pFirst2.x * (pFirst1.y - pSecond1.y) +
pSecond1.x * (pFirst2.y - pFirst1.y);
line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
pFirst2.x * (pFirst1.y - pSecond2.y) +
pSecond2.x * (pFirst2.y - pFirst1.y);
if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
return false;
line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
pSecond2.x * (pSecond1.y - pFirst1.y) +
pFirst1.x * (pSecond2.y - pSecond1.y);
line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
pSecond2.x * (pSecond1.y - pFirst2.y) +
pFirst2.x * (pSecond2.y - pSecond1.y);
if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
return false;
return true;
}
// 获取相交点
bool GetCrossPoint(const cv::Point &p1, const cv::Point &p2, const cv::Point &q1, const cv::Point &q2, long &x, long &y)
{
if (IsRectCross(p1, p2, q1, q2))
{
if (IsLineSegmentCross(p1, p2, q1, q2))
{
//求交点
long tmpLeft, tmpRight;
tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);
x = (int)((double)tmpRight / (double)tmpLeft);
tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x - p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
y = (int)((double)tmpRight / (double)tmpLeft);
return true;
}
}
return false;
}