ドロネー三角形分割(コード改良版)

前に書いたドロネー三角形分割のコードを改良した．マウスをクリックすると新しい点を追加することができる．

ドロネー三角形分割 - 30 min. Processing

/**
* Delaynay Triangulation
*
* @author aa_debdeb
* @date 2015/12/12
*/


Delaynay delaynay;

void setup(){
  size(500, 500);
  smooth();
  
  ArrayList<Point> points = new ArrayList<Point>();
  for(int i = 0; i < 500; i++){
    points.add(new Point(random(width), random(height)));
  }
  
  delaynay = new Delaynay(points);
  
  background(255);
  stroke(128);
  noFill();
  strokeWeight(1);
  delaynay.display();
  
}

void draw(){

}

void mousePressed(){
  Point point = new Point(mouseX, mouseY); 
  delaynay.add(point);
  
  background(255);
  delaynay.display();
}

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;
  }
  
}