Parallel Lines

Solution

Not really much to solve 🙂

2026 Update: Parallel Lines — Geometry Algorithms and Line Intersection

Determining if lines are parallel, intersecting, or identical is fundamental to computational geometry, computer graphics, and geographic algorithms.

from typing import Optional

def line_intersection(p1, p2, p3, p4) -> Optional[tuple]:
    """
    Find intersection of line segments (p1,p2) and (p3,p4).
    Returns intersection point or None if parallel/no intersection.
    Uses parametric form: p1 + t*(p2-p1), p3 + s*(p4-p3).
    """
    x1, y1 = p1; x2, y2 = p2
    x3, y3 = p3; x4, y4 = p4

    # Cross product of direction vectors
    denom = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)

    if denom == 0:
        # Parallel or coincident
        return None

    t = ((x1-x3)*(y3-y4) - (y1-y3)*(x3-x4)) / denom
    s = -((x1-x2)*(y1-y3) - (y1-y2)*(x1-x3)) / denom

    # For full lines: any t works
    # For segments: check 0 <= t <= 1 and 0 <= s  bool:
    """Check if two lines through (p1,p2) and (p3,p4) are parallel."""
    dx1 = p2[0] - p1[0]
    dy1 = p2[1] - p1[1]
    dx2 = p4[0] - p3[0]
    dy2 = p4[1] - p3[1]
    # Parallel if cross product of direction vectors is 0
    return dx1 * dy2 == dy1 * dx2

def point_to_line_distance(point, line_p1, line_p2) -> float:
    """Distance from a point to a line. Uses area formula."""
    import math
    x0, y0 = point
    x1, y1 = line_p1
    x2, y2 = line_p2
    # ||(p2-p1) x (p1-p0)|| / ||p2-p1||
    num = abs((y2-y1)*x0 - (x2-x1)*y0 + x2*y1 - y2*x1)
    denom = math.sqrt((y2-y1)**2 + (x2-x1)**2)
    return num / denom if denom else 0

# Test
p = line_intersection((0,0),(2,2),(0,2),(2,0))
print(f"Intersection: {p}")  # ((1.0, 1.0), (0.5, 0.5))

print(lines_are_parallel((0,0),(1,1),(0,1),(1,2)))  # True (both slope 1)
print(lines_are_parallel((0,0),(1,1),(0,1),(2,2)))  # False

print(f"Distance from (0,0) to line through (1,0)-(1,5): {point_to_line_distance((0,0),(1,0),(1,5)):.1f}")  # 1.0

# Count intersections among n lines: O(n^2) brute force
def count_intersections(lines: list) -> int:
    """Count distinct intersection points among n lines."""
    n = len(lines)
    intersections = set()
    for i in range(n):
        for j in range(i+1, n):
            result = line_intersection(*lines[i], *lines[j])
            if result:
                pt, _ = result
                # Round to handle floating point
                intersections.add((round(pt[0], 9), round(pt[1], 9)))
    return len(intersections)

lines = [((0,0),(1,0)), ((0,1),(1,1)), ((0,0),(1,1)), ((0,1),(1,0))]
print(f"Intersections: {count_intersections(lines)}")  # 3

Applications in interviews: Line intersection appears in: skyline problem (sweep line), closest pair of points, convex hull algorithms (Graham scan), segment intersection (computational geometry). The parametric form (using parameter t) is the standard approach — it avoids special cases for vertical lines that slope-intercept form would require.