Encuentra el punto de intersección de las líneas dentro de una sección

Dadas N líneas en un espacio bidimensional en forma y = mx + b y una sección vertical. Necesitamos averiguar si hay un punto de intersección dentro de la sección dada o no. 
Ejemplos: 
 

In below diagram four lines are there,
L1 :    y = x + 2
L2 :    y = -x + 7
L3 :    y = -3
L4 :    y = 2x – 7
and vertical section is given from x = 2 to x = 4

We can see that in above diagram, the 
intersection point of line L1 and L2 
lies between the section.

Podemos resolver este problema usando la clasificación. Primero, calcularemos el punto de intersección de cada línea con los límites de la sección vertical y lo almacenaremos como un par. Solo necesitamos almacenar las coordenadas y de las intersecciones como un par porque las coordenadas x son iguales al límite mismo. Ahora ordenaremos estos pares sobre la base de su intersección con el límite izquierdo. Después de eso, recorreremos estos pares uno por uno y si para cualquiera de los dos pares consecutivos, el segundo valor del par actual es menor que el del segundo valor del par anterior, entonces debe haber una intersección en la sección vertical dada. . 
La posible orientación de dos pares consecutivos se puede ver en el diagrama anterior para L1 y L2. Podemos ver que cuando el segundo valor es menor, la intersección se encuentra en la sección vertical. 
La complejidad temporal total de la solución será O(n logn) 
 

// C++ program to check an intersection point
// inside a given vertical section
#include <bits/stdc++.h>
using namespace std;
 
// structure to represent a line
struct line {
    int m, b;
    line()  { }
    line(int m, int b) : m(m), b(b)  { }
};
 
// Utility method to get Y-coordinate
// corresponding to x in line l
int getYFromLine(line l, int x)
{
    return (l.m * x + l.b);
}
 
// method returns true if two line cross
// each other between xL and xR range
bool isIntersectionPointInsideSection(line lines[],
                            int xL, int xR, int N)
{
    pair<int, int> yBoundary[N];
 
    // first calculating y-values and putting
    // in boundary pair
    for (int i = 0; i < N; i++)
        yBoundary[i] = make_pair(getYFromLine(lines[i], xL),
                               getYFromLine(lines[i], xR));
     
 
    // sorting the pair on the basis of first
    // boundary intersection
    sort(yBoundary, yBoundary + N);
 
    // looping over sorted pairs for comparison
    for (int i = 1; i < N; i++) {
 
        // if current pair's second value is smaller
        // than previous pair's then return true
        if (yBoundary[i].second < yBoundary[i - 1].second)
            return true;       
    }
 
    return false;
}
 
// Driver code to test above methods
int main()
{
    int N = 4;
    int m[] = { 1, -1, 0, 2 };
    int b[] = { 2, 7, -3, -7 };
 
    // copy values in line struct
    line lines[N];
    for (int i = 0; i < N; i++) {
        lines[i] = line(m[i], b[i]);
    }
   
    int xL = 2;
    int xR = 4;
 
    if (isIntersectionPointInsideSection(lines, xL, xR, N)) {
        cout << "Intersection point lies between "
             << xL << " and " << xR << endl;
    } else {
        cout << "No Intersection point lies between "
             << xL << " and " << xR << endl;
    }
}

//Java program to check an intersection point
// inside a given vertical section
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    // a structure to represent a line
    public static class line
    {
        int m,b;
        line(int s, int d){
            this.m = s;
            this.b = d;
        }
    }
     
    public static class Pair{
        int x,y;
        Pair(int xx, int yy){
            this.x = xx;
            this.y = yy;
        }
    }
     
    // Utility method to get Y-coordinate
    // corresponding to x in line l
    public static int getYFromLine(line l, int x)
    {
        return ((l.m * x) + l.b);
    }
      
    // method returns true if two line cross
    // each other between xL and xR range
    public static boolean isIntersectionPointInsideSection(line lines[], int xL, int xR, int N)
    {
        Pair[] yBoundary = new Pair[N];
      
        // first calculating y-values and putting
        // in boundary pair
        for (int i = 0; i < N; i++){
            yBoundary[i] = new Pair(getYFromLine(lines[i], xL),getYFromLine(lines[i], xR));
        }
      
        // sorting the pair on the basis of first
        // boundary intersection
        Arrays.sort(yBoundary,new Comparator<Pair>(){
            public int compare(Pair p1, Pair p2){
                return p1.x>p2.x?1:-1;
            }
        });
      
        // looping over sorted pairs for comparison
        for (int i = 1; i < N; i++) {
      
            // if current pair's y value is smaller
            // than previous pair's then return true
            if (yBoundary[i].y < yBoundary[i - 1].y){
                return true;
            }
                       
        }
      
        return false;
    }
     
    // Driver program to test above functions
    public static void main (String[] args) {
        int N = 4;
        int m[] = { 1, -1, 0, 2 };
        int b[] = { 2, 7, -3, -7 };
      
        // copy values in line struct
        line lines[] = new line[N];
        for (int i = 0; i < N; i++) {
            lines[i] = new line(m[i], b[i]);
        }
        
        int xL = 2;
        int xR = 4;
      
        if (isIntersectionPointInsideSection(lines, xL, xR, N)) {
            System.out.println("Intersection point lies between "+xL+ " and "+ xR);
        } else {
            System.out.println("No Intersection point lies between "+xL+ " and "+ xR);
        }
    }
}
//This code is contributed by shruti456rawal

// JavaScript program to check an intersection point
// inside a given vertical section
 
// structure to represent a line
class line {
    constructor() {}
    constructor(m, b){
        this.m = m;
        this.b = b;
    }
};
 
// Utility method to get Y-coordinate
// corresponding to x in line l
function getYFromLine(l, x){
    return (l.m * x + l.b);
}
 
// method returns true if two line cross
// each other between xL and xR range
function isIntersectionPointInsideSection(lines, xL, xR, N){
    let yBoundary = new Array(N);
 
    // first calculating y-values and putting
    // in boundary pair
    for (let i = 0; i < N; i++){
        yBoundary[i] = [getYFromLine(lines[i], xL), getYFromLine(lines[i], xR)];
    }
 
    // sorting the pair on the basis of first
    // boundary intersection
    yBoundary.sort();
     
    // looping over sorted pairs for comparison
    for (let i = 1; i < N; i++) {      
        // if current pair's second value is smaller
        // than previous pair's then return true
        if (yBoundary[i][1] < yBoundary[i - 1][1]){
             return true;
        }
    }
 
    return false;
}
 
// Driver code to test above methods
{
    let N = 4;
    let m = [ 1, -1, 0, 2 ];
    let b = [2, 7, -3, -7 ];
 
    // copy values in line struct
    let lines = new Array();
    for (let i = 0; i < N; i++) {
        lines.push(new line(m[i], b[i]));
    }
    let xL = 2;
    let xR = 4;
 
    if (isIntersectionPointInsideSection(lines, xL, xR, N)) {
        console.log("Intersection point lies between ", xL, " and ", xR);
    } else {
        console.log("No Intersection point lies between ", xL, " and ", xR);
    }
}
 
// The code is contributed by Gautam goel (gautamgoel962)

Intersection point lies between 2 and 4

Complejidad del tiempo: O(n*log(n))

Complejidad espacial : O(1)

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.