Given N lines in two-dimensional space in y = mx + b form and a vertical section. We need to find out whether there is an intersection point inside the given section or not.
Examples:
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.
We can solve this problem using sorting. First, we will calculate intersection point of each line with both the boundaries of vertical section and store that as a pair. We just need to store y-coordinates of intersections as a pair because x-coordinates are equal to boundary itself. Now we will sort these pairs on the basis of their intersection with left boundary. After that, we will loop over these pairs one by one and if for any two consecutive pairs, the second value of the current pair is less than that of the second value of the previous pair then there must be an intersection in the given vertical section.
The possible orientation of two consecutive pairs can be seen in above diagram for L1 and L2. We can see that when the second value is less, intersection lies in vertical section.
Total time complexity of solution will be O(n logn)
CPP
// C++ program to check an intersection point// inside a given vertical section#include <bits/stdc++.h>using namespace std;// structure to represent a linestruct 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 lint getYFromLine(line l, int x){ return (l.m * x + l.b);}// method returns true if two line cross// each other between xL and xR rangebool 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 methodsint 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
//Java program to check an intersection point// inside a given vertical sectionimport 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 |
Python3
from typing import Listimport functools# python program to check an intersection point# inside a given vertical section# structure to represent a lineclass line: def __init__(self, m, b): self.m = m self.b = b# Utility method to get Y-coordinate # corresponding to x in line ldef getYFromLine(l, x): return (l.m * x + l.b)def compare(x, y): if x[0] == y[0]: return x[1] - y[1] return x[0] - y[0]# method returns true if two line cross# each other between xL and xR rangedef isIntersectionPointInsideSection(lines, xL, xR, N): yBoundary = [[0]*2]*N # first calculating y-values and putting # in boundary pair for i in range(N): yBoundary[i] = [getYFromLine(lines[i], xL), getYFromLine(lines[i], xR)] # sorting the pair on the basis of first # boundary intersection yBoundary = sorted(yBoundary, key=functools.cmp_to_key(compare)) # looping over sorted pairs for comparison for i in range(1, N): # 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 methodsN = 4m = [ 1, -1, 0, 2 ]b = [2, 7, -3, -7 ]# copy values in line structlines = []for i in range(N): lines.append(line(m[i], b[i]))xL = 2xR = 4if (isIntersectionPointInsideSection(lines, xL, xR, N)): print("Intersection point lies between ", xL, " and ", xR);else: print("No Intersection point lies between ", xL, " and ", xR);# The code is contributed by NIdhi goel. |
C#
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace GFG{ class Program { // a structure to represent a line public class line { public int m, b; public line(int s, int d) { this.m = s; this.b = d; } } public class Pair { public int x, y; public 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 bool 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 Array.Sort(yBoundary, delegate (Pair p1, Pair p2) { if (p1.x > p2.x) return 1; else return -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 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)) { Console.WriteLine("Intersection point lies between " + xL + " and " + xR); } else { Console.WriteLine("No Intersection point lies between " + xL + " and " + xR); } } }} |
Javascript
// JavaScript program to check an intersection point// inside a given vertical section// structure to represent a lineclass line { constructor() {} constructor(m, b){ this.m = m; this.b = b; }};// Utility method to get Y-coordinate // corresponding to x in line lfunction getYFromLine(l, x){ return (l.m * x + l.b);}// method returns true if two line cross// each other between xL and xR rangefunction 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) |
Output
Intersection point lies between 2 and 4
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
