Scribd
Upload
1 views

In computational geometry line segment

Uploaded by

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

In computational geometry line segment

Uploaded by

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

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)log⁡n)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.

You might also like