I am working on a school project where we are implementing Bowyer Watson triangulation algorithm. The code when triangulating creates all the correct triangles needed for the triangulation and removes the super triangle correctly. But when removing the bad triangles, it removes too many of the triangles, not removing any bad triangles and second when removing all. A 'bad triangle' is defined as a triangle who's CircumCentre contains the current point. My thought is that the fault is when checking if the point is in the CircumCentre, either the calculation or the way of doing it. But I could be wrong, and I have been struggling with this for a while so If someone knows how to solve this I would be very grateful.
The code is inspired by Scotty Anderson : https://github.com/ScottyRAnderson/Delaunay-Triangulation
Pictures of the execution and calculation of circumcentre: Not removing any bad triangles Removing all bad triangles Calculating circumcentre`
public class Triangulation {
private List<Point> points;
private List<Triangle> triangles;
private Point superPoint1, superPoint2, superPoint3;
public Triangulation(List<Point> points) {
this.points = points;
this.triangles = new ArrayList<>();
}
public List<Triangle> getTriangulation() {
triangles.add(createSuperTriangle());
List<Triangle> badTriangles = new ArrayList<>();
for (int pIndex = 0; pIndex < points.size(); pIndex++) {
badTriangles.clear();
Point point = points.get(pIndex);
//Identify 'bad triangles'
for (int triIndex = triangles.size() - 1; triIndex >= 0; triIndex--) {
Triangle triangle = triangles.get(triIndex);
double xDelta = point.x - triangle.circumCentre().x;
double yDelta = point.y - triangle.circumCentre().y;
double distance = Math.hypot(yDelta, xDelta);
// A 'bad triangle' is defined as a triangle who's
// CircumCentre contains the current point
if (distance < triangle.circumRadius()) {
badTriangles.add(triangle);
}
}
List<Edge> polygon = new ArrayList<Edge>();
// Contruct a polygon from unique edges,
// i.e. ignoring duplicate edges inclusively
for (int i = 0; i < badTriangles.size(); i++) {
Triangle triangle = badTriangles.get(i);
List<Edge> edges = new ArrayList<>();
edges = triangle.getEdges();
for (int j = 0; j < edges.size(); j++) {
boolean badEdge = false;
for (int t = 0; t < badTriangles.size(); t++) {
if (t != i && badTriangles.get(t).
ContainsEdge(edges.get(j))) {
badEdge = true;
}
}
if (!badEdge) {
polygon.add(edges.get(j));
}
}
}
//Remove bad triangles from the triangulation
for (int i = badTriangles.size() - 1; i >= 0; i--) {
triangles.remove(badTriangles.get(i));
}
//Create new triangles
for (int polygonIndex = 0; polygonIndex < polygon.size(); polygonIndex++) {
Edge edge1 = polygon.get(polygonIndex);
Point pointA = new Point(point.x, point.y);
Point pointB = new Point(edge1.p1);
Point pointC = new Point(edge1.p2);
triangles.add(new Triangle(pointA, pointB, pointC));
}
}
// if corner connected to superTriangle -> remove
triangles.removeIf(triangle -> triangleContainsPoint(triangle, superPoint1)
|| triangleContainsPoint(triangle, superPoint2)
|| triangleContainsPoint(triangle, superPoint3));
return triangles;
}
public Triangle createSuperTriangle() {
double minX = Double.POSITIVE_INFINITY;
double minY = Double.POSITIVE_INFINITY;
double maxX = Double.NEGATIVE_INFINITY;
double maxY = Double.NEGATIVE_INFINITY;
for (Point point : points) {
minX = Math.min(minX, point.x);
minY = Math.min(minY, point.y);
maxX = Math.max(maxX, point.x);
maxY = Math.max(maxY, point.y);
}
double deltaX = maxX - minX;
double deltaY = maxY - minY;
double deltaMax = Math.max(deltaX, deltaY);
superPoint1 = new Point(minX - deltaMax, minY - 2 * deltaMax);
superPoint2 = new Point(minX + 3 * deltaMax, minY - deltaMax);
superPoint3 = new Point(minX + deltaMax, minY + 3 * deltaMax);
return new Triangle(superPoint1, superPoint2, superPoint3);
}
private boolean triangleContainsPoint(Triangle triangle, Point point) {
double d1 = sign(point, triangle.p1, triangle.p2);
double d2 = sign(point, triangle.p2, triangle.p3);
double d3 = sign(point, triangle.p3, triangle.p1);
boolean hasNeg = (d1 < 0) || (d2 < 0) || (d3 < 0);
boolean hasPos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(hasNeg && hasPos);
}
private double sign(Point p1, Point p2, Point p3) {
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
}
public class Triangle {
public Point p1, p2, p3;
private List<Point> points = new ArrayList<Point>();
public Triangle(Point p1, Point p2, Point p3) {
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
points.add(p1);
points.add(p2);
points.add(p3);
}
public boolean ContainsEdge1(Edge edge) {
int sharedVerts = 0;
for (int i = 0; i < points.size(); i++) {
if (points.get(i).equals(edge.p1) || points.get(i).equals(edge.p2)) {
sharedVerts++;
}
}
return sharedVerts == 2;
}
public boolean ContainsEdge(Edge edge) {
return points.contains(edge.p1) && points.contains(edge.p2);
}
public List<Edge> getEdges() {
List<Edge> edges = new ArrayList<Edge>();
for (int i = 0; i < points.size() - 1; i++) {
edges.add(new Edge(points.get(i), points.get(i + 1)));
}
return edges;
}
public List<Point> getPoints() {
return points;
}
public double circumRadius() {
Point circumCentre = circumCentre();
double xDelta = p1.x - circumCentre.x;
double yDelta = p1.y - circumCentre.y;
double distance = Math.hypot(xDelta, yDelta);
return distance;
}
public Point circumCentre() {
double ax = p1.x;
double ay = p1.y;
double bx = p2.x;
double by = p2.y;
double cx = p3.x;
double cy = p3.y;
double d = (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) * 2;
double centerX = (((Math.pow(ax, 2) + Math.pow(ay, 2)) * (by - cy))
+ ((Math.pow(bx, 2) + Math.pow(by, 2)) * (cy - ay))
+ (Math.pow(cx, 2) + Math.pow(cy, 2)) * (ay - by)) / d;
double centerY = (((Math.pow(ax, 2) + Math.pow(ay, 2)) * (cx - bx))
+ ((Math.pow(bx, 2) + Math.pow(by, 2)) * (ax - cx))
+ (Math.pow(cx, 2) + Math.pow(cy, 2)) * (bx - ax)) / d;
return new Point(centerX, centerY);
}
}