Group parallel (similar) polylines together

Question

How can I check if two polylines are close to parallel? They don't have to be exacly parallel, but should be similar in the sense that they are going in the same direction

@Edit

I think I need to explain a bit more the idea behind everything. As a input I get many poly-lines. What I want to do is group the polylines together that are quite parallel (in general similiar orientation). The result will be groups of similar poly-lines.

How do the poly-lines look like. They in general go straight upwards or to the left or right side. The don't have to start at the same y-value. The points of the polylines are in general not at the same height, that means have different y-value. As often the polylines are parallel in some interval and then start to differ I would like to find interval borders and define parts of the polyline parallel in this interval. Of course the interval should not be to small

I will now illustrate an example and what results I would like to have. Starting with 4 polylines, P1 to P4 shown in blue. For a human it is obvious that the lines P1-P3 are quite parallel until the red line b1. Therefore this sould be the first group G1 of parallel polylines. After the redline b1 there are the parallel polylines P1 and P4. Therefore they build group G2. The poly-line P3 is not parallel to anything else and therefore is alone in group G3. Hope that illustration helps

Example of two poly-lines that should be declared as parallel:

.

Example of two poly-lines that should be declared as NOT parallel

@Edit 2 After applying the douglas peuker algorithm to the input polylines I get this result. Now I want to group parallel polylines together. How do I find the corresponding lines segements that I want to compare? Also as you see in figure "How to compare the segments" that the polylines 1 and 2 should only be grouped together in the interval [b1,b2]. How do I find this interval? That actually means I need to find which segments to compare. If I compare them and if they are not parallel I classify as not parallel. If they are parallel I still need to find the interval in which they are parallel, right? That's because one polyline can start and end bevor another one.

Answer 1

What you might be able to do if look at the problem in the dual space. You may have come across the Hough transform which is used in image processing. This maps lines to point, and the set of points is called the dual space.

The basic idea is that you can parametrize a straight line y = m x + c, by the pair of numbers (m,c). You could do this for each segment in each polyline. These give a set of points for each segment. These points should form two clusters centred around (m1,c1) and (m2,c2). For the lines to be parallel then you would have m1 = m2.

This would require some form of clustering algorithm, possibly k-means, so you probably need some for computer vision toolkit. To parametrize the lines you probably don't want to use (m,c) as these don't work for vertical lines. Some algorithms use the angle of the line and the distance from a point.

A refinement on this is to try and fit line segments to parts of the polyline. You could start by defining a length for the line segment and then find subsets of the polylines with approximately this length.
With these subsets then do some line fitting, say linear regression. With these fitted lines you can then use the dual parameters, to compare the fitted lines.

---

If we think about lines and points in dual space there is a relationship

normal space   <--->   dual space

line           <--->       point
point          <--->       line

So every line corresponds to a point and every point corresponds to a line.

If we map the polyline to dual space we might get something like

This is not an acurate diagram. Each line segment becomes a point and each point becomes a line. What you would find is the dual space would kind of wrap around the dual space representative of the fitted line.

Answer 2

For each vertex on polyline A, find the closest point on polyline B and output the distance between these two points. (Using the closest vertex instead may work just fine.) Do the same for B with respect to A.

Now do a linear regression on the distances found. You should get a horizontal line, approximately. Define a threshold for this check.

Answer 3

in your example you know the each of pairs of line segments share y-axis coordinates so those are indexes, Also the lines are continuous per your example.

the distance between the two lines at each endpoint (y coordinate) is known. so:

for y in 0:n
   delta_x[y] = abs(blue_x[y] - red_x[y]) 

then if you subtract the smallest delta_x[y] from all of them you will have a non-negative curve, the area under this curve will be proportional to how parallel your lines are

less area more parallel,
more area less parallel,
perfectly parallel no area.

But only you could choose your threshold.

Answer 4

First reject any intersections.

Then do a linear regression on the lines. Establish a threshold for "roughly parallel". Now choose one polyline and take the most distant point from the line of best fit (if it is an end chose the next point). Now split the other polyline at the point of "best fit" (basically distance with a bit of slop to allow little local deviations and to cut on a corner point if possible).

Repeat until none of the line segments are polylines, and apply a fairly generous distance and direction threshold.