Kiểm tra một điểm thuộc tam giác hay không

Hãy hình dung bạn đang lập trình game pháo đài phòng thủ, bạn cần kiểm tra một nhân vật có bị “mất máu” do nằm trong kết giới do 3 pháo đài tạo ra hay không. Ở đây chúng ta tạm chưa xét đến vấn đề xác định va chạm (Collision detection) trong lập trình game, vốn là chủ đề rất phức tạp, thay vào đó hãy đơn giản hóa vấn đề một chút nha:

“Xác định điểm M nằm trong, nằm trên cạnh hay nằm ngoài tam giác ABC”.

Cách thức để xác định vị trí của M so với tam giác ABC là bằng cách tính diện tích các tam giác: MAB, MAC, MBC và ABC

Tính diện tích tam giác khi biết tọa độ 3 điểm, bằng định thức ma trận cấp 3

Đây là công thức toán học:

Còn đây là công thức được cài đặt (implement) bằng C:

double area(struct Point2D A, struct Point2D B, struct Point2D C) {
   return 0.5 * fabs(A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
}

Nếu tổng diện tích của 3 tam giác này lớn hơn diện tích tam giác ABC tức là điểm M nằm bên ngoài tam giác ABC. Nếu một trong ba tam giác MAB, MAC, MBC có diện tích bằng 0 nghĩa là điểm M nằm trên cạnh của tam giác ABC. Ngoài hai trường hợp trên, chúng ta kết luận điểm M nằm bên trong tam giác ABC. Dưới đây là mã nguồn minh họa:

const double areaABM, areaACM, areaBCM, areaABC;
// Tính toán areaABM, areaACM, areaBCM, areaABC ở đây (...)
const double d = (areaABM + areaACM + areaBCM) - areaABC;

if (d > 0) return "Outside";
else if (areaABM == 0) || areaACM == 0 || areaBCM == 0)
   return "On a side";
else return "Inside";

Đoạn mã trên có một vấn đề. Chính là ở những chỗ so sánh với 0: areaABM == 0. Vì bản chất các phép toán trên số thực là không chính xác, nên không thể so sánh trực tiếp giá trị của số thực được, thay vào đó phải xét hiệu của hai giá trị đó có nhỏ hơn một số cực nhỏ nào đó (EPSILON) hay không. Ở đây chúng ta lấy EPSILON = 0.0001, nếu hiệu của chúng nhỏ hơn EPSILON thì chúng ta công nhận chúng bằng nhau.

Mã nguồn hàm fEqual so sánh hai số thực:

#define EPSILON 0.0001

int fEqual(double a, double b) {
  return (fabs(a - b) < EPSILON) ? 1 : 0;
}

Một lưu ý cuối cùng, khi xác định tam giác bằng tọa độ các đỉnh, không cần phải kiểm tra tam giác có hợp lệ hay không. Tam giác có diện tích bằng 0 cũng hợp lệ, khi đó ba đỉnh của tam giác sẽ thẳng hàng. Ở đây chúng ta sẽ dùng công thức tính diện tích tam giác từ tọa độ các đỉnh của nó bằng định thức (determinant) của ma trận cấp 3.

Cài đặt giải thuật bằng ngôn ngữ C

Các bạn có thể vọc code minh họa bằng C ở editor online dưới đây. Để lấy tọa độ test, các bạn hãy vào đây kéo thả các điểm:
https://www.geogebra.org/classic/sdembke3

Link của editor: https://repl.it/@trainercodescho/Point-inside-triangle

Nếu editor online không load được, thì đây là kết quả in ra trên màn hình:

Mã nguồn hoàn chỉnh:

#include <stdio.h>
#include <math.h>

/*
 * Định nghĩa các hằng số để code dễ đọc hơn
 */
#define TRI_INSIDE 1
#define TRI_ONSIDE -1
#define TRI_OUTSIDE 0
#define EPSILON 0.0001

/*
 * Khai báo cấu trúc dữ liệu theo mô hình hướng đối tượng
 */
struct Point2D {
  double x;
  double y;
};

struct Triangle {
  struct Point2D A;
  struct Point2D B;
  struct Point2D C;
};

/*
 * Tính diện tích tam giác từ tọa độ 3 đỉnh, theo định thức ma trận cấp 3.
 */
double area(struct Point2D A, struct Point2D B, struct Point2D C) {
  return0.5 * fabs(A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
}

/*
 * So sánh 2 số thực có xấp xỉ bằng nhau hay không
 */
int fEqual(double a, double b) {
  return (fabs(a - b) < EPSILON) ? 1 : 0;
}

/*
 * Xét vị trí tương đối giữa điểm pM và tam giác tri
*/
int checkPosition(struct Triangle tri, struct Point2D pM) {
  const double areaABM = area(tri.A, tri.B, pM);
  const double areaACM = area(tri.A, tri.C, pM);
  const double areaBCM = area(tri.B, tri.C, pM);
  const double areaABC = area(tri.A, tri.B, tri.C);
  const double d = (areaABM + areaACM + areaBCM) - areaABC;

  printf("ABM: %f \n", areaABM);
  printf("ACM: %f \n", areaACM);
  printf("BCM: %f \n", areaBCM);
  printf("ABC: %f \n", areaABC);

  if (d > 0)
    return TRI_OUTSIDE;
  else if (fEqual(areaABM, 0) || fEqual(areaACM, 0) || fEqual(areaBCM, 0))
    return TRI_ONSIDE;
  else
    return TRI_INSIDE;
}

void sayPosition(char* pointName, int pos) {
  switch (pos) {
    case TRI_INSIDE:
      printf("%s nam trong Tam Giac.\n\n", pointName);
      break;
    case TRI_ONSIDE:
      printf("%s nam tren canh Tam Giac.\n\n", pointName);
      break;
    default:
      printf("%s nam ngoai Tam Giac.\n\n", pointName);
  }
}

int main(void) {
  struct Point2D A, B, C, D, M1, M2, M3;
  A.x = 1.9757;
  A.y = 8.73603;
  B.x = 6.21207;
  B.y = 0.86331;
  C.x = -5.20612;
  C.y = 1.49967;
  M1.x = 1.89875;
  M1.y = 5.23245;
  M2.x = -0.76931;
  M2.y = 5.97017;
  M3.x = -3.07884;
  M3.y = 6.60876;

  struct Triangle tri;
  tri.A = A;
  tri.B = B;
  tri.C = C;

  sayPosition("M1", checkPosition(tri, M1));
  sayPosition("M2", checkPosition(tri, M2));
  sayPosition("M3", checkPosition(tri, M3));

  return 0;
}