Kiểm tra bốn điểm có tạo thành hình vuông không

Giới thiệu

Trong mặt phẳng 2D, cho bốn điểm. Thuật toán này sẽ kiểm tra xem bốn điểm có tạo thành hình vuông hay không.

Để kiểm tra hình vuông, ta phải thỏa mãn các điều kiện sau:

• Tất cả bốn cạnh tạo thành bởi các điểm cho trước đều bằng nhau.
• Hai cạnh kề nhau đều vuông góc (góc vuông).

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

Đầu vào: Bốn điểm {(20, 10), (10, 20), (20, 20), (10, 10)}
Đầu ra: Các điểm tạo thành hình vuông.

Thuật toán

isFormingSquare(p1, p2, p3, p4)
Trong thủ tục này, ta sẽ dùng phương thức squareDist(p1, p2), nó trả về khoảng cách bình phương của hai điểm cho trước.

Đầu vào: Bốn điểm.
Đầu ra: True khi các điểm cho trước tạo thành hình vuông.

Begin
    dist12 := squareDist(p1, p2)
    dist13 := squareDist(p1, p3)
    dist14 := squareDist(p1, p4)
    if dist12 = dist13 and 2*dist12 = dist14, then
        dist := squareDist(p2, p4)
        return true when dist = squareDist(p3, p4) and dist = dist12
    if dist13 = dist14 and 2*dist13 = dist12, then
        dist := squareDist(p2, p3)
        return true when dist = squareDist(p2, p4) and dist = dist13
    if dist12 = dist14 and 2*dist12 = dist13, then
        dist := squareDist(p2, p3)
        return true when dist = squareDist(p3, p4) and dist = dist12
    return false
End

Ví dụ (C++)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

int squareDist(Point p, Point q) {
    return (p.x - q.x)*(p.x - q.x) + (p.y - q.y)*(p.y - q.y);
}

bool isSquare(Point p1, Point p2, Point p3, Point p4) {
    // kiểm tra bốn điểm tạo hình vuông hay không
    int dist12 = squareDist(p1, p2);  // khoảng cách p1 đến p2
    int dist13 = squareDist(p1, p3);  // khoảng cách p1 đến p3
    int dist14 = squareDist(p1, p4);  // khoảng cách p1 đến p4
    // khi độ dài p1-p2 và p1-p3 bằng nhau, và bình phương (p1-p4) = 2*(p1-p2)
    if (dist12 == dist13 && 2*dist12 == dist14) {
        int dist = squareDist(p2, p4);
        return (dist == squareDist(p3, p4) && dist == dist12);
    }
    // cùng điều kiện cho các tổ hợp khác
    if (dist13 == dist14 && 2*dist13 == dist12) {
        int dist = squareDist(p2, p3);
        return (dist == squareDist(p2, p4) && dist == dist13);
    }
    if (dist12 == dist14 && 2*dist12 == dist13) {
        int dist = squareDist(p2, p3);
        return (dist == squareDist(p3, p4) && dist == dist12);
    }
    return false;
}

int main() {
    Point p1 = {20, 10}, p2 = {10, 20}, p3 = {20, 20}, p4 = {10, 10};
    if(isSquare(p1, p2, p3, p4))
        cout << "Points are forming a square.";
    else
        cout << "Points are not forming a square";
}

Kết quả

Points are forming a square.