如何判断一个点在三角形内部

迈不过友情╰ 2022-06-01 05:36 192阅读 0赞

## 基本思路 ##

![三角示例][20160517152855289]

如图，点P在三角形ABC内部，可以通过以下三个条件判断：

1.  点P和点C在直线AB同侧
2.  点P和点B在直线AC同侧
3.  点P和点A在直线BC同侧

如果以上三个条件同时满足，则点P在三角形ABC内部。

下面将会用到叉乘这个数学工具来确定一个点在直线的哪一侧。

## 判断点在直线的哪一侧 ##

叉乘是一个判断点在直线哪一侧的数学工具。先看一下叉乘的定义：

a⃗ ×b⃗ =∥a⃗ ∥∥b⃗ ∥sinθn⃗

其中，θ为向量夹角，n⃗ 是一个向量，与a⃗ 和b⃗ 都垂直，方向满足右手螺旋法则，即下图所示：

![右手螺旋法则][20160517152925446]

于是，从第一个向量的方向看，如果第二个向量在左边，那个叉乘是正的，在右边，则是负的，在同一个方向上，则是0.叉乘的大小，则是两个向量组成的平行四边形的面积。

那么叉乘具体如何计算呢？先将x、y、z轴方向的单位向量分别记为i⃗ 、j⃗ 和k⃗ ，则如果有两个向量，分别为：

u⃗ =u1i⃗ \+u2j⃗ \+u3k⃗ =(u1,u2,u3)v⃗ =v1i⃗ \+v2j⃗ \+v3k⃗ =(v1,v2,v3)

则有：

u⃗ ×v⃗ =(u2v3−u3v2)i⃗ \+(u3v1−u1v3)j⃗ \+(u1v2−u2v1)k⃗

可以用以下行列式来简记：

u⃗ ×v⃗ =∣∣∣∣∣i⃗ u1v1j⃗ u2v2k⃗ u3v3∣∣∣∣∣

如果叉乘的两个向量都是平面向量，则可以看作是第三个分量为0的三维向量。

以下Processing程序可以验证叉乘用于点在直线哪一侧的判断的正确性：

PVector a = new PVector(100, 200);
    PVector b = new PVector(300, 300);
    PVector c = PVector.sub(b, a);
    
    void setup() {
      size(400, 400);
      fill(0);
    }
    
    void draw() {
      background(255);
      line(a.x, a.y, b.x, b.y);
      PVector d = new PVector(mouseX - a.x, mouseY - a.y);
    
      String side;
      if (c.cross(d).z > 0)
        side = "left";
      else if (c.cross(d).z < 0)
        side = "right";
      else
        side = "on";
      text(side, 40, 40);
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23

有兴趣的读者也可以把cross方法展开试试。

## 算法实现 ##

现在算法已经很明显啦！其中有一点小技巧，三角形的三个顶点是转着来的，算一次就行了。比如，在上图中，点C在直线AB左侧，点B在直线CA的左侧，点A在直接BC的左侧。所以，第一步是先计算三角形的方向：

float signOfTrig = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
     
      
       1

注意这样一下子写出来不太容易看明白，但是如果看成向量AB和向量AC叉乘之后的Z坐标就好懂的多了。

再分别计算P在AB、CA、BC的哪一侧：

float signOfAB = (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);
    float signOfCA = (a.x - c.x)*(p.y - c.y) - (a.y - c.y)*(p.x - c.x);
    float signOfBC = (c.x - b.x)*(p.y - c.y) - (c.y - b.y)*(p.x - c.x);
     
      
       1 
       2 
       3

最后判断它们是否在同一侧：

boolean d1 = (signOfAB * signOfTrig > 0);
    boolean d2 = (signOfCA * signOfTrig > 0);
    boolean d3 = (signOfBC * signOfTrig > 0);
    println(d1 && d1 && d3);
     
      
       1 
       2 
       3 
       4

这就是所有的算法了！最后来个程序验证一下。

## 验证程序 ##

PVector[] trig;
    float r = 150;
    float t = 0;
    float interval = 30;
    
    void setup() {
      size(500, 500);
      trig = new PVector[3];
      ellipseMode(CENTER);
    }
    
    void draw() {
      translate(width/2, height/2);
      updateTrig();
      background(0);
      stroke(255);
      line(trig[0].x, trig[0].y, trig[1].x, trig[1].y);
      line(trig[1].x, trig[1].y, trig[2].x, trig[2].y);
      line(trig[0].x, trig[0].y, trig[2].x, trig[2].y);
    
      noStroke();
      for (float i = -width/2 + interval/2; i < width/2; i += interval) {
        
        for (float j = -height/2 + interval/2; j < height/2; j += interval) {
        
          if (inTrig(i, j)) {
            fill(255, 0, 0);
          } else {
            fill(255);
          }
          ellipse(i, j, 2, 2);
        }
      }
      t += 0.5;
    }
    
    void updateTrig() {
      for (int i = 0; i < 3; i++)
        trig[i] = new PVector(r * cos(radians(i * 120 + t)), r * sin(radians(i * 120 + t)));
    }
    
    boolean inTrig(float x, float y) {
      PVector a = trig[0];
      PVector b = trig[1];
      PVector c = trig[2];
      PVector p = new PVector(x, y);
    
      float signOfTrig = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
      float signOfAB = (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);
      float signOfCA = (a.x - c.x)*(p.y - c.y) - (a.y - c.y)*(p.x - c.x);
      float signOfBC = (c.x - b.x)*(p.y - c.y) - (c.y - b.y)*(p.x - c.x);
    
      boolean d1 = (signOfAB * signOfTrig > 0);
      boolean d2 = (signOfCA * signOfTrig > 0);
      boolean d3 = (signOfBC * signOfTrig > 0);
    
      return d1 && d2 && d3;
    }
    
     
      
       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 
       51 
       52 
       53 
       54 
       55 
       56 
       57

效果如下：

![效果][20160517153010687]

[20160517152855289]: /images/20220601/7e6a1e91459446b582ba1d5ee8419d56.png
[20160517152925446]: /images/20220601/f806bc15f11943b3838d17ae2f8f47fa.png
[20160517153010687]: /images/20220601/59394e5180a34682b21fb31f46541c62.png