Визуализация графов

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

Прим: макет графа (концепция визуализации) зачастую называют Layout.

На базе окружности

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

Как видно из рисунка каждой точке на окружности соответствует некоторое значение параметра t, находящегося на отрезке [0,2Pi]. Таким образом, для каждой вершины существует свое значение параметра. Теперь мы можем однозначно определить координаты каждой вершины.

Если у нас есть n вершин, то координата k-ой вершины определяется по следующей формуле: t = k * 2Pi/n.

Алгоритм на JS

d = 5;
dx = WIDTH/2;
dy = HEIGHT/2;
r = dx/2;
r0 = 5;
n = 10; //VertexCount

///
function plotVertex(i){
    x = r*cos( 2*pi*i/n - pi/2 ) + dx;
    y = r*sin( 2*pi*i/n - pi/2 ) + dy;
    circle( x,y,r0 );
    text( i, x + 2*d, y + 2*d);
}
for (v=0;v<n;v++)
    plotVertex(v);
///
function plotEdge(i,j){
    x1 = r*cos( 2*pi*i/n - pi/2 ) + dx;
    y1 = r*sin( 2*pi*i/n - pi/2 ) + dy;
    x2 = r*cos( 2*pi*j/n - pi/2 ) + dx;
    y2 = r*sin( 2*pi*j/n - pi/2 ) + dy;
    line(x1,y1,x2,y2);
}
plotEdge(5,3);
plotEdge(0,8);
plotEdge(8,3);
plotEdge(7,3);

Дугообразная диаграмма

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

Алгоритм на JS

d = 5;
dx = WIDTH/2;
dy = HEIGHT/2;
r = dx/2;
r0 = 5;
n = 10; //VertexCount
///
function plotVertex(i){
    y = dy;
    x = i * (2 * dx - d)/n + 2*d;
    circle( x,y,r0 );
    text( i, x + 2*d, y + 2*d);
}
for (v=0;v<n;v++)
    plotVertex(v);
///
function plotEdge(i,j){
    y = dy;
    a = i * (2 * dx - d)/n + 2*d;
    b = j * (2 * dx - d)/n + 2*d;
    x = (a+b)/2;
    r = Math.abs(b-a)/2;
    arc(x,y,r,PI,0);
}
plotEdge(5,3);
plotEdge(0,8);
plotEdge(8,3);
plotEdge(7,3);

Force-based диаграмма

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

Алгоритм на AS3

//Vertex class
package
{
   import flash.display.Sprite;
   import flash.geom.Point;
 
   public class Vertex extends Sprite
   {
      // speed of vertex
      public var velocity:Point = new Point(); 
      // force twards other vertices in the network
      public var net_force:Point = new Point();
      public var isDragged:Boolean = false;  // I can drag the vertex

      public function Vertex():void
      {
         // I draw a ring into the middle
         with(graphics)
         {
            beginFill(0xFF005E);
            drawEllipse(-12, -12, 24, 24);
            endFill();
         }
      }

   }
}
//Creating a graph
   // set of vertices
   vertices = new Vector.< Vertex >(n, true);
   // set of edges in symetric incidence matrix
   edges = new Vector. < Vector.< Boolean >>(n, true);
   for(i=0; i < n; i++) edges[i] = new Vector.< Boolean >(n, true);
   while(e > 0) // add some edges
   {
      var a:int = Math.floor(Math.random()*n);
      var b:int = Math.floor(Math.random()*n);
      if(a==b || edges[a][b])continue;
      edges[a][b] = true;
      edges[b][a] = true;
      e--;
   }
   // creating vertices
   for(i=0; i < n; i++)
   {
      var v:Vertex = new Vertex();
      v.x = 200+Math.random()*300;
      v.y = 100+Math.random()*200;
      vertices[i] = v;
      addChild(v);
      v.addEventListener(MouseEvent.MOUSE_DOWN, drag);
      v.addEventListener(MouseEvent.MOUSE_UP, sdrag);
   }
//Drawing the model
function onEF(e:Event):void
{
   for(i=0; i < n; i++) // loop through vertices
   {
      var v:Vertex = vertices[i];
      var u:Vertex;
      v.net_force.x = v.net_force.y = 0;
      for(j=0; j < n; j++) // loop through other vertices
      {
         if(i==j)continue;
         u = vertices[j]; 
         // squared distance between "u" and "v" in 2D space
         var rsq:Number = ((v.x-u.x)*(v.x-u.x)+(v.y-u.y)*(v.y-u.y));
         // counting the repulsion between two vertices 
         v.net_force.x += 200 * (v.x-u.x) /rsq;
         v.net_force.y += 200 * (v.y-u.y) /rsq;
      }
      for(j=0; j < n; j++) // loop through edges
      {
         if(!edges[i][j])continue;
         u = vertices[j];
         // countin the attraction
         v.net_force.x += 0.06*(u.x - v.x);
         v.net_force.y += 0.06*(u.y - v.y);
      }
      // counting the velocity (with damping 0.85)
      v.velocity.x = (v.velocity.x + v.net_force.x)*0.85; 
      v.velocity.y = (v.velocity.y + v.net_force.y)*0.85; 
   }
   for(i=0; i < n; i++) // set new positions
   {
      v = vertices[i];
      if(v.isDragged){ v.x = mouseX; v.y = mouseY; }
      else { v.x += v.velocity.x; v.y += v.velocity.y; }
   }
   // drawing edges
   graphics.clear();
   graphics.lineStyle(3, 0x333333);
   for(i=0; i < n; i++)
   {
      for(j=0; j < n; j++)
      {
         if(!edges[i][j]) continue;
         graphics.moveTo(vertices[i].x, vertices[i].y);
         graphics.lineTo(vertices[j].x, vertices[j].y);
      }
   }
}

Источник

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 12.12.17)