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

Question

Я пишу Risk-подобную настольную игру в Java.Особенностью является то, что игроки могут создавать свои собственные карты, которые они хранят в текстовом файле.В текстовом файле перечислены все территории (== страны) на карте мира, за которыми следуют их прямые соседи.Затем игра сканирует файл и создает коллекцию территорий с соответствующими списками смежности.

Следующим шагом будет перевод этого графа в графическое представление.Это означает, что я хочу представить каждую территорию прямоугольником или какой-либо другой простой формой.Я пока не хочу входить в сложные, острые границы между территориями.Таким образом, в основном территории будут выглядеть как некоторые африканские или североамериканские страны с горизонтальными и вертикальными границами.

Теперь моя проблема такова: хотя было бы легко визуализировать график, где границы представлены нарисованными краями между ними,Мне трудно разместить территории (== вершины), непосредственно примыкающие друг к другу.Другими словами, территории должны «касаться» друг друга, как в реальном мире.

В частности, это трудно из-за таких мест, где 4 или более территорий граничат друг с другом (рассмотрим четыре угла в США сАризона, Колорадо, Нью-Мексико и Юта).

Теперь мне стало интересно, пытался ли кто-нибудь когда-нибудь сделать что-то подобное или существуют ли уже существующие алгоритмы, решающие эту проблему.Буду признателен за любую помощь и творческий вклад.Спасибо!

Answer 1

GMap это именно то, что я хочу.Они сочетают в себе различные методы, в том числе диаграммы Вороного (, вот статья по алгоритму ).Теперь мне просто нужно выяснить, как это получить ...

Answer 2

Если вы можете использовать инструмент макета графа, такой как graphviz, для получения плоской проекции вашего графа, то вы можете посмотреть на вычисление вороной диаграммы точек на вашем графике, которую вы можете затем исказить, чтобы сделать вещи более визуально интересными.(Возможно, вам также следует остерегаться, чтобы убедиться, что вы не изменяете свойства смежности при вычислении диаграммы Вороного, поскольку это зависит от относительного расстояния между точками. Возможно, вам также придется обнаружить места, где«океаническая» ячейка должна быть вставлена ​​для того, чтобы сделать две территории несмежными.)