Как объединить несколько векторов, если они содержат повторяющиеся элементы?

Question

Я пытаюсь объединить векторы, содержащие строки, извлеченные houghLinesP, которые принадлежат друг другу.

Пока у меня есть Вектор, который содержит отрезки:

vector<Vec4i> lines;

У меня также есть алгоритм, который проверяет, достаточно ли похожи отрезки, чтобы считаться принадлежащими другим отрезкам линии (сейчас только на основе расстояния и угла):

    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);
    }

Теперь Вектор lineClusters содержит для каждого отрезка линии вектор отрезков, принадлежащих этому отрезку.

Проблема, с которой я сейчас сталкиваюсь, заключается в том, как объединить эти векторы. По сути, я хочу объединить все векторы, которые содержат хотя бы один повторяющийся отрезок линии, чтобы в итоге осталось только несколько кластеров.

Для иллюстрации я создал небольшое изображение:

На этом изображении присутствуют чёрные отрезки. Я хочу объединить их в линии. Круги, которые я нарисовал, представляют сегменты линий, которые могут быть определены как принадлежащие друг другу, и представлены вектором внутри 'lineClusters'. (Я не вытащил их всех)

У меня действительно нет идеи, как подойти к этой проблеме. У кого-нибудь есть мысли о том, как к этому подойти?

Редактировать Чтобы мои намерения стали более очевидными, я добавил следующее изображение: . Я пытаюсь сгруппировать линейные сегменты, чтобы идентифицировать дорожки.

Обновление

Следование рекомендациям Браиди приводит к следующему результату:

Результат, очевидно, можно улучшить, настроив функцию, определяющую, принадлежат ли фрагменты строки друг другу.

Answer 1

Настройка важна в этой проблеме. Я предполагаю, что vec4i - это пара точек, описывающих отрезок прямой линии (например, (a, b, c, d) => (x1, y1) -> (x2, y2))

Создайте свой vec4i так, чтобы (x1

Это позволяет сделать один проход слева направо по всем отрезкам линий. Создайте новую конструкцию, назовите ее Линия:

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

Определите некоторую новую функцию, которая может определить, достаточно ли близки две конечные точки, чтобы они были соединены. Создайте список из Line s.

Псевдокод общего алгоритма (где seg [0] или seg [1] является конечной точкой сегмента):

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))
}

Это объединяет все слева правые сегменты. Вам понадобится второй проход, который соединит линии, которые знают оба конца линии, если есть более сложные линии, подобные этой:

      \
       \
--------

(горизонтальная, диагональная) или обратная кривая, как в конце вашу диаграмму

   \
    \
     |
    /
   /

(изгиб вниз, изгиб вверх), которую вы хотите объединить в одну линию, а не в две.