计算几何算法2.关于线和点到线的距离（二维和三维）（人家写的，不能转发标记一下）

转发来自 http://www.everyinch.net/index.php/computergeometry2/

关于直线
直线方程
点到直线的距离
用两点表示的直线
2d隐式表示的直线的情形
参数方程表示的直线
一个点到射线或线段的距离
代码实现

距离计算是计算机图形学和计算几何的基本问题&＃xff0c;而且有很多关于这方面的公式。不过&＃xff0c;由于对象描述方式不同&＃xff0c;有替代方案可供选择。我们将说明其中的一些情况。

自始至终&＃xff0c;我们需要有一个度量来计算两点之间的距离。我们假定有基于毕达哥拉斯定理的欧几里德度量标准。也就是说&＃xff0c;对于一个n维向量v &＃61;&＃xff08;用V1&＃xff0c;V2 ,…,Vn&＃xff09;&＃xff0c;其长度| v |由下式给出&＃xff1a;

而两点P值&＃xff08;的p1&＃xff0c;p2 ,…, pn&＃xff09;和Q &＃61;&＃xff08;q1&＃xff0c;q2及,…, qn&＃xff09;&＃xff0c;它们之间的距离是&＃xff1a;

关于直线&＃xff1a;

定义直线L是通过给两个不同的点P0和 P1来定义的。事实上&＃xff0c;它定义了一条从P0至P1的线段&＃xff0c;这是古希腊人理解直线的方式&＃xff0c;它与我们所知道的两个端点之间的最短路径的自然直觉相吻合。直线可以向两端无限地延长&＃xff0c;这就是我们今天经常提到的直线的概念。不过&＃xff0c;对于古希腊人&＃xff0c;线是可以无限延长的有限线段。这种定义方式的好处是&＃xff0c;它适用于所有维度&＃xff1a;二维&＃xff0c;三维&＃xff0c;或任何n维空间。而且&＃xff0c;一般在实际应用中通过端点来定义一条线段&＃xff0c;因为线段一般用来表示多边形、多面体或内嵌图形的边。

直线L也可以通过一个点和一个方向来定义。让P0是直线L上的一点&＃xff0c;vL是表示直线方向的非零向量。这个方法等价于直线的两点定义的方式&＃xff0c;由于可以把vL&＃61;&＃xff08;P1-P0&＃xff09;。或者给定P0和vL&＃xff0c;可以选择P1&＃61;P0&＃43;vL 作为直线的第二个点。如果vL被归一化为方向的单位向量&＃xff0c;uL&＃61;vL/|vL|&＃xff0c;那么它的元素就是直线L的方向余弦。也就是说&＃xff0c;在n 维&＃xff0c;让qi (i&＃61;1,n)是直线L和第i个轴ai的角度&＃xff08;例如&＃xff0c;在2D&＃xff0c;a1是在x轴和a2是y轴&＃xff09;。那么&＃xff0c;向量vL &＃61; (vi)&＃xff0c;有vi &＃61; cos(qi)是直线L的方向向量。在2d如下图所示&＃xff0c;如果q 是直线L与x轴的角度&＃xff0c;那么cos(q2) &＃61; sin(q)&＃xff0c;即vL &＃61; (cos(q1), cos(q2)) &＃61; (cos(q), sin(q)) 是L的单位方向向量&＃xff0c;因为&＃xff1a;cos2(q) &＃43; sin2(q) &＃61; 1。同样&＃xff0c;在任意维度上&＃xff0c;方向余弦的平方和为1&＃xff0c;即&＃xff1a;S cos2(qi) &＃61; 1。

直线方程&＃xff1a;

直线也可以定义为为未知方向上的点坐标方程。以下是一个在实践中通常遇到方程式&＃xff1a;

2d显式的表示方法是在中学讲过的&＃xff0c;但它不是最灵活的方法。2d隐式的表示方法是较为有效的&＃xff0c;显式方法转换为隐式方法是容易实现的。通常使用隐式方法的两个参数定义一个向量nL&＃61;(a,b)&＃xff0c;它垂直于直线L。这是因为直线L上任意两点P0&＃61;(x0,y0) 和 P1&＃61;(x1,y1)&＃xff0c;我们有nL·vL &＃61; (a,b)·(P1-P0) &＃61; a(x1–x0) &＃43; b(y1–y0) &＃61; f(P1) – f(P0) &＃61; 0。因此&＃xff0c;我们说nL是直线L的单位向量&＃xff0c;意味着垂直于直线L。而且&＃xff0c;给定任意直线的法向量nL&＃61;(a,b)和一个直线上任意一点P0&＃xff0c;隐式方程的法线形式是&＃xff1a;

这个方程如果a2 &＃43; b2 &＃61; 1则是归一化的&＃xff0c;从而nL是单位法向量&＃xff0c;常常用uL表示。

