Ron的BLOG
0%

判断一个点是否在三角形内

Posted on

判断一个点是否在三角形内，可以简化为一个点与三角形三条边的关系，所以涉及到两个知识点：

  • 线的表达
  • 点与线的关系

1. 线的表达式

线一般由两个点表示，如A点 $(x_1, y_1)$ 到B点 $(x_2, y_2)$ 的线。线的方程是：

转换一下

其中 $(y_2 - y_1)$ ，$(x_1 - x_2)$ 和 $x_2y_1 - x_1y_2$ 都是确定值，那么一个A点到B点的线可以转换成下面表达式：

使用a,b,c三个常数可以表示一条直线。
注意：以上表达式的线都是带方向的线。

2. 点与线的关系

点与线的关系有三种，点在线的左边，右边或点在线上。
线有上面的表达式之后，这个关系就比较简单表达了：

以上表达式的结果有三种：

  • 小于0，表示点在线的左边；
  • 大于0，表示点在线的右边；
  • 等于0，表示点在线上。

3. 点在三角形内

当一个点在三角形的三条边的同一侧的时候，点就在三角形内。
那么只要点与线的关系一致，则点在三角形内。

以上三点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef struct line
{
    float a;
    float b;
    float c;
} Line;


// 线的表达式
void pointToLine(float x1, float y1, float x2, float y2, Line *l){
    l->a = y2 - y1;
    l->b = x1 - x2;
    l->c = x2*y1 - x1*y2;
}

// 点与线的关系
float pointLineRelation(float x, float y, Line *l){
    return l->a * x + l->b * y + l->c;
}

// 点是否在三角形内
int isPointInTriangle(float x, float y,
    float x1, float y1,
    float x2, float y2,
    float x3, float y3
){
    Line line_obj1, line_obj2, line_obj3;

    Line *line1 = &line_obj1;
    Line *line2 = &line_obj2;
    Line *line3 = &line_obj3;

    pointToLine(x1, y1, x2, y2, line1);
    pointToLine(x2, y2, x3, y3, line2);
    pointToLine(x3, y3, x1, y1, line3);

    float r1 = pointLineRelation(x, y, line1);
    float r2 = pointLineRelation(x, y, line2);
    float r3 = pointLineRelation(x, y, line3);

    if(r1*r2<0){
        return 0;
    }

    if(r1*r3<0){
        return 0;
    }

    return 1;
}