📘

RANSAC Line Fit

Implement a RANSAC algorithm to fit a line to a set of points. The goal is to find the best line that represents the majority of the points, despite the presence of outliers.

The RANSAC algorithm is a model fitting technique that uses a random sampling approach to find the best model. It is based on the idea of selecting a random subset of points, fitting a model to these points, and then checking how well this model fits the rest of the points.

Select a random subset of 2 points
Fit a line to these points using the equation $y = mx + b$
Count the number of inliers, points that are close to the fitted line
Repeat the process for a specified number of iterations

y = mx + b

This technique is widely used in computer vision for tasks such as line detection and image registration.

Example:

Input:

ransac_line([(0,0), (1,1), (2,2), (1,5)], 100, 0.5, 42)

Output:

[1.0, 0.0]

Reasoning:

With seed 42, many random 2-point samples will pick pairs from the three collinear points $(0,0), (1,1), (2,2)$ , all of which lie on the line $y = x$ .
For any such pair, the fitted line has slope $1.0$ and intercept $0.0$ , so its parameters are $[1.0, 0.0]$ .
Distances from all points to this line are: $0$ for $(0,0), (1,1), (2,2)$ and larger than the $0.5$ threshold for $(1,5)$ , so there are 3 inliers.
Across 100 iterations, the model $y = x$ consistently yields the maximum inlier count, so RANSAC returns the best line parameters: $[1.0, 0.0]$ .

Constraints:

iterations: number of RANSAC iterations
threshold: inlier threshold
Return best [m, b] rounded to 4 decimal places

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