How to reduce an abstract 2D trajectory to segments between points in a given set?

[amundsen]

Hello,

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).

Thank you in advance.

[amundsen]

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?

[amundsen]

I guess I’ll have to define my shapes as polylines from the very start. Cos and sin are my friends…

[micuat]

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.

[amundsen]

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]

My understanding of the problem is

1. there are a number of fixed points in 2D space, and
2. a 2D shape that can be calculated from a closed-form expression. The dashed lines in your picture.

Using this information calculate the polyline (solid lines in your picture)

1. whose vertices come from the set of fixed points
2. where a fixed point can only be used once for a particular polyline
3. that best fits the 2D shape
4. minimizes the length of the polyline created

Note that requirements (3) and (4) are not necessarily mutually achievable.

Am I understanding the problem correctly?

[amundsen]

@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?

[quark]

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

@amundsen

I haven’t decided what hierarchy should be established between them.

I suggest that you create a “fitness” function which accepts / calculates 3 values

1. the distance from the last point selected
2. closeness to the 2D curve
3. 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.

[micuat]

Perhaps providing a small program to describe the problem would be beneficial at this point

[amundsen]

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?

int numPoints = 20;
int numSpeakers = 100;
float closest;
int closestID, currentClosest;
IntList UsedPoints;
ArrayList<Point> MyPoints = new ArrayList();
ArrayList<Speakers> MySpeakers = new ArrayList();
float radiusX, radiusY;

void setup() {
  size(900, 900);
  background(0);
  mousePressed();
}

void draw() {
  // draw loudspeakers
  background(0);
  stroke(255);
  fill(0, 64, 255);
  strokeWeight(2);
  for (int i = 0; i < MySpeakers.size(); i++) {
    Speakers monSpeakers = MySpeakers.get(i);
    circle(monSpeakers.pos.x, monSpeakers.pos.y, 20);
  }
  // draw point at start position of figure
  stroke(255, 0, 0);
  fill(255, 0, 0);
  strokeWeight(0);
  Point startpoint = MyPoints.get(0);
  circle(startpoint.pos.x+width/2, startpoint.pos.y+height/2, 20);
  // draw required figure in red
  strokeWeight(5);
  for (int i = 0; i < MyPoints.size(); i++) {
    Point oldp = MyPoints.get(i);
    Point newp = MyPoints.get((i+1)%numPoints); // modulo function to close circle
    line(oldp.pos.x+width/2, oldp.pos.y+height/2, newp.pos.x+width/2, newp.pos.y+height/2);
  }
  // circle the speaker closest to start position
  Speakers myClosest = MySpeakers.get(UsedPoints.get(0));
  stroke(0, 255, 0);
  noFill();
  circle(myClosest.pos.x, myClosest.pos.y, 30);
  // draw actual figure in teal
  stroke(0, 255, 255);
  for (int i = 0; i < UsedPoints.size(); i++) {
    int oldp = UsedPoints.get(i);
    int newp = UsedPoints.get((i+1)%UsedPoints.size());
    Speakers oldSpeakers = MySpeakers.get(oldp);
    Speakers newSpeakers = MySpeakers.get(newp);
    line(oldSpeakers.pos.x, oldSpeakers.pos.y, newSpeakers.pos.x, newSpeakers.pos.y);
  }
}

void mousePressed() {
  // creates the required figure (circle for now)
  MyPoints = new ArrayList(); // important! Recreation of the arraylist to clean it!
  radiusX = width/8+random(width/4);
  radiusY = height/8+random(height/4);
  for (float i = 0; i < numPoints; i++) {
    Point np=new Point();
    np.pos=new PVector(sin(i/numPoints*TWO_PI)*radiusX, cos(i/numPoints*TWO_PI)*radiusY);
    MyPoints.add(np);
  }
  // positions loudspeakers randomly
  MySpeakers = new ArrayList(); // important! Recreation of the arraylist to clean it!
  for (float i = 0; i < numSpeakers; i++) {
    Speakers nSpeakers=new Speakers();
    nSpeakers.pos=new PVector(random(width), random(height));
    MySpeakers.add(nSpeakers);
  }
  // find the speakers closets to the required figure's points
  findPoints();
}

class Point {
  PVector pos;
}

class Speakers {
  PVector pos;
}

// find points closest to required points on actual Speakers's positions
void findPoints() {
  if (UsedPoints == null) UsedPoints = new IntList();
  UsedPoints.clear();
  // tests all points of the required points with all speakers
  for (int i = 0; i < numPoints; i++) {
    // ajoute le Speakers dans la liste des points utilisés
    int numpoint = closestToPoint(i);
    println(numpoint);
    UsedPoints.append(numpoint);
  }
  println(UsedPoints);
}


// identification of the speakers closest to current point
int closestToPoint(int pointNumber) {
  Point currentPoint = MyPoints.get(pointNumber);
  // teste la distance du point actuel avec tous les Speakers
  for (int i = 0; i < numSpeakers; i++) {
    Speakers currentSpeakers = MySpeakers.get(i);
    float currentDist = getDistance(currentPoint.pos.x+width/2, currentPoint.pos.y+height/2, currentSpeakers.pos.x, currentSpeakers.pos.y);
    if (i == 0) {
      closest = currentDist;
      closestID = 0;
    } else if (UsedPoints != null) {
      if (!UsedPoints.hasValue(i)) {
        if (currentDist < closest) {
          closest = currentDist;
          closestID = i;
        }
      }      
    }
  }
  // returns ID of closest speaker
  return closestID;
}

// simple distance calculation
float getDistance(float xa, float ya, float xb, float yb) {
  float dist = sqrt(pow(xa-xb, 2)+pow(ya-yb, 2));
  return dist;
}