java怎么写绘制三角网算法delaunay triangulation算法

Question

怎么才能用java代码实现三角网算法，通过传入的点数来绘制一个三角网

参考链接https://baike.baidu.com/item/Delaunay%E4%B8%89%E8%A7%92%E5%89%96%E5%88%86%E7%AE%97%E6%B3%95/3779918?fr=aladdin

Answer 1

三角网算法也称为三角剖分算法，它是将一个二维平面中的点集进行三角剖分，使得任意两个三角形之间都不存在交集并且包含给定的点集。我们定义了一个 DelaunayTriangulation 类，它接收一个点集作为输入，并使用 Delaunay 三角剖分算法进行三角剖分。在 triangulate() 方法中，我们调用 Delaunay 三角剖分算法的实现代码进行三角剖分。在 paintComponent() 方法中，我们遍历所有的三角形并绘制出它们的面积。在 main() 方法中，我们创建了一个包含随机点的点集，并将 DelaunayTriangulation 添加到 JFrame 中进行绘制。

import java.awt.Graphics;
import java.awt.Point;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class DelaunayTriangulation extends JPanel {

  private List<Point> points;
  private List<Triangle> triangles;

  public DelaunayTriangulation(List<Point> points) {
    this.points = points;
    this.triangles = new ArrayList<>();
    triangulate();
  }

  private void triangulate() {
    // 使用 Delaunay 三角剖分算法进行三角剖分，见下面伪代码实现

  }

  @Override
  protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    // 绘制三角网
    for (Triangle triangle : triangles) {
      Polygon polygon = new Polygon();
      polygon.addPoint(triangle.a.x, triangle.a.y);
      polygon.addPoint(triangle.b.x, triangle.b.y);
      polygon.addPoint(triangle.c.x, triangle.c.y);
      g.drawPolygon(polygon);
    }
  }

  public static void main(String[] args) {
    // 创建一个包含随机点的点集
    List<Point> points = new ArrayList<>();
    int count = 100;
    for (int i = 0; i < count; i++) {
      int x = (int) (Math.random() * 500);
      int y = (int) (Math.random() * 500);
      points.add(new Point(x, y));
    }

    // 创建一个 JFrame 并将 DelaunayTriangulation 添加到其中
    JFrame frame = new JFrame("Delaunay Triangulation");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(600, 600);
    frame.add(new DelaunayTriangulation(points));
    frame.setVisible(true);
  }

  private static class Triangle {
    private Point a;
    private Point b;
    private Point c;
    // ...
  }
}

使用java实现Delaunay三角剖分算法

import java.util.*;

public class Point {
    public double x, y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class Edge {
    public Point a, b;
    public Edge(Point a, Point b) {
        this.a = a;
        this.b = b;
    }
}

public class Triangle {
    public Point a, b, c;
    public Triangle(Point a, Point b, Point c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

public class DelaunayTriangulation {
    List<Point> points;
    List<Triangle> triangles;

    public DelaunayTriangulation(List<Point> points) {
        this.points = points;
        this.triangles = new ArrayList<Triangle>();
        Triangle superTriangle = createSuperTriangle();
        triangles.add(superTriangle);
        for (Point point : points) {
            List<Triangle> badTriangles = new ArrayList<Triangle>();
            for (Triangle triangle : triangles) {
                if (triangleCircumcircleContains(triangle, point)) {
                    badTriangles.add(triangle);
                }
            }
            Set<Edge> polygon = new HashSet<Edge>();
            for (Triangle triangle : badTriangles) {
                for (Edge edge : triangleEdges(triangle)) {
                    if (edgeSharedByTwoTriangles(edge, badTriangles)) {
                        polygon.remove(edge);
                    } else {
                        polygon.add(edge);
                    }
                }
            }
            for (Edge edge : polygon) {
                triangles.add(new Triangle(edge.a, edge.b, point));
            }
            triangles.removeIf(triangle -> triangleHasSuperTriangleVertex(triangle, superTriangle));
        }
    }

    private Triangle createSuperTriangle() {
        double minX = points.get(0).x;
        double minY = points.get(0).y;
        double maxX = minX;
        double maxY = minY;
        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 dx = Math.max(maxX - minX, maxY - minY) * 2;
        Point a = new Point(minX - dx, minY - dx);
        Point b = new Point(minX - dx, maxY + dx);
        Point c = new Point(maxX + dx, maxY + dx);
        return new Triangle(a, b, c);
    }

    private boolean triangleCircumcircleContains(Triangle triangle, Point point) {
        double ax = triangle.a.x - point.x;
        double ay = triangle.a.y - point.y;
        double bx = triangle.b.x - point.x;
        double by = triangle.b.y - point.y;
        double cx = triangle.c.x - point.x;
        double cy = triangle.c.y - point.y;
        double ab = ax * ax + ay * ay;
        double bc = bx * bx + by * by;
        double ca = cx * cx + cy * cy;
        double det = ax * by * ca + bx * cy * ab + cx * ay * bc - ax * cy * bc - bx * ay * ca - cx * by * ab;
        return det > 0;
    }

    private boolean edgeSharedByTwoTriangles(Edge edge, List<Triangle> triangles) {
        int count = 0;
        for (Triangle triangle : triangles) {
            if (triangleEdges(triangle).contains(edge)) {
                count++;
            }
        }
        return count > 1;
    }

    private boolean triangleHasSuperTriangleVertex(Triangle triangle, Triangle superTriangle) {
        return triangle.a == superTriangle.a || triangle.a == superTriangle.b || triangle.a == superTriangle.c ||
                triangle.b == superTriangle.a || triangle.b == superTriangle.b || triangle.b == superTriangle.c ||
                triangle.c == superTriangle.a || triangle.c == superTriangle.b || triangle.c == superTriangle.c;
    }

    private List<Edge> triangleEdges(Triangle triangle) {
        List<Edge> edges = new ArrayList<Edge>();
        edges.add(new Edge(triangle.a, triangle.b));
        edges.add(new Edge(triangle.b, triangle.c));
        edges.add(new Edge(triangle.c, triangle.a));
        return edges;
    }
}