Scribd
Upload
4 views

M05_geometric_algorithm

This document discusses geometric algorithms, focusing on line segments, their properties, and methods for detecting intersections using the sweep line algorithm and the Bentley-Ottmann algorithm. It covers mathematical representations, intersection conditions, and real-world applications in fields like computer graphics and robotics. The document also includes detailed solutions to intersection problems using cross products and concludes with a summary of results.

Uploaded by

Dr. Devil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

M05_geometric_algorithm

This document discusses geometric algorithms, focusing on line segments, their properties, and methods for detecting intersections using the sweep line algorithm and the Bentley-Ottmann algorithm. It covers mathematical representations, intersection conditions, and real-world applications in fields like computer graphics and robotics. The document also includes detailed solutions to intersection problems using cross products and concludes with a summary of results.

Uploaded by

Dr. Devil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

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

You might also like