Tìm giao điểm của các đường bên trong một phần trong C ++

Giả sử chúng ta có tập hợp các đường ở dạng y =mx + c. Có mặt cắt được tạo bởi đường này và mặt cắt dọc. Chúng ta phải tìm giao điểm có trong phần đã cho hay không. Giả sử các dòng giống như -

L1 =y =x + 2

L2 =y =-x + 7

L3 =y =-3

L4 =y =2x - 7

Và mặt cắt dọc được cho từ x =2 đến x =4.

Ở đây các giao điểm của L1 và L2 nằm trong phần này, vì vậy câu trả lời sẽ là đúng.

Để giải quyết vấn đề này, chúng tôi sẽ kiện kỹ thuật sắp xếp. Đầu tiên, chúng ta sẽ tính toán giao điểm của mỗi đường với cả ranh giới của mặt cắt dọc. Sau đó lưu trữ đó như một cặp. Chúng ta chỉ cần lưu trữ các giá trị tọa độ y của các giao điểm dưới dạng một cặp vì tọa độ x bằng với chính đường biên.

Bây giờ chúng ta sẽ sắp xếp các cặp này dựa trên giao điểm của chúng với ranh giới bên trái. Sau đó, chúng ta sẽ lặp lại từng cặp một. Nếu đối với hai cặp liên tiếp bất kỳ, giá trị thứ hai của cặp hiện tại nhỏ hơn giá trị thứ hai của cặp trước đó thì phải có một giao điểm trong mặt cắt dọc đã cho.

Ví dụ

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
class line {
   public:
      int slope, intercept;
      line(){
      }
      line(int slope, int intercept) : slope(slope), intercept(intercept) {
   }
};
int getYCoordinate(line l, int x) {
   return (l.slope * x + l.intercept);
}
bool hasIntersectionPoint(line lines[], int left_range, int right_range, int N) {
   pair<int, int> y_border[N];
   for (int i = 0; i < N; i++)
      y_border[i] = make_pair(getYCoordinate(lines[i], left_range), getYCoordinate(lines[i], right_range));
   sort(y_border, y_border + N);
   for (int i = 1; i < N; i++) {
      if (y_border[i].second < y_border[i - 1].second)
         return true;
   }
   return false;
}
int main() {
   int N = 4;
   int slope[] = { 1, -1, 0, 2 };
   int intercept[] = { 2, 7, -3, -7 };
   line lines[N];
   for (int i = 0; i < N; i++)
      lines[i] = line(slope[i], intercept[i]);
   int left_range = 2;
   int right_range = 4;
   if (hasIntersectionPoint(lines, left_range, right_range, N)) {
      cout << "The intersection point is lies between " << left_range << " and " << right_range;
   } else {
      cout << "No intersection point is present in between " << left_range << " and " << right_range;
   }
}

Đầu ra

The intersection point is lies between 2 and 4