Check if two line segments intersect

This video explains how to find if two line segments intersect or not. This is a computational geometry problem which is frequently asked in interviews of big tech companies like amazon, microsoft, samsung and others. I have explained the concepts required to solve this which includes the concept of vector as well as concept of cross-product and right hand rule for vectors. I have also explained how to find orientation of a point with respect to a line segment. These concepts combined together helps us find if 2 line segments intersect or not. I have also covered special cases for collinear lines and overlapping lines. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[nileshdarji]

Another approach I can think of is find equations for 2 lines based on 2 points and fine intersection point by solving 2 equations. Then we can determine if the intersection point falls on 2 segments. Will that work?

[ZshooterBoy]

I think there is a mistake on the slide of "Concept of Orientation" in the if statement block. The point can't be clockwise or counterclockwise from both ends of the segment, so in each condition shouldn't the point have a Clockwise orientation from one point and a counterclockwise orientation from the other.

[MsVasisth]

thanks a lot for this video.
For those who were wondering how to check the orientation of vector ab to point c? make ac vector and take ab cross ac.

[AbhishekKumar-nxfq]

These two below lines in your code are redundant (no use), using two already use if conditions we can say they are intersecting or not if they are collinear. (you also have included the same logic in your video in case of collinearity):

// p2, q2, and p1 are collinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;

// p2, q2 and q1 are collinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;

[utkarshgupta]

[a, b] and [c, d] denote 2 lines
where a, b, c and d are points. if are of [a, b, c] + [a, b, d] == [b, c, a] + [b, c, d] we can say they intersect. What are your thoughts

[laraibanwar]

Really cool bruh.
Would u plz make a video on line sweeping algorithm ... U can take the source from hackerearth and explain it to the viewers.. Would be grt to see

[ali_T-]

he deserves more follower. i just learned this lesson 12 minutes and I have exam next 2 days. one subscribe and like from me! keep it up!

[miabosheva]

Best explanation out there! Thank you so much

[amolucas]

Thanks a lot, solved my problem on the first try 👍

[alfeinstein]

Is it possible to find the intersection point with this method?

[StarCourtesan]

what if they are along the same line and overlapping?

[achibaba]

this is an accurate approach! thank you dude

[soon]

Won't it be clearer if you have explained how to find the sin theta? instead of assuming it to be whatever value it is, it's confusing for viewers who have forgotten about it.

[eshanjain]

awesome explanation and one more request
sir, please solve the codechef problem of march long challenge (problem code:LASERTST)

[Navneetkumar-oscl]

Sir can't we just check for slope if they are equal then collinear otherwise insecting.

[Mithu]

Very nicely explained the concepts. Thank you for this video

[Tensor]

Your content as well as your explanation is OP👌

[anirudhreddybasani]

Really, awesome explanation. Thanks a ton!

[sloppyguy]

"Peenot" means to have sex in my country!

[mrmonkeyy]

you don't answer the question ever