Merge 2d line segments

Question

I am looking for a way to join together 2D line segments. A line segment is made of up two vector points, the start of the line segment and the end point of the line segment.

I want to join line segments that look like they should form the same straight line, I don't want to join the line segments if they are of completely different orientations but happen to have 2 points close to each other. The system I am going to use this in is a computer vision system so the line segments obtained are not going to be perfect i.e. the orientations might be slightly off, the segments might not be full length e.t.c.

I think the following 3 examples cover the sort of line segments I want to join together:

Thanks

Answer 1

This is computational geometry problem there might be some solutions in related textbooks, but be warned these problems are usually very difficult to solve and finite precision is a real problem. With regard to this problem (in 2D) the term you are likely looking for is that the lines are near collinear. Typically what you do to determine if lines are collinear is to first put them in a vector representation, then take the dot product between the vectors, which will equal the cosine of the angle between the lines. So, if this value is near one they are close to collinear and should be joined.

The next problem is determining if lines are close enough to need to be joined. You could do this by finding lines that intersect or finding lines that have start and end points that are very close... This is not all that easy in general, but you can probably get 95% of them this way.