Point to Line Distance

To solve this problem, you mainly need to understand the point–to–line distance formula and how it relates to epipolar geometry; implementation is then straightforward arithmetic.

---

1. Background Knowledge

In 2D analytic geometry, a line can be written in implicit form as $ax + by + c = 0,$ where $a, b, c$ are real numbers and $(x, y)$ is any point on the plane. The vector $(a, b)$ is normal (perpendicular) to the line, so it encodes the line’s orientation. The perpendicular (shortest) distance from a point $(x_0, y_0)$ to this line is given by:

$$d = \frac{|a x_0 + b y_0 + c|}{\sqrt{a^2 + b^2}}.$$

The numerator is the signed algebraic distance (it can be positive or negative depending on which side of the line the point lies), and the denominator normalizes for the scale of the line coefficients so that the distance is independent of how the line equation is scaled.

In epipolar geometry (stereo vision), corresponding points in two camera images must lie on each other’s epipolar lines. Given a candidate correspondence, we typically compute the epipolar line in one image and then measure the perpendicular distance from the detected point to that line. If this distance is small (e.g., less than 1–2 pixels), the match is considered geometrically consistent with the epipolar constraint.

---

2. Algorithm / General Approach

Given:

• Point $(x, y)$
• Line coefficients $a, b, c$ for $ax + by + c = 0$

General approach:

1. Plug the point into the line equation to get the algebraic value $v = a x + b y + c$.
2. Compute the norm of the normal vector: $n = \sqrt{a^2 + b^2}$.
3. Compute the perpendicular distance: $d = |v| / n$.
4. Optionally, compare $d$ against a threshold (e.g., 1–2 pixels) to decide if the match is acceptable.

This is just direct evaluation of the known geometric formula.

---

3. Step-by-Step Strategy (Implementation View)

Assume you have x, y, a, b, c as inputs.

1. Compute the numerator (signed distance):

num = a * x + b * y + c

2. Compute the denominator (normal length):

denom = math.sqrt(a * a + b * b)

3. Guard against degenerate line (optional but good practice):

• If denom == 0, the line is invalid (both a and b are zero); handle according to the problem’s constraints (e.g., assume it never happens or return 0 / error).

4. Compute the distance:

d = abs(num) / denom

5. Return or print the result in the format expected by the problem (e.g., float, possibly with specific precision).

Conceptually:

• Step 1: project the point onto the line’s normal.
• Step 2–4: normalize that projection to convert from “algebraic” units to Euclidean distance.

---

4. Common Pitfalls

• Forgetting the absolute value: The formula for distance uses $|ax + by + c|$. Without the absolute value, you get a signed value, not a distance.

• Division by zero: If both $a = 0$ and $b = 0$, the equation doesn’t define a line. Problems typically guarantee valid lines, but it’s worth being aware.

• Floating-point precision issues:

• Large values of $a, b, c, x, y$ can cause precision loss.

• When comparing to a threshold (e.g., 1–2 pixels), use standard floating comparison practices (e.g., not relying on exact equality).

• Wrong line form: Make sure your input line really is in the form $ax + by + c = 0$. If you start from slope-intercept form $y = mx + k$, you must first rewrite it as:

$$mx - y + k = 0 \quad\Rightarrow\quad a = m,\ b = -1,\ c = k.$$

---

5. Time & Space Complexity

For a single point–line distance computation:

• Time complexity: $O(1)$ — a constant number of arithmetic operations.

• Space complexity: $O(1)$ — only a few scalar variables.

If you apply this to many points or many candidate matches, total time is linear in the number of distance evaluations (e.g., $O(N)$ for $N$ points).