Algorithm for moving a point around an arbitrary non self-crossing closed polygon in N time

Question

I'm looking for an algorithm that would move a point around an arbitrary closed polygon that is not self-crossing in N time. For example, move a point smoothly around a circle in 3 seconds.

Answer 1

For the record, a circle is not a polygon--it's the limit of a regular polygon as the number of sides go to infinity, but it's not a polygon. What I'm giving you isn't going to work if you don't have defined points.

Assuming you have your polygon stored in some format like a list of adjacent vertices, do a O(n) check to calculate the perimeter by iterating through them and computing the distance between each point. Divide that by the time to get the velocity that you should travel.

Now, if you want to compute the path, iterate back through your vertices again and calculate from your current position where your actual position should be on the next timestep, whatever your refresh time step may be (if you need to move down a different edge, calculate how much time it would take to get to the end of your first edge, then continue on from there..). To travel along the edge, decompose your velocity vector into its components (because you know the slope of the edge from its two endpoints).

Answer 2

A little code might answer this with fewer words (though I'm probably too late for any votes here). Below is Python code that moves a point around a polygon at constant speed.

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

Here I calculated the step size from the step_time (anticipating an graphics delay) but one could calculate the step size, from whatever was needed, for example, the desired speed.