如何对平面上随机生成的圆之间的矩形求和？

Question

我正在尝试用 C# 编写一个程序，它会生成 n 个点，这些点形成 200 x 200 平面中半径为 r 的非碰撞圆的中心（x 和 y 的坐标均为 [-100+r, 100 -r ]）并在这些圆之间创建一组不相交、不重叠的矩形。该程序给出所有这些矩形的面积总和。我的问题是它给我的答案在 5000000 到 6000000 之间，这远远高于理论最大值。

当我比较距离平方时，我尝试将总数除以 200，这给出了预期范围内的答案，但我不知道这实际上是错误还是只是巧合（N = 867 和 r = 2.0） 我不确定错误是否在这部分，但仍然（当然这是一个控制台程序）：

public void GenerateRectangles()
{
    var usedCenters = new HashSet<(double, double)>();

    foreach (var point1 in circleCenters)
    {
        if (usedCenters.Contains(point1)) continue;

        foreach (var point2 in circleCenters)
        {
            if (point1 == point2 || usedCenters.Contains(point2)) continue;

            double dx = point2.x - point1.x;
            double dy = point2.y - point1.y;
            double distanceSquared = dx * dx + dy * dy;

            if (distanceSquared >= (2 * Radius) * (2 * Radius))
            {
                double length = Math.Sqrt(distanceSquared) - 2 * Radius;
                double width = CalculateShortestDistance(point1, point2) - Radius;

                var rectangleCoords = CreateRectangle(point1, point2, width, length);
                rectangleBoundaries.Add((rectangleCoords, width * length));
                totalAreaOfRectangles.Add(width * length);

                usedCenters.Add(point1);
                usedCenters.Add(point2);
                break;
            }
        }
    }

    HandleRemainingPoints(usedCenters);
}

private double CalculateShortestDistance((double x, double y) point1, (double x, double y) point2)
{
    double dx = point2.x - point1.x;
    double dy = point2.y - point1.y;
    return Math.Sqrt(dx * dx + dy * dy);
}

private List<(double x, double y)> CreateRectangle((double x, double y) point1, (double x, double y) point2, double width, double length)
{
    double dx = point2.x - point1.x;
    double dy = point2.y - point1.y;

    double normalX = dy; // Normal vector components
    double normalY = -dx;

    double magnitude = Math.Sqrt(normalX * normalX + normalY * normalY);
    normalX /= magnitude;
    normalY /= magnitude;

    var point3 = (point1.x + normalX * width, point1.y + normalY * width);
    var point4 = (point2.x + normalX * width, point2.y + normalY * width);

    return new List<(double x, double y)> { point1, point2, point4, point3 };
}

可能在这一部分，但我真的不明白如何，因为这只是从列表中添加变量：

public void CalculateTotalArea()
{
    double totalArea = 0;
    foreach (var area in totalAreaOfRectangles)
    {
        totalArea += area;
    }
    Console.WriteLine("Total Area Occupied by Rectangles: " + totalArea);
}

Answer 1

没有代码实际检查交叉点。所以你的矩形几乎肯定会重叠，违反你规定的要求。

让我们考虑一个简化的情况，只有 4 个点，排列在一个矩形中。第一次迭代恰好选取对角的两个点并为这些点生成一个矩形。下一次迭代将被迫选择另外两个点，ofc，它们将生成完全相同的矩形，它将完美重叠。

解决此问题的简单方法是保留所有创建的矩形的列表，并检查与所有先前矩形的相交/重叠。这将是相当低效的，但很容易实现。您可以使用某种空间树（例如 R 树）来优化此搜索。如果您有任何其他标准，例如尝试填充尽可能大的区域，您可能应该查看研究文献，看看是否有任何现有算法可以解决您的问题。

我还强烈建议使用一些几何形状库，例如 System.Numerics、math.net.spatial，或者创建自己的库。如果您有“点”和“矩形”等实际类型，以及距离等实际方法，那么代码将更容易阅读。

另一个建议是单元测试。编写这样的代码时很容易犯一些小错误，但编写有助于捕获此类错误的单元测试也很容易。

如果您仍然遇到问题，我建议您使用 System.Drawing.Graphics 将圆形/矩形绘制到图像上，以便您可以直观地检查结果。