MST из массива 2D треугольников, но с небольшим поворотом
Вот иллюстрация шагов, предпринятых до сих пор:
- Генерация псевдослучайного прямоугольника
- Вставка «центрального узла», прямое разделение и выбор последнего узла
- Триангуляция Делоне (показано с ранее выбранными узлами)
- Визуализация треугольных ребер
На этом этапе (шаг 5) я хотел бы использовать эти данные для формирования Минимальное остовное дерево, но есть незначительный ловить…
Где-то на графике (вероятно, недалеко от центра, но не всегда) будет узел, который требует 3-5 подключений к нему от других уникальных узлов. Это усложняет ситуацию, так как каждый другой узел должен содержать только одно соединение, а используемые структуры данных затрудняют определение «что связано с чем» в надежном, проходимом формате.
Итак, учитывая массив треугольников в указанном выше формате и случайную вершину для использования в качестве «корневого узла», как я мог бы правильно пройти по сети, чтобы создать MST, где есть как минимум 3 соединения с нашим «центральным узлом», но не более 5 подключений к нему? Это возможно?
Решение
Поскольку у вершины в триангуляции Делоне гораздо больше, чем 6 ребер, вы можете использовать грубую силу: есть только 20 + 15 + 6 способов выбрать 3, 4 или 5 ребер из 6 (соответственно), поэтому попробуйте все из них. Для каждого из 41 созданных таким образом (до 336 для степени 9) небольших деревьев (корень и несколько ребер), запустите Алгоритм Крускала или же Алгоритм Прима начиная с этого дерева, уже «найденного», чтобы быть частью MST. (Проигнорируйте другие края корня, чтобы не увеличивать его степень далее.) Затем просто выберите лучший (включая стоимость семенного дерева).
Что касается общей проблемы информации о соседе, то, похоже, вам просто нужно сначала построить стандартное представление графа. Например, вы можете составить список смежности, просканировав все ваши Edge объекты и сохранение каждой конечной точки в списке, связанном с другим (в map<Vector2<T>,vector<Vector2<T>>> или эквивалент, основанный на любых идентификаторах для ваших вершин).
Другие решения
Я принял обходной подход …
После шага 3 моего алгоритма я просто удаляю все ребра, которые соединяются с «центральным узлом», отслеживая, какие ребра образуют вокруг него «кольцо» (также называемое «петля ребер»), и запускаю MST на всех оставшихся ребрах.
Для MST я пошел с библиотекой графов повышения.
Это позволило легко проходить через треугольники, которые у меня были, добавляя каждый из трех ребер к adjacency_list, Затем все остальное позаботился простой вызов того алгоритма MST, который обеспечивает повышение.
Наконец, я прочитал края, которые были ранее удалены. Кратчайший путь — это то, что было на предыдущем шаге, плюс длина любого из считанных ребер, который соединяется с другим ребром в «кольце», является самым коротким.
Затем я могу добавить (или удалить) произвольное количество предыдущих ребер, чтобы обеспечить от 3 до 5 ребер, соединяющих петлю ребер с «центральным узлом».
Выполнение действий в этом порядке также позволяет мне сразу же после шага 3 узнать, будет ли у нас хотя бы допустимое число ребер, чтобы мы не теряли циклов, выполняющих MST.