What is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?

Question

Edit: Changed the title. I'm less interested in the two segments being the same, but rather, if they are colinear with each other, within a certain tolerance. If so, then the lines should be clustered together as a single segment.

Edit: I guess a short way of saying this: I'm trying to cluster similar line segments together in an efficient way.

Say I have line segments f (fx0, fy0) and (fx1, fy1) and g (gx0, gy0) and (gx1, gy1)

These come from something like a computer-vision algorithm edge detector, and in some cases, the two lines are basically the same, but are counted as two distinct lines because of pixel tolerances.

There are several scenarios

• f and g share the exact same endpoints, eg: f = (0,0), (10,10) g = (0,0), (10,10)
• f and g share roughly the same endpoints, and roughly the same length, eg : f = (0,0.01), (9.95,10) g = (0,0), (10,10)
• f is a subset of g, meaning that its endpoints fall within the g segment and share the same slope as the g segment. Think of a roughly drawn line in which the pen has gone back and forth to make it thicker. eg : f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)

The following would not be considered the same:

• f and g have a slope difference beyond a certain tolerance
• f and g may have the same slope but are separated by a distance beyond tolerance, i.e. parallel lines
• f and g are on the same plane and same slope, but don't overlap at all...i.e. a set of segments within a dashed line.

The easiest way to tell if they are the same is if gx1 - fx1 <= tolerance (repeat for the three other points), but in some cases, line f may be shorter than line g (again, because of pixel differences and/or poor photo scanning).

So is it better to convert the two segments into polar coordinates and compare the angles? In that case, the two rho's would be within a tolerance. But then you have to make sure the two line segments have the same "direction", which is trivial to compute in Cartesian or polar coordinates.

So this is easy to figure out a way, but I'm just wondering if there's a much cleaner way, based in the linear algebra that I've long forgotten?

Answer 1

Your problem is two-fold: you want to compare both the difference in length and difference in angles. To compute the difference in length, you'd take the length of the first line and divide it by the length of the second line.

To take the difference in angle, you can use atan or, my favourite:

angle = acos(abs((u dot v)/(u.length * v.length)))

Hopefully this helps. Sorry for the mistaken answer earlier.

Old answer:

Here's an idea for you: why not compare the difference in the start and end points of the two line segments to the total length of one of the lines? Then your difference function would look something like:

def difference(Line l1, Line l2):
    # Distance between first point on first line and first point on second line
    first_point_diff = (Line(l1.x1, l2.x1, l1.y1, l2.y1).length())

    # Distance between first point on first line and first point on second line
    second_point_diff = (Line(l1.x2, l2.x2, l1.y2, l2.y2).length())

    return (first_point_diff + second_point_diff)/l1.length()

This function will return the "difference" between two lines as a fraction of the total length of the first line.

Answer 2

Can you use the coordinates to define equations for the lines? If so, then you could use the two equations in a system of equations, solve the system, and find out if and where the lines intersect. If the lines do not intersect at all but the distance between them is very small, or with in the tolerance you could consider them a single line.