Алгоритм начинается с пути, который вы нашли ранее, в данном случае это список треугольников:
Код в нижней части поста Микко в блоге создает массив порталов, представляющий собой список отрезков, представляющих отрезки между полигонами пути. Это «порталы», через которые должен пройти сглаженный путь (или ребра полигона из «давайте проследим середины ребра полигона»). Обратите внимание, что список порталов начинается и заканчивается вырожденными отрезками в начальной и конечной точках.
Этот список порталов показан в виде желтых пунктирных линий на его рисунках.
Алгоритм начинается с широкой воронки и продолжается итерационным перемещением сторон воронки вперед вдоль боковых точек портала (конечных точек отрезков линии), пока это затягивает воронку (AD).
Это означает, что каждое движение вперед должно перемещать края воронки внутрь, это можно проверить с помощью перекрестного произведения векторов, представляющих старую сторону и потенциальную новую сторону ( P × Q на рисунке ниже; также см. triarea2В коде Микко). Если движение вперед на сторону не затянет воронку, мы не обновляем эту сторону для текущей итерации порталов (E).
Другой случай, который необходимо обработать, - это когда воронка вырождается в отрезок. Чтобы учесть это, алгоритм проверяет, находится ли одна из сторон на «неправильной» стороне, снова используя перекрестное произведение, на этот раз векторов, сделанных вершиной воронки и правой и левой боковыми конечными точками соответственно ( R × S в изображение ниже).
В этом случае вектор из вершины воронки и правильной боковой конечной точки добавляется к сглаженному пути ( R на рисунке выше), и алгоритм перезапускается с конечной точкой в качестве новой вершины (FG), если только, конечно, если это цель цели.
