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

Question

Edit: Name changed. I’m less interested in two segments, the same, but if they are collinear with each other, within a certain tolerance. If so, then the rows should be grouped together as one segment.

Edit: I assume this is a short way to say: I try to group similar line segments in an efficient way.

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

They come from something like an edge detector of a computer vision algorithm, and in some cases the two lines are basically the same, but are considered two different lines due to pixel tolerances.

There are several scenarios

• f and g exchange the same endpoints, for example: f = (0,0), (10,10) g = (0,0), (10,10)
• f and g share approximately the same endpoints and about the same length, for example: f = (0,0.01), (9.95,10) g = (0,0), (10,10)
• f is a subset of g , which means that its end points fall into segment g and have the same slope as segment g . Think of a roughly drawn line in which the pen went back and forth to make it thicker. for example: f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)

The following are not considered the same:

• f and g have a slope difference outside some tolerance
• f and g can have the same slope, but are separated by a distance outside the tolerance , i.e. parallel lines
• f and g are on the same plane and the same slope, but do not overlap at all ... i.e. set of segments in a dashed line.

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

So is it better to convert two segments to polar coordinates and compare angles? In this case, two rho will be within the tolerance. But then you need to make sure that the two line segments have the same “direction”, which is trivial to calculate in Cartesian or polar coordinates.

So it's easy to understand, but I'm just wondering if there is a cleaner way based on linear algebra that I forgot about long ago?

Answer 1

Your problem is twofold: you want to compare both the difference in length and the difference in angles. To calculate the difference in length, you must take the length of the first line and divide it by the length of the second line.

To understand the difference in angle, you can use atan or, my favorite:

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

Hope this helps. Sorry for the erroneous answer earlier.

Old answer:

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

 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 the two lines as part of the total length of the first line.

Answer 2

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

Answer 3

If all you want to do is see if they are in the same direction, could you just look at the product of the points divided by the quantities? The closer to 1, the closer the alignment between the two lines.