# 画像からドロネー図をつくる

#### 出力画像

```/**
* Image by Delaynay Triangulation
*
* @author aa_debdeb
* @date 2015/12/13
*/

Delaynay delaynay;

void setup(){
size(540, 360);
smooth();
noLoop();

image(image, 0, 0);

ArrayList<Point> points = new ArrayList<Point>();
for(int x = 0; x < width; x += 1){
for(int y = 0; y < height; y += 1){
color c = pixels[y * width + x];
float gray = 0.3 * red(c) + 0.59 * green(c) + 0.11 * blue(c);
float p = ((255.0 - gray) / 255.0) * 0.2;
if(random(1) < p){
points.add(new Point(x + map(random(1), 0, 1, -0.1, 0.1), y + map(random(1), 0, 1, -0.1, 0.1)));
}
}
}

delaynay = new Delaynay(points);

background(255);
stroke(128);
noFill();
strokeWeight(1);
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
Triangle outerTriangle = new Triangle(op1, op2, op3);

// shuffles points
ArrayList<Point> shuffledPoints = new ArrayList<Point>();
for(int i = 0; i < _points.size(); i++){
Point p = _points.get(i);
}

// inserts points sequentially
for(Point p: shuffledPoints){
}
}

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

// 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>();

// leagalizes candidate triangles
while(!leagalizedTQueue.isEmpty()){
Triangle leagalizedT = leagalizedTQueue.remove(0);
Side leagalizedS = leagalizedSQueue.remove(0);

Triangle triangle = getTriangleWith(leagalizedS);
if(triangle == null){
} else {
Point point = triangle.getPointNotOn(leagalizedS);
if(leagalizedT.circumcircle.contains(point)){
// flips ths side
triangles.remove(triangle);
} else {
}
}
}
}

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;

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