Как создать карту из графика

7

Я хочу нарисовать 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 , чтобы получить координаты точки на графике:

пример графического представления с использованием sfdp

Использование положений точек привело к следующему представлению карты:

Пример карты с использованием диаграммы Вороного

Проблема этого подхода состоит в том, что, например, узлы 4 и 1 являются соседями, но на диаграмме Вороного они не из-за положения узлов. Так что для меня этот подход не удался.

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

Есть ли ключевое слово или алгоритм, который может помочь мне здесь?

Обновление / результат : Для полноты: это мой результат после использования предложений принятого ответа: результат

Мэгги
источник
Из приведенных данных можно создать несколько карт, особенно с точками 12 и 9, которые имеют только 1 отношение. Это особая проблема?
lewisjb
@ Пиро: нет, это не проблема. Его просто использовали для анализа.
Мэгги
Вы найдете алгоритм для этой двойной задачи, перечисленный как триангуляция Делоне и диаграммы Вороного.
tinyfiledialogs

Ответы:

12

То, что вы хотите, это создать двойной граф ; то есть график, получаемый путем преобразования граней в вершины и их соединения на основе смежных граней в исходном графе. Пример:

двойной граф

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

Чтобы использовать ваш пример, мы можем создать двойной граф в следующие шаги:

Шаг 1: для каждой грани в исходном графе создайте вершину

центроиды и наружное кольцо

Обратите внимание, что мы создаем внешнее «кольцо» для представления внешней «вершины» - так мы можем получить более красивый граф в конце, без сумасшедших пышных ребер.

Шаг 2: Для каждого ребра в исходном графе соедините две грани-вершины с ребром

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

края

Шаг 3: Играть в Риск

цветной график

congusbongus
источник
Спасибо за подсказку. Я начал похожий подход до того, как начал вороной, но не довел его до конца. Я сделаю это и опубликую свои результаты тогда.
Мэгги
Это интересно, также, если это поможет вам, попробуйте найти некоторую информацию о вороной-делоне-дуальности. Это хорошее начало, чтобы хотя бы понять это: scicomp.stackexchange.com/questions/771/…
Густаво
1
Еще один вопрос: какой подход вы бы использовали, если у вас нет помощи sfdp? Существует ли общий подход к созданию подходящего графического представления для получения необходимых позиций узлов?
Мэгги
@maggie вам нужно что-то, что выполняет планарную разметку графиков . Это не тривиальная проблема, и я не могу рекомендовать конкретный пакет, но есть варианты здесь и здесь .
congusbongus
1

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

Блас Сориано
источник
1
Это может использовать немного больше контента, чтобы сделать ответ немного более кратким.
Том Блю Пиддок