File Exchange

image thumbnail

spatialgraph2D

version 2.0.3 (3.3 KB) by Matt J
Creates a graph object with 2D spatial locations associated with the nodes

6 Downloads

Updated 15 Aug 2020

View Version History

View License

This submission defines a graph class which allows 2D (x,y) location data to be attached to the nodes. It was designed with mosaic graphs in mind. By a mosaic graph, I mean a graph in which distinct edges may intersect one another only at the nodes. Currently, its main capability is decomposing a mosaic graph into its constituent polygons. As an example, given the graph,

s = [1 1 1 2 3 3 4 4 5 6 7 6 8 9 10 10 12 12 13 14 15 16 17 17 18 19 20 21 20 25];
t = [2 8 18 3 4 23 5 21 6 7 8 11 9 10 11 12 14 13 15 18 16 17 18 25 19 20 1 22 24 26];
G = graph(s,t);

we associate the nodes of G to the following x, y data

x = [0.5 0 0 0 0.5 1 1.5 2 3 3 3 5.5 6 4 6 6 4 3 2 0.5 -1 -2 -1 1.5 4.5 4.5];
y = [0 0.5 1 1.5 2 2 1.5 1 1 1.5 2 1 0.5 0.5 0 -1 -1 -0.5 -1 -1 1 0.5 0.5 -0.5 -0.5 0];

We create a spatialgraph2D object as follows,

obj=spatialgraph2D(G,x,y);

Then, we can obtain a polyshape array of all the constituent polygons as follows,

pgon=polyshape(obj);

To visualize, use the following pair of overlaid plots. This was used to generate the image thumbnail above.

plot(obj);
hold on
plot(pgon);
hold off

Cite As

