close

要判斷一個點是否在三角形裡面 , 一般來說有三種方法 , 分別是內角和法  , 同向法 , 以及重心法.

在這裡我們會介紹如何使用同向法來判斷 , 

假使一點P是在三角形ABC裡面 , 那麼它必定滿足一個特性 , 那就是他會位於三個邊的右邊.

以下圖來解釋 , 假使我們從AB邊看 , 則P點在右邊 , 從BC邊看 , P點在右邊 , 從CA邊看 , P點在右邊.

 

所以我們若想判斷一個點是否在三角形內 , 只要判斷該點是否與三個頂點在同一邊 , 

也就是從AB邊看 , P與C在同一邊 , BC邊看 , P與A在同一邊 , 從CA看 , P與B在同一邊.

01 // 3D vector
02 class Vector3
03 {
04 public:
05     Vector3(float fx, float fy, float fz)
06         :x(fx), y(fy), z(fz)
07     {
08  
09     }
10  
11      
12     // Subtract
13     Vector3 operator - (const Vector3& v) const
14     {
15         return Vector3(x - v.x, y - v.y, z - v.z) ;
16     }
17  
18      
19     // Dot product
20     float Dot(const Vector3& v) const
21     {
22         return x * v.x + y * v.y + z * v.z ;
23     }
24  
25      
26     // Cross product
27     Vector3 Cross(const Vector3& v) const
28     {
29         return Vector3(
30             y * v.z - z * v.y,
31             z * v.x - x * v.z,
32             x * v.y - y * v.x ) ;
33     }
34  
35  
36 public:
37     float x, y, z ;
38 };
39  
40  
41 // Determine whether two vectors v1 and v2 point to the same direction
42 // v1 = Cross(AB, AC)
43 // v2 = Cross(AB, AP)
44 bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
45 {
46     Vector3 AB = B - A ;
47     Vector3 AC = C - A ;
48     Vector3 AP = P - A ;
49  
50  
51     Vector3 v1 = AB.Cross(AC) ;
52     Vector3 v2 = AB.Cross(AP) ;
53  
54  
55  
56     // v1 and v2 should point to the same direction
57     return v1.Dot(v2) >= 0 ;
58 }
59  
60  
61 // Same side method
62 // Determine whether point P in triangle ABC
63 bool PointinTriangle1(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
64 {
65     return SameSide(A, B, C, P) &&
66         SameSide(B, C, A, P) &&
67         SameSide(C, A, B, P) ;
68 }

ref : http://www.nowamagic.net/algorithm/algorithm_PointInTriangleTest.php

arrow
arrow
    全站熱搜

    JerryCheng 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