โปรแกรมหาจุดตัดของสองเส้นใน C++

โจทย์

กำหนดจุด A และ B ตรงกับเส้น AB และจุด P และ Q ตรงกับเส้น PQ งานคือการหาจุดตัดระหว่างสองเส้นนี้

หมายเหตุ - จุดต่างๆ กำหนดในระนาบ 2 มิติบนพิกัด X และ Y

ที่นี่ A(a1, a2), B(b1, b2) และ C(c1, c2), D(d1, d2) คือพิกัดที่สร้างเส้นสองเส้นที่แตกต่างกัน และ P(p1, p2) คือจุดตัด (เพื่อการอธิบายภาพเท่านั้น)

วิธีการหาจุดตัด

ใช้รูปด้านบนเป็นตัวอย่าง:

ตัวอย่าง

ใช้ (a1, a2), (b1, b2), (c1, c2), (d1, d2) คำนวณ:
A1 = b2 - a2
B1 = a1 - b1
C1 = (A1 * a1) + (B1 * a1)
A2 = d2 - c2
B2 = c1 - d1
C2 = (A2 * c1) + (B2 * c2)
ให้เส้นที่กำหนดเป็น:
1. A1x + B1y = C1
2. A2x + B2y = C2
ตอนนี้ เพื่อหาจุดตัด เราต้องแก้สมการ 2 นี้
เราจะคูณ 1 ด้วย B1 และ 2 ด้วย B2 จะได้:
A1B2x + B1B2y = C1B2
A1B1x + B2B1y = C1B1
ลบทั้งสองสมการ จะได้:
(A1B2 - A2B1)x = C1B2 - C2B1

สิ่งนี้ให้ค่า x และเช่นเดียวกันเราจะได้ค่า y ซึ่งจะเป็นจุดตัด p1 คือ x และ p2 คือ y

หมายเหตุ - สูตรด้านบนจะให้จุดตัดของสองเส้น แต่ถ้าให้เป็นส่วนของเส้น (line segments) แทน เราต้องตรวจสอบว่าจุดที่คำนวณได้อยู่บนส่วนของเส้นนั้นจริงๆ

• min(x1, x2) ≤ x ≤ max(x1, x2)
• min(y1, y2) ≤ y ≤ max(y1, y2)

แนวทางแก้ปัญหา

• รับค่าอินพุต
• หาค่า determinant ซึ่งคือ a1 * b2 - a2 * b1
• ตรวจสอบถ้า determinant = 0 แสดงว่าเส้นขนานกัน
• ถ้า determinant ไม่เป็นศูนย์ แล้ว x = (c1 * b2 - c2 * b1) และ y = (a1 * c2 - a2 * c1)
• คืนค่าและพิมพ์ผลลัพธ์

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศฟังก์ชันแสดงพิกัด x และ y
  void display(mk_pair par)
  พิมพ์ par.first และ par.second
ขั้นตอน 2 → ประกาศฟังก์ชันคำนวณจุดตัด
  mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D)
  ประกาศ double a = B.second - A.second
  ประกาศ double b = A.first - B.first
  ประกาศ double c = a*(A.first) + b*(A.second)
  ประกาศ double a1 = D.second - C.second
  ประกาศ double b1 = C.first - D.first
  ประกาศ double c1 = a1*(C.first)+ b1*(C.second)
  ประกาศ double det = a*b1 - a1*b
  ถ้า (det == 0)
    คืนค่า make_pair(FLT_MAX, FLT_MAX)
  จบถ้า
  มิฉะนั้น
    ประกาศ double x = (b1*c - b*c1)/det
    ประกาศ double y = (a*c1 - a1*c)/det
    คืนค่า make_pair(x, y)
  จบมิฉะนั้น
ขั้นตอน 3 → ใน main()
  ประกาศและเรียกฟังก์ชันสำหรับจุดเป็น mk_pair q = make_pair(2, 1)
  ถ้า (inter.first == FLT_MAX และ inter.second == FLT_MAX)
    พิมพ์ "เส้นที่กำหนดขนานกัน"
  จบถ้า
  มิฉะนั้น
    เรียก display(inter)
  จบมิฉะนั้น
หยุด

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

#include <bits/stdc++.h>
using namespace std;
#define mk_pair pair<double, double>
// แสดงพิกัด x และ y
void display(mk_pair par) {
  cout << "(" << par.first << ", " << par.second << ")" << endl;
}
mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D) {
  // เส้น AB แสดงเป็น a1x + b1y = c1
  double a = B.second - A.second;
  double b = A.first - B.first;
  double c = a*(A.first) + b*(A.second);
  // เส้น CD แสดงเป็น a2x + b2y = c2
  double a1 = D.second - C.second;
  double b1 = C.first - D.first;
  double c1 = a1*(C.first)+ b1*(C.second);
  double det = a*b1 - a1*b;
  if (det == 0) {
    return make_pair(FLT_MAX, FLT_MAX);
  } else {
    double x = (b1*c - b*c1)/det;
    double y = (a*c1 - a1*c)/det;
    return make_pair(x, y);
  }
}
int main() {
  mk_pair q = make_pair(2, 1);
  mk_pair r = make_pair(2, 7);
  mk_pair s = make_pair(4, 4);
  mk_pair t = make_pair(6, 4);
  mk_pair inter = intersection(q, r, s, t);
  if (inter.first == FLT_MAX && inter.second==FLT_MAX) {
    cout << "The given lines AB and CD are parallel.\n";
  } else {
    cout << "The intersection of the given lines AB and CD is: ";
    display(inter);
  }
  return 0;
}

ผลลัพธ์

The intersection of the given lines AB and CD is: (2, 4)