Ellipsenalgo aus Formelsammlung kreieren

[Renate Schaaf]

Also, Ihr wollt z.B. eine Ellipse aus Smileys zeichnen, und dabei sollen die immer den gleichen Abstand haben?
Dazu braucht man eine variable Schrittweite. So ganz krieg ichs nicht hin für die Extremfälle, da brauchts eine bessere Schrittweitensteuerung, und das Schließen der Ellipse ist auch ein Problem. Sh. Anhang.

Für die Schrittweite braucht man die Formel für die Länge einer Kurve, nicht die explizite Formel, man muss nur wissen, wie die in Abhängigkeit vom Parameter t wächst:

(x(t),y(t)) : Kurve l(t): Länge der Kurve.

dl/dt = sqrt((x'(t))² + (y'(t))²) (Ableitungen)

Wenn man jetzt so tut, als wäre dl kein Differential sondern ein Abstand, und dt ein t-Schritt, dann möchte man dl konstant haben. Die Konstante nenne ich mal dist, wie Distanz. Das gibt

dt = dist/sqrt((x'(t))² + (y'(t))²)

Für die Ellipse: x(t) = xm + a*cos(t) y(t) = ym + b*sin(t) x'(t) = -a*sin(t) = -a/b*(y-ym) y(t) = b*cos(t) = b/a*(x-xm)
(Achtung: t ist hier in radian, sonst stimmen die Ableitungen nicht)

dt = dist/sqrt(sqr(a/b*(y-ym))+sqr(b/a*(x-xm))

Hier ist der Code für mein Testprogramm:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var xm,ym,x,y,t,dt,a,b, dist: double;
    xp,yp: integer;
begin
  Image1.Picture.Bitmap.SetSize(image1.width,image1.height);
  Image1.Picture.bitmap.Canvas.Brush.Color:=clblack;
  Image1.picture.bitmap.canvas.FillRect(Image1.clientrect);
  xm:=image1.Width/2; ym:=image1.Height/2;
  a:=Spinedit1.Value; b:=Spinedit2.Value;
  dist:=Spinedit3.Value;
  t:=0;
  while t<2*Pi do
  begin
    x:=a*cos(-t);
    y:=b*sin(-t);
    xp:=round(xm+x);
    yp:=round(ym+y);
    image1.Picture.Bitmap.Canvas.Draw(xp-8,yp-8,image2.Picture.Graphic);
    dt:=dist/sqrt(sqr(a/b*y)+sqr(b/a*x));
    t:=t+dt;
  end;
end;

[Rollo62]

Endlich mal ein richtiger Use-Case für so eine Funktion

[Michael II]

Für Rastergrafik: Midpoint Algorithmus für Kreis und Ellipse

https://www.geeksforgeeks.org/dsa/mi...ing-algorithm/

(könnte man erweitern (stangle,endangle))

Delphi-Quellcode:

procedure DrawEllipseMidpoint(xc, yc, rx, ry: Integer);
var
  x, y: Int64;
  rx2, ry2: Int64;
  twoRx2, twoRy2: Int64;
  px, py: Int64;
  p: Int64;
begin
  x := 0;
  y := ry;

  rx2 := rx * rx;
  ry2 := ry * ry;
  twoRx2 := 2 * rx2;
  twoRy2 := 2 * ry2;

  // Region 1
  p := Round(ry2 - (rx2 * ry) + (0.25 * rx2));
  px := 0;
  py := twoRx2 * y;

  while px < py do
  begin
    // 4-fache Symmetrie
    DrawPixel(xc + x, yc + y);
    DrawPixel(xc - x, yc + y);
    DrawPixel(xc + x, yc - y);
    DrawPixel(xc - x, yc - y);

    Inc(x);
    px := px + twoRy2;

    if p < 0 then
      p := p + ry2 + px
    else
    begin
      Dec(y);
      py := py - twoRx2;
      p := p + ry2 + px - py;
    end;
  end;

  // Region 2
  p := Round(ry2 * (x + 0.5) * (x + 0.5) + rx2 * (y - 1) * (y - 1) - rx2 * ry2);
  px := twoRy2 * x;
  py := twoRx2 * y;

  while y >= 0 do
  begin
    // 4-fache Symmetrie
    DrawPixel(xc + x, yc + y);
    DrawPixel(xc - x, yc + y);
    DrawPixel(xc + x, yc - y);
    DrawPixel(xc - x, yc - y);

    Dec(y);
    py := py - twoRx2;

    if p > 0 then
      p := p + rx2 - py
    else
    begin
      Inc(x);
      px := px + twoRy2;
      p := p + rx2 - py + px;
    end;
  end;
end;

[freimatz]

Ja genau, an sowas dachte ich. Ganz ohne Wurzel, Winkel und teuren trigonometrischen Berechnungen.

[delphifan2004]

Ist ja ein ziemlich komplexes Thema, wie ich sehe.

Ich wollte jedenfalls die Ellipse aber auch den Ellipsenbogen, der nicht die vollständige Ellipse bildet.

@freimatz: da wier ja auch die vollstädige Ellipse gezeichnet. Wie sähe die Erweiterung aus auf Start und Endwinkel? Für den Ellipsenbogen, die sehe ich in diesem Quellcode noch nicht und habe auch keine Vosrstellung, wie die aussehen könnte? Ellipsenbögen braucht es in der Computergrafik für Roundrect, Arc, oder Pie.

Und wie schnell ist eigentlich der Midpoint Algorithmus?

[Michael II]

Zitat von delphifan2004:

Und wie schnell ist eigentlich der Midpoint Algorithmus?

Kannst du doch selbst testen (?).

Kommt drauf an wo du rechnen lässt und wohin du schreibst.

Wenn du den Code anschaust, dann siehst du, dass du diesen rein integer umschreiben könntest (also ohne 0.5, 0.25, round ...).
Früher waren solche integer Approximationen viel schneller als Trigo, floating point Operationen. Mit Einführung von FPUs ist der Speed Vorteil geringer geworden.

Wenn du zum Beispiel auf CPU rechnest und dann auf Grafikkarte ausgibst, dann ist dieser Teil der teure (und für alle Algos gleich).

Zu deiner Startwinkel/Endewinkel Midpoint Frage. Midpoint zeichnet in einem Quadrant und teilt diesen in zwei Regionen (in einer Region verändert sich x schneller als y in der anderen umgekehrt), restliche Punkte via Symmetrie. Du hast also insgesamt 4x2 Gebiete. Der Startwinkel definiert einen Startpunkt (StartX, StartY), welcher in eines dieser 8 Gebiete fällt. Endewinkel ähnlich. Du merkst dir in welchen Gebieten alle Punkte gemalt werden, in welchen keine Punkte gemalt werden und in welchen maximal zwei Gebieten nur ein Teil (nur ab Startx, Starty, bzw. nur bis Endex, Endey). Nur Startpunkt und Endepunkt berechnest du mit Trigo (oder wenn du ganz darauf "verzichten" willst durch Taylorreihe).