In computational geometry, a line segment is a fundamental concept that refers to a part of a
straight line that is bounded by two endpoints. It is often used in geometric algorithms for
solving problems like intersections, triangulations, and convex hulls.
Definition
A line segment is a finite portion of a straight line defined by two endpoints. If the endpoints
are P1(x1,y1)P_1(x_1, y_1)P1(x1,y1) and P2(x2,y2)P_2(x_2, y_2)P2(x2,y2), then the line
segment is the set of all points P(x,y)P(x, y)P(x,y) such that:
P=(1−t)P1+tP2for 0≤t≤1P = (1 - t)P_1 + tP_2 \quad \text{for } 0 \leq t \leq 1P=(1−t)P1+tP2
for 0≤t≤1
Where ttt is a parameter.
Geometric Representation
Endpoints: Two points P1P_1P1 and P2P_2P2.
Length: The Euclidean distance between the endpoints: Length=(x2−x1)2+(y2−y1)2\
text{Length} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}Length=(x2−x1)2+(y2−y1)2
Line Segment Operations in Geometric Algorithms
1. Intersection of Line Segments:
o Determines whether two line segments intersect.
o Often uses orientation tests or cross-product methods to find intersection
points.
2. Point on a Line Segment:
o Checks if a given point lies on a segment using the collinearity test and bounds
check.
3. Segment Comparison:
o Compares two segments based on length or position.
4. Visibility:
o Determines if two points are visible to each other, given line segments as
obstacles.
Example
Problem:
Check if two line segments intersect.
Segment 1: From P1(1,1)P_1(1, 1)P1(1,1) to P2(4,4)P_2(4, 4)P2(4,4)
Segment 2: From P3(1,4)P_3(1, 4)P3(1,4) to P4(4,1)P_4(4, 1)P4(4,1)
Solution:
1. Orientation Test: To check if two line segments intersect, compute the orientation of
the points:
o Orientation of P1,P2,P3P_1, P_2, P_3P1,P2,P3
o Orientation of P1,P2,P4P_1, P_2, P_4P1,P2,P4
o Orientation of P3,P4,P1P_3, P_4, P_1P3,P4,P1
o Orientation of P3,P4,P2P_3, P_4, P_2P3,P4,P2
The orientation is determined by the determinant:
Orientation=(x2−x1)(y3−y1)−(y2−y1)(x3−x1)\text{Orientation} = (x_2 - x_1)(y_3 -
y_1) - (y_2 - y_1)(x_3 - x_1)Orientation=(x2−x1)(y3−y1)−(y2−y1)(x3−x1)
2. Intersection Condition:
o Segments intersect if the endpoints of one segment are on opposite sides of the
other segment.
3. Check: Compute orientations for all combinations:
o P1P2P3=+1P_1P_2P_3 = +1P1P2P3=+1, P1P2P4=−1P_1P_2P_4 = -1P1P2P4
=−1
o P3P4P1=−1P_3P_4P_1 = -1P3P4P1=−1, P3P4P2=+1P_3P_4P_2 = +1P3P4P2
=+1
Since orientations alternate, the two line segments intersect.
Output:
The segments intersect at point (2.5,2.5)(2.5, 2.5)(2.5,2.5) (computed geometrically).
Applications
1. Computer Graphics: Clipping, ray tracing.
2. Geographic Information Systems (GIS): Map overlays and intersections.
3. Robotics: Path planning and obstacle avoidance.
4. Network Design: Checking intersections in wiring or pipelines.
Algorithms Using Line Segments
1. Bentley-Ottmann Algorithm:
o Detects all intersections among a set of line segments.
o Time complexity: O((n+k)logn)O((n + k)\log n)O((n+k)logn), where kkk is
the number of intersections.
2. Sweep Line Algorithm:
o Efficiently handles geometric queries involving line segments using a
sweeping vertical line.
3. Convex Hull Algorithms:
o Use line segments to construct the boundary of a convex polygon.
Line segments are foundational elements in geometric algorithms, enabling solutions to
complex problems involving intersections, visibility, and topology.
