Учитывая многоугольник и точку в 2D, как можно найти особенность (вершину или ребро) полигона, ближайшую к точке?

Question

Наивный подход - найти для каждого ребра в многоугольнике точку на этом ребре, ближайшую к данной точке, а затем выбрать ту, которая ближе всего.Есть ли более быстрый алгоритм?Моя цель - реализовать 2D-платформер в стиле Super Mario Galaxy.

Видимо, это можно сделать в регионах Вороного, как в этом видео: http://www.youtube.com/watch?v=Ldh2YKobuWo

Однако я не могу найтилюбые алгоритмы Вороного, которые имеют дело как с ребрами, так и с точками.Идеи? * * 1006

Answer 1

Рассчитайте расстояние между точками для каждого из ребер, затем выберите самое короткое. Там нет ярлыка. Этот сайт имеет хорошее объяснение и даже реализации на разных языках.

Однако нахождение «точки на этом ребре, ближайшем к данной точке», является ненужным в вычислительном отношении промежуточным результатом.

Answer 2

Если многоугольник выпуклый, тогда накладные расходы на вычисление вороного намного превышают накладные расходы наивного подхода.

Если это выполняется много раз, и каждый раз, когда точка слегка меняется, вам нужно проверить только 3 сегмента (подумайте об этом: когда вы двигаетесь, предполагая много проверок, ближайший край изменится только насмежный край)