Matt J (2021). spatialgraph2D (https://www.mathworks.com/matlabcentral/fileexchange/73630-spatialgraph2d), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (17)

Jimmy Zhang

Thanks Matt. I will try that.

Matt J

Dear Jimmy,
I think the only short term solution would be to convert your x,y,z coordinates to longitude and latitude, and thus convert to a 2D graph. You may need to do this for several different longitude coordinate origins to make sure loops that break across the 0/360 degree longitude line are captured.

Jimmy Zhang

Dear Matt,
Thanks to your fast reply. Sorry for not explaining my problem clearly. I actually have a graph defined on 3D sphere. The 3D sphere surface <V, F> is composed of triangular mesh grids with vertices V and triangular faces F. Each vertex V_i has its corresponding 3D coordinates (x, y, z) on surfaces. There are some neighboring vertices (nodes) connected with each other forming very big loops (similar like your 2D example). I want to detect every loop within the whole graph. Since your code is designed for nodes with 2D spatial locations as input. I tried to see if it is possible to directly adapt your code to deal with 3D locations. I actually only need each loop node list as output and thus I am not sure should I really consider the spatial locations or not? Maybe a simple loop searching within a graph will work for me. Thanks.

Matt J

Dear Jimmy,
What class methods and functions would a 3D version have? Are you saying you have graph which you know forms the edges of a 3D mosaic of polyhedrons and, in analogy with spatial2D.polyshape(), you would like a method spatialgraph3D.polyhedron() to break it up into polyhedrons? If so, can any of the polyhedrons have missing facets? Should the class be able to represent a box with 5-faces, for example?

Jimmy Zhang

Dear Matt,
Would it be possible to make a version for dealing with 3D location data (x, y, z)? Thanks.

C GC

Dear Matt. thank you very much for all your help.

Matt J

Dear C GC,
I believe I understand much of what are causing issues are now. Note first of all that the way you are generating XData and YData for the graphs will not produce the same results in different Matlab versions. Since the XData and YData can be different, or at least in a different order, in two different Matlab versions, the numbering of the nodes need not be the same, and so you have no guarantee of seeing a loop enumerated [7,9,4,10]. Secondly, I have looked deep enough into the code to understand the reason you sometimes see [9,9,9,10]. As I suspected, it has to do with the fact that your graph does not have a mosaic structure. One remedy would be to write a routine which loops through every pair of graph edges, finds where they intersect, and adds a new node there, if one doesn't exist there already.

It may be worth warning you as well that some of what you see may be computer-dependent as well as Matlab version dependent. I have run the code in versions R2018a, R2019a, R2019a, and R2020a. None of my results coincide precisely with what you report, although I am able to reproduce the [9,9,9,10] in R2018a and R2019b.

>> nodeIDs{11:14}

ans =

7 3 8

ans =

9 9 9 10

ans =

8 4 9

ans =

8 9 7

However, in R2019a and R2020a, the results I get are well behaved, unlike what you seem to be seeing:

>> nodeIDs{11:14}

ans =

7 9 4 10

ans =

8 3 9

ans =

7 2 8

ans =

9 7 3

C GC

Dear Matt. Thank you very much for this function. It is really a nice piece of code. i am using it plenty these days. Anyhow, this is strange for Matlab R2019a nodeIDs{12}=[9,9,9,10]. For Matlab 2020a nodeIDs{14}=[9,9,9,10]. In any of the two versions, I was able to fin [7,9,4,10]. Which version of matlab are you using? Thanks again for this code. CGC.

C GC

Just a small update. For matlab 2020a nodeIDs{14}=[9,9,9,10];

Matt J

Dear C GC,

I am seemingly not getting the same output as you. When I run your example, the node sequence [9,9,9,10] does not appear anywhere in the output I'm getting, whereas [7,9,4,10] is indeed in the list,

>> nodeIDs{11}

ans =

7 9 4 10

What I can say though is that you are pushing the function into unplanned territory by applying it to graphs with overlapping polygons. As mentioned in the description, the function was designed for decomposing a "mosaic" into its constituent polygons. By a mosaic, I mean a set of polygons that can be adjoining or non-adjoining, but whose edges intersect other edges only at the nodes. When you have non-mosaic graphs, the ways it can be partitioned into polygons are non-unique, which is probably why you do not find all of the polygons you expect to in the output. However, I am pleased to see that the function does indeed manage to find a complete covering/partitioning of the graph in your example. The final plot that I'm seeing has no unshaded regions and all graph edges have been assigned to at least one polygon.

C GC

Dear Matt. thanks for this function. I have found some issues while trying to implement it. Some polygons do not identify the nodeIDs, in other words, the polygon is reported in pgon but the equivalent nodeIDs cell is an empty vector while running [pgon,nodeIDs]=polyshape(obj).

Other times for complex graphs some polygons are not found and others have a weird collection of points and nodes. In the following example, the polygon formed by [6,9,5,10] is not found, or the [7,9,4,10] is not found, and the pgon(12) is formed by the nodes [9,9,9,10]. I have tried to understand this issues but I have not had much success. Thanks for any help.

n = 3;
A = delsq(numgrid('L',n+2));
A2 = delsq(numgrid('L',n+2));
A3=[[A , A2] ; [A2 , flip(A,1)]];
G = simplify(graph(A3, 'omitselfloops', 'upper'));
h=plot(G, 'Layout','force', 'UseGravity',true)
XData=get(h, 'XData');
YData=get(h, 'YData');
obj=spatialgraph2D(G,XData,YData);
[pgon,nodeIDs]=polyshape(obj);
plot(obj);
hold on
plot(pgon);
hold off

Cheng Ting Tsai

NA

Matt J

So, just to clarify, your examples have multiple mosaics, since some of the polygons "dangle" off the others by a single vertex. As mentioned in the description above, the class wasn't designed for such cases. However, you can try putting the line obj=prune(obj) back in, but modifying the prune() method to the following:

function obj = prune(obj)
%Remove dangling branches

Gp=obj.G;
xp=obj.x;
yp=obj.y;
lp=obj.labels;

tips=find(degree(Gp)<=1);

while ~isempty(tips)

Gp=rmnode(Gp,tips);
xp(tips)=[];
yp(tips)=[];
lp(tips)=[];
tips=find(degree(Gp)<=1);

end

obj=spatialgraph2D(Gp,xp,yp,lp);

end

NA

how about this graph
s = [1 2 2 1 39 9 8 8 7 6 6 11 11 12 10 10 13 14 15 16 19 19 20 16 24 23 23 22 21 16 16 17 18 3 4 4 5 2 26 26 29 29 28 27 27];
t = [2 25 30 39 9 8 5 7 6 31 11 10 12 13 13 32 14 15 16 19 33 20 34 24 23 36 22 35 22 21 17 18 3 4 5 14 6 3 25 29 38 28 26 26 17];
G = graph(s,t);
x = [10 9 7 7 9 9 10 10 11 6 8 7 6 6 5 4 5 6 3 2 4 3 2 3 8 7 6 6 7 10 9 5 3 1 2 1 9 7 11];
y = [6 7 7 6 3 2 2 3 4 2 2 3 4 5 5 7 8 8 6 5 8 9 8 7 8 9 9 10 10 8 1 1 5 4 10 9 9 11 5];
obj=spatialgraph2D(G,x,y);
[pgon,loops]=polyshape(obj);
plot(obj);
hold on
plot(pgon);
hold off
I got this error
Index exceeds the number of array elements (0).
Error in spatialgraph2D/polyshortest (line 102)
E=G.findedge(P,[P(2:end),P(1)]);
Error in spatialgraph2D/polyshape (line 131)
[P,E]=polyshortest(obj,E0);

Matt J

Remove the line

obj=prune(obj)

NA

I have this graph
s = [1 1 1 1 1 2 3 3 4 6];
t = [2 3 5 6 7 3 5 4 5 7];
G = graph(s,t);
x = [5 6 4 3 2 5 7];
y = [6 4 4 3 5 8 7];
obj=spatialgraph2D(G,x,y);
[pgon,loops]=polyshape(obj);
plot(obj);
hold on
plot(pgon);
hold off
how can I get [1,6,7] as a loops?

MATLAB Release Compatibility
Created with R2018a
Compatible with R2016b and later releases
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!