{
Markiere:

         newt := abs( 0.5*(
             ABS(ballr1.r - ball.r)*sqrt(
               (sqr(ballr1.r - ball.r) - sqr(x1 - x2) - sqr(y1 - y2))*
               (
                  sqr(dir.x)*(sqr(ballr1.r - ball.r) - sqr(x1 - x2) - sqr(y1 - y2))
                  + 4*dir.x*dir.y*(x1*y2 + x2*y1)
                  + dir.y^2*(sqr(ballr1.r - ball.r) - sqr(x1 + x2) - sqr(y1 - y2))
               )
             )
             - dir.x*((x1 + x2)*sqr(ballr1.r - ball.r) + (sqr(x1) - sqr(x2) + sqr(y1) - sqr(y2))*(x2 - x1))
             - dir.y*((y1 + y2)*sqr(ballr1.r - ball.r) + (sqr(x1) - sqr(x2) + sqr(y1) - sqr(y2))*(y2 - y1))
           )
           /
           (
             sqr(ballr1.r - ball.r) * (sqr(dir.x)* + sqr(dir.y))
             - sqr(dir.x*(x1 - x2) - dir.y*(y1 - y2))
           ));
           
           Und ersetze x1 durch ballr1.pos.x
}
//{$define td}

unit a1_u;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls,vectors,math, Spin,balls, Buttons, ComCtrls,memory;

  const RadiusBall=20;

