Geschwungene Linie

Gosa · Beiträge: 112

Hallo, ich würde gerne ungefähr so eine Linie Zeichnen wie man sie in Paintbrush unter bogen zeichnen findet. Ich habe aber keine Idee wie das mache. Arc ist glaub ich nicht das was ich suche... bzw. es macht bei mir nicht das was ich eigentlich haben will.

Danke

Moderiert von raziel: Topic aus Sonstiges verschoben am Mi 29.06.2005 um 16:43

BenBE · Verfasst: Mi 29.06.05 13:33

Was Du meinst, sind Bezier-Kurven.

Suche in: Delphi-Forum, Delphi-Library

BEZIER
Außerdem hat www.delphigl.com dafür ein recht gutes Tut.

Wenn Du Hilfe bei der Implementierung brauchst, einfach nochmal melden.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Gosa · Beiträge: 112

Danke hab probiert mich darüber schlau zu machen... Ich versteh jetzt auch wie die funktioniert und es ist genau das was ich suche. Ich finde aber leider dieses Tut nicht und so weis ich leider nicht wie das einfach einbinden kann. Kannst du mir dazu nochmal einen direkten link geben?

Danke

Gosa · Beiträge: 112

Habs jetzt selber gefunden: www.delphigl.com/launcher.php?em=forum

Ich hätte das aber gerne etwas anders und zwar habe ich drei Punkte. Die Kurve soll dann durch diese drei Punkte durchgehen. Bei Bezier geht die Linie ja nicht durch den einen Punkt. Wie kann ich denn das verwirklichen?

BenBE · Verfasst: Mi 29.06.05 15:38

Hab auch einen Post wiedergefunden, wo ich sowas schonmal implementiert hatte:

www.delphi-forum.de/...+zeichnen_42289.html

Ist auch mit Beispielquelltext.

Wen die Kurve durch alle drei Punkte gehen soll, dann musst Du das über eine Interpolation machen

Wenn die X-Werte eindeutig sind, geht das über folgende Funktion:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

Function Interpolate(ListX, ListY: TExtendedArray; X:Extended): Extended;
var
    I,J: Integer;
    E,F: Extended;
begin
    Result := 0;
    For I := 0 To High(ListX) do
    Begin
        E := 1;
        F := 1;
        For J := 0 To High(ListX) do
        Begin
            If I <> J Then
            Begin
                E := E * (X - ListX[J]);
                F := F * (ListX[I] - ListX[J]);
            End;
        end;
        Result := Result + E/F*ListY[I];
    end;
end;

Die Funktion Interpolate liefert dann zu einem gegebenen X-Wert den dazugehörigen Y-Wert. Dieser muss dann nur noch auf das Integer-Raster gelegt werden (z.B. mit Round oder Trunc).

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Gosa · Beiträge: 112

Danke das ist nicht genau das was ich suche aber ich weis jetzt aber was ich suche. Ich brauche eine Cubic Spline Interpolation. Vielen Danke für deine Hilfe BenBe. Wenn ich die funcion dafür fertig habe poste ich die hier...

Vielleicht hat aber einer schonmal so eine gemacht, dann könnte ich mir das ersparen. :roll:

Ganz genau brauch ich das: Parameter-Spline-Interpolation

BenBE · Verfasst: Do 30.06.05 12:00

Geht mit meiner auch, man muss nur ein paar Zeilen abändern:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

Function Interpolate(ListX, ListY: TExtendedArray; X:Extended): TPoint;
var
    I, J, N: Integer;
    E, F: Extended;
    TmpX, TmpY: Extended;
begin
    TmpX := 0;
    TmpY := 0;
    N := High(ListX);
    For I := 0 To N do
    Begin
        E := 1;
        F := 1;
        For J := 0 To N do
        Begin
            If I <> J Then
            Begin
                E := E * (X - J/N);
                F := F * (I/N - J/N);
            End;
        end;
        TmpX := TmpX + E/F*ListX[I];
        TmpY := TmpY + E/F*ListY[I];
    end;
    Result.X := Round(TmpX);
    Result.Y := Round(TmpY);
