菱形重叠检测原理与Java代码实现

本文深入剖析了菱形几何重叠判断的常见误区与正确实现路径，指出仅靠顶点坐标比较或简单包围盒检测极易导致误判，并系统性地给出了基于轴对齐包围盒（AABB）快速预检、凸多边形点包含判定及边边相交检测三重验证的鲁棒Java解决方案；通过重构Rhombus类为顶点有序表示、严谨处理叉积符号、引入浮点容差与性能优化策略，不仅精准解决了任意旋转菱形的重叠判断难题，更将方法自然扩展至通用凸四边形，为图形渲染、物理碰撞和地理信息分析等实际场景提供了兼具理论严谨性与工程落地性的可靠参考。

本文介绍如何在 Java 中正确判断两个任意菱形是否发生几何重叠，指出仅比较顶点坐标的常见误区，并提供基于轴对齐包围盒（AABB）预检与精确凸多边形相交判定的完整解决方案。

菱形是中心对称的凸四边形，其四条边等长、对角线互相垂直平分。然而，仅用四个整型字段（p1–p4）无法唯一确定一个二维菱形的位置和形状——原始代码中 Rhombus(int p1, int p2, int p3, int p4) 的设计存在根本性缺陷：它未区分坐标维度（x/y），也未表达顶点顺序或几何约束，导致无法构建真实菱形。

要严谨判断两个菱形是否重叠，需满足两个前提：

1. 明确的几何表示：每个菱形应由其中心点 (cx, cy)、两对角线长度 d1（水平方向）、d2（垂直方向）及旋转角度 θ 定义；或更通用地，由按顺时针/逆时针顺序排列的 4 个顶点坐标（如 Point[] vertices）表示。
2. 正确的相交逻辑：重叠 ≠ 顶点重合。即使所有顶点互不相同，两个菱形仍可能因边交叉或区域包含而重叠（如下图示意）：

   ▲ y
   │      ◼ Rhombus A (rotated)
   │    ┌───┐
   │   /     \
   │  └───────┘
   │         ┌───┐
   │        /  B  \
   │       └───────┘ → x

✅ 正确实现步骤

1. 重构 Rhombus 类：使用顶点数组表示

import java.awt.geom.Line2D;
import java.util.Arrays;

public class Rhombus {
    private final Point[] vertices; // 4 vertices in CCW order

    public Rhombus(Point... verts) {
        if (verts.length != 4) 
            throw new IllegalArgumentException("Rhombus must have exactly 4 vertices");
        this.vertices = verts.clone();
    }

    // Helper: check if point lies inside convex polygon (ray-casting for convex → optimized)
    private boolean contains(Point p) {
        // For convex quadrilateral: check all cross products have same sign
        for (int i = 0; i < 4; i++) {
            Point a = vertices[i];
            Point b = vertices[(i + 1) % 4];
            double cp = crossProduct(a, b, p);
            if (cp < 0) return false; // assuming CCW order → all cross products ≥ 0
        }
        return true;
    }

    // Cross product of AB × AP
    private double crossProduct(Point a, Point b, Point p) {
        return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    }

    // Check if any edge of this rhombus intersects any edge of r
    private boolean edgesIntersect(Rhombus r) {
        for (int i = 0; i < 4; i++) {
            Point a1 = vertices[i];
            Point a2 = vertices[(i + 1) % 4];
            for (int j = 0; j < 4; j++) {
                Point b1 = r.vertices[j];
                Point b2 = r.vertices[(j + 1) % 4];
                if (Line2D.linesIntersect(a1.x, a1.y, a2.x, a2.y, b1.x, b1.y, b2.x, b2.y)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Main overlap check: either one contains the other's vertex, or edges cross
    public boolean overlaps(Rhombus r) {
        // Quick rejection via bounding box (AABB)
        Rectangle2D bounds1 = getBounds();
        Rectangle2D bounds2 = r.getBounds();
        if (!bounds1.intersects(bounds2)) return false;

        // Check vertex containment (A in B or B in A)
        for (Point p : vertices) {
            if (r.contains(p)) return true;
        }
        for (Point p : r.vertices) {
            if (contains(p)) return true;
        }

        // Check edge-edge intersection
        return edgesIntersect(r);
    }

    private Rectangle2D getBounds() {
        double minX = Arrays.stream(vertices).mapToDouble(p -> p.x).min().orElse(0);
        double minY = Arrays.stream(vertices).mapToDouble(p -> p.y).min().orElse(0);
        double maxX = Arrays.stream(vertices).mapToDouble(p -> p.x).max().orElse(0);
        double maxY = Arrays.stream(vertices).mapToDouble(p -> p.y).max().orElse(0);
        return new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY);
    }

    // Simple helper class
    public static class Point {
        final double x, y;
        Point(double x, double y) { this.x = x; this.y = y; }
    }
}

2. 使用示例

public static void main(String[] args) {
    // Define two rhombi by their 4 CCW vertices
    Rhombus r1 = new Rhombus(
        new Rhombus.Point(0, 2),
        new Rhombus.Point(2, 0),
        new Rhombus.Point(4, 2),
        new Rhombus.Point(2, 4)
    );

    Rhombus r2 = new Rhombus(
        new Rhombus.Point(1, 1),
        new Rhombus.Point(3, 1),
        new Rhombus.Point(3, 3),
        new Rhombus.Point(1, 3)
    );

    System.out.println("Do they overlap? " + r1.overlaps(r2)); // true — r2 is inside r1
}

⚠️ 注意事项与优化建议

• 顶点顺序至关重要：contains() 方法依赖顶点为逆时针（CCW）排列；若为顺时针，需将 crossProduct 判断改为 cp > 0。
• 性能考虑：对于大量菱形检测，可先用 AABB 快速剔除（O(1)），再执行 O(16) 边边检测 + 最多 8 次点面测试。
• 数值精度：生产环境建议使用 double 而非 int 表示坐标，并在 crossProduct 中加入 epsilon 比较（如 Math.abs(cp) < 1e-9）避免浮点误差。
• 扩展性：该方案天然支持任意凸四边形，只需确保输入顶点构成凸包且有序。

✅ 总结

判断菱形重叠绝非简单的“点相等”或“包围盒重叠”，而需结合边界框预检 + 点在多边形内判定 + 线段相交检测三重验证。本文提供的实现兼顾正确性、可读性与工程可用性，适用于图形渲染、碰撞检测、GIS 分析等场景。务必从语义清晰的几何建模出发——这是可靠空间计算的基石。

理论要掌握，实操不能落！以上关于《菱形重叠检测原理与Java代码实现》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！