Java Program to Implement Bowyer-Watson Algorithm

// Java Program to Implement Bowyer-Watson Algorithm
import java.util.*;

// Class representing a point in 2D space
class Point {
    double x, y;

    // Constructor to initialize a point
      // with given coordinates
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    // Method to return string representation of the point
    @Override
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

// Class representing a triangle defined by three points
class Triangle {
    Point[] vertices = new Point[3];

    // Constructor to initialize a triangle with given vertices
    public Triangle(Point p1, Point p2, Point p3) {
        vertices[0] = p1;
        vertices[1] = p2;
        vertices[2] = p3;
    }

    // Method to return string representation of the triangle
    @Override
    public String toString() {
        return "Triangle: " + vertices[0] + ", " + vertices[1] + ", " + vertices[2];
    }
}

public class BowyerWatson {

    // Method to perform the Bowyer-Watson
      // triangulation algorithm
    public static List<Triangle> triangulate(List<Point> points) {
        List<Triangle> triangulation = new ArrayList<>();

        // Create a super triangle that bounds all the points
        double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
        double maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
        for (Point p : points) {
            minX = Math.min(minX, p.x);
            minY = Math.min(minY, p.y);
            maxX = Math.max(maxX, p.x);
            maxY = Math.max(maxY, p.y);
        }

        Point superPoint1 = new Point(minX - 1, minY - 1);
        Point superPoint2 = new Point(maxX + 1, minY - 1);
        Point superPoint3 = new Point((minX + maxX) / 2, maxY + 1);
        Triangle superTriangle = new Triangle(superPoint1, superPoint2, superPoint3);
        triangulation.add(superTriangle);

        // Print the input points
        System.out.println("Input Points:");
        for (Point p : points) {
            System.out.println(p);
        }
        System.out.println();

        // Print the super triangle
        System.out.println(superTriangle);

        return triangulation;
    }

    // Main method to demonstrate the Bowyer-Watson
      // triangulation algorithm
    public static void main(String[] args) {
        // Create a list of points
        List<Point> points = new ArrayList<>();
        points.add(new Point(10, 10));
        points.add(new Point(20, 20));
        points.add(new Point(30, 10));
        points.add(new Point(15, 25));

        // Perform triangulation and store the result
        List<Triangle> triangulation = triangulate(points);
    }
}