Geometric Algorithms
Line Segments, Intersection, and Sweep Line Methods
Dr. Durgesh Kumar
Assitant Professor
SCOPE, VIT Vellore
March 14, 2025
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 1 / 17
Introduction to Geometric Algorithms
Computational geometry deals with algorithms for geometric
problems.
Applications:
Computer graphics
Robotics
Geographic Information Systems (GIS)
CAD software
Interactive Activity: Can you think of any other real-world
applications?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 2 / 17
Line Segments and Their Properties
A line segment is a part of a line defined by two endpoints.
Properties:
Collinearity
Orientation (Clockwise, Counterclockwise, Collinear)
Convexity
Discussion: How can we check if three points are collinear?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 3 / 17
Mathematical Representation of Line Segments
Parametric equation:
P = (1 − t)A + tB, 0≤t≤1
Determining intersection using cross products:
(B − A) × (C − A)
Live Coding Demo: Write a function to check intersection.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 4 / 17
Line Segment Intersection Conditions
Two line segments (A, B) and (C , D) intersect if:
Endpoints are on opposite sides of each other’s supporting lines.
No overlap occurs beyond endpoints.
Edge Cases:
Collinear and overlapping segments
Touching at endpoints
Interactive Exercise: Given a set of segment pairs, determine which
intersect.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 5 / 17
The Sweep Line Algorithm
Used to efficiently detect intersections in a set of line segments.
Key steps:
Sort event points (segment endpoints).
Maintain active segments in a balanced data structure.
Check only neighboring segments for intersections.
Visualization: Step-by-step animation of the sweep line.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 6 / 17
Bentley-Ottmann Algorithm
Optimized sweep-line approach for detecting multiple intersections.
Uses:
Event queue (stores endpoints and intersection points)
Active segment set (BST or AVL tree)
Efficiency: O((n + k) log n), where k is the number of intersections.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 7 / 17
Real-World Applications
Computer Graphics: Hidden surface removal, ray tracing.
Robotics: Path planning, obstacle avoidance.
GIS: Map overlays, road network analysis.
VLSI Design: Checking wire intersections in chip layouts.
Q&A: Can you think of more applications?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 8 / 17
Conclusion and Further Reading
Summary of key takeaways.
Open problems in computational geometry.
Recommended Books:
Computational Geometry: Algorithms and Applications – de Berg et al.
Computational Geometry in C – Joseph O’Rourke
Interactive Discussion: What aspects did you find most interesting?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 9 / 17
Line Segment Intersection using Cross Product
Given three points P = (x1 , y1 ), Q = (x2 , y2 ), and R = (x3 , y3 ),
define the orientation function as:
orient(P, Q, R) = (x2 − x1 )(y3 − y1 ) − (y2 − y1 )(x3 − x1 ).
Interpretation:
> 0: Points are in counterclockwise order.
< 0: Points are in clockwise order.
= 0: Points are collinear.
Intersection Criterion: Two segments P1 Q1 and P2 Q2 intersect if:
label=() orient(P1 , Q1 , P2 ) and orient(P1 , Q1 , Q2 ) have opposite signs, and
lbbel=() orient(P2 , Q2 , P1 ) and orient(P2 , Q2 , Q1 ) have opposite signs.
In the collinear case, additional checks on the projections are required.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 10 / 17
Problem Statement
Determine whether the following line segments intersect using the
cross product method:
label=() L1 : {(1, 23), (10, 15)} and L2 : {(4, 10), (6, 20)}.
lbbel=() L3 : {(4, 5), (7, 10)} and L4 : {(1, 1), (5, 5)}.
lcbel=() L5 : {(1, 1), (10, 10)} and L6 : {(3, 3), (5, 5)}.
ldbel=() L7 : {(1, 1), (10, 10)} and L8 : {(5, 8), (3, 3)}.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 11 / 17
Detailed Solution: Part (a)
Let
A = (1, 23), B = (10, 15), C = (4, 10), D = (6, 20).
Step 1: Compute orientations along AB:
orient(A, B, C ) = (10−1)(10−23)−(15−23)(4−1) = 9(−13)−(−8)(3) = −11
Thus, orient(A, B, C ) < 0.
orient(A, B, D) = (10−1)(20−23)−(15−23)(6−1) = 9(−3)−(−8)(5) = −27+
Hence, orient(A, B, D) > 0.
Step 2: Compute orientations along CD:
orient(C , D, A) = (6−4)(23−10)−(20−10)(1−4) = 2(13)−10(−3) = 26+30
orient(C , D, B) = (6−4)(15−10)−(20−10)(10−4) = 2(5)−10(6) = 10−60 =
Since the orientations for both segments differ, L1 and L2 intersect.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 12 / 17
Detailed Solution: Part (b)
Let
A = (4, 5), B = (7, 10), C = (1, 1), D = (5, 5).
Orientation along AB:
orient(A, B, C ) = (7−4)(1−5)−(10−5)(1−4) = 3(−4)−5(−3) = −12+15 =
orient(A, B, D) = (7−4)(5−5)−(10−5)(5−4) = 3(0)−5(1) = −5 (< 0).
Thus, A and B lie on opposite sides of CD.
Orientation along CD:
orient(C , D, A) = (5−1)(5−1)−(5−1)(4−1) = 4(4)−4(3) = 16−12 = 4 (>
orient(C , D, B) = (5−1)(10−1)−(5−1)(7−1) = 4(9)−4(6) = 36−24 = 12
Since both orientations along CD are positive, A and B lie on the same
side of CD. Therefore, L3 and L4 do not intersect.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 13 / 17
Detailed Solution: Part (c)
Let
A = (1, 1), B = (10, 10), C = (3, 3), D = (5, 5).
All points lie on the line y = x (collinear). Since L6 (from C to D) lies
completely within L5 , the segments intersect (in fact, L6 is a subsegment
of L5 ).
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 14 / 17
Detailed Solution: Part (d)
Let
A = (1, 1), B = (10, 10), C = (5, 8), D = (3, 3).
Orientation along AB:
orient(A, B, C ) = (10−1)(8−1)−(10−1)(5−1) = 9×7−9×4 = 63−36 = 27
orient(A, B, D) = (10−1)(3−1)−(10−1)(3−1) = 9×2−9×2 = 18−18 = 0.
Here, orient(A, B, D) = 0, so D is collinear with AB and lies on L7 .
Orientation along CD:
orient(C , D, A) = (3−5)(1−8)−(3−8)(1−5) = (−2)(−7)−(−5)(−4) = 14−2
orient(C , D, B) = (3−5)(10−8)−(3−8)(10−5) = (−2)(2)−(−5)(5) = −4+2
Since the orientations for A and B with respect to CD differ, L7 and L8
intersect.
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 15 / 17
Conclusion
Summary of Results:
(a) L1 and L2 intersect.
(b) L3 and L4 do not intersect.
(c) L5 and L6 intersect (collinear overlapping).
(d) L7 and L8 intersect.
Discussion: How do the computed orientations help us decide on the
intersection? What additional checks are necessary when points are
collinear?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 16 / 17
Q&A
Questions?
Dr. Durgesh Kumar Geometric Algorithms March 14, 2025 17 / 17
