How to check if two given line segments intersect? | GeeksforGeeks

This video is contributed by Siddharth Chandra

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[lukecronquist]

Just a correction, when you first state the general case it is written as 'one of these 2 conditions' but it should be if and only if both of the orientations are different, as you showed in the examples. And for those saying it is inefficient, you can easily find the orientation by taking the cross product of p1-q1 and p1-p2, etc. if it greater than zero the point is to the right of line p1 to p2, aka anticlockwise. This is a very quick method e.g. for algorithm in programming.

[ryanbarry]

My left ear did *not* enjoy this video.

[DAaaMan]

I did not like this video as much as the others. It simply read the article allowed rather stepping through examples or showing the orientations we were computing.

[joshstubblefield]

Thanks! This was very helpful for a project I'm working on. I have two issues, though.
1st you didn't explain your orientation function. I think you probably find the cross product say of q1-p1 and p2-p1 for instance and if its negative its on one side and if its positive it's on the other side and if it's 0 then you have a special case.
2nd, I think the last two if statements are unnecessary. If neither p2 nor q2 lie between p1 and q1, then we know that the co-linear lines do not intersect (unless I'm picturing it wrong in my head).

[ravishankars]

I think this method is very tedious. A simpler algorithm would be as follows:
1) Check if the lines are parallel by any method (using say, slope). If they are then
1.1) Check if they are collinear. If they are are check the ranges of x1, x2, x3 and x4. There will be a gap between so they dont intersection
1.2) If they are not collinear then parallel lines dont intersect

2) If lines are not parallel then
2.1) Intersect the lines and get the intersection point by any method (say Cramers rule). Now check the intersection point
2.2) The intersections x should fall within the x1x2 and x3x4 and same for y also.

There can of course be simpler methods using say vector representation of lines which can be explored.

[mayankbhandari]

I understood the general case, basically trying to get the area of triangle formed by vectors(vector area instead of scalar one) and taking the sign. But got lost at the special cases.

[rananomi]

The algorithm is difficult but a good one, so thanks.

[CyberrBoss]

Can anyone tell me, the easiest way to check 3d segment intersection, i need only the 3d segments intersect not actual point of intersection

[soumiksarkar]

I heard condition and orientation but no explanation....

[hadgh]

Even if you explained this perfectly, your voice is too funny to be taken seriously😂

[SameerUddin-qk]

ye sb krna seekh lia ha to Kashmir bhi calculate kr k wapis do hamara

[rohith]

I can't understand, try to explain in a better way or atleast explain it by elaborate along with examples.

[getachewgirma]

hello sir pls help write the programming rpc c programming convexhull grhamscan algorthim linux

[someaccount-mptk]

This is absolute garbage... You can solve very easy using Ax=b and checking that no components of x are between 0 and 1

The real solution is trivial. This one is silly