Constructing a Doubly-Linked Edge List
3 ビュー (過去 30 日間)
古いコメントを表示
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 件のコメント
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 件)
参考
カテゴリ
Help Center および File Exchange で Voronoi Diagram についてさらに検索
製品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!