end;

Jetzt nimmt die Funktion X- und Y-Werte der Punkte entgegen und gibt für X zwischen 0 und 1 den dazugehörigen Punkt zurück.

That's it ;-)

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Kleine Bemerkung zur Numerik:

1.) Die Funktion von BenBE macht (soweit ich das überblicke) eine Polynominterpolation. Das direkte Einsetzen in die Lagrangeschen Basispolynome (wie in der Funktion von BenBE) erfordert O(N^2) Operationen. Stattdessen könnte man sich mit den Newtonschen dividierten Differenzen eine Interpolationstabelle erstellen (geht in O(N^2/2)), und könnte danach beliebig viele Interpolationspunkte in O(N) auswerten. (Mit dem gleichen Ergebnis).

2.) Spline-Funktion: Um den kubischen Spline zu berechnen, kommt man nicht daran vorbei, ein nxn Gleichungssystem zu lösen. Das ist aber in linearer Zeit O(n) möglich, da die Matrix sehr gute Eigenschaften hat (tridiagonal symmetrisch positiv definit). Das Auswerten des Splines geht in O(1). (n = Anzahl Stützpunkte)

Der Unterschied zwischen Spline<->Polynominterpolation ist, dass die Spline-Funktion nur in C2 liegt (2x stetig differenzierbar); die Polynominterpolation ist unendlich oft differenzierbar. Da ein Polynom an jeder Stelle die gesamte Information über sich selbst beinhaltet, ist der Einflussbereich einer Stützstelle sehr gross (unendlich gross): Die Polynominterpolation liefert stark oszillierende Resultate und ist deswegen für grosse Stützstellenzahl ungeeignet. Beim Spline hat man dieses Problem nicht (bzw. sehr viel weniger stark). Siehe auch Bild.

Einloggen, um Attachments anzusehen!

Gosa · Beiträge: 112

Vielen Dank BenBe funktioniert jetzt alles!

@delfiphan: Soweit bin ich noch nicht

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Gosa hat folgendes geschrieben:

Ich brauche eine Cubic Spline Interpolation.

Gosa hat folgendes geschrieben:

Vielen Dank BenBe funktioniert jetzt alles!

@delfiphan: Soweit bin ich noch nicht

Was du jetzt benützst ist kein kubischer Spline. Aber wenn das, was du hast (Polynominterpolation) reicht, ist ja gut

Gosa · Beiträge: 112

Ich habe damit jetzt ein bischen rumgespielt... und es ist doch nicht ganz das richtige. Es sieht wenn man nur drei Punkte macht richtig aus aber je mehr es werden wird es komisch ich brauche wohl doch dieses cubic spline.

BenBe hast du noch mal lust einer kleine änderung an deiner Function zu machen?

Ich habe probiert das von dieser Internetseite umzusetzen aber da kommt bei nur komischer kramms raus:
(hodgson.pi.tu-berlin...d_skript/node79.html)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:

Function KubischeSplineInterpolate(P1, P2, P3 : TPoint; X:Extended): Integer;
var
  i: Integer;
  f, fplus1, fminus1, h, hplus1,
  hminus1, c, cplus1, cminus1,
  b, d, XDifferents, Teil1,
  Teil2, Teil3, Y           : Extended;
  XArray : Array[0..2] of Integer;
  yArray : Array[0..2] of Integer;
