摘要： 用途6：判斷點P是否在多邊形中是計算幾何中一個非常基本但是十分重要的算法。以點P為端點，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內部，遇到第二個交點的時候，離開了多邊形，……所以很容易看出當L和多邊形的交點數目C是奇數的時候，P在多邊形內，是偶數的話P在多邊形外。 但是有些特殊情況要加以考慮。 如圖下圖(a)(b)(c)(d)所示。 在圖(a)中，L和多邊形的頂點相交，這時候交點只能計算一次； 在圖(b)中，L和多邊形頂點的交點不應被計算； 在圖(c)和(d) 中，L... 閱讀全文

摘要： 1.點： 只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間。2.線段、折線、多邊形： 因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。3.矩形： 只要比較左右邊界和上下邊界就可以了。4.圓： 很容易證明，圓在矩形中的充要條件是： 圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。 閱讀全文

摘要： 用途4：明白了用途3以后，再來看用途4那是相當的簡單呀。如果線段P1P2和直線Q1Q2相交，則線段P1P2跨立直線Q1Q2，即：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。沒錯，就是這么的簡單，不用懷疑什么。 閱讀全文

摘要： 用途3：我們現在的任務就是判斷線段P1P2和線段Q1Q2是否相交。我們分兩步確定兩條線段是否相交： (1)快速排斥試驗 設以線段 P1P2 為對角線的矩形為R， 設以線段 Q1Q2 為對角線的矩形為T， 如果矩形R和矩形T不相交，顯然兩線段不會相交。 (2)跨立試驗 如果兩線段相交，則兩線段必然相互跨立對方。 若P1P2跨立Q1Q2 ，則矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的兩側， 即1.(P1 - Q1) x (Q2 - Q1)<0, 這個式子表明Q1Q2在P1Q1的右方，也就是說P1Q1在Q1Q2的... 閱讀全文