Autor Beitrag
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 02.10.08 16:27 
Hallo,

Ich suche nach einer schnellen Methode, eine (Halb-)Gerade und ein Gitter auf Schnitt zu prüfen, dabei möchte ich die exakten Koordinaten des Schnittpunktes mit den Gitterfeldern bekommen können. Das Gitter hat einen Wert für die Größe der einzelnen Felder. Jedes Feld kann zwei Zustände haben, entweder kann die Linie das Feld schneiden, oder nicht. Hier ist eine Skizze (Gelber Punkt: Start der Geraden; Roter Punkt: Schnitt mit dem Feld):
user defined image
Ich hab mir schon diverse Sachen angeguckt. Eines davon war der DDA-Algorithmus, dessen Funktionsweise ich hinsichtlich meines Problems noch nicht ganz begriffen habe.

mfg
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Do 02.10.08 18:24 
Das Gitter als Graphen darstellen und dort durchgehen, dabei immer speichern an welchem Punkt du ein Quadrat "betreten" hast?
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 02.10.08 18:40 
Ich verstehe leider nicht ganz was du damit meinst ;)
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Do 02.10.08 18:56 
Sowas in der Art:

Setze Punkt = startpunkt
Setze Quadrat = Quadrat, in dem du startest
- wiederhole:
- berechne, welches Quadrat an welcher Stelle als nächstes "getroffen" wird
- merke dir diesen Punkt
- setze Quadrat = das Quadrat, das als nächstes "getroffen" wird
solange das Quadrat nicht nicht "schwarz" ist

Das Problem ist halt, dass du immer Rundungsfehler reinkriegst...
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 02.10.08 19:09 
Wie finde ich denn heraus welches Quadrat wo getroffen wird?
FinnO
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1331
Erhaltene Danke: 123

Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
BeitragVerfasst: Do 02.10.08 20:09 
für die Senkrechte setzt du in die geradengleichung einfach deinen Gitter X Koordinaten in ein.

für die Waagerechte Gitterwand die Y Koordinate des Gitters.
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 02.10.08 20:19 
Das funktioniert nicht, da die Felder keine Punkte sind, sondern Quadrate.
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Do 02.10.08 20:28 
Erstmal kannst du dir das ja vereinfachen:
Geht die Gerade z.B. nach "rechts oben", musst du nur abprüfen, wann die rechte, und wann die obere Kante des Quadrats geschnitten wird.
Und da die Kanten ja wohl bekannt sind ist das recht einfach, musst halt die zwei Geraden zum Schnitt bringen und dann gucken welcher Schnittpunkt dichter dran ist...
FinnO
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1331
Erhaltene Danke: 123

Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
BeitragVerfasst: Do 02.10.08 20:34 
user profile iconF34r0fTh3D4rk hat folgendes geschrieben Zum zitierten Posting springen:
Das funktioniert nicht, da die Felder keine Punkte sind, sondern Quadrate.


doch es funktioniert. Du Stimmst doch mit mir überein, dass, wenn du das Quadrat schneidest, es an 2 Punkten schneiden musst (rein und raus), bzw. in einem Punkt, dann aber trotzdem 2 verschiedene Achsen. Wenn du jetzt alle 4 Achsen des Rechtecks (oder Quadrats, was auch immer) überprüfst, und du bei 2 einen Schnittpunkt herauskriegst, hast du die 100%ige Gewissheit, dass das Quadrat durchscnitten wird
elundril
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3747
Erhaltene Danke: 123

Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
BeitragVerfasst: Do 02.10.08 20:52 
sind die quadrate grafisch dargestellt oder virtuelle quadrate?

_________________
This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Do 02.10.08 20:55 
Hmm mit Geradengleichungen (der Form y=mx+b) wäre ich vorsichtig, würde das lieber über einen Vektor lösen...

Mit einer Geradengleichung kommst du halt z.B. bei Senkrechten in Schwulitäten...
FinnO
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1331
Erhaltene Danke: 123

Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
BeitragVerfasst: Do 02.10.08 21:08 
nein? wie denn das?
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 02.10.08 21:47 
Hallo,

wo liegt hier ein Problem?
Du kannst doch einfach iterativ rechnen.
Eine Gerade ist Startpunkt P0 + x*Richtungsvektor V
Jetzt liege der Startpunkt auf einer festen Koordinate.
Dann bestimmst Du ein x_0 so, das P0+x_0*V genau auf einer ganzzahligen z Koordinate liegt.
Dann brauchst Du nur noch den Wert dx bestimmen, mit dx so das dx*V in der y Komponente 1 Gitterabstand ist.
Dann machst Du es noch eine Fallunterscheidung ob V_x>V_y und tauscht x und y , dann liegen die schneittpunkte eben mehr horizontal.

