Теория диаграмм - алгоритм автоопределения на основе силы

Просто хочу проверить, что у меня есть моя теория, прежде чем я начну внедрять.

Константы:

  • m= масса вершины (все равно - возможно, это значение равно радиусу node)
  • k= постоянная сила края.
  • l= длина ребра в "минимальном состоянии энергии".

Переменные

  • d= расстояние между двумя вершинами.
  • cl= текущая длина ребра.

Теория: Каждая вершина имеет силу отталкивания на каждой другой вершине, которая равна: m / (d^2). Для каждого ребра проявляется сила, при которой обе вершины "перетаскивают" их в направлении, чтобы получить край в "минимальное энергетическое состояние"; поэтому каждая вершина: -k * ((l - cl) / 2).

псевдокод:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

Комментарии: Так будет ли это работать? Что я должен установить m и k на?

Ответы

Ответ 1

Вы на правильных строках. Ваша терминология/физика немного сбита: то, что вы называете массой, и "k" - это нечто вроде смешения с тем, что лучше назвать "зарядом" (для отталкивания обратно-квадратного закона) и "spring константой" для привлечения внимания Гука.

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

В этой статье wikipedia article есть хороший псевдокод, который вы найдете очень похожим на ваш, но с указанными выше пунктами (хотя обратите внимание, что даже что в псевдокоде отсутствует расхождение по массе при вычислении ускорения, см. обсуждение на странице).

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

Ответ 2

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

Я не знаю, k.