Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Kontaktpunkt (Halb-)Gerade - Gitter
F34r0fTh3D4rk - Do 02.10.08 15:27
Titel: Kontaktpunkt (Halb-)Gerade - Gitter
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):
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 - Do 02.10.08 17:24
Das Gitter als Graphen darstellen und dort durchgehen, dabei immer speichern an welchem Punkt du ein Quadrat "betreten" hast?
F34r0fTh3D4rk - Do 02.10.08 17:40
Ich verstehe leider nicht ganz was du damit meinst ;)
Thorsten83 - Do 02.10.08 17: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 - Do 02.10.08 18:09
Wie finde ich denn heraus welches Quadrat wo getroffen wird?
FinnO - Do 02.10.08 19: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 - Do 02.10.08 19:19
Das funktioniert nicht, da die Felder keine Punkte sind, sondern Quadrate.
Thorsten83 - Do 02.10.08 19: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 - Do 02.10.08 19:34
 F34r0fTh3D4rk hat folgendes geschrieben  : |
| 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 - Do 02.10.08 19:52
sind die quadrate grafisch dargestellt oder virtuelle quadrate?
Thorsten83 - Do 02.10.08 19: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 - Do 02.10.08 20:08
nein? wie denn das?
Horst_H - Do 02.10.08 20: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 - Do 02.10.08 22:10
| FinnO hat folgendes geschrieben : |
| F34r0fTh3D4rk hat folgendes geschrieben : | | 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:)
| elundril hat folgendes geschrieben : |
| sind die quadrate grafisch dargestellt oder virtuelle quadrate? |
Die Quadrate exisitieren nur "virtuell" haben aber eine feste Kantenlänge.
@
Horst_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 - Do 02.10.08 23: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..
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 - Fr 03.10.08 00: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.
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/4) or (winkel<-Pi*3/4) Then
Begin
Treffer:=false;
while ((x div FeldBreit)<=FelderAnzBr) and ((x div FeldBreit)>=1) and not Treffer do
Begin
y:=Py-Round(tan(winkel)*(Px-x)); FK:=getFeldKoord(x,y); if Feld[FK.X,FK.Y] Then Treffer:=true else Begin
if (winkel<=Pi/4) and
(winkel>=-Pi/4) Then Inc(x) Else Dec(x);
End;
end;
if Treffer Then Begin
Result.X:=x;
Result.Y:=y;
End;
end else begin
Treffer:=false;
while ((y div FeldHoehe)<=FelderAnzHo) and ((y div FeldHoehe)>=1) and not Treffer do
Begin
if Abs(winkel)=pi/2 Then x:=PX else
x:=Px-Round(tan(pi/2-winkel)*(Py-y)); FK:=getFeldKoord(x,y); if Feld[FK.X,FK.Y] Then Treffer:=true else Begin
if (winkel>0) Then Inc(y) 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<3) or (x>FelderAnzBr-2) or
(y<3) or (y>FelderAnzHo-2) then 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
alzaimar - Fr 03.10.08 07: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.
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 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 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.
Thorsten83 - Fr 03.10.08 15: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 - Fr 03.10.08 15: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,
F34r0fTh3D4rk - Fr 03.10.08 16: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.
Magic J - Fr 03.10.08 17:29
| F34r0fTh3D4rk hat folgendes geschrieben : |
| 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. |
Bei meinem Programm(siehe oben) weißt du am Ende sowohl die absoluten, als auch die Feld-Koordinaten des Treffers!
Jonas
Hidden - Fr 03.10.08 18:04
| F34r0fTh3D4rk hat folgendes geschrieben : |
| 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. |
Und was machst du bei mehreren Treffern? :D
Magic J - Fr 03.10.08 18:20
| Hidden hat folgendes geschrieben : |
| F34r0fTh3D4rk hat folgendes geschrieben : | | 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. |
Und was machst du bei mehreren Treffern? :D |
Wie soll es den bitte zu mehreren Treffern kommen?
Es kann doch immer nur ein eiziges Feld ZUERST getroffen werden,
solange sich die Felder nicht überschneiden^^.
Gruß,
Hidden - Fr 03.10.08 18:35
Ah, es geht um einen Strahl :D Ich dachte du hättest Halbgerade geschrieben, sry
F34r0fTh3D4rk - Fr 03.10.08 19:23
ja eine Halbgerade ist schon richtig, für mich ist der unterschied zu einem Strahl nicht so wirklich groß. Falls doch müsstest du das erläutern ;)
Hidden - Fr 03.10.08 20:08
Hi,
Naja, ich meinte auch nicht den mathematishen Begriff "Strahl", sondern habe das mehr intuitiv geschrieben. Im nachhinein zimelicher Quatsch, da die mathematischen Begriffe imho deckungsglich sind^^.
Und, dass du "ersten" geschrieben hast, habe ich glatt überlesen. Insofern mein spontanes Verständnis(math. falsch): Lichtstrahl endet am ersten Objekt; Halbgerade hat viele Schnittpunkte.
mfG,
F34r0fTh3D4rk - Sa 04.10.08 17:37
Ich hab ein Programm mit dem "naiven" Ansatz dahingeschleudert (Benutzung deshalb auf eigene Gefahr :mrgreen:):
http://www.exec-dev.de/grid.zip
Das System ist ja eigentlich schon ganz "gut" (bzw es ist recht schnell, bei großer Schrittweite). Ich habe auch gelesen, dass man die Schrittweite nun so wählen kann (wahrscheinlich auf irgendeine Art dynamisch), dass man keine Kollision übersieht, aber ohne unendlich viele Schritte zu brauchen und somit sogar den exakten Treffpunkt bekommt.
Thorsten83 - So 05.10.08 14:02
Dass ihr immer in Delphi programmieren müsst :)
Ich hab mich hier und bei google ein bißchen umgesehen, kann es sein dass es keine vernünftige Delphi-IDE für Linux gibt?
Der Ansatz der von Quadrat zu Quadrat geht sollte auf jeden Fall relativ schnell sein, bei NxM Quadraten ist die worst-case-Lauftzeit halt durch O(N+M) beschränkt, bei z.B. für Bildschirmauflösungen typischen Werten wie 1440x900 würde ich mal schätzen dass das im einstelligen Milisekundenbereich liegt...
Hidden - So 05.10.08 14:12
| Thorsten83 hat folgendes geschrieben : |
| Dass ihr immer in Delphi programmieren müsst :) |
Schleudert ten Purschen zu Poden!! :D Also bisher gefällt mir Delphi relativ gut. Sollte er bessere, kostenlose pascal-Alternativen haben, so poste er sie ;) Ich teste doch gerne :mrgreen:
F34r0fTh3D4rk - So 05.10.08 14:56
| Thorsten83 hat folgendes geschrieben : |
Dass ihr immer in Delphi programmieren müsst :)
Ich hab mich hier und bei google ein bißchen umgesehen, kann es sein dass es keine vernünftige Delphi-IDE für Linux gibt?
Der Ansatz der von Quadrat zu Quadrat geht sollte auf jeden Fall relativ schnell sein, bei NxM Quadraten ist die worst-case-Lauftzeit halt durch O(N+M) beschränkt, bei z.B. für Bildschirmauflösungen typischen Werten wie 1440x900 würde ich mal schätzen dass das im einstelligen Milisekundenbereich liegt... |
Schonmal gelesen in welchem Forum du hier bist? 8) Das könnte dir Aufschluss darüber geben, warum hier alle Delphi benutzen. Lazarus(FPC) läuft super auf Linux und so ziemlich jeder anderen Platform.(ist zwar kein offizielles Delphi, aber dem Original doch sehr ähnlich)
| Zitat: |
| Navigation: Delphi-Forum.de » Algorithmen, Optimierung und Assembler » Kontaktpunkt (Halb-)Gerade - Gitter |
So und nu Back To Topic ;)
Thorsten83 - So 05.10.08 15:15
| F34r0fTh3D4rk hat folgendes geschrieben : |
| Thorsten83 hat folgendes geschrieben : | Dass ihr immer in Delphi programmieren müsst :)
Ich hab mich hier und bei google ein bißchen umgesehen, kann es sein dass es keine vernünftige Delphi-IDE für Linux gibt?
Der Ansatz der von Quadrat zu Quadrat geht sollte auf jeden Fall relativ schnell sein, bei NxM Quadraten ist die worst-case-Lauftzeit halt durch O(N+M) beschränkt, bei z.B. für Bildschirmauflösungen typischen Werten wie 1440x900 würde ich mal schätzen dass das im einstelligen Milisekundenbereich liegt... |
Schonmal gelesen in welchem Forum du hier bist? 8) Das könnte dir Aufschluss darüber geben, warum hier alle Delphi benutzen. Lazarus(FPC) läuft super auf Linux und so ziemlich jeder anderen Platform.(ist zwar kein offizielles Delphi, aber dem Original doch sehr ähnlich)
So und nu Back To Topic ;) |
Bei mir steht oben C-Sharp-Forum :)
Aber ich hab schon mitgekriegt, dass die meisten auf anderen Wegen hierher gekommen sind, und es war auch nicht so wirklich ernst gemeint...
Zum Thema:
Habt ihr mal gemessen wie lange eure Programme rechnen?
Hidden - So 05.10.08 15:18
Afaik nicht länger als andere ;)
Nun aber wirklich back to Topic ;) Es geht darum, eine Gerade mit einem Gitternetz zu schneiden :zwinker:
mfG,
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!