type
  TForm1 = class(TForm)
    PaintBox1: TPaintBox;
    Panel1: TPanel;
    Label1: TLabel;
    Timer1: TTimer;
    Label2: TLabel;
    SpinEdit1: TSpinEdit;
    Label3: TLabel;
    SpinEdit2: TSpinEdit;
    Button1: TButton;
    Label4: TLabel;
    Label5: TLabel;
    SpeedButton1: TSpeedButton;
    SpeedButton2: TSpeedButton;
    SpeedButton3: TSpeedButton;
    SpeedButton4: TSpeedButton;
    SpeedButton5: TSpeedButton;
    SpeedButton6: TSpeedButton;
    SpeedButton7: TSpeedButton;
    SpeedButton8: TSpeedButton;
    SpeedButton9: TSpeedButton;
    Timer2: TTimer;
    CheckBox1: TCheckBox;
    Button2: TButton;
    Button3: TButton;
    Label6: TLabel;
    Label7: TLabel;
    Label8: TLabel;
    SpinEdit3: TSpinEdit;
    RadioButton1: TRadioButton;
    KugelTeleportation: TRadioButton;
    Label9: TLabel;
    Edit1: TEdit;
    Label10: TLabel;
    Button4: TButton;
    Button5: TButton;
    SaveDialog1: TSaveDialog;
    Label11: TLabel;
    SpinEdit4: TSpinEdit;
    StatusBar1: TStatusBar;
    ProgressBar1: TProgressBar;
    CheckBox2: TCheckBox;
    Label12: TLabel;
    Button6: TButton;
    CheckBox3: TCheckBox;
    CheckBox4: TCheckBox;
    SpinEdit5: TSpinEdit;
    Label13: TLabel;
    SpinEdit6: TSpinEdit;
    Button7: TButton;
    Button8: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure PaintBox1Paint(Sender: TObject);
    procedure PaintBox1MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Timer1Timer(Sender: TObject);
    procedure FormResize(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure SpeedButton2MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure SpeedButton2MouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Timer2Timer(Sender: TObject);
    procedure SpinEdit1Change(Sender: TObject);
    procedure SpeedButton5MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure SpeedButton5MouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure Button5Click(Sender: TObject);
    procedure PaintBox1MouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure PaintBox1MouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure CheckBox4Click(Sender: TObject);
    procedure Button8Click(Sender: TObject);
  private
    { Private-Deklarationen}
  public
    { Public-Deklarationen}
    balls: TBallList;

    //minimale/maximale Ausdehnung der Struktur:
    spMinX,spMaxX,spMinY,spMaxY:integer;
    structurePoint:TVector2Int;
    innerCircelRadius:integer;

    xmove,ymove:integer;//Verschiebung der Kugeln zur Darstellung
    sizeFactor:integer;//Größenfaktor in Prozent (100: genau, 50: halb so groß)

    doubleBuffer:TBitmap;

    selectedMoveButton:tspeedbutton;
    allMoving:boolean;
    amsX,amsY:integer;
    newBallX,newBallY:integer;
    creatingNewBall:boolean;
    newBallDir:TVector2Float;
    newBallPos:TVector2Int;
    newBallR:integer;

    moveCursor: array[0..2,0..2] of tcursor;

    useStandardRadius:boolean;

    procedure findOptimalCenterAndRadius(out middle:TVector2Int;out radius:integer);
    procedure calculateKollision(const dir:TVector2Float;const pos:TVector2Int;const radius:byte;
                                  var kollisionTime:single; var kollisionPos:TVector2Int);
    procedure addBall(x,y:integer;r:byte);
    procedure addUserBall(x,y:integer;dir:TVector2Float;r:byte);
    procedure resetInnerCircelRadius();

    procedure updateBalls;
    procedure drawBalls(const size,xmove,ymove:integer;output:TBitmap;numbers:boolean);
    procedure drawBallsDefault;
    procedure updateStructurePos(const newBall:TStaticBall);
  end;

var
  Form1: TForm1;
  {$ifdef td}
  time2:cardinal;
  debug:integer;
  {$endif}
implementation

{$R *.DFM}
{$R cursors.res}
function rrandom(min,max:integer):integer;overload;
begin
  result:=random(max-min+1)+min;
end;
function rrandom(min,max:single):single; overload;
begin
  result:=(random(trunc((max-min)*1000000))+trunc(min*1000000))/1000000;
end;
procedure TForm1.calculateKollision(const dir:TVector2Float;const pos:TVector2Int;const radius:byte;
                                    var kollisionTime:single; var kollisionPos:TVector2Int);
var i:integer;
    {l,newl,}a,b,b_lookup,c,wurzelTerm,oldb,oldw,ltemp:single;
    nearer:boolean;
    ball2,endball:TStaticBall;

begin
  //Kollisionspunkt berechnen:
  //Kollision Bewegungsvektor vom Kugel Nr. ball mit Kugel i
  a:=4*vecDot(dir,dir);
  if a=0 then begin
    kollisionTime:=1e35;
    kollisionPos:=makeVector(0,0);
    exit;
  end;
  b_lookup:=(dir.x*pos.x+dir.y*pos.y);
  oldb:=1e30;
  oldw:=-1e30;

  i:=0;
  while i<=balls.countStatic-1 do begin
    ball2:=balls.getStaticBall(i);
    if i+StaticBallsInArray<balls.countStatic then
      endball:=balls.getStaticBall(i+StaticBallsInArray-1)
     else
      endball:=balls.getStaticBall(balls.countStatic-1);
    i:=i+StaticBallsInArray;
    while (cardinal(ball2)<=cardinal(endball)) do begin
      //Zu finden Ein l mit distance(ball1.pos+l*ball1.dir,ball2.pos)=2*radius
      {
        length(ball1.pos+l*ball1.dir-ball2.pos)=r1+r2

        sqrt(<ball1.pos+l*ball1.dir-ball2.pos,ball1.pos+l*ball1.dir-ball2.pos>)=2*r1+r2

        <ball1.pos+l*ball1.dir-ball2.pos,ball1.pos+l*ball1.dir-ball2.pos>=(r1+r2)^2

        <l*ball1.dir,ball1.pos+l*ball1.dir-ball2.pos>+
        <ball1.pos-ball2.pos,ball1.pos+l*ball1.dir-ball2.pos>=(r1+r2)^2

        <l*ball1.dir,ball1.pos-ball2.pos> + <l*ball1.dir,l*ball1.dir>+
        <ball1.pos-ball2.pos,ball1.pos+l*ball1.dir-ball2.pos>=(r1+r2)^2

        <l*ball1.dir,ball1.pos-ball2.pos> + <l*ball1.dir,l*ball1.dir>+
        <ball1.pos-ball2.pos,ball1.pos-ball2.pos>+<ball1.pos-ball2.pos,l*ball1.dir>=(r1+r2)^2

        <l*ball1.dir,l*ball1.dir>+
        <l*ball1.dir,ball1.pos-ball2.pos> + <ball1.pos-ball2.pos,l*ball1.dir>+
        (<ball1.pos-ball2.pos,ball1.pos-ball2.pos>-(r1+r2)^2)=0

        l*l*<ball1.dir,ball1.dir>+
        l*(<ball1.dir,ball1.pos-ball2.pos> + <ball1.pos-ball2.pos,ball1.dir>)+
        (<ball1.pos-ball2.pos,ball1.pos-ball2.pos>-(r1+r2)^2)=0

        l*l*<ball1.dir,ball1.dir>+
        l*(<ball1.pos-ball2.pos,ball1.dir> + <ball1.pos-ball2.pos,ball1.dir>)+
        (<ball1.pos-ball2.pos,ball1.pos-ball2.pos>-(r1+r2)^2)=0

        l*l*<ball1.dir,ball1.dir>+
        l*(2*<ball1.pos-ball2.pos,ball1.dir>)+
        (<ball1.pos-ball2.pos,ball1.pos-ball2.pos>-(r1+r2)^2)=0

        a=  <ball1.dir,ball1.dir>
        b=  <ball1.dir,ball1.pos-ball2.pos> + <ball1.pos-ball2.pos,ball1.dir>
        c=(-(r1+r2)^2 + <balls[ball].pos-balls[i].pos,balls[ball].pos-balls[i].pos>)

        b weiter optimiert:
        b = 2*<ball1.dir,ball1.pos-ball2.pos>
        = 2*(<ball1.dir,ball1.pos>-<ball1.dir,ball2.pos>)
        Das erste Skalarprodukt, kann vorberechnet werden
      }

      //Das b ist negativiert, dann ist eine subtraktion gespart
      b:=(-2)*(b_lookup-(dir.x*ball2.pos.x+dir.y*ball2.pos.y));
      if b<0 then begin
        inc(ball2);
        continue; //Bei b<0,  wäre der andere Kreis hinter
      end;
      c:=sqr(pos.x-ball2.pos.x)+sqr(pos.y-ball2.pos.y)-sqr(radius+ball2.r);

      wurzelTerm:=b*b-a*c;
      if (wurzelTerm<0) then begin
        inc(ball2);
        continue;
      end;
      {  Die Frage ist jetzt, ist b# - sqrt(w#) > b - sqrt(w)?
        Fall 1: b# >= b und w# <= w:             JJJJJ    AAAA
             => sqrt(w#) <= sqrt(w)                  J  AA    AA
             => b# + sqrt(w) >= b + sqrt(w)     J    J  AAAAAAAA
             => b# - sqrt(w#)>= b - sqrt(w)      JJJJ   AA    AA
             Ja

        Fall 2: b# <= b und w# >= w:            NNNN   NN  OOOOOOO
             => sqrt(w#) >= sqrt(w)             NN NN  NN  OO   OO
             => b# + sqrt(w) <= b + sqrt(w)     NN  NN NN  OO   OO
             => b# - sqrt(w#)<= b - sqrt(w)     NN   NNNN  OOOOOOO
             Nein

        Fall 3: b# >= b und w# > w
             b# - sqrt(w#)  ?  b - sqrt(w)
             b# - b ? sqrt(w#) - sqrt(w)
             Beide Seiten sind größer gleich 0
             sqr(b# - b) ? sqr(sqrt(w#) - sqrt(w))
             sqr(b# - b) ? w# - 2sqrt(w# * w) + w
             sqr(b# - b) - w# - w ?  - 2sqrt(w# * w)
             (w# + w - sqr(b# - b)) / 2   !? sqrt(w# * w)
             Die rechte Seite ist >= 0.
               Unterfall 1: Linke Seite >= 0
                 sqr((w# + w - sqr(b# - b)) / 2)   !?  w# * w
                 sqr((w# + w - sqr(b# - b)) )/ 4   !?  w# * w
                 sqr((w# + w - sqr(b# - b)) )      !?  4 * w# * w
                 Ja, wenn sqr((w# + w - sqr(b# - b))  < 4 * w# * w
               Unterfall 2: Linke Seite < 0
                 Ja

        Fall 4: b# <= b und w# < w
             b# - sqrt(w#)  ?  b - sqrt(w)
             b# - b ? sqrt(w#) - sqrt(w)
             Beide Seiten sind kleiner gleich 0
             sqr(b# - b) !? sqr(sqrt(w#) - sqrt(w))
             sqr(b# - b) !? w# - 2sqrt(w#*w) + w
             sqr(b# - b) - w# - w !?  - 2sqrt(w# * w)
             (w# + w - sqr(b# - b)) / 2   ? sqrt(w# * w)
             Die rechte Seite ist >= 0.
               Unterfall 1: Linke Seite >= 0
                 sqr((w# + w - sqr(b# - b)) / 2)   ?  w# * w
                 sqr((w# + w - sqr(b# - b)) )/ 4   ?  w# * w
                 sqr((w# + w - sqr(b# - b)) )      ?  4 * w# * w
                 Ja, wenn sqr((w# + w - sqr(b# - b)) >  4 * w# * w
               Unterfall 2: Linke Seite < 0
                 Nein
      }
      if oldb>= b then begin
        if oldw <= wurzelTerm then nearer:=true //Fall 1
        else begin //Fall 3
          ltemp:=(oldw + wurzelTerm - sqr(oldb - b));//(oldw + wurzelTerm - sqr(oldb - b)) / 2;
          if ltemp>= 0 then  nearer:=ltemp*ltemp<4*oldw*wurzelTerm//Unterfall 1
          else nearer:=true;//Unterfall2
        end;
      end else begin
        if oldw < wurzelTerm then begin //Fall 4
          ltemp:=(oldw + wurzelTerm - sqr(oldb - b));//(oldw + wurzelTerm - sqr(oldb - b)) / 2;
          if ltemp>= 0 then  nearer:=ltemp*ltemp>4*oldw*wurzelTerm//Unterfall 1
          else nearer:=false;//Unterfall 2
        end else nearer:=false; //Fall 2
      end;
      if nearer then begin
        oldb:=b;
        oldw:=wurzelTerm;
      end;
      inc(ball2);
    end;
  end;
  if oldw>=0 then begin
   kollisionTime:=2*(oldb-sqrt(oldw))/(a);
    if kollisionTime<1e10 then
      kollisionPos:=vecAdd(pos,vectrunc(vecmul(dir,kollisionTime)))
  end else kollisionTime:=1e35;
end;

//Fügt eine Kugel mit Radius r an der Stelle (x,y) ein
procedure TForm1.addBall(x,y:integer;r:byte);
var ball:TMovableBall;
    alpha,usedalpha,len:single;
    longDir:TVector2Int;
begin
  ball:=balls.createMovableBall;
  ball.currentTime:=0;
  ball.pos.x:=x;
  ball.pos.y:=y;

  //Richtung
  longDir:=vecSub(ball.pos,structurePoint);
  len:=vecLength(longDir);
  alpha:=(innerCircelRadius + r div 2)/len;
  if ( alpha<0) or (alpha>1) then alpha:=1;
  alpha:=arcsin(alpha);

  usedalpha:=rrandom(-alpha,alpha);
  ball.dir:=vecRot(longDir,usedalpha);
  ball.dir.x:=-ball.dir.x/len; //Normalisieren
  ball.dir.y:=-ball.dir.y/len; //Normalisieren
  ball.r:=r;

  calculateKollision(ball.dir, ball.pos,ball.r,ball.kollisionTime,ball.kollisionPos);
end;

//Fügt eine Kugel mit Radius r an der Stelle (x,y) ein, die sich in Richtung dir
//bewegt
procedure TForm1.addUserBall(x,y:integer;dir:TVector2Float;r:byte);
var ball:TMovableBall;
begin
  if vecDotSelf(dir)>0 then begin
    ball:=balls.createMovableBall;
    ball.pos.x:=x;
    ball.pos.y:=y;
    ball.dir:=dir;
    ball.r:=r;
    ball.currentTime:=0;
    calculateKollision(ball.dir, ball.pos,ball.r,ball.kollisionTime,ball.kollisionPos);
    updateBalls;
  end else addBall(x,y,r);
end;

//Aktualisiert den alle Kugeln enthaltenen Kreis mit Radius innerCircelRadius
//um den Mittelpunkt structurePoint
//Dabei wird versucht den Radius möglichst gering zu halten, gleichzeitig aber
//auch möglichst schnell zu sein, weshalb als Mittelpunkt der Schnittpunkt der
//Diagonalen eines alle Kugeln enthaltenen Rechteckes genommen wird, und als
//Radius der kleinste Wert für den noch alle Kugel im Kreis sind.
//Das läuft in O(n), das schnellste absolut präzise Verfahren was ich gefunden
//habe (einen Kreis zu schrumpfen), bräuchte zum Vergleich O(n^2)
procedure TForm1.updateStructurePos(const newBall:TStaticBall);
var i:integer;
    dotProduct:integer;
    changed:boolean;
    ball,endball:TStaticBall;
begin
  //Neue Rechteckgrößen berechnen
  changed:=false;
  if newBall.pos.x<spMinX then begin
    spMinX:=newBall.pos.x;
    changed:=true;
  end;
  if newBall.pos.x>spMaxX then begin
    spMaxX:=newBall.pos.x;
    changed:=true;
  end;
  if newBall.pos.y<spMinY then begin
    spMinY:=newBall.pos.y;
    changed:=true;
  end;
  if newBall.pos.y>spMaxY then begin
    spMaxY:=newBall.pos.y;
    changed:=true;
  end;

  if changed then begin//Wenn das Rechteck verändert wurde
    //Neuen Mittelpunkt berechnen (O(1))
    structurePoint.x:=(spMinX+spMaxX) div 2;
    structurePoint.y:=(spMinY+spMaxY) div 2;

    //Neuen Radius berechnen (O(n))
    if useStandardRadius then begin
      //Alle Kugeln haben den gleichen Radius
      innerCircelRadius:=0;
      i:=0;
      while i<=balls.countStatic-1 do begin
        ball:=balls.getStaticBall(i);
        if i+StaticBallsInArray<balls.countStatic then
          endball:=balls.getStaticBall(i+StaticBallsInArray-1)
         else
          endball:=balls.getStaticBall(balls.countStatic-1);
        i:=i+StaticBallsInArray;
        while (cardinal(ball)<=cardinal(endball)) do begin
          dotProduct :=vecDotSelf(vecSub(ball.pos,structurePoint));
          if dotProduct>innerCircelRadius then innerCircelRadius:= dotProduct;
          inc(ball);
        end;
      end;
      innerCircelRadius:=trunc(sqrt(innerCircelRadius))+RadiusBall;
    end else begin
      //Kugeln lönnen einen unterschiedlichen Radius haben 
      innerCircelRadius:=0;
      i:=0;
      while i<=balls.countStatic-1 do begin
        ball:=balls.getStaticBall(i);
        if i+StaticBallsInArray<balls.countStatic then
          endball:=balls.getStaticBall(i+StaticBallsInArray-1)
         else
          endball:=balls.getStaticBall(balls.countStatic-1);
        i:=i+StaticBallsInArray;
        while (cardinal(ball)<=cardinal(endball)) do begin
          dotProduct :=trunc(sqrt(vecDotSelf(vecSub(ball.pos,structurePoint))))+
                       ball.r;
          if dotProduct>innerCircelRadius then innerCircelRadius:= dotProduct;
          inc(ball);
        end;
      end;
    end;
  end;
end;
procedure TForm1.resetInnerCircelRadius;
begin
  structurePoint.x:=0;
  structurePoint.y:=0;
  innerCircelRadius:=balls.getStaticBall(0).r;
end;
procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
  useStandardRadius:=true;
  allMoving:=false;
  newBallR:=RadiusBall;

  spMinX:=0;
  spMaxX:=0;
  spMinY:=0;
  spMaxY:=0;

  balls:=TBallList.Create;
  with balls.createStaticBall^ do begin
    pos.x:=0;
    pos.y:=0;
    r:=RadiusBall;
  end;
  resetInnerCircelRadius;

  doubleBuffer:=TBitmap.Create;
  doubleBuffer.Width:=PaintBox1.Width;
  doubleBuffer.Height:=PaintBox1.Height;

  xmove:=doubleBuffer.Width div 2;
  ymove:=doubleBuffer.Height div 2;
  sizeFactor:=100;

  //Cursor laden
  for i:=1 to 9 do
    screen.Cursors[i]:=LoadCursor(HINSTANCE, MAKEINTRESOURCE(i));
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  balls.free;
  doubleBuffer.free;
end;

procedure TForm1.drawBalls(const size,xmove,ymove:integer;output:TBitmap;numbers:boolean);
procedure drawDirArrow(x,y:integer;const dir:TVector2Float;dirlength:single);
var tempdir:TVector2Float;
    dx,dy:integer;
begin
  output.Canvas.MoveTo(x,y);
  x:=x+trunc(dir.x*dirLength);
  y:=y+trunc(dir.y*dirLength);
  output.Canvas.LineTo(x,y);
  tempdir:=vecRot(dir,135*pi/180);
  dx:=trunc(tempdir.x*dirLength) div 2;
  dy:=trunc(tempdir.y*dirLength) div 2;
  output.Canvas.MoveTo(x,y);
  output.Canvas.LineTo(x+dx,y+dy);
  output.Canvas.MoveTo(x,y);
  output.Canvas.LineTo(x-dy,y+dx);
end;
var i,x,y:integer;
    ballMove:TMovableBall;
    ballStatic:TStaticBall;
    temp:single;
    kolPos:TVector2Int;
    arrowLength:single;
begin
  arrowLength:=max(10,70*size /100);
  Label2.Caption:='Angezeigte Kugeln: '+IntToStr(balls.countStatic)+ ' feste ';
  Label12.Caption:=IntToStr(balls.countMovable)+' bewegliche';;
  with output do begin
    canvas.brush.Color:=clWhite;
    canvas.brush.Style:=bsSolid;
    Canvas.Rectangle(-10,-10,Width+10,Height+10);
    canvas.pen.Color:=clBlack;
    canvas.pen.style:=psSolid;
    if size>40 then canvas.pen.Width:=3
    else if size>10 then canvas.pen.Width:=2
    else if size>5 then canvas.pen.Width:=1
    else canvas.pen.style:=psClear;
    if size>5 then canvas.brush.Color:=clGray
    else begin
      canvas.brush.Color:=clBlack;
    end;
  end;
  //Feste
  for i:=0 to balls.countStatic-1 do begin
    ballStatic:=TStaticBall(balls.getStaticBall(i));
    with output.Canvas do begin
      //Zeichnen
      x:=ballStatic.pos.x*size div 100+xmove;
      y:=ballStatic.pos.y*size div 100+ymove;
      Ellipse(x-ballStatic.r*size div 100,y-ballStatic.r*size div 100,
              x+ballStatic.r*size div 100,y+ballStatic.r*size div 100);
      if numbers then TextOut(x-textwidth(inttostr(i)) div 2,
                              y-textheight(inttostr(i)) div 2,inttostr(i));
    end;
  end;
  //Bewegliche
  output.canvas.pen.Width:=1;
  canvas.pen.style:=psSolid;
  for i:=0 to balls.countMovable-1 do begin
    ballMove:=TMovableBall(balls.getMovableBall(i));
    with output.Canvas do begin
      //Zeichnen
      x:=ballMove.kollisionPos.x*size div 100+xmove;
      y:=ballMove.kollisionPos.y*size div 100+ymove;
      brush.Style:=bsClear;
      Ellipse(x-ballMove.r*size div 100,y-ballMove.r*size div 100,
              x+ballMove.r*size div 100,y+ballMove.r*size div 100);

      x:=trunc((ballMove.pos.x+ballMove.dir.x*ballMove.currenttime))*size div 100+xmove;
      y:=trunc((ballMove.pos.y+ballMove.dir.y*ballMove.currenttime))*size div 100+ymove;
      brush.Color:=clGray;
      Ellipse(x-ballMove.r*size div 100,y-ballMove.r*size div 100,
              x+ballMove.r*size div 100,y+ballMove.r*size div 100);
      drawDirArrow(x,y,ballMove.dir,max(arrowLength,ballMove.r*size div 100));
      if numbers then TextOut(x-textwidth(inttostr(i)) div 2,
                              y-textheight(inttostr(i)) div 2,inttostr(i));

    end;
  end;
  with output.canvas do begin
    if creatingNewBall then begin
      brush.Style:=bsClear;
      Ellipse(newBallX-newBallR*size div 100,newBallY-newBallR*size div 100,
              newBallX+newBallR*size div 100,newBallY+newBallR*size div 100);
      drawDirArrow(newBallX,newBallY,newBallDir,max(arrowLength,newBallR*size div 100));
      calculateKollision(newBallDir,newBallPos,newBallR,temp,kolPos);
      if temp<1e30 then 
      Ellipse(kolPos.x*size div 100+xmove-newBallR*size div 100,kolPos.y*size div 100+ymove-newBallR*size div 100,
              kolPos.x*size div 100+xmove+newBallR*size div 100,kolPos.y*size div 100+ymove+newBallR*size div 100);
    end;

    //Kreis um die Struktur zeichnen
    brush.Style:=bsClear;
    pen.Width:=3;
    x:=trunc((structurePoint.x*size) /100)+xmove;
    y:=trunc((structurePoint.y*size) /100)+ymove;
    pen.Color:=clSilver;
    Ellipse(x-(innerCircelRadius*size) div 100,y-(innerCircelRadius*size) div 100,
            x+(innerCircelRadius*size) div 100,y+(innerCircelRadius*size) div 100);

    if allMoving then Draw(PaintBox1.Width div 2-7,PaintBox1.Height div 2-7, SpeedButton5.Glyph);
  end;
end;
procedure TForm1.drawBallsDefault;
begin
  drawBalls(sizeFactor,xmove,ymove,doubleBuffer,CheckBox3.Checked);
  PaintBox1.Canvas.Draw(0,0,doubleBuffer);
end;

procedure TForm1.updateBalls;
var i,j:integer;
    ball,ball2:TMovableBall;
    x,y:integer;
    window:TRect; //Sichtbarer Ausschnitt der Kugelanordnung
    kollision:boolean;
begin
  window.Left:=-xmove*100 div sizeFactor;
  window.top:=-ymove*100 div sizeFactor;
  window.right:=(-xmove+doubleBuffer.width)*100 div sizeFactor;
  window.bottom:=(-ymove+doubleBuffer.Height)*100 div sizeFactor;
  kollision:=false;
  for i:=balls.countMovable-1 downto 0 do begin
    //Berechnen
    ball:=balls.getMovableBall(i);
    //Ball bewegen
    ball.currenttime:=ball.currenttime+SpinEdit3.Value;
    if (ball.currenttime>ball.kollisionTime)or //Über dem Kollisionspunkt hinaus
        (KugelTeleportation.Checked and (ball.currenttime>3*SpinEdit3.Value)and
        (ball.kollisionTime<1e34)) then
      ball.currenttime:=ball.kollisionTime; //Ball anhalten
    //Position berechnen
    ball.currentPos.x:=ball.pos.x+trunc(ball.dir.x*ball.currenttime);
    ball.currentPos.y:=ball.pos.y+trunc(ball.dir.y*ball.currenttime);

    if ball.currenttime=ball.kollisionTime then begin
      //Als unbeweglich markiern
      ball.pos.x:=ball.currentPos.x;
      ball.pos.y:=ball.currentPos.y;
      balls.convertMovableToStatic(i);
      updateStructurePos(balls.getStaticBall(balls.countStatic-1));
      kollision:=true;
      continue;
    end;

    if (ball.kollisionTime>1e34) then begin//kollidiert nie
      x:=trunc((ball.pos.x+ball.dir.x*ball.currenttime));
      y:=trunc((ball.pos.y+ball.dir.y*ball.currenttime));
      if ((x<window.Left-ball.r) or (x>window.right+ball.r)or //und unsichtbar
       (y<window.top-ball.r) or (y>window.bottom+ball.r)) then begin
         balls.deleteMovableBall(i);
         continue;
      end;
    end;

    //Kollisionserkennung:
  end;
  for i:=balls.countMovable-1 downto 0 do begin
    j:=balls.countMovable-1;
    while (j>i) do begin
      ball:=balls.getMovableBall(i);
      ball2:=balls.getMovableBall(j);
      if vecDotSelf(vecSub(ball.currentPos,ball2.currentPos))<=
        4*RadiusBall*RadiusBall then begin
          ball.pos:=ball.currentPos;
          ball2.pos:=ball2.currentPos;
          balls.convertMovableToStatic(j);
          balls.convertMovableToStatic(i);
          updateStructurePos(balls.getStaticBall(balls.countStatic-1));
          updateStructurePos(balls.getStaticBall(balls.countStatic-2));
          kollision:=true;
          break;
      end;
      dec(j);
    end;
  end;

  //Bei einer Kollision zwischen beweglichen Kugel, alle Kollisionszeitpunkte
  //mit festen Kugel neu berechnen, da vorher bewegliche zu festen geworden sind
  //und damit oben bei einer Kollision mit einer Dritten nicht berücktsichtigt
  //wurden
  if kollision then
    for i:=balls.countMovable-1 downto 0 do begin
      ball:=balls.getMovableBall(i);
      calculateKollision(ball.dir, ball.pos,ball.r,ball.kollisionTime,ball.kollisionPos)

    end;

  drawBallsDefault;
end;
procedure TForm1.PaintBox1Paint(Sender: TObject);
begin
  updateBalls;
end;


procedure TForm1.PaintBox1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if (button =mbLeft) then begin//CHANGEIT
    if not creatingNewBall then
      if useStandardRadius then
        addUserBall((x-xmove)*100 div sizeFactor,(y-ymove)*100 div sizeFactor,makeVector(0.0,0),RadiusBall)
       else
        addUserBall((x-xmove)*100 div sizeFactor,(y-ymove)*100 div sizeFactor,makeVector(0.0,0),random(50)+10);
    creatingNewBall:=false;
    updateBalls;
  end else if button=mbRight then begin
    creatingNewBall:=true;
    newBallX:=x;
    newBallY:=y;
    drawBallsDefault;
  end;
end;

procedure TForm1.Timer1Timer(Sender: TObject);
begin
  if (balls.countMovable>0) then updateBalls;
end;

procedure TForm1.FormResize(Sender: TObject);
begin
  doubleBuffer.Width:=PaintBox1.Width;
  doubleBuffer.Height:=PaintBox1.Height;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,startcount,failed:integer;
    xtemp,ytemp:integer;
    minR,maxR:integer;
    winkelGrad:integer;
    winkelBogen:single;
    cos,sin:extended;
    ball:TMovableBall;
    time:cardinal;
begin
  Randomize;
  //Alle anderen löschen
  if CheckBox2.Checked then begin
    for i:=balls.countMovable-1 downto 0 do balls.deleteMovableBall(i);
    for i:=balls.countstatic-1 downto 1 do balls.deleteStaticBall(i);
    spMinX:=0;
    spMaxX:=0;
    spMinY:=0;
    spMaxY:=0;
    resetInnerCircelRadius;
  end;
  {$ifdef td}  debug:=0;  {$endif}

  startcount:=SpinEdit2.Value;
  i:=balls.countStatic;
  failed:=0;
  time:=GetTickCount;
  minR:=SpinEdit5.Value;
  maxR:=SpinEdit6.Value;
  while i<startcount do begin
     winkelGrad:=rrandom(0,360000); //1000 Schritte pro Grad
     winkelBogen:=winkelGrad*pi/180000;
     SinCos(winkelBogen,cos,sin);
     xtemp:=trunc(2*(innerCircelRadius+radiusBall)*cos+structurePoint.x);
     ytemp:=trunc(2*(innerCircelRadius+radiusBall) *sin+structurePoint.y);
     if useStandardRadius then
       addBall(xtemp,ytemp,RadiusBall)
      else
       addBall(xtemp,ytemp,rrandom(minR,maxR));
     ball:=balls.getMovableBall(balls.countMovable-1);
     if ball.kollisionTime<1e34 then begin
       ball.pos:=ball.kollisionPos;
       balls.convertMovableToStatic(balls.countMovable-1);
       updateStructurePos(balls.getStaticBall(balls.countStatic-1));
       inc(i);
       if i and 1023 =0then 
         ProgressBar1.Position:=i*200 div startcount;
     end else begin
       inc(failed);
       balls.deleteMovableBall(balls.countMovable-1);
     end;
  end;
  ProgressBar1.Position:=200;
  StatusBar1.Panels[0].Text:='Muster mit '+INtToStr(i)+' Kugel erzeugt. Benötigte Zeit: '+IntToStr((gettickcount-time) div 1000)+ ' Sekunden. Nicht kollidierte Kugeln: '+Inttostr(failed);
  {$ifdef td}showmessage(inttostr(debug));  {$endif}


  Button3.Click;
end;

procedure TForm1.SpeedButton2MouseDown(Sender: TObject;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  selectedMoveButton:=sender as tspeedbutton;
  timer2.Enabled:=true;
  Timer2Timer(timer2);
end;

procedure TForm1.SpeedButton2MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  timer2.Enabled:=false;

end;

procedure TForm1.Timer2Timer(Sender: TObject);
var inv:integer;
    cursor:TPoint;
    dx,dy:integer;
    c,d:integer;
begin
  if CheckBox1.Checked then inv:=-1
  else inv:=1;
  if allMoving then begin
    GetCursorPos(cursor);
    dx:=(amsX-cursor.x) div 5;
    dy:=(amsY-cursor.y) div 5;
    if (dx>1) then c:=0
    else if (dx<-1) then c:=2
    else c:=1;
    if (dy>1) then d:=0
    else if (dy<-1) then d:=2
    else d:=1;
    screen.Cursor:=d*3+c+1;
  end else begin
    if selectedMoveButton.Left<SpeedButton5.Left then dx:=-20*inv
    else if selectedMoveButton.Left>SpeedButton5.Left then dx:=xmove+20*inv
    else dx:=0;
    if selectedMoveButton.top<SpeedButton5.top then dy:=-20*inv
    else if selectedMoveButton.top>SpeedButton5.top then dy:=20*inv
    else dy:=0;
  end;
  xmove:=xmove+dx*inv;
  ymove:=ymove+dy*inv;
  updateBalls;
end;

procedure TForm1.SpinEdit1Change(Sender: TObject);
begin
  if spinedit1.text='' then exit;
  sizeFactor:=strtointdef(SpinEdit1.text,50);
  updateBalls;
end;

procedure TForm1.SpeedButton5MouseDown(Sender: TObject;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
var rect:trect;
begin
  allMoving:=true;
  rect.TopLeft:=ClientToScreen(point(PaintBox1.left,PaintBox1.top));
  rect.BottomRight:=ClientToScreen(point(PaintBox1.left+PaintBox1.width,PaintBox1.top+PaintBox1.Height));
  ClipCursor(@rect);
  screen.Cursor:=crSizeAll;
  amsx:=(rect.Left+rect.Right)div 2;
  amsy:=(rect.Top+rect.Bottom)div 2;
  SetCursorPos(amsX,amsY);
  Timer2.Enabled:=true;
end;

procedure TForm1.SpeedButton5MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  Timer2.Enabled:=false;
  allMoving:=false;
  ClipCursor(nil);
  screen.Cursor:=crDefault;
  updateBalls;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  xmove:=PaintBox1.Width div 2-trunc((structurePoint.x*sizeFactor) /100);
  ymove:=PaintBox1.height div 2-trunc((structurePoint.y*sizeFactor) /100);
  updateBalls;
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
  SpinEdit1.Value:=max(1,min(PaintBox1.Width*50 div innerCircelRadius,PaintBox1.Height *50div innerCircelRadius));
  Button2.Click;
end;

procedure TForm1.Button4Click(Sender: TObject);
begin
  if SaveDialog1.Execute then Edit1.Text:=SaveDialog1.FileName;
end;

procedure TForm1.Button5Click(Sender: TObject);

var save:TBitmap;
    memory:int64;
begin
  //Benötigter Speicherplatz (width*height), halbiert da 4 Bit-Format
  memory:=sqr(innerCircelRadius*2 * SpinEdit4.Value div 100) div 2;
  //Arbeitsspeicher
  if getfreeMem<memory then begin
    ShowMessage('Leider ist nicht genug Arbeitsspeicher für die angeforderte Aktion verfügbar. Bitte verringern Sie die Größe.');
    exit;
  end;
  //Festplatte
  if getFreeDiskSpace(edit1.text)<memory then begin
    ShowMessage('Leider ist nicht genug Festplattenspeicher für die angeforderte Aktion verfügbar. Bitte verringern sie die Größe, wählen Sie einen anderen Speicherort, oder löschen sie einige Dateien.');
    exit;
  end;

  save:=TBitmap.create;
  save.PixelFormat:=pf4bit;
  save.Width:=innerCircelRadius*2 * SpinEdit4.Value div 100;
  save.Height:=save.Width;
  try
    drawBalls(SpinEdit4.Value,(innerCircelRadius -structurePoint.x )*SpinEdit4.Value div 100,(innerCircelRadius-structurePoint.y)*SpinEdit4.Value div 100,save,false);
    save.SaveToFile(edit1.text);
  finally
    save.free;
  end;
end;

procedure TForm1.PaintBox1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
  if creatingNewBall then begin
    newBallDir:=vecNorm(makeVector(x-newBallX,y-newBallY));
    newBallPos.x:=(newBallX-xmove)*100div sizeFactor;
    newBallPos.y:=(newBallY-ymove)*100div sizeFactor;
    if not useStandardRadius then
      newBallR:=min(250,max(5,trunc(sqrt(sqr(x-newBallX)+sqr(y-newBallY)))*100div sizeFactor));

    drawBallsDefault;
  end;
end;

procedure TForm1.PaintBox1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if creatingNewBall and not ((ssLeft in shift)or(button=mbLeft)) then
    if useStandardRadius then
      addUserBall(newBallPos.x,newBallPos.y,newBallDir,RadiusBall)
     else
      addUserBall(newBallPos.x,newBallPos.y,newBallDir,newBallR); //changeit
  creatingNewBall:=false;
  drawBallsDefault;
end;

procedure TForm1.CheckBox4Click(Sender: TObject);
begin
  useStandardRadius:=not CheckBox4.Checked;
end;

//Sucht einen möglichst kleinen Kreis der alle Kugeln enthält.
//Dazu wird ein Kreist, der alle Kugeln enthält, langsam geschrumpft
procedure TForm1.findOptimalCenterAndRadius(out middle:TVector2Int;out radius:integer);
  procedure findFarestBall(const pos:TVector2Ext; out distance:extended;out ballnr:integer);
  var i:integer;
      ball,endball:TStaticBall;
      farer:boolean;
      oldRadius,oldSqrDistance:extended;
      newRadius,newSqrDistance:extended;
      ltemp:extended;
  begin
    distance:=0;
    ballnr:=-1;
    oldSqrDistance:=0;
    oldRadius:=0;
    i:=0;
    while i<=balls.countStatic-1 do begin
      ball:=balls.getStaticBall(i);
      if i+StaticBallsInArray<balls.countStatic then
        endball:=balls.getStaticBall(i+StaticBallsInArray-1)
       else
        endball:=balls.getStaticBall(balls.countStatic-1);
    //  i:=i+StaticBallsInArray;
      while (cardinal(ball)<=cardinal(endball)) do begin
        //Hier drin werden alle Kugeln durchlaufen
        newSqrDistance :=vecDotSelf(vecSub(toExtVector(ball.pos),pos));
        newRadius:=ball.r;
        //Der folgende Teil berechnet:
        farer := oldRadius+sqrt(oldSqrDistance)<newRadius+sqrt(newSqrDistance);
        //Dabei wird eine ähnliche Methode zur Wurzelvermeidung wie in
        //calculateKollision benutzt (WVII)
{        farer:=false;
        if oldRadius>= newRadius then begin
          if oldSqrDistance >= newSqrDistance then farer:=false
          else begin
            ltemp:=sqr(newRadius - oldRadius) - oldSqrDistance - newSqrDistance;
            if abs(ltemp)<1e2000 then
              if ltemp>= 0 then  farer:=false
              else farer:=ltemp*ltemp>4*oldRadius*newRadius;
          end;
        end else begin
          if oldSqrDistance > newSqrDistance then begin
            ltemp:=sqr(newRadius - oldRadius) - oldSqrDistance - newSqrDistance;
            if abs(ltemp)<1e2000 then
              if ltemp>= 0 then farer:=true
              else  farer:=ltemp*ltemp>=4*oldRadius*newRadius;
          end else farer:=true; //Fall 2
        end;}
        if farer then begin
          oldSqrDistance:=newSqrDistance;
          oldRadius:=newRadius;
          ballnr:=i;
        end;
        //Schleifenende
        inc(ball);
        inc(i);
      end;
    end;
    distance:=trunc(sqrt(oldSqrDistance))+oldRadius;
  end;

  //Testet, ob im übergebenen Kreis wirklich aller Kugeln sind
  function isCenterAndRadiusOK(const center: TVector2Ext; const radius: extended):boolean;
  var distance:extended;temp:integer;
  begin
    findFarestBall(center,distance,temp);
    result:=distance<=radius+1;
      if (radius<0) or (radius>400000) then begin
      MessageBeep(0);
      //sleep(1000);
        exit;
      end;
    if Result then
      PaintBox1.Canvas.pen.Color:=clGreen
     else
      PaintBox1.Canvas.pen.Color:=clRed;
   PaintBox1.Canvas.brush.style:=bsClear;
 //   PaintBox1.Canvas.Ellipse(trunc((center.x-distance)*sizeFactor) div 100 + xmove,trunc((center.y-distance)*sizeFactor) div 100 +ymove,trunc(center.x+distance)*sizeFactor div 100 +xmove,trunc(center.y+distance)*sizeFactor div 100+ymove);
    PaintBox1.Canvas.Ellipse(trunc((center.x-radius)*sizeFactor) div 100 + xmove,trunc((center.y-radius)*sizeFactor) div 100 +ymove,trunc(center.x+radius)*sizeFactor div 100 +xmove,trunc(center.y+radius)*sizeFactor div 100+ymove);
    PaintBox1.Canvas.Ellipse(trunc(center.x)*sizeFactor div 100-1 + xmove,trunc(center.y*sizeFactor) div 100-1 +ymove,trunc(center.x*sizeFactor) div 100+1 +xmove,trunc(center.y*sizeFactor) div 100++1 +ymove);
     // sleep(1000);
  end;
procedure markball(const ball:TStaticBall);
begin
   PaintBox1.Canvas.brush.style:=bsClear;
      PaintBox1.Canvas.pen.Color:=clBlue;
    PaintBox1.Canvas.Ellipse((ball.pos.x-ball.r)*sizeFactor div 100 + xmove,
     (ball.pos.y-ball.r)*sizeFactor div 100 + ymove,(ball.pos.x+ball.r)*sizeFactor div 100 + xmove,
     (ball.pos.y+ball.r)*sizeFactor div 100 + ymove);
end;
var
    ballR1,ballR2,ballR3:TStaticBall; //Erste, 2te und 3te Kugel auf dem Kreisrand
    ballnr:integer;
    distance:extended;
    dirtemp:single;
    t,newt,tempT1,tempT2,tempTDiv:single;
    dir,pos,start:TVector2Ext;
    sqrLen:integer;
    i:integer;                 //Schleifenindex
    ball,endball:TStaticBall;  //Kugeln für die Schleife
begin
  PaintBox1.Canvas.pen.width:=1;
  //Zuerst wird der Radius eines Kreises um den Nullpunkt genau so gesetzt, dass
  //eine Kugel berührt wird, und alle Kugeln innerhalb des Kreises sind.
  findFarestBall(makeVectorExt(0,0),distance,ballnr);
  if ballnr=-1 then begin
    middle:=makeVector(0,0);
    radius:=0;
    exit;
  end;
  ballR1:=balls.getStaticBall(ballnr);
  markball(ballR1);
  //Anschließend wird der Kreis so bewegt, dass jede andere Kugel gleichzeitig
  //mit der zu erst berührten berührt wird.
  //Der kleinste, daher der, der am weitesten om Nullpunkt entfernt ist,
  //der dadurch entstehenden Kreise der auch alle anderen Kugel enthält wird
  //genommen.

  //Also:
  dir:=vecNorm(toExtVector(ballr1.pos));
  //gesucht t so dass:
  //distance(t * dir, ballr1.pos) + ballr1.r =
  //distance(t * dir, ballr2.pos) + ballr2.r
  //und 0 < t < length(ballr1.pos)
  start:=makevectorext(0,0);
  ballr2:=nil;
  t:=0;
  sqrLen:=vecDotSelf(ballr1.pos);
  i:=0;
  while i<=balls.countStatic-1 do begin
    ball:=balls.getStaticBall(i);
    if i+StaticBallsInArray<balls.countStatic then
      endball:=balls.getStaticBall(i+StaticBallsInArray-1)
     else
      endball:=balls.getStaticBall(balls.countStatic-1);
    i:=i+StaticBallsInArray;
    while (cardinal(ball)<=cardinal(endball)) do begin
      //Hier drin werden alle Kugeln durchlaufen (siehe Gleichung 1)
      if (ball<>ballr1) then begin
         newt := abs( 0.5*(
             ABS(ballr1.r - ball.r)*sqrt(
               (sqr(ballr1.r - ball.r) - sqr(x1 - x2) - sqr(y1 - y2))*
               (
                  sqr(dir.x)*(sqr(ballr1.r - ball.r) - sqr(x1 - x2) - sqr(y1 - y2))
                  + 4*dir.x*dir.y*(x1*y2 + x2*y1)
                  + dir.y^2*(sqr(ballr1.r - ball.r) - sqr(x1 + x2) - sqr(y1 - y2))
               )
             )
             - dir.x*((x1 + x2)*sqr(ballr1.r - ball.r) + (sqr(x1) - sqr(x2) + sqr(y1) - sqr(y2))*(x2 - x1))
             - dir.y*((y1 + y2)*sqr(ballr1.r - ball.r) + (sqr(x1) - sqr(x2) + sqr(y1) - sqr(y2))*(y2 - y1))
           )
           /
           (
             sqr(ballr1.r - ball.r) * (sqr(dir.x)* + sqr(dir.y))
             - sqr(dir.x*(x1 - x2) - dir.y*(y1 - y2))
           ));
        pos:=vecmul(dir,newt);
        if (newt>t) and(newt*newt<sqrLen) and isCenterAndRadiusOK(pos,vecDistance(pos,toExtVector(ball.pos))+ball.r) then begin
          ballR2:=ball;
          t:=newt;
        end;
      end;
      //Schleifenende
      inc(ball);
    end;
  end;
  if ballr2=nil then begin
    middle:=ballr1.pos;
    radius:=ballr1.r;
    exit;
  end;
  markball(ballR2);

  //Ballr1, und ballr2 liegen auf dem Kreisrand, deshalb liegt der Mittelpunkt
  //des Kreises auf der Mittelsenkrechten zu der Stecke der Mittelpunkte der
  //beiden Kugeln
  dir:=toExtVector(vecNorm(vecSub(ballr2.pos,ballr1.pos)));
  //Richtung um 90° drehen
  dirtemp:=dir.x;
  dir.x:=-dir.y;
  dir.y:=dirtemp;

  //Startpunkt der Mittelsenkrechten berechnen (g2)
  start:=vecAdd(toExtVector(ballr1.pos),
                vecMul(
                  vecNorm(
                   toExtVector(vecSub(ballr2.pos,ballr1.pos))
                  ),
                  (vecDistance(ballr1.pos,ballr2.pos)-ballr1.r+ballr2.r)/2
                )
         );

  //Überprüfen ob der Mittelsenkrechtenstartpunkt als Mittelpunkt von dem gesamten
  //Kreis geeignet ist
  if isCenterAndRadiusOK(start,vecDistance(toExtVector(ballr1.pos),start)+ballr1.r) then begin
    //Einen kleineren Kreis kann es nicht geben, da dann nicht alle Kugel drin
    //wären
    middle:=vecTrunc(start);
    radius:=round(vecDistance(toExtVector(ballr1.pos),start))+ballr1.r;
    exit;
  end;

  ballr3:=nil;
  t:=1e30;
  i:=0;
  while i<=balls.countStatic-1 do begin
    ball:=balls.getStaticBall(i);
    if i+StaticBallsInArray<balls.countStatic then
      endball:=balls.getStaticBall(i+StaticBallsInArray-1)
     else
      endball:=balls.getStaticBall(balls.countStatic-1);
    i:=i+StaticBallsInArray;
    while (cardinal(ball)<=cardinal(endball)) do begin
      //Hier drin werden alle Kugeln durchlaufen
      if (ball<>ballr1)and(ball<>ballr2) then begin
        //Jetzt muss ein t gefunden werden, so dass:
        //distance(t * dir + start, ballr1.pos) + ballr1.r  =
        //distance(t * dir + start, ball.pos) + ball.r

        //Mit einem Matheprogramm hab ich diese Gleichung nach t aufgelöst,
        //und dabei diese zwei Riesenlösungen gefunden:
tempT1:=(ballr1.r - ball.r)
        * sqrt(
          (
            sqr(ballr1.pos.x-ball.pos.x) 
            + sqr(ballr1.pos.y-ball.pos.y) 
            - sqr(ball.r-ballr1.r)
          )
          * ( 
            sqr(dir.x)
            *(
              - 2*ballr1.pos.x*ball.pos.x 
              + 2*ballr1.pos.y*ball.pos.y 
              - 4*start.y * (
                ballr1.pos.y
                + ball.pos.y
                - start.y
              )
              
              + vecDot(ballr1.pos,ballr1.pos)
              + vecDot(ball.pos,ball.pos)
              - sqr(ballr1.r-ballr1.r)
           )
           - 4*dir.x*dir.y*(
              ballr1.pos.x*(ball.pos.y - start.y)
              + ballr1.pos.y*(ball.pos.x - start.x)
              - ball.pos.x*start.y
              - start.x*(ball.pos.y - 2*start.y)
           )
           + sqr(dir.y)*(
              2*ballr1.pos.x*ball.pos.x
              - 2*ballr1.pos.y*ball.pos.y
              - 4*start.x * (
                ballr1.pos.x
                + ball.pos.x
                - start.x
              )

              + vecDot(ballr1.pos,ballr1.pos)
              + vecDot(ball.pos,ball.pos)
              - sqr(ballr1.r-ballr1.r)
              )
          )
        );
        tempT2:=dir.x*(ballr1.pos.x*ballr1.pos.x*ballr1.pos.x - sqr(ballr1.pos.x)*(ball.pos.x + 2*start.x) + ballr1.pos.x*(sqr(ballr1.pos.y) - 2*ballr1.pos.y*start.y - sqr(ball.pos.x) + 4*ball.pos.x*start.x - sqr(ball.pos.y) + 2*ball.pos.y*start.y - sqr(ballr1.r - ball.r)) - sqr(ballr1.pos.y)*ball.pos.x + 2*ballr1.pos.y*ball.pos.x*start.y + ball.pos.x*ball.pos.x*ball.pos.x - 2*sqr(ball.pos.x)*start.x + ball.pos.x*(sqr(ball.pos.y) - 2*ball.pos.y*start.y - sqr(ballr1.r - ball.r)) + 2*start.x*sqr(ballr1.r - ball.r))
+
dir.y*(sqr(ballr1.pos.x)*(ballr1.pos.y - ball.pos.y) + 2*ballr1.pos.x*start.x*(ball.pos.y - ballr1.pos.y) + ballr1.pos.y*ballr1.pos.y*ballr1.pos.y - sqr(ballr1.pos.y)*(ball.pos.y + 2*start.y) - ballr1.pos.y*(sqr(ball.pos.x) - 2*ball.pos.x*start.x + sqr(ball.pos.y) -
4*ball.pos.y*start.y + sqr(ballr1.r - ball.r)) + sqr(ball.pos.x)*ball.pos.y - 2*ball.pos.x*ball.pos.y*start.x + ball.pos.y*ball.pos.y*ball.pos.y - 2*sqr(ball.pos.y)*start.y - ball.pos.y*sqr(ballr1.r - ball.r) + 2*start.y*sqr(ballr1.r -
ball.r));

tempTDiv:=(2*(sqr(dir.x)*(sqr(ballr1.pos.x) - 2*ballr1.pos.x*ball.pos.x + sqr(ball.pos.x) - sqr(ballr1.r - ball.r)) + 2*dir.x*dir.y*(ballr1.pos.x - ball.pos.x)*(ballr1.pos.y - ball.pos.y) +
sqr(dir.y)*(sqr(ballr1.pos.y) - 2*ballr1.pos.y*ball.pos.y + sqr(ball.pos.y) - sqr(ballr1.r - ball.r))));



        newt:=(tempT1+tempT2)/tempTDiv;
          pos:=vecadd(vecmul(dir,newt),start);
          if (abs(newt)<abs(t)) and isCenterAndRadiusOK(pos,vecDistance(pos,toExtVector(ball.pos))+ball.r) then begin
            ballR3:=ball;
            t:=newt;
          end;
        newt:=-(tempT1-tempT2)/tempTDiv;
          pos:=vecadd(vecmul(dir,newt),start);
          if (abs(newt)<abs(t)) and isCenterAndRadiusOK(pos,vecDistance(pos,toExtVector(ball.pos))+ball.r) then begin
            ballR3:=ball;
            t:=newt;
          end;
      end;
      //Schleifenende
      inc(ball);
    end;
  end;
  if ballr3=nil then exit;
  markball(ballR3);
  pos:=vecadd(vecmul(dir,t),start);
  middle:=vecTrunc(pos);
  radius:=round(vecDistance(pos,toExtVector(ballr3.pos)))+ballr3.r;
end;
procedure TForm1.Button8Click(Sender: TObject);
var rad:integer;
    mid:TVector2Int;
begin
  findOptimalCenterAndRadius(mid,rad);
  PaintBox1.Canvas.pen.width:=3;
  PaintBox1.Canvas.pen.Color:=clBlack;
  PaintBox1.Canvas.brush.style:=bsClear;
  PaintBox1.Canvas.Ellipse((mid.x-rad)*sizeFactor div 100 + xmove,(mid.y-rad)*sizeFactor div 100 +ymove,(mid.x+rad)*sizeFactor div 100 +xmove,(mid.y+rad)*sizeFactor div 100 +ymove);
  PaintBox1.Canvas.Ellipse((mid.x)*sizeFactor div 100 + xmove-1,mid.y*sizeFactor div 100-1 +ymove,mid.x*sizeFactor div 100+1 +xmove,mid.y*sizeFactor div 100+1 +ymove);
end;

end.
