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座標値をペアとして格納する必要があります。

次に、これらのペアを左側の境界との交点に基づいて並べ替えます。その後、これらのペアを1つずつループします。連続する2つのペアについて、現在のペアの2番目の値が前のペアの2番目の値よりも小さい場合は、指定された垂直セクションに交差が存在する必要があります。

例

#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