Java Program to Implement Bowyer-Watson Algorithm
Below is the implementation of 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);
}
}
Output:
Input Points:
(10.0, 10.0)
(20.0, 20.0)
(30.0, 10.0)
(15.0, 25.0)
Triangle: (9.0, 9.0), (31.0, 9.0), (20.0, 26.0)
Java Program to Implement Bowyer-Watson Algorithm
To gain some practical programming experience related to computational geometry topics, we will apply the Bowyer-Watson algorithm that will be able to facilitate the process to some extent.
Contact Us