計算幾何初步認(rèn)識

——Wjx昨晚給我速成的計算幾何

一、點。

l        點的坐標(biāo)A(x1, y1)，B(x2, y2)

二、向量。

l        向量AB = (x2-x1, y2-y1) = (x3,y3) ，CD = (x4, y4)。

l        向量的模|AB| = sqrt(x3*x3 + y3*y3) 即向量的長度。

三、點積。

l        點積的結(jié)果為一個數(shù)值。

l        數(shù)值計算方法AB * CD ＝ x3*x4 + y3*y4。

l        幾何意義AB * CD = |AB| * |CD| * cos(a)，a為向量AB逆時針轉(zhuǎn)向CD的角度，0<=a<360，也可以認(rèn)為是兩向量的夾角，0<=a<=180。一般用于求夾角，a = acos( (AB * CD) / (|AB| * |CD|) )。也可：|CD| * cos(a) = AB * CD / |AB|，即向量CD在AB上的投影。

四、叉積。

l        叉積的結(jié)果為一個向量。

l        AB×CD數(shù)值= x3*y4 – x4*y3。

l        方向由右手螺旋定則判定。

l        幾何意義：AB×CD = |AB| * |CD| * sin(a)，取絕對值即是以AB和CD為邊的平行四邊形面積。

五、線段相交的判定（判定線段AB和線段CD是否相交，屬于哪種相交）。

l        規(guī)范相交：交點只有一個，且不是線段的端點。

1、充要條件：點A和點B在CD的兩側(cè)并且點C和點D在AB的兩側(cè)。

2、如何判斷點A在向量CD的左側(cè)還是右側(cè)：CA×CD的數(shù)值大于0則左側(cè)，小于0則右側(cè)。于是CA×CD的數(shù)值和CB×CD的數(shù)值異號，點A和點B在CD的兩側(cè)，同理可判斷點C和點D是否在AB的兩側(cè)（注意，必須嚴(yán)格異號）。

l        不規(guī)范相交：交點為某個線段的端點，甚至兩線段有一段重合。

1、充要條件，一條線段的一個端點在另一條線段上。即A在CD上或B在CD上或C在AB上或D在AB上。

2、A在線段CD上的充要條件：

a)        AC×AD = 0，幾何意義，AC和AD組成的平行四邊形的面積為0，即A、C、D三點共線。

b)        A點在CD之間，A.x處于C.x和D.x之間并且A.y處于C.y和D.y之間