Punkt auf Gitter(n) = n*dx *V +P0+x_0*V n aus Menge der ganzen Zahlen


Gruß Horst
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 02.10.08 23:10 
user profile iconFinnO hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconF34r0fTh3D4rk hat folgendes geschrieben Zum zitierten Posting springen:
Das funktioniert nicht, da die Felder keine Punkte sind, sondern Quadrate.


doch es funktioniert. Du Stimmst doch mit mir überein, dass, wenn du das Quadrat schneidest, es an 2 Punkten schneiden musst (rein und raus), bzw. in einem Punkt, dann aber trotzdem 2 verschiedene Achsen. Wenn du jetzt alle 4 Achsen des Rechtecks (oder Quadrats, was auch immer) überprüfst, und du bei 2 einen Schnittpunkt herauskriegst, hast du die 100%ige Gewissheit, dass das Quadrat durchscnitten wird

Dazu muss ich aber eine Menge Quadrate prüfen. (es wäre dann aber exakt :mrgreen:)
user profile iconelundril hat folgendes geschrieben Zum zitierten Posting springen:
sind die quadrate grafisch dargestellt oder virtuelle quadrate?

Die Quadrate exisitieren nur "virtuell" haben aber eine feste Kantenlänge.
@user profile iconHorst_H:
Deine Iterative Lösung hab ich nicht ganz verstanden. Das Problem bei der "normalen" Iterativen Lösung ist die Inexaktheit und das Problem, dass Kollisionen "übersehen" werden können.

mfg
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 03.10.08 00:58 
Hallo,

inexakt ?? Es ist doch gar nicht iterativ ;-)
Sei P0(x;y)=(1/8;1/6), und V= (8/9;13/8 ); // v_y > v_x
Dein Gitter beginne in (0;0) und habe eine Kantenlänge der Quadrate von 1.

f0 so, das P0+x_0*V auf Gitter liegt und weil wir es einfachhaben wollen soll y zu 0 werden.
Der linearfaktor f0 wird also : 0 = P0_y+f0*v_y => f0 = -P0_y/v_y = -1/6*8/13 = -4/39;

Jetzt dx bestimmen, ssodass dx*v_y= 1 == Gitterabstand
also dx= 1/v_y = 8/13
Die Simple Formel: n*dx*v+ (P0+f0*V){= konstant neuer Startpunkt der Geraden}
SchnittePunkt(n) = n*8/13*(8/9;13/8 )+ (-4/39*8/9+1/8;0)
Wie schön auch, dass durch die Wahl die Gerade jetzt auf x-Achse des Gitters beginnen zu lassen, so dass n die y-Koordinate des Gitters ist.
Das passende x(n) = n*8/13*8/9 + 319/2808; y(n)= n;
iterativ kann man es jetzt machen, wenn man Gitter für Gitter auf der Geraden testen will.
x(0) = 319/2808, y(0) = 0;
x(n)= x(n-1)+64/117;y(n)= y(n-1)+1;
Du wirst wohl kaum Millionen von Additionen ausführen.
Mit single bist Du bis 5e5 Addition auf 1 Promille genau.
Mit double eine Ewigkeit um auf 1e-6 relative Abweichung zu kommen, habe ich nicht probiert..
ausblenden volle Höhe 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:
program Addtest;
{$AppType CONSOLE}

const
  fx= 64.0/117.0;
  x0= 319.0/2808;
  eps0 = 1.0e-6;
  epd0 = 1.0e-14;
var
  xs,
  xs_iter: single;
  xd,
  xd_iter: double;
  eps,epd: double;
  n : integer;

begin
  n := 0;
  eps := eps0;
  xs_iter:= X0;
  repeat
    repeat
      inc(n);
      xs_iter:= xs_iter+fx;
      xs := n*fx+x0;
    until abs(1.0-xs/xs_iter)>eps;
    writeln(n:10,'  ',eps);
    eps := eps*10.0;
  until eps > 2e-3;
  writeln;

  n := 0;
  epd := epd0;
  xd_iter:= X0;
  repeat
    repeat
      inc(n);
      xd_iter:= xd_iter+fx;
      xd := n*fx+x0;
    until abs(1.0-xd/xd_iter)>epd;
    writeln(n:10,'  ',epd);
    epd := epd*10.0;
  until epd > epd0*10000.0;

  writeln('****************');
  readln;
