判断点是否在三角形内(转帖)_迈克老狼

假设点P位于三角形内，会有这样一个规律，当我们沿着ABCA的方向在三条边上行走时，你会发现点P始终位于边AB，BC和CA的右侧。我们就利用这一点，但是如何判断一个点在线段的左侧还是右侧呢？我们可以从另一个角度来思考，当选定线段AB时，点C位于AB的右侧，同理选定BC时，点A位于BC的右侧，最后选定CA时，点B位于CA的右侧，所以当选择某一条边时，我们只需验证点P与该边所对的点在同一侧即可。问题又来了，如何判断两个点在某条线段的同一侧呢？可以通过叉积来实现，连接AP，将AP和AB做叉积，再将AC和AB做叉积，如果两个叉积的结果方向一致，那么两个点在同一测。判断两个向量是否方向一致，可以用点积实现，如果点积大于0，则两向量夹角是锐角，此时两向量方向一致，否则是钝角，两向量方向不一致。

http://pic002.cnblogs.com/img/zdd/201008/2010080517445256.png

代码如下，为了实现程序功能，添加了一个Vector3类，该类表示三维空间中的一个向量。

1 
// 3D vector

2 
class Vector3

3 
{

4 
public:

5 
    Vector3(float fx, float fy, float fz)

6 
        :x(fx), y(fy), z(fz)

7 
    {

8 
 
9 
    }

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 
}

69

三、重心法

上面这个方法简单易懂，速度也快，下面这个方法速度更快，只是多用了一些数学概念：

三角形的三个点在同一个平面上，如果选中其中一个点，其他两个点不过是相对该点的位移而已，比如选择点A作为起点，那么点B相当于在AB方向移动一段距离得到，而点C相当于在AC方向移动一段距离得到。

http://pic002.cnblogs.com/img/zdd/201008/2010080517455778.png

所以对于平面内任意一点，都可以由如下方程来表示

P = A + u * (C – A) + v * (B - A) // 方程1

如果系数u或v为负值，那么相当于朝相反的方向移动，即BA或CA方向。那么如果想让P位于三角形ABC内部，u和v必须满足什么条件呢？有如下三个条件

u >= 0

v >= 0

u + v <= 1

几个边界情况，当u = 0且v = 0时，就是点A，当u = 0,v = 1时，就是点B，而当u = 1, v = 0时，就是点C

整理方程1得到P – A = u(C - A) + v(B - A)

令v0 = C – A, v1 = B – A, v2 = P – A，则v2 = u * v0 + v * v1，现在是一个方程，两个未知数，无法解出u和v，将等式两边分别点乘v0和v1的到两个等式

(v2) • v0 = (u * v0 + v * v1) • v0

(v2) • v1 = (u * v0 + v * v1) • v1

注意到这里u和v是数，而v0，v1和v2是向量，所以可以将点积展开得到下面的式子。

v2 • v0 = u * (v0 • v0) + v * (v1 • v0) // 式1

v2 • v1 = u * (v0 • v1) + v * (v1• v1) // 式2

解这个方程得到

u = ((v1•v1)(v2•v0)-(v1•v0)(v2•v1)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))

v = ((v0•v0)(v2•v1)-(v0•v1)(v2•v0)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))

是时候上代码了，这段代码同样用到上面的Vector3类

1 
// Determine whether point P in triangle ABC

2 
bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P)

3 
{

4 
    Vector3 v0 = C - A ;

5 
    Vector3 v1 = B - A ;

6 
    Vector3 v2 = P - A ;

7 
 
8 
    
9 
    float dot00 = v0.Dot(v0) ;

10 
    float dot01 = v0.Dot(v1) ;

11 
    float dot02 = v0.Dot(v2) ;

12 
    float dot11 = v1.Dot(v1) ;

13 
    float dot12 = v1.Dot(v2) ;

14 
 
15 
    
16 
    float inverDeno = 1 / (dot00 * dot11 - dot01 * dot01) ;

17 
 
18 
    
19 
    float u = (dot11 * dot02 - dot01 * dot12) * inverDeno ;

20 
    if (u < 0 || u > 1) // if u out of range, return directly

21 
    {

22 
        return false ;

23 
    }

24 
 
25 
    
26 
    float v = (dot00 * dot12 - dot01 * dot02) * inverDeno ;

27 
    if (v < 0 || v > 1) // if v out of range, return directly

28 
    {

29 
        return false ;

30 
    }

31 
 
32 
    
33 
    return u + v <= 1 ;

34 
}

35

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：一个有用的GJK帖子地址

后一篇：判断空间点在三角形内部

新浪BLOG意见反馈留言板　欢迎批评指正

1	// 3D vector
2	class Vector3
3	{
4	public:
5	Vector3(float fx, float fy, float fz)
6	:x(fx), y(fy), z(fz)
7	{
8
9	}
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	}
69

1	// Determine whether point P in triangle ABC
2	bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
3	{
4	Vector3 v0 = C - A ;
5	Vector3 v1 = B - A ;
6	Vector3 v2 = P - A ;
7
8
9	float dot00 = v0.Dot(v0) ;
10	float dot01 = v0.Dot(v1) ;
11	float dot02 = v0.Dot(v2) ;
12	float dot11 = v1.Dot(v1) ;
13	float dot12 = v1.Dot(v2) ;
14
15
16	float inverDeno = 1 / (dot00 * dot11 - dot01 * dot01) ;
17
18
19	float u = (dot11 * dot02 - dot01 * dot12) * inverDeno ;
20	if (u < 0 \|\| u > 1) // if u out of range, return directly
21	{
22	return false ;
23	}
24
25
26	float v = (dot00 * dot12 - dot01 * dot02) * inverDeno ;
27	if (v < 0 \|\| v > 1) // if v out of range, return directly
28	{
29	return false ;
30	}
31
32
33	return u + v <= 1 ;
34	}
35

判断点是否在三角形内(转帖)

概述

一、 内角和法

二、 同向法

三、 重心法

一、内角和法

二、同向法

三、重心法