不幸的是&＃xff0c;一个隐式&＃xff08;或显式&＃xff09;方程仅仅能够定义一条2d直线&＃xff0c;而在3d中直线方程定义了一个平面&＃xff0c;在n维空间中它定义了一个n-1维的超平面。

另一方面&＃xff0c;在任意n维空间&＃xff0c;直线的参数方程是有效的&＃xff0c;也是最通用的一种表示方法。通过两个点P0和P1、方向向量vL来定义一条直线&＃xff0c;即&＃xff1a;

其中t是一个实数。其中P(0)&＃61;P0&＃xff0c;P(1)&＃61; P1。P(t) 有 0<t<1 表示P0和P1之间的线段&＃xff0c;其中t是分数。也就是说&＃xff0c;t &＃61; d(P0,P(t)) / d(P0,P1)&＃xff0c;因此&＃xff0c;P(1/2)&＃61;(P0&＃43;P1)/2 是线段的中点。而且&＃xff0c;如果t <0&＃xff0c;则P(t)位于P0方向的外侧&＃xff0c;如果t >1&＃xff0c;则P(t)位于P1方向的外侧。

我们可以方便地从一种表示方法向另一种表示方法转换。例如&＃xff0c;给定两个直线上的点P0&＃61;(x0,y0) 和 P1&＃61;(x1,y1) &＃xff0c;可以推导出它的隐式方程&＃xff0c;即通过vL&＃61;(xv,yv)&＃61;P1-P0&＃61;(x1–x0, y1–y0)&＃xff0c;我们有nL&＃61;(-yv,xv)&＃61;(y0–y1,x1–x0) 是垂直于直线L的法向量。因为 nL·vL&＃61; 0&＃xff0c;直线L的隐式方程为&＃xff1a;

其中x和y的系数是nL的组成部分。

另外&＃xff0c;在2d&＃xff0c;如果直线L与x轴的角度为q&＃xff0c;回忆一下即vL &＃61; (cos(q), sin(q)) 是单位方向向量&＃xff0c;那么nL &＃61; (-sin(q), cos(q)) 是单位法向量。所以如果P0&＃61;(x0,y0)是直线L上一点&＃xff0c;那么直线L归一化的隐式方程为&＃xff1a;

因为sin2(q) &＃43; cos2(q) &＃61; 1。参数方程是&＃xff1a;

点到直线的距离&＃xff1a;

给定一条线L和一个点P&＃xff0c;让d(P,L) 表示点P到直线L的距离&＃xff0c;这是P到直线L的最短距离&＃xff0c;假如L是一条无限延伸的直线&＃xff0c;那么这是一个从点P到直线L的垂线。但是如果直线L是一条有限长度的线段S&＃xff0c;那么垂线的底可能超出线段&＃xff0c;这是计算最短距离需要考虑一些其他的因素。我们首先考虑点到无限延伸的直线的垂直距离。

用两点表示的直线&＃xff1a;

在2d和3d中&＃xff0c;直线L是由两个点P0和 P1确定&＃xff0c;可以使用叉乘直接计算从任意一点P到直线L的距离。2d情况可以作为z轴等于0的特例来处理。关键的发现是两个3d向量的叉乘等于由它们围起来的平行四边形的面积&＃xff0c;既然|v×w| &＃61; |v| |w| |sinq | &＃xff0c;其中q 是两个向量v和w之间的夹角。同时&＃xff0c;平行四边形的面积还等于底乘以高&＃xff0c;我们把高定义为d(P,L)。vL&＃61;P0P1&＃61;(P1-P0) 和w&＃61;P0P&＃61;(P-P0)&＃xff0c;如图&＃xff1a;

那么&＃xff0c;|vL× w| &＃61; Area(平行四边形(vL,w) ) &＃61; |vL| d(P,L)的结果为&＃xff1a;

其中uL&＃61; vL / |vL| 是直线L的单位方向向量&＃xff0c;如果需要计算许多个点到一条直线的距离&＃xff0c;首先计算 uL是最有效的方式。

对于内嵌到3d空间的2d情况&＃xff0c;点P&＃61;(x,y,0)&＃xff0c;叉乘为&＃xff1a;

和距离计算公式为&＃xff1a;

2d隐式表示的直线的情形&＃xff1a;

在2d&＃xff0c;直线L是定义为隐式方程f(x,y) &＃61; ax&＃43;by&＃43;c &＃61; 0。对于任意2d点P&＃61;(x,y)&＃xff0c;距离d(P,L)可以利用这个方程来直接计算。

回忆一下&＃xff0c;向量nL &＃61; (a,b)垂直于直线L。利用nL可以计算任意点P到直线L的距离。手续ian选择直线L上任意点P0&＃xff0c;然后做P0P到nL的垂线&＃xff0c;如下图所示&＃xff1a;

