Check If two Line segments Intersect | Problem of the Day | GeeksForGeeks
Given the coordinates of the endpoints(p1,q1, and p2,q2) of the two line segments. Check if they intersect or not. If the Line segments intersect return true otherwise return false.
Note: Please check the intersection lies within the line segments.
Examples
Input: p1=(1,1), q1=(10,1), p2=(1,2), q2=(10,2)
Output: false
Explanation:The two line segments formed by p1-q1 and p2-q2 do not intersect.
Input: p1=(10,0), q1=(0,10), p2=(0,0), q2=(10,10)
Output: true
Explanation: The two line segments formed by p1-q1 and p2-q2 intersect.
Input: p1=(5,-2), q1=(13,2), p2=(2,-3), q2=(3,0)
Output: false
Explanation: The two line segments formed by p1-q1 and p2-q2 are intersecting beyond endpoints, so it is not considerable.
Expected Time Complexity: O(1)
Expected Auxillary Space: O(1)
Table of Contents
0:00 Problem Statement
2:13 Solution -General Idea
8:49 Solution - Concept of Direction
10:46 Solution - Concept of On-Segment
12:08 Pseudo Code
18:54 Code
Пікірлер: 2
class Solution: def directions(self, p, q, r): point1 = [r[0] - p[0], r[1] - p[1]] point2 = [q[0] - r[0], q[1] - r[1]] return (point1[0]*point2[1] - point2[0]*point1[1]) def on_segment(self, p, q, r): if r[0] >= min(p[0], q[0]) and r[0] = min(p[1], q[1]) and r[1] 0 and d2 0)) and ((d3 > 0 and d4 0)): return "true" if d1 == 0 and self.on_segment(p1, q1, p2): return "true" if d2 == 0 and self.on_segment(p1, q1, q2): return "true" if d3 == 0 and self.on_segment(p2, q2, p1): return "true" if d4 == 0 and self.on_segment(p2, q2, p1): return "true" return "false"
Table of Contents 0:00 Problem Statement 2:13 Solution -General Idea 8:49 Solution - Concept of Direction 10:46 Solution - Concept of On-Segment 12:08 Pseudo Code 18:54 Code