最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

计算几何之两条线段的交点|世界时快讯

来源:博客园

1. 概述

可以通过线段的跨立实验[1]判断两条线段是否相交,但是想要进一步求它们的交点还是比较麻烦。[2]给出的方法更加简单,其原理来自求三维空间两条线段的交点[3]。为了更好的理解,本文将详细介绍二维空间两条线段的交点求解过程。

2. 两条线段交点求解过程

给定两条线段\(\overline{P_1 P_2}\)和\(\overline{P_3 P_4}\),端点表示为\(P_1(x_1,y_1)\)、\(P_2(x_2,y_2)\)、\(P_3(x_3,y_3)\)和\(P_4(x_4,y_4)\),两条线段对应的向量表示为\(\overrightarrow{P_1 P_2}\)和\(\overrightarrow{P_3 P_4}\)。假设两条线段的交点为\(P_0(x_0,y_0)\),且\(t=\frac{|\overline{P_1 P_0}|}{|\overline{P_1 P_2}|}\) 、\(s=\frac{|\overline{P_3 P_0}|}{|\overline{P_3 P_4}|}\),那么 \(P_0\) 可以表示为:

\[\begin{cases}P_0=P_1 + t * \overrightarrow{P_1 P_2} , 0\leq t \leq 1 \\P_0=P_3 + s * \overrightarrow{P_3 P_4} , 0\leq s \leq 1\end{cases}\]

\(t\)和\(s\)在等于\(0\)或\(1\)时表示两条线段相交在端点,如果为其他值,表示两条线段不相交。将点坐标代入公式得:


(资料图片仅供参考)

\[\begin{cases}x_1 + t * (x_2 - x_1) = x_3 + s * (x_4 - x_3) \\y_1 + t * (y_2 - y_1) = y_3 + s * (y_4 - y_3)\end{cases}\]

利用公式消元法求得\(t\)和\(s\):

\[t = \frac{ (x_3 - x_1)(y_4 - y_3) - (y_3 - y_1)(x_4 - x_3) }{ (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3) } \\ s = \frac{ (x_3 - x_1)(y_2 - y_1) - (y_3 - y_1)(x_2 - x_1) }{ (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3)} \]

\(t\)和\(s\)方程的分子和分母都是向量的叉乘:

\[t = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_4 P_3} } { \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \\ s = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_2 P_1} }{ \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \]

如果\(\overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} = 0\),表示两条线段平行,如果端点在另一条线段上,则该端点为交点,否则不是。如果\(t\)和\(s\)有一个没有落在区间\([0,1]\)内,则两条线段不相交。那么交点\(P_0\)的坐标为:

\[\begin{cases}x_0 = x_1 + t*(x_2 - x_1) \\y_0 = y_1 + t*(y_2 - y_1)\end{cases}\]

\[\begin{cases}x_0 = x_3 + s*(x_4 - x_3) \\y_0 = y_3 + s*(y_4 - y_3)\end{cases}\]

至此,整个求解过程介绍完成,再去看[2]的代码就非常容易理解了。

参考文献

  1. How to check if two given line segments intersect?

  2. Find the Intersection Point of Two Line Segments

  3. Intersections of Lines In Three-Space - Jon Garvin

关键词: