Check if two line segments intersect

Introduction

The problem of checking if two line segments intersecting can be solved using the concept of coordinate geometry. Here we will use some formula that comes from coordinate geometry.

Problem Statement

For two line segments (a1,a2) and (b1,b2), check if these two are intersecting where a1,a2 endpoints of the first line segment and b1,b2 endpoints of the second segment.

Example

Input: a1=(1,5), a2=(5,8) ; b1=(2,1); b2=(3,10)

Output:Yes (i.e intersecting)

Prerequisite

Orientation of ordered triplet of points p1,p2, and p3 depends on the value of the below expression.

exp = (p2.y - p1.y)*(p3.x - p2.x) - (p2.x - p1.x)*(p3.y - p2.y)

Where p.x and p.y are respectively x and y coordinates of point p.

[ this relation can be proved from the slope of lines]

If exp=0, the orientation is collinear; if exp>0, orientation is clockwise, and if exp<0, the orientation is counterclockwise.

Code

int orientation(Point p1, Point p2, Point p3)
{

   int exp = (p2.y - p1.y)*(p3.x - p2.x) - (p2.x - p1.x)*(p3.y - p2.y);

   if (exp == 0) return 0; // collinear

   return (exp > 0)? 1: 2; // clock or counterclock wise
}

Method

To know if two line segments are intersecting or not, we need to know about the orientation of their endpoints a1,a2,b1, and b2. Here we will consider the orientation of the ordered triplet of endpoints. Orientation of ordered triplet can be clockwise, counterclockwise or colinear.

In general if (a1,a2,b1), (a1,a2,b2) these two ordered triplets have different orientation and (b1,b2,a1), (b1,b2,a2) these two ordered triplets have different orientation, two line segments will intersect.

Otherwise, one endpoint of a line segment can lie on the other line segment. So

(a1,a2,b1) or (a1,a2,b2) or (b1,b2,a1) or (b1,b2,a2) can be collinear. In this case also two line segments are intersecting.

Code

// A C++ program to check if two given line segments intersect
#include <iostream>
using namespace std;

struct Point
{
int x;
int y;
};

// the function to check if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
  if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;

return false;
}

// function to check orientation of a triplet of endpoints (p1,p2,p3)
int orientation(Point p1, Point p2, Point p3)
{

int exp = (p2.y - p1.y)*(p3.x - p2.x) - (p2.x - p1.x)*(p3.y - p2.y);

  if (exp == 0) return 0; // collinear

return (exp > 0)? 1: 2; // clock or counterclock wise
}

// function that returns true if line segment 'a1a2'
// and 'b1b2' intersect.
bool intersect(Point a1, Point a2, Point b1, Point b2)
{
// orientations of four triplets of endpoints needed

int o1 = orientation(a1, a2, b1);
int o2 = orientation(a1, a2, b2);
int o3 = orientation(b1, b2, a1);
int o4 = orientation(b1, b2, a2);

// general case
  if (o1 != o2 && o3 != o4)
return true;

// special Cases
// a1, a2 and b1 are collinear and b1 lies on segment a1a2
  if (o1 == 0 && onSegment(a1, b1, a2)) return true;

// a1, a2 and b2 are collinear and b2 lies on segment a1a2
  if (o2 == 0 && onSegment(a1, b2, a2)) return true;

// b1, b2 and a1 are collinear and a1 lies on segment b1b2
  if (o3 == 0 && onSegment(b1, a1, b2)) return true;

// b1, b2 and a2 are collinear and a2 lies on segment b1b2
  if (o4 == 0 && onSegment(b1, a2, b2)) return true;

return false; // doesn't fall in any of the above cases
}

// Driver code
int main()
{
  struct Point a1 = {1, 5}, a2 = {5, 8};
  struct Point b1 = {2, 1}, b2 = {3, 10};

intersect(a1, a2, b1, b2)? cout << "Yes\n": cout << "No\n";


  a1 = {-5, -5}, a2 = {0, 0};
  b1 = {1, 1}, b2 = {10, 10};
intersect(a1, a2, b1, b2)? cout << "Yes\n": cout << "No\n";



return 0;
}

Output

Yes

FAQs

What is orientation?

Orientation of a triplet is how these points lie on a 2D plane. Orientation of ordered triplet can be clockwise, counterclockwise or colinear. It depends on their coordinates.

What is a line segment?

A segment of a line connecting two given points is known as a line segment.

What is slope a line segment and its formula?

For a line segment connecting two points (x1,y1) and (x2,y2),

Slope =(y2 - y1) / (x2 - x1)

Key Takeaways

This article covered the method of checking if two line segments intersect.

Side by side, we should also learn how to check if a point lies in the interior of a polygon as this concept is used there.

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!