画像をドロネー分割して三次元のモザイクにする

/**
* 3D Color Image by Delaynay Triangulation
*
* @author aa_debdeb
* @date 2015/12/22
*/


Delaynay delaynay;

void setup(){
  size(512, 512, P3D);
  smooth();
  noLoop();
  
  PImage image = loadImage("lena.jpg");
  image(image, 0, 0);
  
  ArrayList<Point> points = new ArrayList<Point>();
  color[][] imagePixels = new color[width][height];
  loadPixels();
  for(int x = 0; x < width; x += 1){
    for(int y = 0; y < height; y += 1){
      color c = pixels[y * width + x];
      imagePixels[x][y] = c;
      float gray = 0.3 * red(c) + 0.59 * green(c) + 0.11 * blue(c);
      float p = ((255.0 - gray) / 255.0) * 0.03;
      if(random(1) < p){
        points.add(new Point(x + map(random(1), 0, 1, 0.0, 0.1), y + map(random(1), 0, 1, 0.0, 0.1)));
      }
    }
  }
  
  delaynay = new Delaynay(points);
  
  background(64);
  translate(0, 0, -150);
  lights();
  noStroke();
  for(Triangle triangle: delaynay.triangles){
    Point p1 = triangle.points[0];
    Point p2 = triangle.points[1];
    Point p3 = triangle.points[2];
    if(!delaynay.outerPoints.contains(p1) && !delaynay.outerPoints.contains(p2) && !delaynay.outerPoints.contains(p3)){
      float red = (red(imagePixels[floor(p1.x)][floor(p1.y)]) + 
                   red(imagePixels[floor(p2.x)][floor(p2.y)]) + 
                   red(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;
      float green = (green(imagePixels[floor(p1.x)][floor(p1.y)]) + 
                   green(imagePixels[floor(p2.x)][floor(p2.y)]) + 
                   green(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;
      float blue = (blue(imagePixels[floor(p1.x)][floor(p1.y)]) + 
                   blue(imagePixels[floor(p2.x)][floor(p2.y)]) + 
                   blue(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;  
      float p1z = (max(red(imagePixels[floor(p1.x)][floor(p1.y)]),
                      green(imagePixels[floor(p1.x)][floor(p1.y)]),
                      blue(imagePixels[floor(p1.x)][floor(p1.y)])) / 255) * 200;
      float p2z = (max(red(imagePixels[floor(p2.x)][floor(p2.y)]),
                      green(imagePixels[floor(p2.x)][floor(p2.y)]),
                      blue(imagePixels[floor(p2.x)][floor(p2.y)])) / 255) * 200;
      float p3z = (max(red(imagePixels[floor(p3.x)][floor(p3.y)]),
                      green(imagePixels[floor(p3.x)][floor(p3.y)]),
                      blue(imagePixels[floor(p3.x)][floor(p3.y)])) / 255) * 200;                      
      fill(red, green, blue);
      beginShape();
      vertex(p1.x, p1.y, p1z);
      vertex(p2.x, p2.y, p2z);
      vertex(p3.x, p3.y, p3z);
      endShape(CLOSE);

    }
  }  
}

class Delaynay {
  
  ArrayList<Point> points;
  ArrayList<Point> outerPoints;
  ArrayList<Triangle> triangles;
  
  Delaynay(ArrayList<Point> _points){  
    points = new ArrayList<Point>();
    outerPoints = new ArrayList<Point>();
    triangles = new ArrayList<Triangle>();
    
    // defines outer points and outer triangle
    Point op1 = new Point(width / 2 - 100000, -1000); // upper left
    Point op2 = new Point(width / 2 + 100000, -1000); // upper right
    Point op3 = new Point(width / 2, height / 2 + 100000); // lower center
    outerPoints.add(op1);
    outerPoints.add(op2);
    outerPoints.add(op3);
    points.add(op1);
    points.add(op2);
    points.add(op3);
    Triangle outerTriangle = new Triangle(op1, op2, op3);
    triangles.add(outerTriangle);
    
    // shuffles points
    ArrayList<Point> shuffledPoints = new ArrayList<Point>();
    for(int i = 0; i < _points.size(); i++){
      Point p = _points.get(i);
      shuffledPoints.add((int)random(shuffledPoints.size() + 1) ,p);
    }
    
    // inserts points sequentially
    for(Point p: shuffledPoints){
      add(p);
    }
  }
  
  void add(Point p){
    // checks whether point with same position was already provided or not
    for(Point point: points){
      if(point.x == p.x && point.y == p.y){
        return;
      }
    }
    points.add(p);
    
    // finds a triangle which contain the point
    Triangle dividedTriangle = null;
    for(Triangle triangle: triangles){
      if(triangle.contains(p)){
        dividedTriangle = triangle;
      }
    }
    
    // divides the triangles and makes new triangles
    triangles.remove(dividedTriangle);
    ArrayList<Triangle> leagalizedTQueue = new ArrayList<Triangle>();
    ArrayList<Side> leagalizedSQueue = new ArrayList<Side>();
    leagalizedTQueue.add(new Triangle(dividedTriangle.points[0], dividedTriangle.points[1], p));
    leagalizedTQueue.add(new Triangle(dividedTriangle.points[0], dividedTriangle.points[2], p));
    leagalizedTQueue.add(new Triangle(dividedTriangle.points[1], dividedTriangle.points[2], p));
    leagalizedSQueue.add(new Side(dividedTriangle.points[0], dividedTriangle.points[1]));
    leagalizedSQueue.add(new Side(dividedTriangle.points[0], dividedTriangle.points[2]));
    leagalizedSQueue.add(new Side(dividedTriangle.points[1], dividedTriangle.points[2]));
    
    // leagalizes candidate triangles
    while(!leagalizedTQueue.isEmpty()){
      Triangle leagalizedT = leagalizedTQueue.remove(0);
      Side leagalizedS = leagalizedSQueue.remove(0);
      
      Triangle triangle = getTriangleWith(leagalizedS);
      if(triangle == null){
        triangles.add(leagalizedT);
      } else {
        Point point = triangle.getPointNotOn(leagalizedS);
        if(leagalizedT.circumcircle.contains(point)){
          // flips ths side
          triangles.remove(triangle);
          leagalizedTQueue.add(new Triangle(p, point, leagalizedS.points[0]));
          leagalizedSQueue.add(new Side(point, leagalizedS.points[0]));
          leagalizedTQueue.add(new Triangle(p, point, leagalizedS.points[1]));
          leagalizedSQueue.add(new Side(point, leagalizedS.points[1]));
        } else {
          triangles.add(leagalizedT);
        }
      }
    } 
  }
  
  Triangle getTriangleWith(Side side){
    for(Triangle triangle: triangles){
      if(triangle.has(side)){
        return triangle;
      }
    }
    return null;
  }
  
  void display(){
    for(Triangle triangle: triangles){
      Point p1 = triangle.points[0];
      Point p2 = triangle.points[1];
      Point p3 = triangle.points[2];
      if(!outerPoints.contains(p1) && !outerPoints.contains(p2) && !outerPoints.contains(p3)){
       triangle.display();
      }
    }
  }
}

static class Point extends PVector {
  Point(float x, float y){
    super(x, y);
  }
}

class Side {
  Point[] points;
  Side(Point p1, Point p2){
    points = new Point[2];
    points[0] = p1;
    points[1] = p2;
  }
}

class Triangle {
  Point[] points;
  Circumcircle circumcircle;
  
  Triangle(Point p1, Point p2, Point p3){
    points = new Point[3];
    points[0] = p1;
    points[1] = p2;
    points[2] = p3;
    circumcircle = new Circumcircle(this);
  }
  
  boolean contains(Point p){
    float c1 = (points[2].x - points[1].x) * (p.y - points[1].y) - (points[2].y - points[1].y) * (p.x - points[1].x);
    float c2 = (points[0].x - points[2].x) * (p.y - points[2].y) - (points[0].y - points[2].y) * (p.x - points[2].x);
    float c3 = (points[1].x - points[0].x) * (p.y - points[0].y) - (points[1].y - points[0].y) * (p.x - points[0].x);
    return (c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0);
  }
  
  Point getPointNotOn(Side side){
    for(Point p: points){
      if(p != side.points[0] && p != side.points[1]){
        return p;
      }
    }
    return null;
  }
  
  boolean has(Side side){
    return has(side.points[0]) && has(side.points[1]);
  }
  
  boolean has(Point point){
    for(Point p: points){
      if(point == p){
        return true;
      }
    }
    return false;
  }
  
  void display(){
    triangle(points[0].x, points[0].y, points[1].x, points[1].y, points[2].x, points[2].y);
  }
}

class Circumcircle{
  PVector center;
  float radious;
  
  Circumcircle(Triangle triangle){
    Point p1 = triangle.points[0];
    Point p2 = triangle.points[1];
    Point p3 = triangle.points[2];
    float c = 2.0 * ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x));
    float x = ((p3.y - p1.y) * (sq(p2.x) - sq(p1.x) + sq(p2.y) - sq(p1.y)) +
               (p1.y - p2.y) * (sq(p3.x) - sq(p1.x) + sq(p3.y) - sq(p1.y))) / c;
    float y = ((p1.x - p3.x) * (sq(p2.x) - sq(p1.x) + sq(p2.y) - sq(p1.y)) +
               (p2.x - p1.x) * (sq(p3.x) - sq(p1.x) + sq(p3.y) - sq(p1.y))) / c;
    center = new Point(x, y);
    radious = p1.dist(center);
  }
  
  boolean contains(Point p){
    return p.dist(center) < radious;
  }
  
}