画像からドロネー図をつくる
入力画像
出力画像
入力画像を工夫しないと上手くいかない．
/** * Image by Delaynay Triangulation * * @author aa_debdeb * @date 2015/12/13 */ Delaynay delaynay; void setup(){ size(540, 360); smooth(); noLoop(); PImage image = loadImage("photo.jpg"); image(image, 0, 0); ArrayList<Point> points = new ArrayList<Point>(); loadPixels(); 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 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; } }