如何绘制石原变换（无圆的圆圈）？

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