在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的交点位于此部分内部，因此答案是正确的。

为了解决这个问题，我们将起诉分选技术。首先，我们将计算每条线与垂直截面的边界的交点。之后，将其存储为一对。我们只需要将交叉点的y坐标值存储为一对，因为x坐标等于边界本身。

现在，我们将基于它们与左边界的交集对它们进行排序。之后，我们将一对一地遍历这些对。如果对于任意两个连续对，当前对的第二个值小于前一对对的第二个值，则在给定的垂直截面中必须有一个交点。

示例

#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