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

ドロネー三角形分割 - 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++){
}

delaynay = new Delaynay(points);

background(255);
stroke(128);
noFill();
strokeWeight(1);
delaynay.display();

}

void draw(){

}

void mousePressed(){
Point point = new Point(mouseX, mouseY);

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