我们有&＃xff1a;
&＃xff08;1&＃xff09;由于a和b不能同时为零&＃xff0c;假设一个a!&＃61;0&＃xff0c;并选择直线上点P0&＃61;(-c/a,0)&＃xff0c; [否则&＃xff0c;若a &＃61; 0而b !&＃61; 0&＃xff0c;选择P0&＃61;(0,-c/b)&＃xff0c;具有同样的结果]
&＃xff08;2&＃xff09;对于任意直线L上的点P0我们有&＃xff1a;nL · P0P &＃61; |nL| |P0P| cos q &＃61; |nL| d(P,L)
&＃xff08;3&＃xff09;对于我们指定的P0&＃xff1a; nL ·P0P &＃61; (a,b) · (x&＃43;c/a, y) &＃61; ax&＃43;c&＃43;by &＃61; f(x,y) &＃61; f(P)
结合&＃xff08;2&＃xff09;和&＃xff08;3&＃xff09;得出公式如下&＃xff1a;

而且&＃xff0c;我们可以在|nL|上除以f(x,y)的系数而预先归一化方程&＃xff0c;使 |nL|&＃61;1。就会得到非常有效率的公式&＃xff1a;

其中对于每次的距离计算只有2次乘法和2次加法。因此&＃xff0c;如果需要计算二维多点到直线L的距离&＃xff0c;那么应该计算单位法向量来使用这个公式。另外请注意&＃xff0c;如果只是比较距离&＃xff08;例如&＃xff0c;需要寻找距离直线最近或最远的点&＃xff09;&＃xff0c;那么归一化是没有必要&＃xff0c;因为它只是改变了一个常数因子。

回忆以下&＃xff0c;有直线L&＃xff0c;做直线L与x轴的夹角q 和直线上任意点 P0&＃61;(x0,y0)&＃xff0c;然后归一化的隐式方程有&＃xff1a;a &＃61; -sin(q), b &＃61; cos(q), c &＃61; sin(q)x0 -cos(q)y0.

参数方程表示的直线&＃xff1a;

为了计算任意维度空间从任意点P到直线L的距离d(P,L)&＃xff0c;直线L的方程由参数方程给出。假设P(b)为点P到直线L的垂足。那么直线有参数方程给出&＃xff1a;P(t)&＃61;P0 &＃43; t (P1-P0)。那么向量P0P(b)是向量P0P在线段P0P1上的投影&＃xff0c;如图所示&＃xff1a;

因此&＃xff0c;通过vL&＃61;(P1-P0)和w&＃61;(P-P0)&＃xff0c;有&＃xff1a;

这里uL是直线的单位方向向量。这个公式的优势是&＃xff1a;可以工作在任意维度上&＃xff0c;有时候计算垂足P(b)也是有用的。在3D中叉乘公式是更有效率的。在2D当不需要P(b)时&＃xff0c;隐式的公式更好&＃xff0c;特别是计算多点到同一直线的距离的时候。

一个点到射线或线段的距离

射线R是从点P0开始向某一方向无限延伸。它可以使用参数方程表示为P(t)&＃xff0c;其中t>&＃61;0有起点P0。线段S有两个端点P0和P1&＃xff0c;使用参数方程表示为P(0)&＃61;P0 和P(1)&＃61;P1 &＃xff0c;P(t)有 0<&＃61;t<&＃61;1。

计算任意点P到射线R和线段S的距离和计算任意点P到直线L的距离之间的差异在于&＃xff1a;从点P到直线L的垂足P(b)有可能位于射线R或线段S之外&＃xff0c;在这种情况下&＃xff0c;实际的最短距离是点P到射线R的起点P0或是到线段S的两个端点之一的距离。

对于射线只有一种选择。但对于线段S而言必须确定哪个端点距离点P最近&＃xff0c;我们可以计算两个端点到点P的距离&＃xff0c;然后使用最短的那个&＃xff0c;但这不是最有效率的办法。我们首先确定点P的垂足位于线段S之外&＃xff0c;一个容易的做法是考虑线段P0P或P1P和线段P0P1之间的角度。如果任意角度是90度&＃xff0c;那么P(b)是对应的端点。如果不是90度&＃xff0c;那么看它们是锐角还是钝角。可以通过点积的方法来进行测试。这个结果决定应该使用哪个端点来计算距离&＃xff0c;或者计算点P到线段S的垂直距离本身。它可以工作在n为空间&＃xff1a;

既然w0 &＃61; v &＃43; w1&＃xff0c;两次测试的结果w0·v和v·v实际是距离计算公式的分子和分母&＃xff0c;通过预先保留计算结果从而提高算法的效率&＃xff1a;

然而&＃xff0c;在二维情况下&＃xff0c;如果我们需要计算从多点到射线或线段的距离&＃xff0c;使用规范化方程式做是否一点P有一个新的最小距离的初步测试从L会更加有效&＃xff1b;在实践中&＃xff0c;一个特定的应用细节将决定哪些是最有效的方法。

代码实现

参考文献