processing.pde

PImage imageMask;
ArrayList<ArrayList<PVector>> polygons;

final int MAX_RECURSION_DEPTH = 1000;

void setup() {
  size(512, 512);
  imageMask = loadImage("imageMask.png");

  // Create an empty array to store the polygons
  polygons = new ArrayList<ArrayList<PVector>>();

  // Iterate through each pixel in the image
  for (int y = 0; y < imageMask.height; y++) {
    for (int x = 0; x < imageMask.width; x++) {
      // If the pixel is black and hasn't been visited yet, start a new polygon and add it to the polygons array
      if (brightness(imageMask.get(x, y)) == 0 && brightness(imageMask.get(x, y)) != 255) {
        ArrayList<PVector> polygon = new ArrayList<PVector>();
        polygons.add(polygon);
        tracePolygon(polygon, x, y, 0);
      }
    }
  }

  // Smooth the polygon outlines
  smoothPolygons(polygons, 0);
}

void draw() {
  background(255);
  for (ArrayList<PVector> polygon : polygons) {
    beginShape();
    fill(random(255), 0, 0);
    for (PVector point : polygon) {
      vertex(point.x, point.y);
    }
    endShape(CLOSE);
  }
}


void tracePolygon(ArrayList<PVector> polygon, int x, int y, int recursionDepth) {
  // Add the current point to the polygon
  polygon.add(new PVector(x, y));
  // Set the current pixel to white to mark it as visited
  imageMask.set(x, y, color(255));

  // Check the pixels around the current point
  for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
      // Skip the current point and pixels outside the image
      if (dx == 0 && dy == 0 || x + dx < 0 || x + dx >= imageMask.width || y + dy < 0 || y + dy >= imageMask.height) {
        continue;
      }
      // If the pixel is black and hasn't been visited yet, recursively trace the polygon from that point
      if (brightness(imageMask.get(x + dx, y + dy)) == 0 && brightness(imageMask.get(x + dx, y + dy)) != 255) {
        // Check if the recursion depth is too large
        if (recursionDepth > MAX_RECURSION_DEPTH) {
          // If the recursion depth is too large, add a point halfway between the current point and the next point to the polygon
          PVector p1 = polygon.get(polygon.size() - 1);
          PVector p2 = new PVector(x + dx, y + dy);
          PVector p3 = p1.lerp(p2, 0.5);
          polygon.add(p3);
        } else {
          // If the recursion depth is not too large, recursively trace the polygon from the next point
          tracePolygon(polygon, x + dx, y + dy, recursionDepth + 1);
        }
      }
    }
  }
}

void smoothPolygons(ArrayList<PVector>[] polys, int depth) {
  if (depth > MAX_RECURSION_DEPTH) {
    return;
  }
  ArrayList<PVector>[] newPolys = new ArrayList[polys.length];
  for (int i = 0; i < polys.length; i++) {
    ArrayList<PVector> poly = polys[i];
    ArrayList<PVector> newPoly = new ArrayList<PVector>();
    PVector first = poly.get(0);
    PVector last = poly.get(poly.size()-1);
    PVector p = first;
    for (int j = 0; j < poly.size()-1; j++) {
      PVector q = poly.get(j+1);
      PVector mid = PVector.lerp(p, q, 0.5f);
      float d = getPerpendicularDistance(mid, poly);
      if (d > 5) {
        newPoly.add(p);
        newPoly.add(mid);
      }
      else {
        newPoly.add(p);
      }
      p = q;
    }
    if (!last.equals(first)) {
      newPoly.add(last);
    }
    newPolys[i] = newPoly;
  }
  smoothPolygons(newPolys, depth+1);
}

ArrayList<PVector> smoothPolygon(ArrayList<PVector> points, float epsilon) {
  // Check if the list of points is empty or has only one element
  if (points.size() < 2) return points;

  // Create a new list to store the simplified version of the polygon
  ArrayList<PVector> simplifiedPolygon = new ArrayList<PVector>();

  // Find the point with the maximum distance from the line formed by the first and last points
  float dmax = 0;
  int index = 0;
  for (int i = 1; i < points.size() - 1; i++) {
    PVector point = points.get(i);
    float d = getPerpendicularDistance(point, points.get(0), points.get(points.size() - 1));
    if (d > dmax) {
      index = i;
      dmax = d;
    }
  }

  // If the maximum distance is greater than the specified epsilon, recursively simplify the line formed by the first and last points
  // and the point with the maximum distance
  if (dmax > epsilon) {
    // Recursively simplify the line formed by the first and last points
    ArrayList<PVector> line1 = smoothPolygon(new ArrayList<PVector>(points.subList(0, index + 1)), epsilon);
    ArrayList<PVector> line2 = smoothPolygon(new ArrayList<PVector>(points.subList(index, points.size())), epsilon);

    // Remove the last point from the first line and the first point from the second line
    line1.remove(line1.size() - 1);
    line2.remove(0);

    // Concatenate the two lines
    simplifiedPolygon.addAll(line1);
    simplifiedPolygon.addAll(line2);
  } else {
    // If the maximum distance is less than or equal to the specified epsilon, add the first and last points to the simplified polygon
    simplifiedPolygon.add(points.get(0));
    simplifiedPolygon.add(points.get(points.size() - 1));
  }

  return simplifiedPolygon;
}

float getPerpendicularDistance(int x, int y, int x1, int y1, int x2, int y2) {
  float A = x - x1;
  float B = y - y1;
  float C = x2 - x1;
  float D = y2 - y1;

  float dot = A * C + B * D;
  float len_sq = C * C + D * D;
  float param = dot / len_sq;

  float xx, yy;

  if (param < 0 || (x1 == x2 && y1 == y2)) {
    xx = x1;
    yy = y1;
  } else if (param > 1) {
    xx = x2;
    yy = y2;
  } else {
    xx = x1 + param * C;
    yy = y1 + param * D;
  }

  float dx = x - xx;
  float dy = y - yy;
  return sqrt(dx * dx + dy * dy);
}