# Issues with Delaunay triangulation (Bowyer-Watson)

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

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

// 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)
{
}

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

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

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!

2 Likes

I am unfamiliar with that algorithm, and I have also been unable to reproduce the problem you mentioned, but I can only imagine one thing: It must be that at some point, you divide between the distance between a point and the outer edge. If that distance is very small (and we’re talking 0.000000001 and smaller), there might be some problems with precision. But I can’t really imagine that since the distance is usually at least 1. It would be helpful if you could send a screenshot of that issue.

Also, do you know if it is a problem with the mechanics of the algorithm or just the rendering?

Hi, sorry for not answering earlier!
The main issue is that the algorithm, when working properly, is supposed to form what is called a “convex hull”, which is to say, the smallest perimeter possible around the shape.
While this holds true in most cases, it doesn’t when a vertex is too close to an outer edge, like so
(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

As you said, it may be a form of rounding error, but I don’t see where in a code that could happen, as the visual distance seems way to big to be from a float rounding error

Ah OK, now I know what you mean. So part of the algorithm is sorting the points from left to right, isn’t it? Maybe something’s wrong with that sorting algorithm, and it thinks the vertex in the middle is further to the right than the two at the top and bottom? Though that wouldn’t make much sense either. Just like float rounding error, seems very unlikely.
I still don’t really get the algorithm, but maybe something’s wrong with the `trigangle.radius`?