在 Java 中查找重叠的圆圈

Question

有没有一种简单的方法可以在 Java 中找到重叠的圆（每个圆在中间有一个点且半径相同）？

例如，如果我有一个数据集并且我有那些点

Point1 (3|3)
Point2 (4|2)
r = 1

所以我会这样：

如何检查 Java，这两个点是否重叠？

最好，提前谢谢！

Answer 1

实际上只是应用勾股定理的问题。

boolean areCirclesOverlappint(Point a, Point b, double radius) {
    double diffX = a.x - b.x;
    double diffY = a.y - b.y;
    return diffX * diffX + diffY * diffy <= radius * radius * 4;
}

Answer 2

如果中心之间的距离小于半径之和，则圆重叠：

public static boolean checkOverlap(Circle c1, Circle c2) {
    return Math.hypot(c1.x - c2.x, c1.y - c2.y) < c1.r + c2.r;
}

如果你有很多圈子并且正在寻找成对的重叠，你可以使用 k-d tree 比 O(n²) 做得更好。

Answer 3

一个简单的启发式算法。（这只是对 arshajii 回答的补充。）

如果您想避免 k-D 树，您可以根据 X 坐标对中心进行排序。然后依次考虑所有的圆，只检查中心横坐标在[X,X+2R]的圆是否重叠。

假设 N 个圆均匀分布在相对大小为 M（边长大于直径）的域中，您将仅用 N²/2 次比较换取 max(N²/M, N)。

在 Java 中查找重叠的圆圈

Find overlapping circles in Java

java

geometry

overlapping

points