How does the Simple Stupid Funnel Algorithm work?

Question

Working with the funneling algorithm shown on Digesting Duck I'm not sure how the detection of the funnel works.

Can someone explain the method clearly to me or suggest an alternative way of detecting the funnel and if the funnels sides overlap?

Answer 1

The algorithm start with a path you found earlier, in this case a list of triangles:

path

The code at the bottom of Mikko's blog post constructs the portals array, which is a list of line segments representing the line segments between the path's polygons. These are the "portals" the smoothed path has to go through (or the polygon edges from "let's trace the polygon edge midpoints"). Note that the portals list starts and ends with degenerate line segments at the start and goal points.

This portals list is shown as the yellow dotted line segments in his pictures.

portals

The algorithm starts with a wide funnel and proceeds by iteratively moving the funnel sides forward along the portal side points (the end points of the line segments) as long as this tightens the funnel (A-D).

algorithm

This means each move forward should move the funnel edges inward, this can be checked with the cross product of the vectors representing the old side and the potential new side (P ×ばつ Q in the image below; also see triarea2 in Mikko's code). If a move forward for a side would not tighten the funnel, we don't update that side for the current iteration of the portals (E).

moving inward

The other case that needs to be handled is when the funnel degenerates to a line segment. To account for this the algorithm checks if one of the sides is on the "wrong" side by using the cross product again, this time of the vectors made by the funnel apex and the right and left side end points respectively (R ×ばつ S in the image below).

degenerate funnel

If this is the case, the vector from the funnel apex and the correct side end point is added to the smoothed path (R in the image above) and the algorithm is restarted with its end point as the new apex (F-G), unless, of course, if it is the goal point.

• Eric: @Rolfcore Is the answer clear? If not, which parts need improvement?
• CoffeDeveloper: I think he just forgot to accept the answer, this one is very good and should be serially upvoted ^^.
• CoffeDeveloper: Maybe, tonly gotcha, is that in move F you do not tell that we don't start again from scratch because there exists the chance a tight corner pointing south would make possible a tightest funnel, so we have to wait bot sides actually fail the test and not just only one. So we do that in G instead of F.. good explaination anyway :)