ตรวจสอบว่าจุดสี่จุดสร้างเป็นสี่เหลี่ยมจัตุรัสหรือไม่

บทนำ

บนระนาบ 2D กำหนดจุดสี่จุด อัลกอริทึมนี้จะตรวจสอบว่าจุดสี่จุดสร้างเป็นสี่เหลี่ยมจัตุรัสหรือไม่

เงื่อนไขในการตรวจสอบสี่เหลี่ยมจัตุรัส:

• ด้านทั้งสี่ที่เกิดจากจุดที่กำหนดมีความยาวเท่ากัน
• ด้านประกอบทั้งสองตั้งฉากกัน (มุมฉาก)

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

Input: จุดสี่จุด {(20, 10), (10, 20), (20, 20), (10, 10)}
Output: จุดสร้างเป็นสี่เหลี่ยมจัตุรัส

อัลกอริทึม

isFormingSquare(p1, p2, p3, p4)
ในกระบวนการนี้ เราจะใช้เมธอด squareDist(p1, p2) จะคืนค่าระยะทางยกกำลังสองของจุดสองจุด

Input: จุดสี่จุด
Output: True เมื่อจุดที่กำหนดสร้างเป็นสี่เหลี่ยมจัตุรัส

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 เมื่อ dist = squareDist(p3, p4) และ dist = dist12
    if dist13 = dist14 and 2*dist13 = dist12, then
        dist := squareDist(p2, p3)
        return true เมื่อ dist = squareDist(p2, p4) และ dist = dist13
    if dist12 = dist14 and 2*dist12 = dist13, then
        dist := squareDist(p2, p3)
        return true เมื่อ dist = squareDist(p3, p4) และ dist = dist12
    return false
End

ตัวอย่างโค้ด (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) {
    // ตรวจสอบจุดสี่จุดสร้างสี่เหลี่ยมจัตุรัสหรือไม่
    int dist12 = squareDist(p1, p2);  // ระยะทางจาก p1 ถึง p2
    int dist13 = squareDist(p1, p3);  // ระยะทางจาก p1 ถึง p3
    int dist14 = squareDist(p1, p4);  // ระยะทางจาก p1 ถึง p4
    
    // เมื่อความยาว p1-p2 และ p1-p3 เท่ากัน และกำลังสองของ (p1-p4) = 2*(p1-p2)
    if (dist12 == dist13 && 2*dist12 == dist14) {
        int dist = squareDist(p2, p4);
        return (dist == squareDist(p3, p4) && dist == dist12);
    }
    // เงื่อนไขเดียวกันสำหรับการจับคู่อื่นๆ
    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";
}

ผลลัพธ์

Points are forming a square.