ตรวจสอบว่าจุดอยู่ภายในสามเหลี่ยมหรือไม่

บทนำ

กำหนดจุดสามจุดของสามเหลี่ยม และจุด P อีกจุดหนึ่ง ต้องการตรวจสอบว่าจุด P อยู่ภายในสามเหลี่ยมหรือไม่

วิธีแก้: ให้จุดของสามเหลี่ยมคือ A, B, และ C เมื่อพื้นที่ของสามเหลี่ยม ΔABC = ΔABP + ΔPBC + ΔAPC แสดงว่าจุด P อยู่ภายในสามเหลี่ยม

อินพุตและเอาต์พุต

Input: จุดของสามเหลี่ยม {(0, 0), (20, 0), (10, 30)} และจุด p (10, 15) ที่ต้องการตรวจสอบ
Output: จุดอยู่ภายในสามเหลี่ยม

อัลกอริทึม

isInside(p1, p2, p3, p)
Input: สามจุดของสามเหลี่ยม, จุด p ที่ต้องการตรวจสอบ
Output: True เมื่อ p อยู่ภายในสามเหลี่ยม

Begin
    area := พื้นที่สามเหลี่ยม(p1, p2, p3)
    area1 := พื้นที่สามเหลี่ยม(p, p2, p3)
    area2 := พื้นที่สามเหลี่ยม(p1, p, p3)
    area3 := พื้นที่สามเหลี่ยม(p1, p2, p)
    if area = (area1 + area2 + area3), then
        return true
    else return false
End

ตัวอย่างโค้ด (C++)

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

struct Point {
    int x, y;
};

float triangleArea(Point p1, Point p2, Point p3) {
    // หาพื้นที่สามเหลี่ยมที่เกิดจาก p1, p2 และ 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) {
    // ตรวจสอบว่า p อยู่ภายในหรือภายนอก
    float area = triangleArea(p1, p2, p3);      // พื้นที่สามเหลี่ยม ABC
    float area1 = triangleArea(p, p2, p3);      // พื้นที่ PBC
    float area2 = triangleArea(p1, p, p3);      // พื้นที่ APC
    float area3 = triangleArea(p1, p2, p);      // พื้นที่ ABP
    return (area == area1 + area2 + area3);     // เมื่อสามเหลี่ยมสามอันรวมเป็นสามเหลี่ยมทั้งหมด
}

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";
}

ผลลัพธ์

Point is inside the triangle.