Ox-Blog

不同的Solution有不同的效能表現、時間複雜度以及編寫的難度。

以下是一個自己近期想出來的檢測的方式，不知道是否有其他人也寫過類此的檢測方式。

已知點 O        多邊形 I 頂角 為 A、B、C、D、E

如何證明點 O 在 多邊形 I 內 ?

步驟 :

1. 把多邊形 I 的頂角以兩個分組，結果應為AB、BC、CD、DE、EA。

2. 把各組頂角加入點O，使其成為三角形，結果應為△ABO、△BCO、△CDO、△DEO、△EAO。

3. 計算各個三角形面積，並加總和。

4. 計算多邊形 I 的面積。

5. 比較各個三角形面積總和 與 多邊形 I 的面積 是否相等，

    是的話點O於多邊形 I 內，否的話點O於多邊形 I 外

 

 

步驟 :

1. 計算多邊形 I 的中心點，並定義中心點為 c

2. 計算多邊形中心點 C 與 圓心 P 的距離( S )以及向量 ( V )

3. 如果 R( 半徑 ) > S ( 距離 ) ，以 向量 ( V ) * R( 半徑 ) 計算出點 ( F )

     如果 R( 半徑 ) <= S ( 距離 ) ，以 向量 ( V ) * 距離( S ) 計算出點 ( F )

4. 用上一部分提及的「點 與 多邊形碰撞檢測」來計算點 ( F ) 是否在多邊形內

5. 如果點 ( F ) 在多邊形內，即圓形 O 及 多邊形 I 有碰撞

     如果點 ( F ) 在多邊形外，即圓形 O 及 多邊形 I 沒有碰撞

p.s. 但請留意此方法無法檢測太複雜的圖形(例如M形)，如要提高檢測精準度，

        可以把步驟3中的點 F 計算方式應用在多邊形的所有頂點以取得 n 個檢測點，

        並用第「點 與 多邊形碰撞檢測」來檢測 n 個檢測點。

        只不過，檢測效能和時間也會增加 n 倍。