How to merge multiple vectors if containing duplicate elements?

Question

I am trying to merge vectors containing lines extracted by houghLinesP that belong together.

So far I have a Vector that contains line segments:

vector<Vec4i> lines;

I also have an algorithm that checks if line segments are similar enough to be considered belonging to other line segments (for now only based on distance and angle):

    vector<vector<Vec4i>> lineClusters;

    for(Vec4i line1: sortedLines){
        Point l1o = Point(line1[0], line1[1]);
        Point l1d = Point(line1[2], line1[3]);
        vector<Vec4i> cluster;
        for(Vec4i line2: sortedLines){
            Point l2o = Point(line2[0], line2[1]);
            Point l2d = Point(line2[2], line2[3]);
            if ((getDistance(l1o, l1d, l2o, l2d) <= 20) and
                (abs(angle(l1o, l1d) - angle(l2o, l2d)) <= 10)) {
                cluster.push_back(line2);
            }
        }
        lineClusters.push_back(cluster);
    }

Now the Vector lineClusters contains for each line segment a vector of line segments belonging to that line segment.

The problem I now face is how to merge these vectors. Basically I want to merge all vectors that contain at least one duplicate line segment so that in the end only a few clusters remain.

To illustrate I have created a little image:

In this image there are black line segments which are found. I want to merge those into lines. The circles I have drawn represent the line segments that might be determined to belong together and are represented by a vector inside of 'lineClusters'. (I have not drawn them all out)

I don't really have an idea of how to approach this problem. Does anyone have any thought on how to approach this?

Edit To make my intent a little more obvious I have added the following image: . I am trying to group line segments in order to identify lanes.

Update

Following the suggestions provided by Braaedy leads to the following result:

The result can obviously be improved by adjusting the function that determines if line fragments belong together.

Answer 1

Set up is important in this problem. I'm assuming the vec4i is a pair of points describing a straight line segment (e.g. (a, b, c, d) => (x1, y1) -> (x2, y2))

Construct your vec4i such that (x1 < x2) || (x1 == x2 && y1 < y2).

This allows you to make a single left-to-right pass over all lines segments. Create a new construct, call it a Line:

struct Line {
  std::vector<vec4i> segs;
  const vec2i &getEnd() const { *segs.rbegin(); }
};

Define some new function that can determine if two endpoints are "close enough" that they are connected. Create a list of Lines.

General algorithm pseudocode (where seg[0] or seg[1] is a segment endpoint):

for (seg : Segments) {
  for (line : Lines) {
    if (close(line.getEnd()[1], seg[0])) {
      line.addSegment(seg)
      // break to next *segment*, a segment can only be added to one line.
    }
  }
  // reaching here means we didn't make attach the segment; start a new line.
  Lines.add(Line(seg))
}

This joins all left-to right segments. You'll need a second pass that joins lines that is aware of both ends of the line if there's more complicated lines like this:

      \
       \
--------

(horizontal, diagonal) or a back curve like at the end of your diagram

   \
    \
     |
    /
   /

(curve down, curve up) that you want joined into one line rather than two.