您當前位置：首頁 > php開源 > php教程 > 計算幾何問題匯總--點與線的位置關系

計算幾何問題匯總--點與線的位置關系

來源：程序員人生發(fā)布時間：2016-09-26 08:53:10 閱讀次數(shù)：3117次

點與點之間，線與線之間，點與線之間的位置關系是1類非常重要的問題。它不但是平面幾何學的基石，也常常利用于LBS(Location Based Service)，社交網(wǎng)絡，和數(shù)據(jù)庫查詢等領域。

本文中，我將給出判斷這些關系的相干算法，作為參考。需要說明的是，我給出的這些問題的解法，都是建立在2維平面空間之上。有關多維空間的位置關系，大家可以仿照2維空間中問題的思路，做相應的拓展。

語言上，我用確當然還是Python.

點與點之間的距離

先從最簡單的點與點的位置關系說起。1般情況下，我們只關心點與點之間的距離。

1. 點類的定義

為使算法思路更加清晰，先定義點類Point，既然是在2維空間上，那末每一個點都應當有兩個屬性：x, y分別代表點的橫縱坐標。

class Point(object): """Point are two-dimension""" def __init__(self, x, y): self.x = x self.y = y

接下來就看看如何計算兩點之間距離：固然可以用初中學的歐氏距離最基本的計算方法。但是斟酌到代碼編寫的效力，和方便以后向高維空間拓展。我在本文中將盡可能使用向量計算。

而為了簡化代碼，我們使用對向量運算已相當做熟的庫numpy

2. 兩點之間距離的計算

明顯，兩點可以構成向量，而向量的長度則是其內積的開方?？臻g中，點A與點B的距離可以用向量AB?→?的模|AB?→?|表示。所以，現(xiàn)在需要做的，就是寫1個函數(shù)，以兩點為參數(shù)，計算由這兩點構成的向量的模。

為了和本文以后的問題保持編碼風格上1致，同時簡化代碼編寫。我使用對向量運算已極其成熟的庫numpy幫助計算。并且定義了1個新的類Vector，類Vector以向量的出發(fā)點和終點作為輸入，生成1個只具有屬性x和y的向量對象。

最后，和前面定義的類放在1起，代碼以下：

import numpy as np # numpy help us do some vector calculation 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: a Vector object v = Vector(p1, p2) # translate v to a ndarray object t = np.array([v.x, v.y]) # calculate the inner product of ndarray t return float(np.sqrt(t @ t))

說明1下，在Python3.5以后的版本中，使用numpy庫時，ndarray對象之間的乘法可以用@，代替之前的v1.dot(v2)這樣的情勢。

點與線之間的位置關系

1. 線的分類

點與線之間的位置關系就要略微復雜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定說左側的點就是p1，右側就是p2）

2. 點與線的位置關系

(1) 計算點到直線的距離

如Fig.1(a)所示，現(xiàn)要求點C到直到直線AB的距離。還是向量法，據(jù)向量知識可知：

c o s ∠ C A B = A C ? \to ? ? A B ? \to ? | A C ? \to ? | ? | A B ? \to ? |

再由3角形知識可知，線段AD的長度為：

| A C ? \to ? | ? c o s ∠ C A B

所以，AD?→?可以這樣計算：

A D ? \to ? = A B ? \to ? | A B ? \to ? | ? | A D ? \to ? | = A B ? \to ? | A B ? \to ? | ? | A C ? \to ? | ? c o s ∠ C A B = A B ? \to ? ? A C ? \to ? | A B ? \to ? | 2 A B ? \to ?

當AD?→?計算完成以后，可以根據(jù)AD?→?相應的坐標值得到點D的坐標，再由上面點和點之間的距離，便可得到線段CD的長度。

這里寫圖片描述

給出完全的代碼以下：

import numpy as np # numpy help us do some vector calculation 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: a Vector object v = Vector(p1, p2) # translate v to a ndarray object t = np.array([v.x, v.y]) # calculate the inner product of ndarray t 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""" # two Vector object vector_AB = Vector(AB.p1, AB.p2) vector_AC = Vector(AB.p1, C) # two ndarray object tAB = np.array([vector_AB.x, vector_AB.y]) tAC = np.array([vector_AC.x, vector_AC.y]) # vector AD, type: ndarray tAD = ((tAB @ tAC) / (tAB @ tAB)) * tAB # get point D 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) <

生活不易，碼農辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生