Python Coding Test Course, Determining the Intersection of Line Segments

You are now going to take a closer look at one of the algorithm problems, “Determining if Line Segments Intersect.” In this lecture, we will explain the theory and actual implementation process step by step to solve this problem. It will be very beneficial for those who want to improve their algorithm problem-solving skills.

Problem Definition

The problem of determining whether two line segments intersect involves deciding if the given two segments cross each other. We will represent the two segments as A(x1, y1) to B(x2, y2) and C(x3, y3) to D(x4, y4). The problem is as follows:

Given two segments AB and CD, determine whether the two segments intersect.

Input Format

The input consists of four integers, where each integer represents the endpoints of the respective segments:

  • A(x1, y1)
  • B(x2, y2)
  • C(x3, y3)
  • D(x4, y4)

Output Format

If the segments intersect, output “YES”; otherwise, output “NO”.

Basic Theory for Problem Solving

One of the methods we can use to determine if segments intersect is a geometric approach. Specifically, we can use the cross product of vectors to ascertain whether the two segments cross each other.

Cross Product

The cross product between two vectors AB(x2-x1, y2-y1) and AC(x3-x1, y3-y1) is defined as follows:


    Cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

This value allows us to determine the direction of the two vectors. If the value of the cross product is 0, it means the vectors are collinear; a positive value indicates one direction, while a negative value indicates the opposite direction.

Intersection Conditions for Line Segments

To determine if two segments AB and CD intersect, we need to check the following conditions:

  1. When the two segments are in the “general case” (the endpoints of AB and CD are in different directions)
  2. When the two segments “meet at a single point” (intersecting at an internal point)
  3. When the two segments “meet at an endpoint” (an endpoint of one segment is on the other segment)

General Case

To confirm that segments AB and CD are in different directions, we compare the signs of the cross products using the points A, B and C, and A, B and D. If the two segments are in different directions, these two signs must be different.

Single/Endpoint Meeting Cases

Unlike the general case, to judge if they meet at a point rather than crossing, we need to check if the endpoints of the segments are on each other’s segments.

Python Code Implementation

Based on the basic theory above, we can write the following Python code.


def orientation(px, py, qx, qy, rx, ry):
    val = (qy - py) * (rx - qx) - (qx - px) * (ry - qy)
    if val == 0: return 0  # Collinear
    return 1 if val > 0 else 2  # Clockwise or Counterclockwise

def on_segment(px, py, qx, qy, rx, ry):
    return min(px, qx) <= rx <= max(px, qx) and min(py, qy) <= ry <= max(py, qy)

def do_intersect(p1, q1, p2, q2):
    o1 = orientation(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1])
    o2 = orientation(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1])
    o3 = orientation(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1])
    o4 = orientation(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1])

    if o1 != o2 and o3 != o4:
        return True
    
    if o1 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1]):
        return True

    if o2 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1]):
        return True

    if o3 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1]):
        return True

    if o4 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1]):
        return True

    return False

# Test case
A = (0, 0)
B = (10, 10)
C = (0, 10)
D = (10, 0)

if do_intersect(A, B, C, D):
    print("YES")
else:
    print("NO")

Code Explanation and Test Cases

In the above code, the orientation function first determines the relative position of three points. The on_segment function checks if a point lies on a given segment. The do_intersect function determines whether two segments intersect. At the end of the code, the actual test case allows us to verify the results.

Conclusion

In this lecture, we explored various theoretical backgrounds and Python code implementations to solve the problem of "Determining if Line Segments Intersect." I hope this has provided an opportunity to enhance both your geometric thinking and programming skills while working through a specific algorithm problem. I wish for your continued growth in coding abilities!