end.
       137   1.00000000000000E-006
      1113   1.00000000000000E-005
     17471   1.00000000000000E-004
    501102   1.00000000000000E-003

      3870   1.00000000000000E-014
      4985   1.00000000000000E-013
     93149   1.00000000000000E-012
   1055443   1.00000000000000E-011
  16438618   1.00000000000000E-010
****************


Die FPU ist so schnell, das wohl nicht auffällt, ob mit genauer Rechnung oder Iteration gerechnet wurde.

Gruß Horst
Magic J
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 66

WinXP Prof., Vista
Delphi6, Delphi 2009, Java(Eclipse), C++, Basic
BeitragVerfasst: Fr 03.10.08 01:19 
Hi zusammen,

Das Thema hat mich iregendwie dazu hingerissen selber mal dran rumzubrobieren.
Nun habe ich ein Programm geschrieben, dass das "getroffen" Feld und den genauen Treffpunkt errechnet und Grafisch darstellt.

ausblenden volle Höhe 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:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
uses math;

Const FeldBreit=20;
      FeldHoehe=20;
      FelderAnzBr=25;
      FelderAnzHo=25;

var Feld:Array[1..FelderAnzBr,1..FelderAnzHo] of Boolean;

    SX,SY,RX,RY,TX,TY:Integer;
    W:Double;
    mausdown:Boolean=false;
    art:Boolean=true;


function TForm1.getFeldKoord(Px,Py:Integer):TPoint;
Begin
  Result.X:=Px div FeldBreit+1;
  Result.Y:=Py div FeldHoehe+1;
End;

function TForm1.getTreffPunkt(Px,Py:Integer; Winkel:Double):TPoint;
Var x,y :Integer;
    Treffer:Boolean;
    FK:TPoint;
