浏览量:129

3.3. 点到线性对象的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

3.3. 点到线性对象的距离

点到线性对象的距离问题包括二维和三维两种情况,三维空间上点到线性对象的距离计算方法与二维的相同,只是维度上存在差别,所以这里只阐述二维的情况。

3.3.1. 点到直线的距离

问题描述:求二维空间上的点\(Y\)到直线\(L(t) = P + t\vec d,t \in \left( { - \infty , + \infty } \right)\)的距离。

2015-3-22 15-28-01

图3.3 点\(Y\)到直线\(L(t)\)的距离

如图3.3所示,设直线上与\(Y\)最近的点是\(L(\hat t)\),易知点\(L(\hat t)\)是点\(Y\)到直线上的投影,\(Y\)\(L(\hat t)\)的连线,垂直于直线。因此可以得到等式:

\[\vec d \cdot (Y - L(\hat t)) = \vec d \cdot (Y - P - \hat t\vec d) = \vec d \cdot (Y - P) - \hat t{\left\| {\vec d} \right\|^2} = 0 \tag{3.15}\]

 解得\(\hat t = \vec d \cdot (Y - P)/{\left\| {\vec d} \right\|^2}\),把\(\hat t\)值代入直线方程,得到点\(L(\hat t)\),点\(Y\)与点\(L(\hat t)\)距离的平方是,\({\left\| {Y - L(\hat t)} \right\|^2}\),可得:

\[{{\mathop{\rm dist}\nolimits} ^2}(L,Y) = {\left\| {Y - L(\hat t)} \right\|^2} = {\left\| {Y - P - \hat t\vec d} \right\|^2} = {\left\| {Y - P} \right\|^2} - \frac{{{{\left( {\vec d \cdot (Y - P)} \right)}^2}}}{{{{\left\| {\vec d} \right\|}^2}}} \tag{3.16}\]

如果直线的方向向量是单位长度,即\(\left\| {\vec d} \right\| = 1\),则计算距离平方时,不再需要除法运算。

3.3.2. 点到射线的距离

问题描述:求二维空间上的点\(Y\)到射线\(L(t) = P + t\vec d,t \in \left[ {0, + \infty } \right)\)的距离。

2015-3-22 15-28-12

图3.4 点\(Y\)到射线\(L(t)\)的距离

如图3.4(a)所示,与点\(Y\)到直线距离计算的方法相类似,不同的是当点\(Y\)在射线所在的直线的投影不在射线上时,点到射线原点的距离就是点到射线的距离,如图3.4(b)所示。换句话说,求点到射线的距离,需要对求得的\(\hat t\)判断,如果\(\hat t \prec 0\),则点到射线原点的距离最近;否则,点到射线上的投影\(L(\hat t)\)的距离最近。最后的计算公式,如等式(3.17)所示。

\[{{\mathop{\rm dist}\nolimits} ^2}(L,Y) = \left\{ {\begin{array}{*{20}{l}}{{{\left\| {Y - P} \right\|}^2} - \frac{{{{\left( {\vec d \cdot (Y - P)} \right)}^2}}}{{{{\left\| {\vec d} \right\|}^2}}},}&{\vec d \cdot (Y - P) > 0}\\{{{\left\| {Y - P} \right\|}^2},}&{\vec d \cdot (Y - P) \le 0}\end{array}} \right. \tag{3.17}\]

3.3.3. 点到线段的距离

问题描述:求二维空间上的点\(Y\)到线段\(\overline {{P_0}{P_1}} \)的距离。

2015-3-22 15-28-26

图3.5 点\(Y\)到线段\(\overline {{P_0}{P_1}} \)的距离

\(Y\)在线段所在直线的投影可能不在线段上,即投影点可能在线段的起点之前或者终点之后,如图3.5所示,总共有三种情况。线段可以表示成类似于直线参数方程的形式,即表示为\(S(t) = {P_0} + ({P_1} - {P_0})t,t \in [0,1]\),代入(3.15)式,计算得到\(\hat t\),对\(\hat t\)进行判断。若\(0 \le \hat t \le 1\),则是图3.5(a)所示的情况,点\(Y\)\(L(\hat t)\)的距离最近;如果\(\hat t \prec 0\),则是图3.5(b)所示的情况,点\(Y\)\({P_0}\)的距离最近;如果\(\hat t \succ 1\),则是图3.5(c)所示的情况,点\(Y\)\({P_1}\)的距离最近。最终,点\(Y\)到线段\(\overline {{P_0}{P_1}} \)的公式是:

\[{{\mathop{\rm dist}\nolimits} ^2}(S,Y) = \left\{ {\begin{array}{*{20}{l}}{{{\left\| {Y - {P_0}} \right\|}^2},}&{\hat t \le 0}\\{{{\left\| {Y - {P_0}} \right\|}^2} - \frac{{{{\left( {\vec d \cdot (Y - {P_0})} \right)}^2}}}{{{{\left\| {\vec d} \right\|}^2}}},}&{\hat t \in (0,1)}\\{{{\left\| {Y - {P_1}} \right\|}^2},}&{\hat t \ge 0}\end{array}} \right. \tag{3.18}\]

spacer

Leave a reply