Constructing a Doubly-Linked Edge List

8 次查看（过去 30 天）

Ian Wood 2013-8-19

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/85114-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

13 个评论
显示 11更早的评论隐藏 11更早的评论

Cedric 2013-8-29

编辑：Cedric 2013-8-29

在 MATLAB Online 中打开

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 2013-8-29

编辑：Ian Wood 2013-8-31

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 2013-9-3

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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（0 个）

请先登录，再回答此问题。

类别

MATLAB Mathematics Computational Geometry Voronoi Diagram

在 Help Center 和 File Exchange 中查找有关 Voronoi Diagram 的更多信息

产品

MATLAB

Community Treasure Hunt

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

Start Hunting!

Translated by

Constructing a Doubly-Linked Edge List

13 个评论
显示 11更早的评论隐藏 11更早的评论

回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

Constructing a Doubly-Linked Edge List

13 个评论 显示 11更早的评论隐藏 11更早的评论

回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

13 个评论
显示 11更早的评论隐藏 11更早的评论