1
\$\begingroup\$

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?

enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ Ok, my guess is next apex should be the middle of first portal, and left and right points stays the same \$\endgroup\$ – eMka Feb 15 '20 at 15:34
2
\$\begingroup\$

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.

Step one

  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.

Step two

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

Step three

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

Step four

  1. 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.

enter image description here

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.