Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.
Before we discuss solution, let us define notion of orientation. Orientation of an ordered triplet of points in the plane can be
–counterclockwise
–clockwise
–colinear
The following diagram shows different possible orientations of (a, b, c)
[ad type=”banner”]
How is Orientation useful here?
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified
1. General Case:
– (p1, q1, p2) and (p1, q1, q2) have different orientations and
– (p2, q2, p1) and (p2, q2, q1) have different orientations.
[ad type=”banner”]
2. Special Case
– (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
– the x-projections of (p1, q1) and (p2, q2) intersect
– the y-projections of (p1, q1) and (p2, q2) intersect
Following is C++ implementation based on above idea.
[pastacode lang=”cpp” manual=”%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0Astruct%20Point%0A%7B%0A%20%20%20%20int%20x%3B%0A%20%20%20%20int%20y%3B%0A%7D%3B%0A%20%0A%2F%2F%20Given%20three%20colinear%20points%20p%2C%20q%2C%20r%2C%20the%20function%20checks%20if%0A%2F%2F%20point%20q%20lies%20on%20line%20segment%20’pr’%0Abool%20onSegment(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20if%20(q.x%20%3C%3D%20max(p.x%2C%20r.x)%20%26%26%20q.x%20%3E%3D%20min(p.x%2C%20r.x)%20%26%26%0A%20%20%20%20%20%20%20%20q.y%20%3C%3D%20max(p.y%2C%20r.y)%20%26%26%20q.y%20%3E%3D%20min(p.y%2C%20r.y))%0A%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20To%20find%20orientation%20of%20ordered%20triplet%20(p%2C%20q%2C%20r).%0A%2F%2F%20The%20function%20returns%20following%20values%0A%2F%2F%200%20–%3E%20p%2C%20q%20and%20r%20are%20colinear%0A%2F%2F%201%20–%3E%20Clockwise%0A%2F%2F%202%20–%3E%20Counterclockwise%0Aint%20orientation(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20%2F%2F%20See%20http%3A%2F%2Fwww.geeksforgeeks.org%2Forientation-3-ordered-points%2F%0A%20%20%20%20%2F%2F%20for%20details%20of%20below%20formula.%0A%20%20%20%20int%20val%20%3D%20(q.y%20-%20p.y)%20*%20(r.x%20-%20q.x)%20-%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20(q.x%20-%20p.x)%20*%20(r.y%20-%20q.y)%3B%0A%20%0A%20%20%20%20if%20(val%20%3D%3D%200)%20return%200%3B%20%20%2F%2F%20colinear%0A%20%0A%20%20%20%20return%20(val%20%3E%200)%3F%201%3A%202%3B%20%2F%2F%20clock%20or%20counterclock%20wise%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20returns%20true%20if%20line%20segment%20’p1q1’%0A%2F%2F%20and%20’p2q2’%20intersect.%0Abool%20doIntersect(Point%20p1%2C%20Point%20q1%2C%20Point%20p2%2C%20Point%20q2)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20the%20four%20orientations%20needed%20for%20general%20and%0A%20%20%20%20%2F%2F%20special%20cases%0A%20%20%20%20int%20o1%20%3D%20orientation(p1%2C%20q1%2C%20p2)%3B%0A%20%20%20%20int%20o2%20%3D%20orientation(p1%2C%20q1%2C%20q2)%3B%0A%20%20%20%20int%20o3%20%3D%20orientation(p2%2C%20q2%2C%20p1)%3B%0A%20%20%20%20int%20o4%20%3D%20orientation(p2%2C%20q2%2C%20q1)%3B%0A%20%0A%20%20%20%20%2F%2F%20General%20case%0A%20%20%20%20if%20(o1%20!%3D%20o2%20%26%26%20o3%20!%3D%20o4)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Special%20Cases%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20p2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o1%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20p2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20q2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o2%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20q2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20p1%20are%20colinear%20and%20p1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o3%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20p1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20q1%20are%20colinear%20and%20q1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o4%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20q1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%20%2F%2F%20Doesn’t%20fall%20in%20any%20of%20the%20above%20cases%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20Point%20p1%20%3D%20%7B1%2C%201%7D%2C%20q1%20%3D%20%7B10%2C%201%7D%3B%0A%20%20%20%20struct%20Point%20p2%20%3D%20%7B1%2C%202%7D%2C%20q2%20%3D%20%7B10%2C%202%7D%3B%0A%20%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20p1%20%3D%20%7B10%2C%200%7D%2C%20q1%20%3D%20%7B0%2C%2010%7D%3B%0A%20%20%20%20p2%20%3D%20%7B0%2C%200%7D%2C%20q2%20%3D%20%7B10%2C%2010%7D%3B%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20p1%20%3D%20%7B-5%2C%20-5%7D%2C%20q1%20%3D%20%7B0%2C%200%7D%3B%0A%20%20%20%20p2%20%3D%20%7B1%2C%201%7D%2C%20q2%20%3D%20%7B10%2C%2010%7D%3B%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]
|
Output:
No
Yes
No