Я хочу нарисовать 2-хугольную карту на основе данных, предоставленных другим источником, чтобы упростить анализ действий на карте. Данные имеют следующий формат:
1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...
Первое число является идентификатором узла, следующий список содержит идентификаторы его соседей. Поскольку число соседей узла отличается, мне нужно нарисовать карту многоугольника.
Поэтому я попытался использовать полигоны Вороного для представления карты. Проблема в том, как я могу определить точки, чтобы удовлетворить все отношения соседства? Я предполагаю, что моя первая попытка более или менее является ошибкой в моем цикле попыток и ошибок. Я использовал ПРМФ инструмент GraphViz , чтобы получить координаты точки на графике:
Использование положений точек привело к следующему представлению карты:
Проблема этого подхода состоит в том, что, например, узлы 4 и 1 являются соседями, но на диаграмме Вороного они не из-за положения узлов. Так что для меня этот подход не удался.
Погуглив, я нашел много учебных пособий, генерирующих карты с полигонами или плитками, но я еще не выяснил, как я могу создать карту для моих данных. Я предполагаю, что есть подход, использующий (многократные) шестиугольники / треугольники / квадраты или смесь, чтобы достигнуть того, что мне нужно, но я не знаю, что я буду искать.
Есть ли ключевое слово или алгоритм, который может помочь мне здесь?
Обновление / результат : Для полноты: это мой результат после использования предложений принятого ответа:
Ответы:
То, что вы хотите, это создать двойной граф ; то есть график, получаемый путем преобразования граней в вершины и их соединения на основе смежных граней в исходном графе. Пример:
Проблема, как вы можете видеть, заключается в том, что если вы хотите сохранить ту же схему графика, вы получите действительно изогнутые ребра в двойном графике. Кроме того, вы часто будете получать мультиграф - граф, в котором у некоторых вершин есть несколько ребер. Он гарантированно будет плоским, так что это что-то.
Чтобы использовать ваш пример, мы можем создать двойной граф в следующие шаги:
Шаг 1: для каждой грани в исходном графе создайте вершину
Обратите внимание, что мы создаем внешнее «кольцо» для представления внешней «вершины» - так мы можем получить более красивый граф в конце, без сумасшедших пышных ребер.
Шаг 2: Для каждого ребра в исходном графе соедините две грани-вершины с ребром
Кроме того, вам придется что-то делать, чтобы эти края не перекрывали друг друга. Разрыв между 3 и 12 особенно проблематичен. Эти новые края, возможно, должны быть изогнуты, чтобы сделать это возможным. Это то, что вы получаете за вогнутый граф.
Шаг 3: Играть в Риск
источник
Если первое изображение, где каждая точка представляет собой небольшой квадрат определенного цвета, это то, что вы ищете, вам нужно построить триангуляцию Делоне.
источник