Kiểm tra điểm có nằm trong tam giác không

Giới thiệu

Cho ba điểm của một tam giác; một điểm P khác cũng được cho để kiểm tra xem điểm P có nằm bên trong tam giác hay không.

Để giải bài toán, hãy coi các điểm của tam giác là A, B và C. Khi diện tích tam giác ΔABC = ΔABP + ΔPBC + ΔAPC, thì điểm P nằm trong tam giác.

Đầu vào và Đầu ra

Đầu vào: Các điểm của tam giác {(0, 0), (20, 0), (10, 30)} và điểm p (10, 15) cần kiểm tra.
Đầu ra: Điểm nằm trong tam giác.

Thuật toán

isInside(p1, p2, p3, p)
Đầu vào: Ba điểm của tam giác, điểm p cần kiểm tra.
Đầu ra: True, khi p nằm trong tam giác.

Begin
    area := diện tích tam giác(p1, p2, p3)
    area1 := diện tích tam giác(p, p2, p3)
    area2 := diện tích tam giác(p1, p, p3)
    area3 := diện tích tam giác(p1, p2, p)
    if area = (area1 + area2 + area3), then
        return true
    else return false
End

Ví dụ (C++)

#include <iostream>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
};

float triangleArea(Point p1, Point p2, Point p3) {
    // tìm diện tích tam giác tạo bởi p1, p2 và p3
    return abs((p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y)+ p3.x*(p1.y-p2.y))/2.0);
}

bool isInside(Point p1, Point p2, Point p3, Point p) {
    // kiểm tra p nằm trong hay ngoài
    float area = triangleArea(p1, p2, p3);  // diện tích tam giác ABC
    float area1 = triangleArea(p, p2, p3);  // diện tích PBC
    float area2 = triangleArea(p1, p, p3);  // diện tích APC
    float area3 = triangleArea(p1, p2, p);  // diện tích ABP
    return (area == area1 + area2 + area3);  // khi ba tam giác tạo thành toàn bộ tam giác
}

int main() {
    Point p1={0, 0}, p2={20, 0}, p3={10, 30};
    Point p = {10, 15};
    if (isInside(p1, p2, p3, p))
        cout << "Point is inside the triangle.";
    else
        cout << "Point is not inside the triangle";
}

Kết quả

Point is inside the triangle.