Find if there are 4 collinear points in a set of points

Detecting Collinear Points: An Algorithmic Approach

Explore efficient algorithms to determine if a set of points contains at least four collinear points, a fundamental problem in computational geometry.

The problem of finding collinear points within a given set of points is a classic challenge in computational geometry. Specifically, identifying if there are four or more points that lie on the same straight line has applications in various fields, including computer graphics, pattern recognition, and geographic information systems. This article delves into different algorithmic strategies to tackle this problem, focusing on efficiency and practical implementation.

Understanding Collinearity

Two points always define a line. Three points are collinear if they lie on the same straight line. For four or more points, the condition remains the same: all points must fall on a single line. Mathematically, for three points (x1, y1), (x2, y2), and (x3, y3) to be collinear, the slope between (x1, y1) and (x2, y2) must be equal to the slope between (x2, y2) and (x3, y3). This can be expressed as (y2 - y1) / (x2 - x1) = (y3 - y2) / (x3 - x2). To avoid division by zero for vertical lines, a more robust check involves the cross product or area of a triangle: x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) = 0. If this equation holds, the three points are collinear. For four points, we extend this concept.

flowchart TD
    A[Start with a set of N points] --> B{Choose 2 points: P1, P2}
    B --> C{Calculate slope/equation of line L through P1, P2}
    C --> D{Iterate through remaining N-2 points}
    D --> E{Check if current point Pk lies on line L}
    E -- Yes --> F{Increment collinear count}
    E -- No --> D
    F --> G{Is collinear count >= 4?}
    G -- Yes --> H[Found 4+ collinear points: STOP]
    G -- No --> D
    D -- All points checked --> B
    B -- All pairs checked --> I[No 4+ collinear points found: END]

Basic Brute-Force Approach for Collinearity Detection

Brute-Force Approach

The most straightforward approach is to iterate through all possible combinations of four points and check if they are collinear. This involves selecting four points P1, P2, P3, P4 and then verifying their collinearity. A more optimized brute-force method involves picking two points to define a line, and then checking how many other points fall on that line. If at any point four or more points are found on the same line, we can stop and return true. This method has a time complexity of O(N^3) because we pick two points (N^2 combinations) and then iterate through the remaining N points to check for collinearity.

def are_collinear(p1, p2, p3):
    # Using cross product to check collinearity for 3 points
    # (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) == 0
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) == (p2[1] - p1[1]) * (p3[0] - p1[0])

def find_four_collinear_brute_force(points):
    n = len(points)
    if n < 4:
        return False

    for i in range(n):
        for j in range(i + 1, n):
            # P_i and P_j define a line
            collinear_count = 2 # P_i and P_j are always collinear
            for k in range(j + 1, n):
                if are_collinear(points[i], points[j], points[k]):
                    collinear_count += 1
            
            # After checking all points against the line defined by P_i and P_j
            if collinear_count >= 4:
                return True
    return False

# Example Usage:
points1 = [(0,0), (1,1), (2,2), (3,3), (0,1)]
print(f"Points 1 has 4 collinear: {find_four_collinear_brute_force(points1)}") # True

points2 = [(0,0), (1,1), (2,3), (3,4), (4,5)]
print(f"Points 2 has 4 collinear: {find_four_collinear_brute_force(points2)}") # False

Python implementation of the O(N^3) brute-force approach.

Optimized Approach: Sorting by Slope

A more efficient approach leverages sorting. For each point P in the set, we calculate the slopes it forms with every other point Q. If multiple points Q1, Q2, Q3, ... form the same slope with P, then P, Q1, Q2, Q3, ... are collinear. By sorting these slopes, we can easily count consecutive points that share the same slope. If any slope appears three or more times (meaning P and three other points form the same slope), then we have found four collinear points. This method reduces the complexity to O(N^2 log N) due to the sorting step for each point.

import math
from collections import defaultdict

def find_four_collinear_optimized(points):
    n = len(points)
    if n < 4:
        return False

    for i in range(n):
        p1 = points[i]
        slopes = defaultdict(int)
        # Count points that are identical to p1
        same_point_count = 0

        for j in range(n):
            if i == j:
                continue
            p2 = points[j]

            if p1 == p2:
                same_point_count += 1
                continue
            
            # Calculate slope. Use a tuple (dy, dx) to represent slope
            # to handle vertical lines and avoid floating point issues.
            # Normalize by dividing by GCD to get simplest fraction.
            dy = p2[1] - p1[1]
            dx = p2[0] - p1[0]

            if dx == 0: # Vertical line
                slope = (math.inf, 1) # Represent as (infinity, 1) or similar unique identifier
            else:
                gcd_val = math.gcd(dy, dx)
                slope = (dy // gcd_val, dx // gcd_val)
            
            slopes[slope] += 1
        
        # Check if any slope has at least 3 other points (total 4 including p1)
        # Or if there are enough identical points + points on a line
        for slope, count in slopes.items():
            if count + same_point_count >= 3: # 3 other points + p1 = 4 total
                return True
        
        # Special case: if there are 4 or more identical points
        if same_point_count >= 3: # 3 other identical points + p1 = 4 total
            return True

    return False

# Example Usage:
points1 = [(0,0), (1,1), (2,2), (3,3), (0,1)]
print(f"Points 1 has 4 collinear (optimized): {find_four_collinear_optimized(points1)}") # True

points2 = [(0,0), (1,1), (2,3), (3,4), (4,5)]
print(f"Points 2 has 4 collinear (optimized): {find_four_collinear_optimized(points2)}") # False

points3 = [(0,0), (0,0), (0,0), (0,0), (1,1)]
print(f"Points 3 has 4 collinear (optimized): {find_four_collinear_optimized(points3)}") # True

Python implementation of the O(N^2 log N) optimized approach using slope sorting.