Как нарисовать исихара-преобразования (круги в круге без пересечения)?

Question

Вопрос: мне нужно рисовать картинки, как показано ниже в C # / VB.NET
Обратите внимание, что моя проблема НЕ рисовать круги в C #.

Мои проблемы - рисовать их без лишних пробелов и без пересечений.
Моя мысль будет использовать «Орбиты», а затем нарисовать круги с центром на линиях «орбиты». (с некоторыми орбитальными линиями для больших, а некоторые только для меньших кругов) Проблема в том, что не должно быть пересечений.

У кого-нибудь есть идея получше? Или как проверить, будет ли нарисованный круг заданного радиуса пересекаться с уже существующим кругом?

Answer 1

Пересечение окружностей легко вычислить: если квадрат разности вдоль x плюс квадрат разности вдоль y меньше квадрата суммы радиусов, круги пересекаются.

Обратите внимание, что это уже немного оптимизировано, поскольку позволяет избежать получения квадратного корня.Возможна дополнительная оптимизация, например, когда разница по x больше суммы радиусов, они никогда не пересекутся.

Просто протестируйте новый круг на всех существующих кругах, и все готово.

Это O (n ^ 2), но это просто и довольно быстро, поскольку каждый тест - это всего лишь несколько быстрых операций.

Конечно, вы можете искать оптимизацию, которой у вас нетпроверить каждый круг на соответствие всем остальным, но это дорого, много кода, и, следовательно, оно того стоит только для большого количества кругов.Сначала попробуйте простое решение.

В коде C ++ (извините, я не говорю на 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
}

Редактировать: исправлены мелкие ошибки и замечено, что вопрос нео C ++

Answer 2

Вот моя попытка интерпретировать код @ Sjoerd (в VB.Net). Код взят из стандартного пустого приложения WinForm. Рисует кучу кругов в прямоугольник. Я оставлю это на OP, чтобы ограничить их кругом. Функция DoCirclesIntersect принимает дополнительный параметр PadCircle, который пытается увеличить расстояние между кругами, чтобы они не сталкивались друг с другом. Это немного наивно, но, похоже, работает. Чем больше кругов вы рисуете, тем медленнее это становится, поскольку нужно проверять все больше и больше границ.

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