求两线段的交点

求两个线段的交点

#include <iostream>

struct Point {
  double x;
  double y;
};

bool is_intersection(Point A, Point B, Point C, Point D) {
  // 计算向量 AB 和 AC 的叉积
  double c1 = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
  // 计算向量 AB 和 AD 的叉积
  double c2 = (B.x - A.x) * (D.y - A.y) - (B.y - A.y) * (D.x - A.x);
  // 计算向量 CD 和 CA 的叉积
  double c3 = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);
  // 计算向量 CD 和 CB 的叉积
  double c4 = (D.x - C.x) * (B.y - C.y) - (D.y - C.y) * (B.x - C.x);

  // 如果向量 AB 和 AC 叉积为负，表示 C 在向量 AB 的左侧， 否则在右侧；同理，如果向量 AB 和 AD 叉积为负，表示 D 在向量 AB 的左侧， 否则在右侧。
  // 同理，如果向量 CD 和 CA 叉积为负，表示 A 在向量 CD 的左侧， 否则在右侧；同理，如果向量 CD 和 CB 叉积为负，表示 B 在向量 CD 的左侧， 否则在右侧。
  // 如果两条线段相交，那么 C 和 D 必然在 A 和 B 的两侧，同理，A 和 B 必然在 C 和 D 的两侧。
  // 所以，如果 c1 * c2 <= 0 && c3 * c4 <= 0，表示两条线段相交。
  // 注意：如果两条线段有一个端点相同，也算相交。
  return c1 * c2 <= 0 && c3 * c4 <= 0;
}

Point get_intersection(Point A, Point B, Point C, Point D) {
  // 计算线段 AB 的斜率
  double k1 = (B.y - A.y) / (B.x - A.x);
  // 计算线段 CD 的斜率
  double k2 = (D.y - C.y) / (D.x - C.x);

  if (k1 == k2) {
    // 如果两条线段的斜率相同，表示两条线段平行，没有交点
    return {0, 0};
  }

  // y = k * x + b
  // b = y - k * x
  // 计算线段 AB 的截距
  double b1 = A.y - k1 * A.x;
  double b2 = C.y - k2 * C.x;

  // 计算交点的 x 坐标
  // k1 * x + b1 = k2 * x + b2
  // k1 * x - k2 * x = b2 - b1
  // (k1 - k2) * x = b2 - b1
  // x = (b2 - b1) / (k1 - k2)
  double x = (b2 - b1) / (k1 - k2);

  // 计算交点的 y 坐标
  // y = k * x + b
  double y = k1 * x + b1;

  return {x, y};
}

int main() {
  Point A = {0, 0};
  Point B = {1, 1};
  Point C = {1, 1};
  Point D = {2, 4};


  if (is_intersection(A, B, C, D)) {
    Point intersection = get_intersection(A, B, C, D);
    double x = intersection.x;
    double y = intersection.y;
    std::cout << "Intersection: (" << x << ", " << y << ")" << std::endl;
  } else {
    std::cout << "No intersection" << std::endl;
  }
  return 0;
}