Quote: Vertices are popped from that side of the funnel until the wedge in which the current vertex lies is discovered, at which point that vertex is added to the end of the funnel deque on that side.Here's where I get confused. Do I pick the first vertex and go on to pop vertices until the wedge in which the picked vertex is found? (Also how do I find this 'wedge'?) Then go on to repeat the process with that vertex? If the apex is popped in this manner then vertex becomes the new apex. Each apex is a point in the new path?
Funnel Algorithm
September 18, 2009 05:41 AM
Hello I've been searching for any material regarding the implementation of the funnel algorithm. The best explanation I've found is
http://www.cs.ualberta.ca/~mburo/ps/thesis_demyen_2006.pdf
Page 52.
I start with my apex at the start point and a funnel structure storing the left and right vertices of the first edge in the channel(In separate arrays/vectors?). I go on to check each edge's vertices adding each vertex depending on its side.
It says:
2,389
September 18, 2009 06:39 AM
Ah, the funnel algorithm. Only have time for a quick reply at the moment, but here are some quick comments:
First of all, yes, when a new apex is found, it's added as a new point on the path.
As for storing the funnel, rather than using a separate container for each side, you'll want to use a single container - the most logical choice for this is probably a double-ended queueu (in C++, for example, you might use std::deque).
It might be helpful to draw some examples and work through the algorithm step by step in order to fully understand what's going on. Keep in mind that each funnel side should represent the shortest path from the apex to the leading (i.e. most recently added) vertex on that side (another way to think of this is that the funnel side should always be inward convex). Roughly speaking, whenever you add a new vertex, you then want to remove all vertices that cause this convexity constraint to be violated.
Ok, this was not a very good post - it's early, and I'm not entirely sure I got everything right :| I hope it'll be at least somewhat helpful though.
First of all, yes, when a new apex is found, it's added as a new point on the path.
As for storing the funnel, rather than using a separate container for each side, you'll want to use a single container - the most logical choice for this is probably a double-ended queueu (in C++, for example, you might use std::deque).
It might be helpful to draw some examples and work through the algorithm step by step in order to fully understand what's going on. Keep in mind that each funnel side should represent the shortest path from the apex to the leading (i.e. most recently added) vertex on that side (another way to think of this is that the funnel side should always be inward convex). Roughly speaking, whenever you add a new vertex, you then want to remove all vertices that cause this convexity constraint to be violated.
Ok, this was not a very good post - it's early, and I'm not entirely sure I got everything right :| I hope it'll be at least somewhat helpful though.
September 19, 2009 03:19 AM
Quite helpful although the implementation is still giving me trouble.
I'll post what I've put so far while I continue to try to figure out.
Code removed.
[Edited by - Antonym on September 20, 2009 2:19:05 AM]
I'll post what I've put so far while I continue to try to figure out.
Code removed.
[Edited by - Antonym on September 20, 2009 2:19:05 AM]
September 20, 2009 01:28 AM
Looking at the pseudocode I've come with an approximation of it but I am confused about several things. I've commented some of the lines of code.
I've tried to manage the deque with several iterators. Pushing front the left vertices and back the right ones. The apex(tracked with an iterator) is set to the first vertex added and is changed each time it's popped.
I've tried to manage the deque with several iterators. Pushing front the left vertices and back the right ones. The apex(tracked with an iterator) is set to the first vertex added and is changed each time it's popped.
enum sideType{LEFT_SIDE,RIGHT_SIDE,POINT_SIDE};struct FunnelDeque{ std::deque<b2Vec2> fdeque; std::deque<b2Vec2>::iterator apex; sideType apexType; FunnelDeque(b2Vec2 s){AddLeft(s);AddRight(s);apex = fdeque.begin();apexType = POINT_SIDE;} std::deque<b2Vec2>::iterator Left(){return fdeque.begin();} std::deque<b2Vec2>::iterator Right(){return fdeque.end() - 1;} std::deque<b2Vec2>::iterator Apex(){return apex;} sideType ApexType(){return apexType;} void AddLeft(b2Vec2 v){fdeque.push_front(v);} void AddRight(b2Vec2 v){fdeque.push_back(v);} void PopLeft(){fdeque.pop_front();} void PopRight(){fdeque.pop_back();} void PopApexLeft(){apex += 1; apexType = RIGHT_SIDE;} void PopApexRight(){apex -= 1; apexType = LEFT_SIDE;}};struct Path{ std::vector<b2Vec2> path; void Add(b2Vec2 v){path.push_back(v);}};Path ShipEnemy::Funnel(std::vector<b2Vec2> c, b2Vec2 s, b2Vec2 g){ Path p; b2Vec2 vl,vl_,vr,vr_; int NumEdges = c.size()/2; if(NumEdges < 1){ p.Add(s);p.Add(g); return p; } AddVertex(s,p);/*Do I simply add the start to the path?*/ FunnelDeque f(s); vl = c[0]; Add(f,vl,LEFT_SIDE,p); vr = c[1]; Add(f,vr,RIGHT_SIDE,p); for(int i = 2; i < NumEdges;){ vl_ = c; vr_ = c;<br> <span class="cpp-keyword">if</span>(vl == vl_){ <span class="cpp-comment">/*Won't this cause vertices to become skipped?*/</span><br> vr = vr_; Add(f,vr,RIGHT_SIDE,p);<br> }<br> <span class="cpp-keyword">else</span>{<br> vl = vl_; Add(f,vl,LEFT_SIDE,p);<br> }<br> }<br><br> Add(f,g,POINT_SIDE,p);<br><br> <span class="cpp-keyword">return</span> p;<br>}<br><span class="cpp-keyword">void</span> ShipEnemy::Add(FunnelDeque &f, b2Vec2 v, sideType t, Path &p)<br>{<br> <span class="cpp-keyword">float</span> a0,a1,a2;<br><br> <span class="cpp-keyword">if</span>(t == LEFT_SIDE){<br> <span class="cpp-keyword">while</span>(<span class="cpp-number">1</span>){<br> <span class="cpp-keyword">if</span>(f.Left() == f.Right()){<br> f.AddLeft(v);<br> <span class="cpp-keyword">break</span>;<br> }<br> <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>(f.Left() == f.Apex()){<br> a0 = Angle(*(f.Left()), *(f.Left() + <span class="cpp-number">1</span>)); <span class="cpp-comment">/*Won't this access a vertex on the other(right) side causing a problem?*/</span><br> a1 = Angle(*(f.Left()), v);<br> }<br> <span class="cpp-keyword">else</span>{<br> a0 = Angle(*(f.Left() + <span class="cpp-number">1</span>), *(f.Left()));<br> a1 = Angle(*(f.Left()), v);<br> }<br> <span class="cpp-keyword">if</span>(CounterclockwiseTo(a0,a1)){<span class="cpp-comment">/*I am not sure how to perform this test*/</span><br> f.AddLeft(v);<br> <span class="cpp-keyword">break</span>;<br> }<br> <span class="cpp-keyword">if</span>(f.Left() == f.Apex()){<br> a2 = Angle(*(f.Apex()),f.ApexType(),*(f.Apex() + <span class="cpp-number">1</span>), RIGHT_SIDE);<br> AddVertex(*(f.Apex()),p);<br> f.PopApexLeft();<br> }<br> f.PopLeft();<br> }<br> }<br><span class="cpp-comment">//Right side repeat</span><br> <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>(t == POINT_SIDE){<br> <span class="cpp-keyword">int</span> i = <span class="cpp-number">0</span>;<br> <span class="cpp-keyword">while</span>(f.Apex() + i != f.Right()){<br> i = i + <span class="cpp-number">1</span>;<br> AddVertex(*(f.Apex() + i), p);<br> }<br> }<br>}<br><br><span class="cpp-keyword">float</span> ShipEnemy::Angle(b2Vec2 v1, b2Vec2 v2)<br>{<br> b2Vec2 v = v2 - v1;<br> <span class="cpp-keyword">return</span> atan2(v.y,v.x);<br>}<br><span class="cpp-keyword">float</span> ShipEnemy::Angle(b2Vec2 v1, sideType apexT, b2Vec2 v2, sideType t)<br>{<br><span class="cpp-comment">/*…???…*/</span><br>}<br><span class="cpp-keyword">bool</span> ShipEnemy::CounterclockwiseTo(<span class="cpp-keyword">float</span> a0,<span class="cpp-keyword">float</span> a1)<br>{<br><span class="cpp-comment">/*…???…*/</span><br>}<br><span class="cpp-keyword">void</span> ShipEnemy::AddVertex(b2Vec2 v, Path &p)<br>{<br> p.Add(v);<span class="cpp-comment">//?</span><br>}<br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>Putting this half-baked attempt aside.<br><br>I think it'd be best as you mentioned to break this down into simpler steps(I seem to be getting in way over my head) and approach each one individually. I don't see how to decompose this algorithm though. What should I try doing first?<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - Antonym on September 20, 2009 9:28:04 AM]<!–EDIT–></span><!–/EDIT–>
2,389
September 20, 2009 11:11 AM
Hm, wish I could be more helpful, but to figure out what's wrong I'd really have to dig into your code (and I've got my hands full with my own code!).
Here's a suggestion though. When I was implementing this I found it helpful to draw out some example cases on paper and work through them a step at a time. Another thing you could do would be to create a test application that allows you to step through the algorithm, and that displays at each step the current state (path, apex, funnel sides, etc.). If you could step through the algorithm and see what's happening at each step, I imagine it would be a lot easier to see where things are going wrong.
[Looks like you edited your post while I was posting, but I think the suggestions I made probably still apply :)]
Here's a suggestion though. When I was implementing this I found it helpful to draw out some example cases on paper and work through them a step at a time. Another thing you could do would be to create a test application that allows you to step through the algorithm, and that displays at each step the current state (path, apex, funnel sides, etc.). If you could step through the algorithm and see what's happening at each step, I imagine it would be a lot easier to see where things are going wrong.
[Looks like you edited your post while I was posting, but I think the suggestions I made probably still apply :)]
September 21, 2009 12:46 PM
It's finally done ^_^! Gonna leave my code here in case someone else too stumbles into this nightmare. It may be a little messy cause I didn't really thought it through, may update later on with a cleaner version.
channel1 contains all vertices in the right side of the funnel and channel2 contains all on the left.
Apex will contain the completed path.
s = start, g = goal.
fright and fleft are vectors to store temporarily vertices on each side of the funnel to be processed.
[Edited by - Antonym on September 21, 2009 10:46:03 PM]
channel1 contains all vertices in the right side of the funnel and channel2 contains all on the left.
Apex will contain the completed path.
s = start, g = goal.
fright and fleft are vectors to store temporarily vertices on each side of the funnel to be processed.
Path ShipEnemy::Funnel(b2Vec2 s, b2Vec2 g){ b2Vec2 vl,vr, s1,s2; apex.push_back(s); bool update; std::vector<b2Vec2>::iterator u; for(int i = 0; i < channel1.size(); i++){ vr = channel1; update = false; if(fright.empty()){//Other side isn't empty fright.push_back(vr); update = true; } else if(vr.x != fright.back().x || vr.y != fright.back().y){//Don't add duplicates fright.push_back(vr); update = true; } u = fright.begin(); if(update && fright.size() >= 3){ while(u < fright.end() - 2){ s1 = *(u + 1) - *(u); s2 = *(u + 2) - *(u + 1); if(b2Cross(s1,s2) >= 0){//b2Cross is the perp dot product, test is s2 is clockwise with respect to s1 fright.erase(u + 1); u = fright.begin(); } else u++; } if(u == fright.begin() && fleft.size() > 1){//If we are at the current apex s1 = *(u + 1) - *(u); s2 = *(fleft.begin() + 1) - *(u); if(b2Cross(s1,s2) <= 0){//Check if first left segment(s2) is counterclockwise with respect to first right segment(s1) apex.push_back(*(fleft.begin() + 1));//Make first segment in the other side the new apex. fright.erase(u); fleft.erase(fleft.begin()); fright.insert(fright.begin(),*fleft.begin()); u = fright.begin(); } } }/*Simply reverse some of the values(fleft to fright and vice versa and the clockwise test*/ }}[Edited by - Antonym on September 21, 2009 10:46:03 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
