Алгоритм перемещения точки вокруг произвольного несамопересекающегося замкнутого многоугольника за N раз

Question

Я ищу алгоритм, который бы перемещал точку вокруг произвольного замкнутого многоугольника, который не является самопересекающимся в N раз. Например, плавно переместите точку вокруг круга за 3 секунды.

Answer 1

1) Calculate the polygon's perimeter  (or estimate it if exact time of circling 
is not critical)
2) divide the perimieter by the time desired for circling
3) move point around polygon at this speed.

Редактировать после комментариев гнева и проклятия.

Возможно, я читаю вопрос слишком буквально, я не вижу сложности или вопросов, поднятых ire_and_curses.

Следующее описывает более конкретно логику, которую я представляю для шага № 3. Более точное описание потребовало бы знания деталей о системе координат, структуре, используемой для описания многоугольника, и указания относительно желаемой / разрешенной частоты обновления анимации.

«Точка перемещения», которая проходит вокруг многоугольника, будет начинаться с на на любом ребре полигопа (возможно, на вершине, чтобы сделать начальную и конечную точку более очевидной) и останется на край все время .

С этой начальной точки, будь то предопределенной или выбранной случайным образом), точка перемещения будет двигаться в направлении вершины с вычисленной скоростью. Оказавшись там, он должен был идти к другой вершине ребра, к которому он только что прибыл, и продолжаться, пока не вернется к начальной точке.

Уравнения для вычисления точек на заданном ребре те же, что и для трассировки многоугольника: простой триг или даже Пифагор (*) . Визуальный эффект основан на обновлении положения точки движения, по крайней мере, 15 раз в секунду. Частота обновления (или, скорее, ее период) может использоваться для определения расстояния двух последовательных точек анимации.

Единственная менее тривиальная задача - обнаружить конец заданного ребра, т. Е. Когда точка перемещения должна «повернуться», чтобы следовать за следующим ребром. В этих случаях необходимо вычислить дробное расстояние перемещения, чтобы следующая точка в анимации находилась на следующем ребре. Особо отметим также для очень коротких ребер, так как они могут потребовать повторения логики дробного расстояния (или сделать иначе).

Извините за столь подробное объяснение довольно прямолинейного буквально ;-) алгоритма ...

Исправление : как отметил Джефроми в комментарии для другого ответа, все, что необходимо в отношении трассировки, - это просто разложить компоненты x и y движения. Хотя нам нужен Пифагор для вычисления расстояния между каждой вершиной для расчета периметра, и нам нужно экстраполировать, потому что число шагов анимации на ребре не [обязательно] является целым числом.

Answer 2

Для справки, круг не является многоугольником - это предел правильного многоугольника, так как количество сторон стремится к бесконечности, но это не многоугольник. То, что я вам даю, не сработает, если у вас нет определенных баллов.

Предполагая, что полигон хранится в каком-либо формате, например, в списке смежных вершин, выполните проверку O (n), чтобы вычислить периметр, просматривая их и вычисляя расстояние между каждой точкой. Разделите это на время, чтобы получить скорость, с которой вы должны путешествовать.

Теперь, если вы хотите вычислить путь, повторите итерацию ваших вершин снова и вычислите из вашей текущей позиции, где ваша фактическая позиция должна быть на следующем временном шаге, каким бы ни был ваш шаг времени обновления (если вам нужно перейти другой край, посчитайте, сколько времени потребуется, чтобы добраться до конца вашего первого края, а затем продолжайте оттуда ..). Чтобы путешествовать по краю, разложите вектор скорости на его составляющие (потому что вы знаете наклон края по двум его конечным точкам).

Answer 3

Небольшой код может ответить на это с меньшим количеством слов (хотя я, вероятно, слишком поздно для любых голосов здесь). Ниже приведен код Python, который перемещает точку вокруг многоугольника с постоянной скоростью.

from turtle import *
import numpy as nx
import time

total_time = 10. # time in seconds
step_time = .02 # time for graphics to make each step

# define the polygone by the corner points
#    repeat the start point for a closed polygon
p = nx.array([[0.,0.], [0.,200.], [50.,150.], [200.,200.], [200.,0.], [0.,0.]])

perim = sum([nx.sqrt(sum((p[i]-p[i+1])**2)) for i in range(len(p)-1)])
distance_per_step = (step_time/total_time)*perim

seg_start = p[0]  # segment start point
goto(seg_start[0], seg_start[1])  # start the graphic at this point
for i in range(len(p)-1):
    seg_end = p[i+1]  # final point on the segment
    seg_len = nx.sqrt(sum((seg_start-seg_end)**2))
    n_steps_this_segment = int(seg_len/distance_per_step)
    step = (seg_end-seg_start)/n_steps_this_segment # the vector step
    #
    last_point = seg_start
    for i in range(n_steps_this_segment):
        x = last_point + step
        goto(x[0], x[1])
        last_point = x
        time.sleep(step_time)
    seg_start = seg_end

Здесь я рассчитал размер шага по времени шага (предвидя задержку графики), но можно было рассчитать размер шага, исходя из того, что было необходимо, например, желаемой скорости.