begin
  XArray[0] := P1.X;
  XArray[1] := P2.X;
  XArray[2] := P3.X;
  YArray[0] := P1.Y;
  YArray[1] := P2.Y;
  YArray[2] := P3.Y;

  Result := 0;
  For i := 0 To 2 do
  Begin

    f := YArray[i];
    fplus1 := YArray[i + 1];
    h := XArray[i + 1] - XArray[i];

    //Polynomkoeffizenten
    If i = 0 then
    Begin
      c := 10; //f"1 / 2;
      cplus1 := 0; //Da ich nur drei Werte habe
    End
    else if i = 2 then
    Begin
      c := 10; //f"n / 2
      cplus1 := (((3 * (fplus1 - f) / h) - (3 * (f - fminus1) / hminus1)) //der normale Teil
                 - (hminus1 * cminus1) - (h * cplus1)) / (2 * (hminus1 + h));; //Da ich nur drei Werte habe
    End
    else
    Begin
      fminus1 := XArray[i - 1];
      hminus1 := XArray[i] - XArray[i - 1];
      cminus1 := 0; //f"1 / 2;
      cplus1 := 10; //f"n / 2

      If hminus1 = 0 then hminus1 := 0.00000001;

      If h = 0 then h := 0.00000001;
      c := (((3 * (fplus1 - f) / h) - (3 * (f - fminus1) / hminus1)) //der normale Teil
           - (hminus1 * cminus1) - (h * cplus1)) / (2 * (hminus1 + h));
      cplus1 := 10; //f"n / 2 //Da ich nur drei Werte habe
    End;

    If h = 0 then h := 0.00000001;

    b := ((fplus1 - f) / h) - (h * (cplus1 + 2 * c) / 3);

    d := (cplus1 - c) / (3 * h);

    XDifferents := XArray[0] - XArray[i];
    Teil1 := YArray[i] + b * XDifferents;
    Teil2 := c * sqr(XDifferents);
    Teil3 := d * sqr(XDifferents) * (XDifferents);

    Y := Teil1 + Teil2 + Teil3;
    Result := round(Y);

    FHockeyPlatz.Canvas.Pixels[round(X), round(Y)] := clred;
  End;
End;

Ich habe einfach probiert das in Delphi umzusätzen ohne zu versuchen es zu verstehen... (hab keine wirklichen ansatz wie ich den kram verstehen soll.)

iX0r · Beiträge: 34 Ubuntu D6, Lazarus

kubische splinte interpolation ist auch nicht so einfach umzusetzen, denn du hast noch verschiedene nebenbedingungen:
- an den äußeren randpunkten können deine ableitungen =0 sein (natürlicher spline)
- oder aber auch gleichs ein
- oder aber auch den not-a-knot bedingungen genügen

ich empfehle dir, einen fertigen algorithmus, der in jedem besseren buch über numerik zu finden ist, zu benutzen. ob es allerdings irgendwo hier im netz schon eine fertige unit gibt, kann ich dir leider nicht sagen. ansonsten wenn du ein rein mathematisches problem zu lösen hast, empfehle ich dir eventuell LINPACK(algorithmenimplementationen für die numerische mathematik) oder gerade im Bereich der numerik Matlab(riesenpaket mit eigener skripsprache)!

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Naja, offenbar hört mir hier niemand zu:

iX0r hat folgendes geschrieben:

ich empfehle dir, einen fertigen algorithmus, der in jedem besseren buch über numerik zu finden ist, zu benutzen.

Statt ein "besseres Buch über Numerik" zu kaufen, hab ich ein wirklich einfaches Rezept aus meiner Zusammenfassung gepostet (Link in deinem parallelen Thread über kubische Splines).

Gosa hat folgendes geschrieben:

Es sieht wenn man nur drei Punkte macht richtig aus aber je mehr es werden wird es komisch

Genau das hatte ich im Beitrag oben schon erwähnt/erklärt. Sogar mit einem Bildchen zur Veranschaulichung..

So schwer ist der Spline auch nicht zu implementieren. Nimm einfach natürliche Randbedingungen und äquidistante Stützstellen für die Parametrisierung in x und y. Das sollte eigentlich in wenigen Zeilen gehen (vielleicht 30-40 Zeilen).

//Edit:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
  StdCtrls, ExtCtrls;

type
  TExtendedArray = array of Extended;

  TForm1 = class(TForm)
    Image1: TImage;
    procedure Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Image1MouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure FormCreate(Sender: TObject);
  private
    xList, yList: TExtendedArray;
    LastX, LastY: Integer;
    Dragging: Boolean;
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// (2005 delfiphan; free for any use; use at own risk)
procedure createCubicSpline(const y: TExtendedArray; out K: TExtendedArray);
var
 n: Integer;
 I: Integer;
 r: TExtendedArray;
 u, t: TExtendedArray;
 b: Extended;
