Java实现Bowyer-Watson算法时Bad Triangles识别异常求助

我正在进行一项实现Bowyer-Watson三角剖分算法的学校项目。当前代码可生成正确的三角网并正确移除超级三角形，但在识别和移除Bad Triangles时出现异常：要么完全不移除，要么全部移除。Bad Triangles定义为外接圆包含当前点的三角形，我怀疑问题出在点是否在三角形外接圆内的判断逻辑或计算上，已困扰许久，恳请提供解决方案。

代码参考自Scotty Anderson的仓库，执行效果存在以下异常：

• 不移除任何Bad Triangles
• 移除全部Bad Triangles
• 外接圆圆心计算结果异常

相关代码 #

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

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

            // 识别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);
                
                // 原判断逻辑：外接圆包含当前点的三角形为Bad Triangle
                if (distance < triangle.circumRadius()) {
                    badTriangles.add(triangle);
                }
            }

            List<Edge> polygon = new ArrayList<>();
            
            // 构建多边形：只保留Bad Triangles中不重复的边
            for (int i = 0; i < badTriangles.size(); i++) {
                Triangle triangle = badTriangles.get(i);
                List<Edge> 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));
                    }
                }
            }
            
            // 从三角网中移除Bad Triangles
            for (int i = badTriangles.size() - 1; i >= 0; i--) {
                triangles.remove(badTriangles.get(i));
            }
            
            // 生成新三角形
            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));
            }
        }

        // 移除包含超级三角形顶点的三角形
        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);
    }
}

class Triangle {
    public Point p1, p2, p3;
    private List<Point> points = new ArrayList<>();
    private Point cachedCircumCentre; // 新增缓存变量

    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<>();
        // 修复：补上第三条边
        edges.add(new Edge(points.get(0), points.get(1)));
        edges.add(new Edge(points.get(1), points.get(2)));
        edges.add(new Edge(points.get(2), points.get(0)));
        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() {
        if (cachedCircumCentre != null) {
            return cachedCircumCentre;
        }
        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;

        cachedCircumCentre = new Point(centerX, centerY);
        return cachedCircumCentre;
    }
}

class Edge {
    public Point p1, p2;
    public Edge(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }
}

class Point {
    public double x, y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    public Point(Point p) {
        this.x = p.x;
        this.y = p.y;
    }
    // 必须重写equals和hashCode，否则contains判断失效
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return Double.compare(point.x, x) == 0 && Double.compare(point.y, y) == 0;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

解决方案 #

1. 修复外接圆内点判断的精度问题

原判断使用开方运算（Math.hypot）会损失精度，且未处理浮点数误差。替换为平方比较，并加入epsilon阈值：

// 替换原Bad Triangle识别逻辑中的判断部分
Point centre = triangle.circumCentre();
double dx = point.x - centre.x;
double dy = point.y - centre.y;
double distSq = dx*dx + dy*dy;
double radiusSq = triangle.circumRadius() * triangle.circumRadius();
// 用epsilon处理浮点数精度误差，避免因计算误差导致误判
if (distSq < radiusSq - 1e-8) {
    badTriangles.add(triangle);
}

2. 修复Triangle类的getEdges方法

原方法只生成两条边，导致构建多边形时缺失边，进而引发后续逻辑错误。补上第三条边（见上方代码中Triangle类的getEdges方法）。

3. 确保Point类重写equals和hashCode

如果Point类未重写这两个方法，points.contains(edge.p1)会默认使用引用比较，导致判断失效，进而错误地将所有边加入多边形，最终删除全部三角形。上方代码已补充这两个方法的实现。

4. 优化Bad Triangles的移除逻辑

原移除方式依赖对象引用的一致性，改用集合判断更可靠：

// 替换原移除Bad Triangles的循环
java.util.Set<Triangle> badSet = new java.util.HashSet<>(badTriangles);
triangles.removeIf(badSet::contains);

5. 缓存外接圆圆心计算结果

每次调用circumCentre()都会重新计算，引入额外的计算误差和性能消耗。在Triangle类中加入缓存变量（见上方代码中的cachedCircumCentre），避免重复计算。

内容的提问来源于stack exchange，提问作者steve