Describe the algorithm for computing the intersection of two line segments in Computational Geometry.

The algorithm for computing the intersection of two line segments in Computational Geometry can be described as follows:

1. First, we need to determine if the two line segments intersect at all. To do this, we can use the concept of orientation. We calculate the orientation of three points: the starting point of the first line segment, the ending point of the first line segment, and the starting point of the second line segment. If the orientations of these three points are different, it implies that the line segments intersect. Otherwise, they do not intersect.

2. If the line segments intersect, we need to find the actual point of intersection. To do this, we can use the parametric equation of a line. Let the two line segments be defined by the equations:
Line segment 1: P1 + t1 * (P2 - P1)
Line segment 2: P3 + t2 * (P4 - P3)
where P1, P2, P3, and P4 are the starting and ending points of the line segments, and t1 and t2 are the parameters.

3. To find the point of intersection, we need to solve the equations for t1 and t2. By equating the x and y coordinates of the two line segment equations, we can obtain two linear equations in terms of t1 and t2. Solving these equations will give us the values of t1 and t2.

4. Once we have the values of t1 and t2, we can substitute them back into the line segment equations to find the coordinates of the point of intersection. If the values of t1 and t2 are within the range [0, 1], it means that the intersection point lies within the line segments. Otherwise, the line segments only intersect at their extensions.

5. Finally, we need to handle special cases such as parallel line segments or overlapping line segments. If the line segments are parallel, they do not intersect. If the line segments overlap, we need to determine the overlapping region as the intersection.

Overall, the algorithm involves checking the orientation of points, solving linear equations, and handling special cases to compute the intersection of two line segments in Computational Geometry.