begin
  n := Length(y)-1;
  SetLength(r, n);
  SetLength(u, n-1);
  SetLength(t, n-1);
  SetLength(K, 4*n);
  for I := 0 to n-2 do
   r[I] := 3*(y[I+2]-2*y[I+1]+y[I]);
  b := 4;
  u[0] := r[0]/b;
  for I := 1 to n-2 do
  begin
   t[I] := 1/b;
   b := 4-t[I];
   u[I] := (r[I]-u[I-1])/b;
  end;
  for I := n-3 downto 0 do
   u[I] := u[I]-t[I+1]*u[I+1];
  for I := 0 to n-1 do
   K[I*4+0] := y[I+1];
  for I := 0 to n-2 do
   K[I*4+2] := u[I];
  K[0*4+3] := K[0*4+2]/3;
  for I := 1 to n-1 do
   K[I*4+3] := (K[I*4+2]-K[(I-1)*4+2])/3;
  K[0*4+1] := y[1]-y[0]+2/3*K[0*4+2];
  for I := 1 to n-1 do
   K[I*4+1] := y[I+1]-Y[I]+(2*K[I*4+2]+K[(I-1)*4+2])/3;
end;

function getCubicSplineAt(const K: TExtendedArray; const t: Extended): Extended;
var
 p: Extended;
 I: Integer;
begin
  I := trunc(t);
  p := t-I-1;
  Result := K[I*4+0]+(K[I*4+1]+(K[I*4+2]+K[I*4+3]*p)*p)*p;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  with Image1.Canvas do
   FillRect(ClipRect);
  with Image1 do
  begin
   OnMouseDown := Image1MouseDown;
   OnMouseMove := Image1MouseMove;
   OnMouseUp := Image1MouseUp;
  end;
end;

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if Button = mbLeft then
  begin
   Dragging := True;
   with Image1.Canvas do
    FillRect(ClipRect);
   SetLength(xList, 0);
   SetLength(yList, 0);
  end;
end;

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if Button = mbLeft then
   Dragging := False;
end;

procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
  
 procedure DrawBox(x, y: Extended);
 var
  IX, IY: Integer;
 begin
   IX := Round(x);
   IY := Round(y);
   Image1.Canvas.Rectangle(IX-1,IY-1,IX+2,IY+2);
 end;

const
 MinDist = 80;
 dt = 1/32;
var
 Index: Integer;
 Kx, Ky: TExtendedArray;
 t: Extended;
begin
  if not Dragging or (sqr(LastX-X)+sqr(LastY-Y)<sqr(MinDist)) then
   exit;
  LastX := X;
  LastY := Y;
  Index := Length(xList);
  SetLength(xList, Index+1);
  SetLength(yList, Index+1);
  xList[Index] := X;
  yList[Index] := Y;
  with Image1.Canvas do
  begin
   FillRect(ClipRect);
   DrawBox(xList[0], yList[0]);
   if Index=1 then
   begin // linear interpolation
    DrawBox(xList[1], yList[1]);
    t := dt;
    repeat
     Pixels[Round(xList[0]*t+xList[1]*(1-t)),Round(yList[0]*t+yList[1]*(1-t))] := 0;
     t := t + dt;
    until t>=1;
   end else
    if Index>1 then
    begin // equidistant natural cubic spline interpolation
     createCubicSpline(xList, Kx);
     createCubicSpline(yList, Ky);
     t := dt;
     repeat
      Pixels[Round(getCubicSplineAt(Kx,t)),Round(getCubicSplineAt(Ky,t))] := 0;
      t := t + dt;
      if frac(t)=0 then
       DrawBox(xList[round(t)],yList[round(t)]);
     until t>=Index;
    end;
  end;
end;

end.

TImage auf Form1 und FormCreate mit Form1.OnCreate verknüpfen.

PS: Wenn du keine äquidistante Parametrisierung willst, kannst du's ja erweitern (siehe Zusammenfassung)
[meta]spline, kubischer spline, cubic spline, natürlicher spline, natural spline[/meta]

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme