Constructing a Doubly-Linked Edge List

Hi everyone,

I am working on constructing a linked list, that connects edges in two directions and traverses through all points of a list. The code requires pointers to do, since we do not want to store this information recursively. Suppose the following:

we have six points, arranged in a closed polygon, labeled p0 to p5. At any one time, we're looking for a vector "e" in the direction from one point to the closest adjacent to it (i.e. p1 and p2), making a half-edge.

We are also looking for a vector "twin(e)", which goes in the direction from p2 to p1 (the other way) as the other half-edge. Finally we need 2 more vectors, "Next(e)" and "Prev(e)", which point to the points before and after the current ones in "e". Therefore, Next(e) will go in the direction from p2 to p3 and Prev(e) will go in the direction of p0 to p1.

We must also know the face that lies on the side of the line that the vector is. This is a very confusing explanation but hopefully this image clears it up: http://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Dcel-halfedge-connectivity.svg/447px-Dcel-halfedge-connectivity.svg.png

In this image the vectors "next(e)", "prev(e)" and "e" all point to the same face, whereas "twin(e)" points to a face outside of the closed polygon.

I have no idea how to use pointers in MATLAB, but the idea behind the pseudo-code is this:

   P = 10*rand(10,2);
   for i=1:length(P)-1

      % starting from the first point
      e -> P(i+1,:);         % p1
      next_e -> P(i+2,:);    % p2
      prev_e -> P(i,:);      % p0
      twin_e -> P(i+2,:);    % p2

      [f_e,f_twin,f_next,f_prev] = get_face(e,twin(e),prev(e),next(e));
      % this will tell you what direction to go

   end

Any help towards this subject and understanding the algorithm, or even just pointers in MATLAB will be very helpful. I understand the theory, but how to code it is something different entirely. Especially when programming for all scenarios.

Ian

[Cedric]

Your illustration shows points/nodes connected to multiple other nodes (some associated with other faces I guess), which means that there can be multiple prev() and next(); how do you manage this? Are these functions meant to return only edges that are defining the same polygon?

There are many ways to implement such a logic; which one is best (or just suitable) is certainly related to the usage that will make of this mechanism in your final application. You should therefore provide more information about what it is that you want to achieve ultimately.

[Ian Wood]

There are supposed to be multiple prev() and next(), the idea of the code is it is supposed to traverse around the outermost figure drawn by a series of points, let's say going in the direction the figure is showing in the link. Every vector's position would move one over, so the edge with the current "next()" will be the edge with the next "e" and "twin()". Then "prev()" will be assigned to the current position of "e" and "twin()". Hopefully that's not too confusing to understand, and yes I want to return the edges.

I am working on constructing a Voronoi diagram, which involves subdivisions of polygons and the doubly-connected list needs to be closed by a box containing all of the points (vertices) inside of it, including all polygons.

[Cedric]

Why not using directly http://www.mathworks.com/help/matlab/ref/voronoi.html?

[Ian Wood]

Because I am not implementing Delaunay Triangulation in my code, which is what "voronoi" does. I am implementing Fortune's Algorithm (sweep line) and running the code in the most optimal time.

[Cedric]

If you want optimal performance, you should use C/MEX. Implementing it in pure MATLAB is likely to be slower than qhull/voronoi/etc, so it is interesting only if you wanted e.g. to build a demonstrator for the algorithm. I you really want performance, I guess that your best option is to use an existing well optimized algorithm written in C/C++ and build a MEX wrapper to "mount" it in MATLAB. Your focus would then not be on the proper implementation of the algorithm, but on the MEX interface.

[Ian Wood]

So I shouldn't write the code in MATLAB is what you're saying, provided I want maximum performance. I've never worked with MEX before, but the C implementation shouldn't be too difficult. I'll read up on it and if I have any questions, I'll be sure to ask you.

[Cedric]

Yes that's it, and there are C/C++ implementations available online already (even Fortune's own implementation is available); it's just a matter of taking one which was well implemented and/or peer reviewed.

[Ian Wood]

Thanks for the help and advice so far Cedric!

[Cedric]

You're welcome!

[Ian Wood]

Unfortunately, my professor does not want me to use any other program, just MATLAB to do this. I would imagine that instead of pointers, I should use cells inside of cells. Is this a correct assumption?

[Cedric]

Or numeric arrays of vertex/node IDs inside cell array(s). The advantage of cell arrays is that they can store inhomogeneous (in class/size) data, but they are not as handy and efficient for manipulating regular arrays of numbers, so whenever you can, prefer a regular numeric array. Now sometimes you want to favor clarity of data structure over efficiency, so there are cases where the choice of cell array versus numeric array is a question of preference. To illustrate, if you have a variable amount of vertices per node, you can store this information in a cell array with one cell per node, each cell containing a numeric array of destination node IDs and lengths:

 % Node 1 
 %   -> node 2 with length 8.9 
 %   -> node 3 with length 17.2
 vertices{1} = [2, 8.9; 3, 17.2] ;

 % Node 2 
 %   -> node 1 with length 8.9
 %   -> node 3 with length 22.4
 %   -> node 5 with length 3.1
 vertices{2} = [1, 8.9; 3, 22.4; 5, 3.1] ;

But you could also code it as one large numeric array with column 1 = start node IDs, column 2 = destination node IDs, column 3 = lengths:

 vertices = [1, 2, 8.9   ; ...
             1, 3, 17.2  ; ...
             2, 1, 8.9   ; ...
             2, 3, 22.4  ; ...
             2, 5, 3.1] ;

If connections are symmetrical, you can build an array of unidirectional connections, and append the other directions as I did there link but using, in your case, something like

 vertices = [vertices; vertices(:,[2,1,3]) ;

to append an array of vertices with same lengths but permuted start/destination node IDs.

[Ian Wood]

Right, I can see how this would work for a single case for a doubly-connected edge list, but i will not always have the same placements for the nodes. They will also vary in length through each iteration, since I am working on constructing a general code. I still have a feeling that I can use what you presented, but I think there's another step involved to do exactly what I need.

I was thinking of reading into the nodes by calling them in order from high to low (basically decreasing y-value). That way I would be able to label them no matter what the case, and call them when needed. However, the method that these nodes are actually connected with edges is a different story and involves a completely different program than this, and obviously more research into Voronoi diagrams.

I still don't have a way to identify the faces in my code though. An incident face needs to be assigned to each side of the edges in the doubly-connected edge list (to represent different cells).

EDIT: upon further reading, I discovered that the number of faces is equal to the number of nodes (not vertices) in the diagram. This has to be used in the "vertices" vector.

[Cedric]

Both methods explained above can deal with arbitrary numbers of vertices associated with each node. In MATLAB, arrays and cell arrays can be easily extended/truncated, and pre-allocated when possible (which increases dramatically the efficiency).

You should "play" for a few days full time with arrays and cell arrays, and build a small demonstrator that you can then discuss on the forum. People here can help you optimizing your code if you present code, even if they don't fully understand the algorithm (most cannot take all the time that it requires for understanding the algorithm though, which explains why you had almost no answer). Once you have a small demonstrator which is roughly OK, you can profile it using MATLAB profiler, and understand where it spends most of its runtime.