How do I know if two line segments are near collinear

Question

I am having some trouble determining if two line segments are collinear because of floating point precision. How can I determine if the line segments are collinear with some tolerance?

Answer 1

I need to know for my application if two segments are near-collinear. It's about extracting lines from a laser scan. I will explain the solution I am using. It works pretty well. (Excuse my English!)

I think the conditions that KeithS proposes for near-collinearity are wrong.

They are near-colinear if they share one point and are near-parallel.

If two segments (or lines) are parallel but they are near, we can consider them near-collinear.

My solution consists in using a polar representation of the lines.

y * sin(theta) = rho - x * cos(theta)

With this representation, a line can be represented like a point using theta and rho. The trick is that, if those "points" are near, the lines are near-collinear. You just need to calculate the euclidean distance and use a threshold for determine if they are near-collinear.

Answer 2

Several solutions seem plausible depending on your definition of "almost collinear".

Fit a line through 4 points

Two line segments are defined by 4 points, and you could fit a line through the starts and ends of the 2 line segments.

You can use SVD to get the least square fit of a line through 4 points, similar to this answer: https://stackoverflow.com/a/2333251/5069869

With this approach, you take the direction of the line segments as well as the offset between the end of the first and the start of the second line segment into account.

However, if the two line-segments are parallel but not collinear, and if they are short relative to the distance between them, the fitted line will be perpendicular to the two line-segments. This is no problem for unit tests, where you like "almost collinear up to several digits behind zero", but for other applications this might be a problem.

Use average direction and average location independently

Alternatively, you can construct a target line using the average direction of the two line segments as direction of the target line. Thuis can be calculated by (v1/|v1|+v2/|v2|)/2, if the vectors v1 and v2 point in the same direction. Then use the mean of the 4 points as an anchor point for the target line.

Finally, you can calculate the individual distances of your 4 points to the target line and use them as measure of collinearity.

The effect of lengths of your segments & the space between segments

When you find a suitable definition of "almost collinear", you need to consider, how different lengths of line segments effect the result, as pointed out by Vahid in a comment. Furthermore, you should think about the effect of the space between the two line segments.

By calculating the distance of 4 points to a target line, I try to reduce the effect of different segment lengths (every segment only contributes 2 points), but I cannot completely eliminate it

Answer 3

EDITED:

Line segments are colinear if they contain two of the same points. They are near-colinear if they share one point and are near-parallel.

Vectors are effectively parallel if the angle between them is less than a threshold you state. Maybe less than .000027 degrees, which is the decimal equivalent of one tenth of a degree-second (which is in latitudinal distance, and equivalently of longitudinal distance at the equator, a difference of approximately ten feet; that's about the accuracy of civilian GPS).

You didn't tell us what language or library you're using; in .NET's System.Windows.Media.3D library there is a Vector3D struct which has an AngleBetween() method, making this check a one-liner.

The "basic" math (it's actually vector trig, not a "basic" concept by most definitions) is that θ=cos^-1( A*B / |A||B| ); that is, the arc-cosine of the quantity of the scalar product of the two vectors divided by the product of their magnitudes.

The dot product of vector A and vector B, both containing components X, Y, and Z, is X_AX_B + Y_AY_B + Z_AZ_B. The magnitude of a vector A is sqrt(X_A² + Y_A² + Z_A²).

So, in pseudo-C-ish:

//Vector is a simple immutable class or struct containing integer X, Y and Z components
public bool CloseEnough(Vector a, Vector b, decimal threshold = 0.000027m)
{
   int dotProduct = a.X*b.X + a.Y*b.Y + a.Z*b.Z;
   decimal magA = sqrt(a.X*a.X + a.Y*a.Y + a.Z*a.Z); //sub your own sqrt
   decimal magB = sqrt(b.X*b.X + b.Y*b.Y + b.Z*b.Z); //sub your own sqrt

   decimal angle = acos(dotProduct/(magA*magB)); //sub your own arc-cosine

   if(angle <= threshold
}

Answer 4

In my opinion, if two lines are approximately collinear, the following conditions should be satisfied:

1. The angle of two line is less than a threshold
2. The distance between a point and two line segments is less than a threshold

My solution:

import math
import numpy as np

def line_to_angle(line, use_abs=True):
    x1, y1, x2, y2 = line[:4]
    if abs(x2 - x1) <= 0.0000001:
        angle_val = 90 if y2 > y1 else -90
    else:
        angle_val = np.degrees(math.atan((y2 - y1) / (x2 - x1)))
    if use_abs:
        angle_val = abs(angle_val)
    return angle_val


def distance_line_point(p, line):
    p1 = np.array(p)
    p2, p3 = np.array(line[:2]), np.array(line[2:4])
    return np.abs(np.cross(p2-p1, p1-p3) / np.linalg.norm(p2-p1))


def near_collinear(linea, lineb, angle_thres=1.5, distance_thres=5):
    pointa = ((linea[0] + lineb[0]) / 2, (linea[1] + lineb[1]) / 2)
    pointb = ((linea[2] + lineb[2]) / 2, (linea[3] + lineb[3]) / 2)
    mid_angle = line_to_angle([*pointa, *pointb], use_abs=False)
    angle_a, angle_b = line_to_angle(linea, use_abs=False), line_to_angle(lineb, use_abs=False)
    angle_diff_a, angle_diff_b = abs(angle_a - mid_angle), abs(angle_b - mid_angle)
    angle_diff_a = min(angle_diff_a, 180 - angle_diff_a)
    angle_diff_b = min(angle_diff_b, 180 - angle_diff_b)
    if angle_diff_a > angle_thres or angle_diff_b > angle_thres:
        return False
    mid_point = ((pointa[0] + pointb[0]) / 2, (pointa[1] + pointb[1]) / 2)
    distance_a = distance_line_point(mid_point, linea)
    distance_b = distance_line_point(mid_point, lineb)
    if distance_a > distance_thres or distance_b > distance_thres:
        return False
    return True