Hi, as the name says, I’m currently trying to code a simple Delaunay triangulation, using the Bowyer-Watson algorithm, I found great tutorials to help me along the way and my code is nearly working fine, except for one issue : It seems there is some sort of … margin of error in generating the outer edges, meaning that if a point is too close an outer edge, that outer edge with disappear and will only reappear once that distance is increased. Here’s the code I wrote :
ArrayList<Point> points = new ArrayList<Point>();
ArrayList<Triangle> triangles = new ArrayList<Triangle>();
int numberOfPoints = 10;
int padding = 200;
import java.util.*;
void setup()
{
size(1920, 1080);
stroke(255);
fill(255, 125, 255);
for (int i = 0; i < numberOfPoints; i++)
{
Point point = GeneratePoint(0 + padding, width - padding, 0 + padding, height - padding);
points.add(point);
}
}
Point GeneratePoint(int xMin, int xMax, int yMin, int yMax) { return new Point(random(xMin, xMax), random(yMin, yMax)); }
void draw()
{
//for (int i = 0; i < points.size(); i++)
// points.get(i).move();
background(155);
Collections.sort(points);
triangles = Triangulate(points);
for (int j = 0; j < triangles.size(); j++)
triangles.get(j).display();
}
int offset = 500;
ArrayList<Triangle> Triangulate(ArrayList<Point> vertices)
{
HashSet<Triangle> delaunay = new HashSet<Triangle>();
ArrayList<Triangle> triangles = new ArrayList<Triangle>();
// Create Super Triangle
// 1- Calculate the bounds of our rectangle
float xMin = width, xMax = 0, yMin = height, yMax = 0;
for (int i = 0; i < vertices.size(); i++)
{
xMin = min(xMin, vertices.get(i).x);
xMax = max(xMax, vertices.get(i).x);
yMin = min(yMin, vertices.get(i).y);
yMax = max(yMax, vertices.get(i).y);
}
float rectWidth = xMax - xMin + 1;
float rectHeight = yMax - yMin + 1;
// To create a triangle that contains our bounding rectangle, we can simply double the size of the right triangle which hypotenuse links the (xMax, yMax) point to
// the that is midway across (xMin, yMin) and (xMax, yMin)
// As this triangle perfectly contains the bounding rectangle, there's a chance a point lying in a corner of the rectangle also lies on the edge of this triangle,
// If this is the case, the 3 points become colinear, which makes the algorithm fail. We fix that by simply adding a small offset to every point so that it's a big bigger
float topX = xMin + (rectWidth / 2); // Calculate the midway point
float topY = yMin - rectHeight - offset;
float rightX = xMax + (rectWidth/2) + offset;
float leftX = xMin - (rectWidth/2) - offset;
float yMaxOffset = yMax + offset;
Point topVertex = new Point(topX, topY);
Point leftVertex = new Point(leftX, yMaxOffset);
Point rightVertex = new Point(rightX, yMaxOffset);
Triangle startingTriangle = new Triangle(new Point[] { topVertex, leftVertex, rightVertex });
triangles.add(startingTriangle);
// 2- Iterate through every point
for (int i = 0; i < vertices.size(); i++)
{
Point point = vertices.get(i);
ArrayList<Edge> edgesBuffer = new ArrayList<Edge>();
for (int j = triangles.size()-1; j >= 0; j--)
{
Triangle triangle = triangles.get(j);
if (delaunay.contains(triangle)) continue;
// As our points are sorted by their x coordinates (left to right), if the x coordinate of a point is to the right of
else if (point.x > triangle.circumcenter.x + triangle.radius)
{
delaunay.add(triangle);
}
// If our triangle doesn't contain the point but our point isn't right of our circumcircle, there's a possibility that another point lies
// inside of this triangle's circumcircle, therefore its state is considered "unsure"
else if (triangle.isPointInRadius(point)) // If the point lies within the circle then we know this is an invalid triangle
{
// If the point is within the circumcircle of this triangle, get the edges of the triangle and add them
edgesBuffer.add(new Edge(triangle.vertices[0], triangle.vertices[1]));
edgesBuffer.add(new Edge(triangle.vertices[1], triangle.vertices[2]));
edgesBuffer.add(new Edge(triangle.vertices[2], triangle.vertices[0]));
// Then remove this triangle from the triangle list
triangles.remove(j);
}
}
int eL_ = edgesBuffer.size() - 1;
int eL = edgesBuffer.size();
Edge e1 = new Edge();
Edge e2 = new Edge();
for (int j = 0; j < eL_; e1 = edgesBuffer.get(j++))
for (int k = j + 1; k < eL; e2 = edgesBuffer.get(k++))
if (e1.a == e2.b && e1.b == e2.a) e1.a = e1.b = e2.a = e2.b = null;
for (int j = 0; j < edgesBuffer.size(); j++)
{
if (edgesBuffer.get(j).a == null || edgesBuffer.get(j).b == null) continue;
triangles.add(new Triangle(new Point[] { edgesBuffer.get(j).a, edgesBuffer.get(j).b, point } ));
}
}
for (int i = triangles.size() - 1; i >= 0; i--)
if (sharedVertex(triangles.get(i), startingTriangle)) triangles.remove(i);
return triangles;
}
public boolean sharedVertex(Triangle t1, Triangle t2)
{
return t1.vertices[0] == t2.vertices[0] || t1.vertices[0] == t2.vertices[1] || t1.vertices[0] == t2.vertices[2] ||
t1.vertices[1] == t2.vertices[0] || t1.vertices[1] == t2.vertices[1] || t1.vertices[1] == t2.vertices[2] ||
t1.vertices[2] == t2.vertices[0] || t1.vertices[2] == t2.vertices[1] || t1.vertices[2] == t2.vertices[2];
}
class Point implements Comparable<Point>
{
public float x, y;
public float xSpeed, ySpeed;
public Point(float x, float y)
{
this.x = x;
this.y = y;
this.xSpeed = random(-2, 2);
this.ySpeed = random(-2, 2);
}
public void move()
{
x += xSpeed;
y += ySpeed;
if (x < 0 || x >= width)
xSpeed = -xSpeed;
if (y < 0 || y >= height)
ySpeed = -ySpeed;
}
@Override
public int compareTo(Point point) { return this.x < point.x ? -1 : this.x == point.x ? 0 : 1; }
public boolean compare(Point point) { return (this.x == point.x) && (this.y == point.y); }
}
class Edge
{
Point a, b;
public Edge()
{
}
public Edge(Point a, Point b)
{
this.a = a;
this.b = b;
}
public boolean compareTo(Edge edge) { return (this.a.compare(edge.a) && this.b.compare(edge.b)) || (this.a.compare(edge.b) && this.b.compare(edge.a)); }
}
class Triangle
{
Point[] vertices;
Point circumcenter;
float radiusSquared;
float radius;
float aux1;
float aux2;
float div;
public Triangle(Point[] vertices)
{
this.vertices = vertices;
calculateCircumcircle();
}
public void display()
{
triangle(vertices[0].x, vertices[0].y, vertices[1].x, vertices[1].y, vertices[2].x, vertices[2].y);
}
public void calculateCircumcircle()
{
Point p0 = vertices[0];
Point p1 = vertices[1];
Point p2 = vertices[2];
float dA = p0.x * p0.x + p0.y * p0.y;
float dB = p1.x * p1.x + p1.y * p1.y;
float dC = p2.x * p2.x + p2.y * p2.y;
aux1 = (dA * (p2.y - p1.y) + dB * (p0.y - p2.y) + dC * (p1.y - p0.y));
aux2 = -(dA * (p2.x - p1.x) + dB * (p0.x - p2.x) + dC * (p1.x - p0.x));
div = (2 * (p0.x * (p2.y - p1.y) + p1.x * (p0.y - p2.y) + p2.x * (p1.y - p0.y)));
if (div == 0)
return;
Point center = new Point(aux1 / div, aux2 / div);
circumcenter = center;
radiusSquared = (center.x - p0.x) * (center.x - p0.x) + (center.y - p0.y) * (center.y - p0.y);
radius = sqrt(radiusSquared);
}
public boolean isPointInRadius(Point point)
{
float px = point.x - circumcenter.x;
float py = point.y - circumcenter.y;
float dist = px * px + py * py;
return dist < radiusSquared;
}
}
As for how it works :
1- Generate a random set of points within the canvas and sort them left to right (x coordinate)
2- Generate a triangle that encompasses all of these points
3- For each point, draw the circumcircle of each triangle and check whether the point is inside the circle
4- If the point is right of the circle, then it is a Delaunay triangle and added to the delaunay list, if it’s not inside the circle, it may be a Delaunay triangle but we’re not sure, so do nothing, if the point is inside, the point is invalid and the triangle removed from the triangle list, its edges are added to the edgesBuffer list
5- Remove any duplicate edge from the edgesBuffer list
6- Once we went through every point, fuse the delaunay and triangle lists, then remove from this list every triangle that shares at least a vertex with the initial triangle (as it is not part of the initial set of points given)
7- Return the triangle list
Thanks a lot for your help!
(not working properly, the circled top and bottom vertices should be linked by an edge, as it is the shortest path without crossing any other edge