Optimization of Visibility Graph calculation

I'm trying to optimize Visibility Graph calculation. Can I somehow optimize the tripple loop im using? I am new to matlab, so the code is probbably not realy matlab like.

Visibility graph is a matrix, that represents all visible vertices for each vertice in some space. In my case, 2d polygonal space. A vertice is visible to another vertice if a line segment connecting those two vertices doesn't intersect any edge of polygons laying inside the 2d space. Line segment must also lie inside the main polygon but not in the obstacle polygon.

function visible = visibilityGraph( vx, vy, edg, poligons )

%cmap = hsv(length(vx));
visible = zeros(length(vx));
for i=1:length(vx)
    for j=i:length(vx)
        if j~=i
            l = [vx(i),vy(i),vx(j),vy(j)];
            m = [(vx(i)+vx(j))/2, (vy(i)+vy(j))/2];
            it = 0;
            if ~inpolygon(m(1),m(2),poligons{1}{1},poligons{1}{2})  
                it = 1; 
            end
            for n=2:length(poligons)
                [in,on] = inpolygon(m(1),m(2),poligons{n}{1},poligons{n}{2}) ;
                if in
                    if ~on
                        it = 1;
                        break;
                    end
                end
             end

              if ~it           
                  for k=1:length(edg)
                      e = edg{k};
                      d = lineSegmentIntersect([l(1) l(2) l(3) l(4)], [e(1) e(2) e(3) e(4)]);
                      d2 = lineSegmentIntersect([l(3) l(4) l(1) l(2)], [e(1) e(2) e(3) e(4)]);
                      if d.intAdjacencyMatrix
                          if d.intMatrixX == e(1) && d.intMatrixY == e(2) ||  d.intMatrixX == e(3) && d.intMatrixY == e(4)
                          else
                              it = 1;
                              break;                            
                          end
                      elseif d2.intAdjacencyMatrix  
                          if d2.intMatrixX == e(1) && d2.intMatrixY == e(2) ||  d2.intMatrixX == e(3) && d2.intMatrixY == e(4)
                          else
                              it = 1;
                              break;
                          end
                      end
                  end
             end

          if ~it
              X = [vx(i),vy(i);vx(j),vy(j)];
              d = pdist(X,'euclidean');
              visible(i,j) = d;
              visible(j,i) = d;
          end
        end
      end
    end
  end

• visible is an NxN matrix where N is number of all vertices, that will represent the visibilty graph
• vx and vy are vectors that contain x and y coortindates of vertices
• edg is a cell array that contains pairs of coordinates, each pair represeting and edge of a polygon
• poligons is a cell array that contains all polygons

First we check if a line segment between vi and vj is laying inside first polygon (border of the space) and not inside other polygons (obstacles).

Than we check if it intersects any of the edges (we filter out the edges that contain the vertices of the line segment).

If line segment doesn't intersect we write the length of it into the matrix.

I hope that my bad english will not be a problem. I would be realy greatful for any help or tips! Thanks

Answer 1

[tanu wadhera]

hello i read your code. At run time it is asking for input.. what kind of input i should give. Please give an example of the inputs.

Regards tanu