Java开发者求助：如何计算多圆形构成的区域数量？

核心思路：基于欧拉公式的准确计算 #

平面图形的欧拉公式为 (V - E + F = 2)，其中：

• (V)：所有圆之间的交点总数（每个交点仅算一次）
• (E)：所有圆被交点分割后的弧段总数
• (F)：最终的区域数（包含外部无限区域）

通过变形公式 (F = E - V + 2)，我们可以精准计算出区域总数，无需依赖理想情况的最大区域公式。

具体实现步骤 #

1. 预处理：去重重复圆 #

如果两个圆的圆心坐标和半径完全相同，它们不会增加任何区域，因此需要先从数组中移除重复的圆（使用极小精度值EPS处理浮点数比较误差）。

2. 计算两圆交点数量 #

对每一对圆，根据圆心距和半径关系判断交点数：

• 圆心距 (d = \sqrt{(x2-x1)^2 + (y2-y1)^2})
  • (d > r1 + r2) 或 (d < |r1 - r2|)：0个交点（外离/内含）
  • (d = r1 + r2) 或 (d = |r1 - r2|)：1个交点（外切/内切）
  • (|r1 - r2| < d < r1 + r2)：2个交点（相交）

3. 统计顶点数V和边数E #

• 顶点数V：所有两两圆交点数之和除以2（每个交点被两个圆各计算一次）
• 边数E：每个圆的总交点数之和（每个交点会将圆分割为一段弧，弧的数量等于交点数）

4. 代入欧拉公式计算区域数 #

用公式 (F = E - V + 2) 得到最终区域数，包含外部的无限区域。

Java代码实现 #

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

public class CircleRegionCounter {
    private static final double EPS = 1e-8; // 处理浮点数精度误差

    static class Circle {
        double x, y, r;
        Circle(double x, double y, double r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }

    public static int countRegions(List<Circle> circles) {
        // 去重重复圆
        List<Circle> uniqueCircles = new ArrayList<>();
        for (Circle c : circles) {
            boolean isDuplicate = false;
            for (Circle uc : uniqueCircles) {
                if (Math.abs(c.x - uc.x) < EPS && Math.abs(c.y - uc.y) < EPS && Math.abs(c.r - uc.r) < EPS) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueCircles.add(c);
            }
        }

        int n = uniqueCircles.size();
        if (n == 0) return 1; // 无圆时只有1个区域

        int[] circleIntersections = new int[n];
        int totalIntersections = 0;

        // 遍历所有圆对，统计交点数
        for (int i = 0; i < n; i++) {
            Circle c1 = uniqueCircles.get(i);
            for (int j = i + 1; j < n; j++) {
                Circle c2 = uniqueCircles.get(j);
                int count = getIntersectionCount(c1, c2);
                circleIntersections[i] += count;
                circleIntersections[j] += count;
                totalIntersections += count;
            }
        }

        int V = totalIntersections / 2;
        int E = 0;
        for (int cnt : circleIntersections) {
            E += cnt;
        }

        return E - V + 2;
    }

    private static int getIntersectionCount(Circle c1, Circle c2) {
        double dx = c2.x - c1.x;
        double dy = c2.y - c1.y;
        double dSquared = dx * dx + dy * dy;
        double d = Math.sqrt(dSquared);
        double r1 = c1.r;
        double r2 = c2.r;

        // 外离或内含
        if (d > r1 + r2 + EPS || d < Math.abs(r1 - r2) - EPS) {
            return 0;
        }
        // 外切或内切
        if (Math.abs(d - (r1 + r2)) < EPS || Math.abs(d - Math.abs(r1 - r2)) < EPS) {
            return 1;
        }
        // 相交
        return 2;
    }

    public static void main(String[] args) {
        List<Circle> circles = new ArrayList<>();
        circles.add(new Circle(-2, 0, 1));
        circles.add(new Circle(0, 0, 2));
        circles.add(new Circle(2, 0, 1));
        System.out.println(countRegions(circles)); // 输出6
    }
}

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