polyline_reduce_test.pde

polyline.pde

//
// polyline.pde
//
// Copyright (c) 2018 yoggy <yoggy0@gmail.com>
// Released under the MIT license
// http://opensource.org/licenses/mit-license.php;
//
import java.util.*;

class Polyline {  
  Vector<PVector> v = new Vector<PVector>();

  public color line_color = #00ff00;
  public color point_color = #ff0000;

  public int rmse_sampling_point_num = 50;

  float cached_total_length;
  float [] cached_l = null;
  float [] cached_l_total = null;
  float [] cached_t = null;
  float [] cached_t_total = null;

  public Polyline dup() {
    Polyline obj = new Polyline();
    obj.fromString(polyline.toString());
    return obj;
  }

  public void clear() {
    v.clear();
  }

  public void add(PVector p) {
    v.add(p);
    update_cache();
  }

  public void remove_idx(int idx) {
    if (idx < 0 || v.size() <= idx) return;
    v.remove(idx);
    update_cache();
  }

  public float length() {
    return cached_total_length;
  }

  void update_cache() {
    cached_l = null;
    cached_l_total = null;
    cached_t = null;
    cached_t_total = null;

    if (v.size() < 2) {
      cached_total_length = 0.0f;
      return;
    }

    cached_l = new float[v.size() - 1];
    cached_l_total = new float[v.size() - 1];
    cached_t = new float[v.size() - 1];
    cached_t_total = new float[v.size() - 1];

    float total = 0.0f;

    for (int i = 0; i < v.size() -1; ++i) {
      PVector p0 = v.get(i);      
      PVector p1 = v.get(i+1);
      float l = p0.dist(p1); 
      cached_l[i] = l;
      total += l;
      cached_l_total[i] = total;
    }

    cached_total_length = total;

    for (int i = 0; i < v.size() -1; ++i) {
      cached_t[i] = cached_l[i] / cached_total_length;
      cached_t_total[i] = cached_l_total[i] / cached_total_length;
    }
  }

  public PVector lerp(PVector p0, PVector p1, float t) {
    if (t < 0.0f || 1.0f < t) return null;

    PVector diff = new PVector(p1.x - p0.x, p1.y - p0.y);  
    PVector p = new PVector(p0.x + diff.x * t, p0.y + diff.y * t);
    return p;
  }

  public PVector lerp(float t) {
    if (t < 0.0f || 1.0f < t) return null;

    int idx = 0;
    for (int i = 0; i < v.size() -1; ++i) {
      if (t <= cached_t_total[i]) {
        idx = i;
        break;
      }
    }

    float st = 0.0f;
    if (idx >= 1) {
      st = cached_t_total[idx - 1];
    }

    PVector p0 = v.get(idx);
    PVector p1 = v.get(idx + 1);
    float tt = (t - st) / cached_t[idx];

    return lerp(p0, p1, tt);
  }

  public double rmse(Polyline p) {
    double rmse = 0.0;

    for (int i = 0; i < rmse_sampling_point_num; ++i) {
      float t = i / (float)rmse_sampling_point_num;

      PVector p0 = lerp(t);
      PVector p1 = p.lerp(t);

      float d = pow(p0.dist(p1), 2);
      rmse += d;
    }    

    return rmse;
  }

  public float calc_area(PVector p0, PVector p1, PVector p2) {
    PVector v0 = new PVector(p1.x - p0.x, p1.y - p0.y);
    PVector v1 = new PVector(p2.x - p0.x, p2.y - p0.y);

    println("v0=" + v0 + ", v1=" + v1);

    float magsq0 = v0.mag() * v0.mag();
    float magsq1 = v1.mag() * v1.mag();
    float dot = v0.dot(v1);
    float area = 0.5f * sqrt(magsq0 * magsq1 - dot * dot);
    return area;
  }

  public int get_minimum_area_idx(Polyline org) {
    // see also... https://bost.ocks.org/mike/simplify/    
    double min_area = Double.MAX_VALUE;
    int min_area_idx = -1;

    for (int i = 0; i < v.size()-2; ++i) {
      PVector p0 = v.get(i);
      PVector p1 = v.get(i+1);
      PVector p2 = v.get(i+2);

      float area = calc_area(p0, p1, p2);
      println("idx=" + (i+1) + ", area=" + area);
      if (area <= min_area) {
        min_area = area;
        min_area_idx = i + 1;
      }
    }

    return min_area_idx;
  }

