I am looking for the right tools/algorithms to code some movements/trajectories in 2D. The idea is to have abstract movements and translate them to sequences of line segments (polylines?) linking points selected for the minimal distance between them among a given set.

In the picture below are two examples (depicted in blue and orange). The first abstract movement is a straight line (dotted blue line) which is translated to the polyline (light blue). The second is a rotation (dotted orange circle).

Iâ€™ve seen there are line simplification algorithms, used for map contours for instance. But it requires the drawing to be defined as a polyline first, which is a bit complicated for curved shapes. Any idea how to achieve this?

I would say the first step is, as you wrote, to define a polyline and then to deform it with some kind of noise. But if you want to make the movement infinite (for example, circling around), you need to adapt this to calculate the next point on the fly; otherwise it will follow the same trajectory.

Actually the movement might change slightly from lap to lap when circular and this will prevent the same trajectory to be repeated. However I cannot use noise as you suggest as the possible points will be fixed beforehand, which is also different from what is used in line simplification algorithms.

@quark Youâ€™re mostly right. Youâ€™re right with constraint #1 (vertices coming from set of fixed points). Constraint #3 is right too. Constraints #2 and #4 are not relevant. However, there is a constraint #5 : avoid jumping between points when they are too far apart from each other. But maybe it might be better to express it as â€śchoose the point closer to the model 2D shape but if the distance is beyond some distance from the current point you can go to another pointâ€ť. I understand this constraint can collide with constraint #3 and I havenâ€™t decided what hierarchy should be established between them. This will be decided later.

One additional question: can this system function if a complete trajectory is not defined beforehand but only created step by step in real-time?

I think you might want to keep constraint #2 to avoid the polyline oscillating or looping infinitely over 2 or more fixed points, also it would reduce the amount of computation needed to select the next fixed point

I suggest that you create a â€śfitnessâ€ť function which accepts / calculates 3 values

the distance from the last point selected

closeness to the 2D curve

distance along the curve for the position nearest to the fixed point

The output would be a single number that represents the fitness of a fixed point and the most fit point will be selected for the vertex.

(3) this is needed because we want to move forward along the 2D shape contour

The advantage of the fitness function is that a fixed hierarchy is no longer needed because a weighting factor can be used for each constraint. This makes the selecting algorithm much more flexible.

This is on my first attempt. It uses the closest distance as point selector only. The main weakness is that sometimes there are consecutive segments with opposite directions. Also, sometimes the shape is really distorted, looking more like a star than a circle where obviously some circle - bigger or smaller than the original probably however - would have fit. How could I encode the shape globally rather than only points? By coding it as vectors?