Наивный подход состоит в том, чтобы найти для каждого ребра многоугольника точку на этом ребре, ближайшую к данной точке, а затем выбрать ближайшую. Есть ли более быстрый алгоритм? Моя цель — реализовать 2D-платформер в стиле Super Mario Galaxy.
Судя по всему, это можно сделать с регионами Вороного, как на этом видео: http://www.youtube.com/watch?v=Ldh2YKobuWo
Однако я не могу найти ни одного алгоритма Вороного, который бы работал не только с точками, но и с ребрами. Идеи?
Если многоугольник выпуклый, то накладные расходы вычисления Вороного намного превышают наивные подходы.
Если это выполняется много раз, и каждый раз, когда точка немного меняется, вам нужно проверить только 3 сегмента (подумайте об этом: когда вы перемещаетесь, предполагая много проверок, ближайшее ребро будет меняться только на соседнее ребро)
Вычислите расстояние между точкой и линией для каждого ребра, затем выберите кратчайшее. . Нет ярлыка. На этом сайте есть хорошее объяснение и даже реализации на разных языках.
Однако нахождение «точки на этом ребре, ближайшей к данной точке», является ненужным с точки зрения вычислений промежуточным результатом.
