How to draw ishihara-transformations (circles in circle without intersection)?

Question

Question: I need to draw pictures as below in C#/VB.NET
Note that my problem is NOT drawing circles in C#.

My problems is drawing them without much whitespace and without intersection.
My thought would be using "Orbits" and then draw the circles with center on the "orbit" lines. (with some orbit lines for bigger and some only for smaller circles) The problem is that there should be no intersections.

Anyone has a better idea ? Or how would I test whether a to be drawn circle of given radius would intersect with an already present circle ?

Answer 1

Intersection of circles is easy to calculate: if the square of the difference along the x plus the square of the difference along the y is less than the square of the sum of the radii, the circles intersect.

Note that this is already optimized a bit, as it avoids taking a square root. Additional optimizations are possible, e.g. when the difference along the x is greater than the sum of the radii, they will never intersect.

Just test the new circle against all existing circles, and you're done.

This is O(n^2), but is easy and pretty fast as each test is just a few, fast operations.

Of course, you could look for an optimization that you do not have to test each circle against all others, but those are expensive, lots of code, and thus only worth it for lots of circles. Try out the simple solution first.

In C++ code (sorry, I don't speak VB):

struct { double x, y, r; } Circle;

bool circleIsAllowed(const std::vector<Circle>& circles, const Circle& newCircle)
{
   for(std::vector<Circle>::const_iterator it = circles.begin(); it != circles.end(); ++it) // foreach(Circle it in circles)
   {
      double sumR = it->r + newCircle.r; // + minimumDistanceBetweenCircles (if you want)
      double dx = it->x - newCircle.x;
      double dy = it->y - newCircle.y;
      double squaredDist = dx*dx + dy*dy;
      if (squaredDist < sumR*sumR) return false;
   }

   return true; // no existing circle overlaps
}

Edit: corrected minor bugs, and noticed that the question wasn't about C++

Answer 2

Here's my attempt at interpreting @Sjoerd's code (in VB.Net). The code is from a standard blank WinForm app. It draws a bunch of circles into a rectangle. I'll leave it to the OP to constrain these to a circle. The DoCirclesIntersect function takes an optional PadCircle parameter which tries to give more spacing between circles so they don't bump up against each other. Its a little naive but it seems to work. The more circles that you draw the slower this gets as it needs to check more and more bounds.

Option Explicit On
Option Strict On

Public Class Form1
    ''//NOTE: The circles in this code are bound to a rectangle but it should be fairly trivial to create a master circle and check that

    ''//Dimension of the bounding image
    Private Shared ReadOnly ImageMaxDimension As Integer = 500
    Private Shared ReadOnly MinCircleDiameter As Integer = 4
    Private Shared ReadOnly MaxCircleDiameter As Integer = 15
    Private Shared ReadOnly CircleCount As Integer = 500
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        ''//Create a picture box to output to
        Dim PB As New PictureBox()
        PB.Dock = DockStyle.Fill
        Me.Controls.Add(PB)

        ''//List of bounds of all circles created so far
        Dim AllBounds As New List(Of RectangleF)

        ''//Our random number generator
        Dim R As New Random()

        ''//Values for our individual circles
        Dim W, X, Y As Integer
        Dim Re As RectangleF

        ''//Create a bitmap to draw on
        Dim TempB As New Bitmap(ImageMaxDimension, ImageMaxDimension)
        Using G = Graphics.FromImage(TempB)
            For I = 1 To CircleCount
                ''//We can only draw so many circles, this just gives us a counter so we know when we reach the limit for a given size
                Trace.WriteLine(I)

                ''//Create an infinite loop that we will break out of if we have found a circle that does not intersect anything
                Do While True
                    ''//Create a random diameter
                    W = R.Next(MinCircleDiameter, MaxCircleDiameter + 1)
                    ''//Create a random X,Y
                    X = R.Next(0 + W, ImageMaxDimension - W)
                    Y = R.Next(0 + W, ImageMaxDimension - W)
                    ''//Create our rectangle
                    Re = New RectangleF(X, Y, W, W)

                    ''//Check each existing bound to see if they intersect with the current rectangle
                    For Each B In AllBounds
                        ''//If they do, start the loop over again
                        If DoCirclesIntersect(B, Re, 1) Then Continue Do
                    Next

                    ''//If we are here, no circles intersected, break from the infinite loop
                    Exit Do
                Loop

                ''//All the circle to our list
                AllBounds.Add(Re)

                ''/Draw the circle on the screen
                G.FillEllipse(Brushes.BurlyWood, Re)
            Next

            ''//Draw the image to the picture box
            PB.Image = TempB
        End Using
    End Sub
    Private Shared Function DoCirclesIntersect(ByVal r1 As RectangleF, ByVal r2 As RectangleF, Optional ByVal PadCircle As Integer = 0) As Boolean
        ''//This code is hopefully what @Sjoerd said in his post
        Dim aX = Math.Pow(r1.X - r2.X, 2)
        Dim aY = Math.Pow(r1.Y - r2.Y, 2)
        Dim Dif = Math.Abs(aX - aY)
        Dim ra1 = r1.Width / 2
        Dim ra2 = r2.Width / 2
        Dim raDif = Math.Pow(ra1 + ra2, 2)
        Return (raDif + PadCircle) > Dif
    End Function
End Class