• Trang chủ
  • Bài viết
    CodeSchool - Make coding great againCodeSchool - Make coding great again
    • Trang chủ
    • Bài viết

      Giải thuật

      • Home
      • Blog
      • Giải thuật
      • Kiểm tra một điểm thuộc tam giác hay không

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

      • Date 18/06/2020

      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ông thức tính diện tích tam giác khi biết tọa độ 3 đỉnh, bằng định thức ma trận cấp 3

      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àn hình kết quả chương trì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;
      }

      Facebook Comments

      Tag:algorithm, clang

      • Share:
      author avatar
      CodeSchool trainer

      Previous post

      Kỹ thuật layout đơn giản với table
      18/06/2020

      Next post

      So sánh Docker Container và Máy Ảo (Virtual Machine)
      21/06/2020

      Tìm kiếm

      Bài viết mới

      Routing với webapp React: Không dùng và có dùng thư viện
      12Jul2020
      Phân biệt kỹ thuật routing tại client-side và server-side
      11Jul2020
      Các thủ thuật với JSX trong React (phần 1)
      02Jul2020

      Giao lưu Facebook

      Facebook Pagelike Widget

      Giáo trình và bài viết được biên soạn và biên dịch bởi CodeSchool VN, bảo lưu mọi quyền.

      • Privacy
      • Terms
      • Sitemap