Simple stupid funnel algorithm without visible points

Question

In the simple stupid funnel algorithm we are searching for consecutive portals points, that are tightening the funnel (the angle between the current left and right point decreases).

But what when there is no single visible point, that would tighten the funnel, like presented on image below. How to determinate next apex and current left and right point?

Answer 1

You first determine the left and right points of the funnel as the left and right points of the closest portal, then correct these points every time you find a point inside the funnel.

To determine the apex you also need to find a point that produces a turn. It either a left point of a portal that happens to be on the right side of the funnel or vice versa a right point of a portal that is on the left side of the funnel.

The steps below show how to determine the first apex from your example.

1. Considering that we enumerated points this way, we first set A as the tightest point from the right side and B as the tightest point from the left side.

2. We check the next portal. The left point of it (C) is on the left side of the funnel. So we ignore C.

3. We check the third portal. The right point (D) is on the right side of the funnel. Skip D as well.

4. We check the fourth portal. Its left point (E) is on the right side of the funnel. That means we have a turn to the right.

At this point, we restart the algorithm from the tightest right point of the funnel (A) and also add A to our smoothed path.

This answer provides a step-by-step demonstration that covers the general solution in more detail.