Line from Two Points

You are fitting the equation of a line in 2D, using exactly two points, which is the minimal data needed to uniquely define a non-vertical line. In the broader RANSAC context, this is the “minimal sample” used to propose a line model before checking it against many noisy points.

1. Background Knowledge

• A line in 2D can be written in slope-intercept form: $y = mx + b$ where:

• $m$ is the slope (how steep the line is),

• $b$ is the y-intercept (where the line crosses the y-axis, i.e., at $x = 0$).

• Given two distinct points $(x_1, y_1)$ and $(x_2, y_2)$, there is exactly one line that passes through both (unless it’s a vertical line, which is a special case where the slope is undefined). In RANSAC for line fitting, you repeatedly:

• randomly pick two points,

• compute the line through them,

• then measure how many other points agree with this line (inliers).

2. Algorithm / Approach

The general pattern to compute a line from two points:

1. Use the slope formula: $m = \frac{y_2 - y_1}{x_2 - x_1}$
2. Plug one point into $y = mx + b$ to solve for $b$: $b = y_1 - m \cdot x_1$
3. Return $(m, b)$ as the line parameters.

In more robust systems (like RANSAC), this is wrapped inside a loop that tests many point pairs, but the core computation of $m$ and $b$ is what you’re implementing here.

3. Step-by-Step Strategy

1. Read inputs: $x_1, y_1, x_2, y_2$.
2. Check denominator:

• Compute $\Delta x = x_2 - x_1$.
• If $\Delta x = 0$, the line is vertical (slope infinite); depending on the problem, you may:
• avoid such pairs, or
• handle this as a special case (e.g., return some flag or separate representation).

3. Compute slope:

• $m = (y_2 - y_1) / (x_2 - x_1)$.

4. Compute intercept:

• $b = y_1 - m \cdot x_1$.

5. Output:

• Return or print $m$ and $b$.

Example (in a C++/Python-like pseudocode):

def line_from_two_points(x1, y1, x2, y2):
 dx = x2 - x1
 if dx == 0:
 # vertical line: x = x1
 # handle according to problem spec
 raise ValueError("Vertical line: slope undefined")

 m = (y2 - y1) / dx
 b = y1 - m * x1
 return m, b

4. Common Pitfalls

• Division by zero: when $x_1 = x_2$, $\Delta x = 0$, and the slope formula is undefined. You must check this.
• Integer division: in languages like C++/Java/Python 2, if you use integers, (y2 - y1) / (x2 - x1) can truncate to an integer. Use floating point (double, float, or float64) to get a real-valued slope.
• Precision issues: large coordinates or very close $x_1$ and $x_2$ can lead to numerical instability; for this easy problem it usually doesn’t matter, but be aware conceptually.
• Point order doesn’t matter: using $(x_2, y_2)$ instead of $(x_1, y_1)$ to compute $b$ should give the same result; if it doesn’t, there’s likely a bug.

5. Time & Space Complexity

• Time complexity: $O(1)$
• Just a constant number of arithmetic operations.
• Space complexity: $O(1)$
• Only a few scalar variables are used, regardless of input size.