C++에서 섹션 내 선의 교차점 찾기

y =mx + c 형식의 선 집합이 있다고 가정합니다. 이 선과 수직 단면에 의해 만들어진 섹션이 있습니다. 우리는 주어진 섹션에 존재하는 교차점을 찾아야 합니다. 라인이 다음과 같다고 가정합니다 -

L1 =y =x + 2

L2 =y =-x + 7

L3 =y =-3

L4 =y =2x - 7

그리고 수직 단면은 x =2에서 x =4까지 주어집니다.

여기 L1과 L2의 교차점이 이 섹션 안에 있으므로 답은 참입니다.

이 문제를 해결하기 위해 정렬 기술을 고소합니다. 먼저 수직 단면의 두 경계를 사용하여 각 선의 교차점을 계산합니다. 그 후에 그것을 쌍으로 저장하십시오. x 좌표가 경계 자체와 같기 때문에 교차점의 y 좌표 값을 쌍으로 저장하기만 하면 됩니다.

이제 왼쪽 경계와의 교차점을 기준으로 이 쌍을 정렬합니다. 그런 다음 이 쌍을 하나씩 반복합니다. 두 개의 연속 쌍에 대해 현재 쌍의 두 번째 값이 이전 쌍의 두 번째 값보다 작으면 주어진 수직 섹션에 교차점이 있어야 합니다.

예시

#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;
   }
}

출력

The intersection point is lies between 2 and 4