Begin
  Result.X:=PX;
  Result.Y:=PY;
  x:=Px;
  y:=Py;

  while winkel<-pi do winkel:=Winkel+2*pi;
  while winkel> pi do winkel:=Winkel-2*pi;

  if (winkel<=Pi/4)  and (winkel>=-Pi/4)  or
     (winkel>Pi*3/4or (winkel<-Pi*3/4Then
  Begin
    (*Flache Steigung*)
    Treffer:=false;
    while ((x div FeldBreit)<=FelderAnzBr) and  // Schleifenabbruch bei Verlassen der Felder
          ((x div FeldBreit)>=1and not Treffer do
    Begin
      y:=Py-Round(tan(winkel)*(Px-x));             // Y-Wert der Halbgeraden an der Stelle X ermitteln
      FK:=getFeldKoord(x,y);                    // Feld ermitteln, auf dem der Punkt liegt
      if Feld[FK.X,FK.Y] Then Treffer:=true     // Wenn Feld besetzt ist, Schleifenabbruch
      else Begin
        if (winkel<=Pi/4)  and
           (winkel>=-Pi/4Then Inc(x)          // Weiter geht´s
                           Else Dec(x);
      End;
    end;
    if Treffer Then Begin
      Result.X:=x;
      Result.Y:=y;
    End;
  end else begin
    (*Steile Steigung*)
    Treffer:=false;
    while ((y div FeldHoehe)<=FelderAnzHo) and  // Schleifenabbruch bei Verlassen der Felder
          ((y div FeldHoehe)>=1and not Treffer do
    Begin
      if Abs(winkel)=pi/2 Then x:=PX else
         x:=Px-Round(tan(pi/2-winkel)*(Py-y));        // X-Wert der Halbgeraden an der Stelle Y ermitteln
      FK:=getFeldKoord(x,y);                    // Feld ermitteln, auf dem der Punkt liegt
      if Feld[FK.X,FK.Y] Then Treffer:=true     // Wenn Feld besetzt ist, Schleifenabbruch
      else Begin
        if (winkel>0Then Inc(y)               // Weiter geht´s
                      Else Dec(y);
      end;
    end;
    if Treffer Then Begin
      Result.X:=x;
      Result.Y:=y;
    End;
  end;
End;


procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
Var FK:TPoint;
begin
  mausdown:=true;
  case RadioGroup1.ItemIndex of
    0:Begin
        FK:=getFeldKoord(x,y);
        Feld[FK.x,FK.y]:=not Feld[FK.x,FK.y];
        Art:=Feld[FK.x,FK.y];
      End;
    1:Begin
        SX:=x;
        SY:=y;
      End;
    2:Begin
        RX:=x;
        RY:=y;
      End;
  end;
  Malen;
end;

procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
  Var FK:TPoint;
begin
  if not mausdown then exit;
  case RadioGroup1.ItemIndex of
    0:Begin
        FK:=getFeldKoord(x,y);
        Feld[FK.x,FK.y]:=Art;
      End;
    1:Begin
        SX:=x;
        SY:=y;
      End;
    2:Begin
        RX:=x;
        RY:=y;
      End;
  end;
  malen;
end;

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
  Var FK:TPoint;
begin
  case RadioGroup1.ItemIndex of
    0:Begin
        FK:=getFeldKoord(x,y);
        Feld[FK.x,FK.y]:=Art;
      End;
    1:Begin
        SX:=x;
        SY:=y;
      End;
    2:Begin
        RX:=x;
        RY:=y;
      End;
  end;
  mausdown:=false;
   malen;
end;
procedure TForm1.Malen;
Var x,y:Integer;
    dx,dy:Integer;
    TP,FK:TPoint;
begin
  dx:=RX-SX;
  dy:=RY-SY;
  if dx=0 then Begin
  if dy>0 Then w:=pi/2 else w:=-pi/2;
  end else W:=arctan(dy/dx);

  if dx<0 then Begin
    if dx<0 Then w:=w-pi else w:=w+pi;
  end;

  TP:=getTreffPunkt(SX,SY,w);
  TX:=TP.X;
  TY:=TP.Y;

  Label1.Caption:='SX: '+IntToStr(SX);
  Label2.Caption:='SY: '+IntToStr(SY);

  Label3.Caption:='RX: '+IntToStr(RX);
  Label4.Caption:='RY: '+IntToStr(RY);

  Label5.Caption:='W: '+FloatToStrF(W*180/pi,ffNumber,99,2)+'°';

  Label6.Caption:='TX: '+IntToStr(TX);
  Label7.Caption:='TY: '+IntToStr(TY);

  FK:=getFeldKoord(TX,TY);
  Label12.Caption:='FX: '+IntToStr(FK.X);
  Label13.Caption:='FX: '+IntToStr(FK.Y);

  Application.ProcessMessages;


  Image1.Canvas.Brush.Color:=clWhite;
  Image1.Canvas.Pen.Color:=clBlack;
  Image1.Canvas.Rectangle(0,0,Image1.Width,Image1.Height);
  Image1.Canvas.Brush.Color:=clBlack;
  For y:=1 to FelderAnzHo do Begin
    For x:=1 to FelderAnzBr do Begin
      if Feld[x,y] then Image1.Canvas.Rectangle(x*FeldBreit-FeldBreit,y*FeldHoehe-FeldBreit,x*FeldBreit,y*FeldHoehe);
    end;
  end;
  if (SX=TX) and (SY=TY) Then Image1.Canvas.Brush.Color:=clYellow
                         Else Image1.Canvas.Brush.Color:=clNavy;
  Image1.Canvas.Rectangle(FK.x*FeldBreit-FeldBreit,FK.y*FeldHoehe-FeldBreit,FK.x*FeldBreit,FK.y*FeldHoehe);


  Image1.Canvas.Brush.Color:=clGreen;
  Image1.Canvas.Pen.Color:=clGreen;
  Image1.Canvas.Ellipse(SX-2,SY-2,SX+2,SY+2);
  Image1.Canvas.Brush.Color:=clBlue;
  Image1.Canvas.Pen.Color:=clBlue;
  Image1.Canvas.Ellipse(RX-2,RY-2,RX+2,RY+2);

  Image1.Canvas.Brush.Color:=clRed;
  Image1.Canvas.Pen.Color:=clRed;
  Image1.Canvas.Ellipse(TX-2,TY-2,TX+2,TY+2);
  Image1.Canvas.MoveTo(SX,SY);
  Image1.Canvas.LineTo(TX,TY);

  
end;

procedure TForm1.Button1Click(Sender: TObject);
Var x,y:Integer;
begin
  For y:=1 to FelderAnzHo do Begin
    For x:=1 to FelderAnzBr do Begin
      if (x<3or (x>FelderAnzBr-2or
         (y<3or (y>FelderAnzHo-2then Feld[x,y]:=true;
    end;
  end;
  Malen;
end;

procedure TForm1.Button2Click(Sender: TObject);
var i,r1,r2:Integer;
begin
  for i:=1 to 50 do Begin
    r1:=Random(FelderAnzBr);
    r2:=Random(FelderAnzHo);
    Feld[r1,r2]:= not Feld[r1,r2];
  End;
  Malen;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize;

  SX:=Image1.Width div 2;
  SY:=Image1.Height div 2;
  RX:=Image1.Width div 2+20;
  RY:=Image1.Height div 2;

  malen;
end;

procedure TForm1.Button3Click(Sender: TObject);
var x,y:Integer;
begin
  For y:=1 to FelderAnzHo do Begin
    For x:=1 to FelderAnzBr do Begin
      Feld[x,y]:=false;
    end;
  end;
  Malen;
end;


Ich muss allerdings zugeben, dass meine Lösung nicht wirklich für eine "virtuelle" Errechnung taugt, da sie den Punkt nur auf Pixel-Basis annähert.

Für die grafische Darstellung allerdings mehr als genug.

Für Intessierte: siehe Anhang...

Gruß, Jonas
Einloggen, um Attachments anzusehen!
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Fr 03.10.08 08:39 
Man könnte das auch über eine Schleife lösen, die über Max (dX, dY) und das Raster läuft und dann für jeden Schleifenwert per Geradengleichung den Y/X-Wert berechnet.

Der Code ist etwas aufgebauscht, das eine Fallunterscheidung sowie der Sonderfall einer senkrechten Geraden berücksichtigt werden muss.

ausblenden volle Höhe 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:
procedure TForm2.RasterPoints(P0, P1: TRealPoint; Raster: Double);
var
  A, B, Eps, Delta,
    X, Xend, Y, Yend: Double;
  bPerpendicular: Boolean;

  function _Rasterize(X: Double): Double;
  begin
    Result := Trunc((X + Raster / 2) / Raster) * Raster;
  end;

begin
  Eps := Raster / 2;
  if Abs(P1.X - P0.X) < 1E-20 then // Senkrechte?
    bPerpendicular := True
  else begin
    bPerpendicular := False;
    A := (P1.Y - P0.Y) / (P1.X - P0.X);
    B := P1.Y - A * P1.X;
  end;

  if Abs(P1.X - P0.X) > Abs(P1.Y - P0.Y) then Begin // Winkel < 45°, also über X laufen
    if P1.X > P0.X then
      Delta := Raster
    else
      Delta := -Raster;
    X := _Rasterize(P0.X+Eps);
    Xend := _Rasterize(P1.X+eps);
    while Abs(X - Xend) > eps do begin
      Y := A * X + B;
      memo1.lines.add(Format('%4.2f / %4.2f', [X, Y]));
      x := x + Delta;
    end;
  end else begin
    Y := _Rasterize(P0.Y+Eps);
    YEnd := _Rasterize(P1.Y+Eps);
    if P1.Y > P0.Y then
      Delta := Raster
    else
      Delta := -Raster;
    while Abs(Y - YEnd) > Eps do begin
      if bPerpendicular then
        X := P0.X
      else
        X := (Y - B) / A;
      memo1.lines.add(Format('%4.2f / %4.2f', [X, Y]));
      Y := Y + Delta;
    end;
  end;
end;


Kommt ganz ohne Iterationen aus. Eigentlich sollte das noch einfacher gehen, denn die Delta_X / Delta_Y, also die Abstände der Schnittpunkte sind ja konstant und die kann man vorher berechnen und dann einfach eine simple Schleife von P0 nach P1 laufen lassen.

_________________
Na denn, dann. Bis dann, denn.
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Fr 03.10.08 16:20 
@Magic: sieht ja schon ganz gut aus :)

Muss mal eine doofe Frage stellen, ich hab noch nie was mit Delphi gemacht:
Sehe ich das richtig, dass jede Funktion eine "Result"-Variable hat? Und die bei Beenden der Funktion automatisch zurückgegeben wird?
Werd erstmal frühstücken und mir das dann nochmal angucken ;)
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Fr 03.10.08 16:41 
Hi,

Das Thema ist interessant :)

Je nachdem, welchen Erwartungswert man an die Kästchenzahl/Verteilung hat, ob mehrere Geraden nacheinander geprüft werden müssen, etc., lohnt es sich eventuell sogar, zuerst einen Algorithmus über das Kästchen-Array laufen zu lassen, der zusammenhängende Kästchen zu geometrischen Formen verknüpft.

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Fr 03.10.08 17:52 
Das mit den geometrischen Formen ist zwar keine schlechte Idee, würde aber alles nur unnötig verkomplizieren, da ich im nachhinein wissen muss, welches Feld getroffen wurde und wo.