  public void reduce(int total_point_num) {
    println("total_point_num=" + total_point_num);
    if (total_point_num < 2 || v.size() <= total_point_num) return;

    int reduce_count = v.size() - total_point_num;

    println("reduce_count=" + reduce_count);

    Vector idxs = new Vector();
    for (int i = 0; i < reduce_count; ++i) {
      Polyline p = this.dup();
      Polyline pre = this.dup();

      for (int j = 0; j < idxs.size(); ++j) {
        int idx = (int)idxs.get(j);
        p.remove_idx(idx);
      }

      int idx = -1;
      idx = p.get_minimum_area_idx(pre);
      println("remove_idx=" + idx);

      idxs.add(idx);
    }

    for (int i = 0; i < idxs.size(); ++i) {
      int idx = (int)idxs.get(i);
      this.remove_idx(idx);
    }
  }

  public void fromString(String str) {
    clear();

    JSONObject json = parseJSONObject(str);
    JSONArray array = json.getJSONArray("line");
    for (int i = 0; i < array.size(); ++i) {
      JSONObject obj = array.getJSONObject(i);
      float x = obj.getFloat("x");
      float y = obj.getFloat("y");      
      PVector p = new PVector(x, y);
      v.add(p);
    }

    update_cache();
  }

  public String toString() {
    JSONArray array = new JSONArray();

    for (int i = 0; i < v.size(); ++i) {
      PVector p = v.get(i);
      JSONObject obj = new JSONObject();
      obj.setFloat("x", p.x);
      obj.setFloat("y", p.y);
      obj.setInt("idx", i);
      array.append(obj);
    }

    JSONObject json = new JSONObject();
    json.setJSONArray("line", array);

    return json.toString();
  }

  public void draw() {
    if (v.size() < 2) return;

    strokeWeight(2);
    stroke(line_color);
    noFill();

    // line
    for (int i = 0; i < v.size() - 1; ++i) {
      PVector p0 = v.get(i);      
      PVector p1 = v.get(i+1);

      line(p0.x, p0.y, p1.x, p1.y);
    }

    // point
    noStroke();
    fill(point_color);
    for (int i = 0; i < v.size(); ++i) {
      PVector p = v.get(i);
      ellipse(p.x, p.y, 10, 10);
    }
  }
}

polyline_reduce_test.pde

//
// polyline_reduce_test.pde - see also... https://bost.ocks.org/mike/simplify/ 
//
// Copyright (c) 2018 yoggy <yoggy0@gmail.com>
// Released under the MIT license
// http://opensource.org/licenses/mit-license.php;
//
import controlP5.*;

ControlP5 cp5;

Polyline polyline;
int segment_num = 16;
int slider_value = segment_num;

void setup() {
  size(640, 640);
  cp5 = new ControlP5(this);
  cp5.addSlider("slider_value")
    .setPosition(50, height - 50)
    .setSize(width - 100, 30)
    .setRange(0, segment_num)
    ;

  generateLine();
}

void draw() {
  background(#000000);

  polyline.draw();

  Polyline tmp1 = polyline.dup();
  tmp1.reduce((int)slider_value);

  double rmse = polyline.rmse(tmp1);
  println("rmse=" + rmse);

  tmp1.line_color = #aaaaff;
  tmp1.draw();

  float t = (frameCount%100)/100.0f;
  PVector p0 = polyline.lerp(t);
  noStroke();
  fill(#ffff00);
  ellipse(p0.x, p0.y, 10, 10);

  PVector p1 = tmp1.lerp(t);
  noStroke();
  fill(#ffff00);
  ellipse(p1.x, p1.y, 10, 10);
  
  pushMatrix();
  translate(0, height / 2);
  tmp1.draw();  
  popMatrix();
}

void keyPressed() {
  if (keyCode == 0x20) {
    generateLine();
  }
}

void generateLine() {
  polyline = new Polyline();

  float step = width / (segment_num + 2);
  float h4 = height / 4;

  for (int i = 0; i < segment_num; ++i) {
    float x = step + i * step + random(-step/2, step/2);
    float y = h4  + random(-h4/2, h4/2);
    polyline.add(new PVector(x, y));
  }

  println(polyline.toString());
}