點與點之間， 線與線之間，點與線之間的位置關(guān)系是1類非常重要的問題。它不但是平面幾何學的基石，也常常利用于LBS(Location Based Service)，社交網(wǎng)絡(luò)，和數(shù)據(jù)庫查詢等領(lǐng)域。
本文中，我將給出判斷這些關(guān)系的相干算法，作為參考。需要說明的是，我給出的這些問題的解法，都是建立在2維平面空間之上。有關(guān)多維空間的位置關(guān)系，大家可以仿照2維空間中問題的思路，做相應(yīng)的拓展。
語言上，我用確當然還是Python.
點與點之間的距離
先從最簡單的點與點的位置關(guān)系說起。1般情況下，我們只關(guān)心點與點之間的距離。
1. 點類的定義
為使算法思路更加清晰，先定義點類Point，既然是在2維空間上，那末每一個點都應(yīng)當有兩個屬性：x, y分別代表點的橫縱坐標。
class Point(object): """Point are two-dimension""" def __init__(self, x, y): self.x = x
self.y = y
接下來就看看如何計算兩點之間距離：固然可以用初中學的歐氏距離最基本的計算方法。但是斟酌到代碼編寫的效力，和方便以后向高維空間拓展。我在本文中將盡可能使用向量計算。
而為了簡化代碼，我們使用對向量運算已相當做熟的庫numpy
2. 兩點之間距離的計算
明顯，兩點可以構(gòu)成向量，而向量的長度則是其內(nèi)積的開方?？臻g中，點A與點B的距離可以用向量AB?→?的模|AB?→?|表示。所以，現(xiàn)在需要做的，就是寫1個函數(shù)，以兩點為參數(shù)，計算由這兩點構(gòu)成的向量的模。
為了和本文以后的問題保持編碼風格上1致，同時簡化代碼編寫。我使用對向量運算已極其成熟的庫numpy幫助計算。并且定義了1個新的類Vector，類Vector以向量的出發(fā)點和終點作為輸入，生成1個只具有屬性x和y的向量對象。
最后，和前面定義的類放在1起，代碼以下：
import numpy as np class Point(object): """Point are two-dimension""" def __init__(self, x, y): self.x = x
self.y = y class Vector(object): """start and end are two points""" def __init__(self, start, end): self.x = end.x - start.x
self.y = end.y - start.y def pointDistance(p1, p2): """calculate the distance between point p1 and p2""" v = Vector(p1, p2) t = np.array([v.x, v.y]) return float(np.sqrt(t @ t))
說明1下，在Python3.5以后的版本中，使用numpy庫時，ndarray對象之間的乘法可以用@，代替之前的v1.dot(v2)這樣的情勢。
點與線之間的位置關(guān)系
1. 線的分類
點與線之間的位置關(guān)系就要略微復雜1些了，復雜的地方在于線分線段和直線兩種情況。但是，在定義類的時候我都用兩點來代表線段（直線）的兩個屬性。因而，最少代碼看上去是沒甚么分別的。
不同的地方在于，線段的兩個點事兩個端點，而直線的兩個點是直線上任意兩點。
class Segment(object): """the 2 points p1 and p2 are unordered""" def __init__(self, p1, p2): self.p1 = p1
self.p2 = p2 class Line(object): """p1 and p2 are 2 points in straight line""" def __init__(self, p1, p2): self.p1 = p1
self.p2 = p2
需要注意的是，這里并沒有說線段的兩個點是甚么順序（不1定說左側(cè)的點就是p1，右側(cè)就是p2）
2. 點與線的位置關(guān)系
(1) 計算點到直線的距離
如Fig.1(a)所示，現(xiàn)要求點C到直到直線AB的距離。還是向量法，據(jù)向量知識可知：
cos∠CAB=AC?→??AB?→?|AC?→?|?|AB?→?|
再由3角形知識可知，線段AD的長度為：
|AC?→?|?cos∠CAB
所以，AD?→?可以這樣計算：
AD?→?=AB?→?|AB?→?|?|AD?→?|=AB?→?|AB?→?|?|AC?→?|?cos∠CAB=AB?→??AC?→?|AB?→?|2AB?→?
當AD?→?計算完成以后，可以根據(jù)AD?→?相應(yīng)的坐標值得到點D的坐標，再由上面點和點之間的距離，便可得到線段CD的長度。
給出完全的代碼以下：
import numpy as np class Point(object): """Point are two-dimension""" def __init__(self, x, y): self.x = x
self.y = y class Segment(object): """the 2 points p1 and p2 are unordered""" def __init__(self, p1, p2): self.p1 = p1
self.p2 = p2 class Line(object): """p1 and p2 are 2 points in straight line""" def __init__(self, p1, p2): self.p1 = p1
self.p2 = p2 class Vector(object): """start and end are two points""" def __init__(self, start, end): self.x = end.x - start.x
self.y = end.y - start.y def pointDistance(p1, p2): """calculate the distance between point p1 and p2""" v = Vector(p1, p2) t = np.array([v.x, v.y]) return float(np.sqrt(t @ t)) def pointToLine(C, AB): """calculate the shortest distance between point C and straight line AB, return: a float value""" vector_AB = Vector(AB.p1, AB.p2)
vector_AC = Vector(AB.p1, C) tAB = np.array([vector_AB.x, vector_AB.y])
tAC = np.array([vector_AC.x, vector_AC.y]) tAD = ((tAB @ tAC) / (tAB @ tAB)) * tAB Dx, Dy = tAD[0] + AB.p1.x, tAD[1] + AB.p1.y
D = Point(Dx, Dy) return pointDistance(D, C)
(2) 判斷點是不是在直線上
既然已能夠計算點到直線的距離了，那末，只需要看點到直線的距離是不是為0便可知道這個點在不在直線上。
接著上面的代碼，可以寫出以下函數(shù)：
def pointInLine(C, AB): """determine whether a point is in a straight line""" return pointToLine(C, AB) <
