How to sum rectangles between randomly generated circles on a plane?

Question

I am trying to make a program in C# that would generate n number of points, which form centers of non colliding circles with radius r in 200 by 200 plane (coordinates for both x and y are [-100+r, 100 -r]) and create set of non intersecting, non overlaping rectangles between these circles. The program gives the sum of areas of all these rectangles . My problem is that it gives me and answer between 5000000 and 6000000 which is well above the theoretical maximum.

I tried dividing the total are by 200 as I compare distances squared, this gives answers in an expected range, but I do not know if this is in fact the error or if it's just a coincidence (N=867 and r=2.0) I'm not sure if the error is in this part but still (it is a console program of course):

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

and possibly in this part but I don't really see how as this is just adding variables from a list:

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

Answer 1

There is no code that actually checks for intersections. So your rectangles will almost certainly overlap, violating your stated requirement.

Lets consider a simplified case, with just 4 points, arranged in a rectangle. The first iteration happens to pick two points in opposite corners and generate a rectangle for these points. The next iteration will be forced to pick the other two points, ofc, these will generate the exact same rectangle, that will perfectly overlap.

The easy way to fix this is to keep a list of all created rectangles, and check for intersection/overlap with all previous rectangles. This will be fairly inefficient, but easy to implement. You could possibly use some kind of spatial tree, like an R-Tree, to optimize this search. If you have any additional criteria, like trying to fill the greatest possible area you should probably look in the research literature if there are any existing algorithms for solving your problem.

I would also highly recommend using some library for geometrical shapes, like System.Numerics, math.net.spatial, or create your own library. The code will be much easier to read if you have actual types for things like "point" and "rectangle", with actual methods for things like distance.

Another recommendation is unit testing. It is fairly easy to make trivial mistakes when writing code like this, but it is also easy to write unit tests that help catch such mistakes.

If you still have issues I would recommend using System.Drawing.Graphics to draw your circles/rectangles to an image, so you can visually inspect the result.