Как объединить набор неотсортированных отрезков в многоугольники за время не более O(n)?

Question

Есть набор неотсортированных отрезков lineSegments.

std::vector<std::array<glm::vec3, 2>> lineSegments.
lineSegments = {P1P2, A3A2, P2P3, A4A5 ...} (P1P2 = {{x, y, z}, {x, y, z}})

Как мне их отсортировать так, чтоб получились наборы вершин P1-P2-...-Р8 и А1-А2-...-А8: std::vector<std::vector<glm::vec3>> polygons за О(n) или быстрее?

Вот алгорит, который сделал я, но здесь O(n^2):

void orderVertices(std::vector<std::vector<Vec>>& polygons)
{
    while (lineSegments.size() != 0)
    {
        std::vector<Vec> polygon;
        polygon.push_back(lineSegments.front()[0]);
        polygon.push_back(lineSegments.front()[1]);
        lineSegments.erase(lineSegments.begin());
        while (1)
        {
            bool isFound = false;
            for (size_t j = 0; j < lineSegments.size(); j++)
            {
                if (compareWithPrecision(polygon.back(), lineSegments[j][0]))
                {
                    isFound = true;
                    polygon.push_back(lineSegments[j][1]);
                    lineSegments.erase(lineSegments.begin() + j);
                    break;
                }
                else if (compareWithPrecision(polygon.back(), lineSegments[j][1]))
                {
                    isFound = true;
                    polygon.push_back(lineSegments[j][0]);
                    lineSegments.erase(lineSegments.begin() + j);
                    break;
                }
            }

            if (!isFound)
            {
                polygon.pop_back();
                polygons.push_back(polygon);
                break;
            }
        }
    }
}

Пример работы программы:

Вход:

std::vector<std::array<glm::vec3, 2>> lineSegments = {
    {{-1, 1, 0}, {1, 1, 0}},
    {{-1, 1, 0}, {-1, -1, 0}},
    {{1, 1, 0}, {1, -1, 0}},
    {{-1, -1, 0}, {1, -1, 0}}
};

Выход:

std::vector<std::vector<glm::vec3>> polygons = {
   {
     {-1, 1, 0},
     {1, 1, 0},
     {1, -1, 0},
     {-1, -1, 0}
   }
}

Answer 1

В этой задаче нет геометрии, только графы. Из списка рёбер нужно составить граф рёбер, обойти его поиском в глубину. Каждая компонента связности - многоугольник.

Граф представлен как список смежности.

Компоненты связности ищутся рекурсивным поиском в глубину.

С++ добавляет сложности, так требуется определить хеш-функцию для вектора из трёх вещественных значений. Реализация заимствована из boost.hash_combine.

Весь алгоритм выполняется за линейное время от числа вершин многоугольников.

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror -Iglm restore-polygons.cpp

#include <array>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <glm/glm.hpp>

using point_t = glm::vec3;
using segment_t = std::array<point_t, 2>;

void hash_combine(size_t& seed, size_t hash_value) {
    seed ^= hash_value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct hash_t {
    std::size_t operator()(const point_t& p) const {
        std::size_t seed = std::hash<decltype(p.x)>{}(p.x);
        hash_combine(seed, std::hash<decltype(p.y)>{}(p.y));
        hash_combine(seed, std::hash<decltype(p.z)>{}(p.z));
        return seed;
    }
};

std::vector<segment_t> read_segments() {
    std::vector<segment_t> segments;
    point_t p1;
    point_t p2;
    while (std::cin >> p1.x >> p1.y >> p1.z >> p2.x >> p2.y >> p2.z) {
        segments.push_back({p1, p2});
    }
    return segments;
}

using graph_t = std::unordered_map<point_t, std::vector<point_t>, hash_t>;
using set_t = std::unordered_set<point_t, hash_t>;

void restore_polygon(const graph_t& graph, const point_t& point, set_t& visited,
                     std::vector<point_t>& polygon) {
    if (visited.find(point) == visited.end()) {
        visited.insert(point);
        polygon.push_back(point);
        for (const point_t& q : graph.find(point)->second) {
            restore_polygon(graph, q, visited, polygon);
        }
    }
}

void restore_polygons(const std::vector<segment_t>& segments,
                      std::vector<std::vector<point_t>>& polygons) {
    graph_t graph;
    for (const segment_t &s : segments) {
        graph[s[0]].push_back(s[1]);
        graph[s[1]].push_back(s[0]);
    }

    set_t visited;
    for (const auto& it : graph) {
        if (visited.find(it.first) == visited.end()) {
            polygons.push_back(std::vector<point_t>());
            restore_polygon(graph, it.first, visited, polygons.back());
        }
    }
}

void print_polygons(const std::vector<std::vector<point_t>>& polygons) {
    for (const std::vector<point_t>& polygon : polygons) {
        bool first = true;
        for (const point_t& p : polygon) {
            if (first) {
                first = false;
            } else {
                std::cout << ", ";
            }
            std::cout << '(' << p.x << ", " << p.y << ", " << p.z << ')';
        }
        std::cout << '\n';
    }
}

int main() {
    const std::vector<segment_t> segments = read_segments();
    std::vector<std::vector<point_t>> polygons;
    restore_polygons(segments, polygons);
    print_polygons(polygons);
}

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror -Iglm restore-polygons.cpp

$ cat segments 
 1  1  0      1 -1  0
 1  1 10      1 -1 10
-1  1  0      1  1  0
-1  1  0     -1 -1  0
-1  1 10      1  1 10
-1  1 10     -1 -1 10
-1 -1  0      1 -1  0
-1 -1 10      1 -1 10

$ ./a.out < segments 
(-1, -1, 0), (-1, 1, 0), (1, 1, 0), (1, -1, 0)
(-1, 1, 10), (1, 1, 10), (1, -1, 10), (-1, -1, 10)

БЛОГ НА HUSL

Как объединить набор неотсортированных отрезков в многоугольники за время не более O(n)?

Ответы (1 шт):