Flamefire - Mo 26.10.09 17:30
Titel: Schnittpunkt 2er Strecken -->Bereichsproblem
Ich habe eine Funktion geschrieben, die mir den Schnittpunkt 2er Strecken ausgibt (NICHT geraden)
die musste stark optimiert werden darum könnte manches seltsam aussehen. aber prinzip wird klar.
funktion sieht so aus:
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:
| function LineIntersect(cX1,cY1,cX2,cY2,lX1,lY1,lX2,lY2:Integer; var sX,sY:Integer): boolean;
var a1,a2,b1,b2,c1,c2,tmp,tmp2:Integer;
sxf,syf:Double;
begin
a1 := cY2-cY1;
b1 := cX1-cX2;
a2 := lY2-lY1;
b2 := lX1-lX2;
c1 := a1*cX1 + b1*cY1;
c2 := a2*lX1 + b2*lY1;
tmp:=(a1*b2-a2*b1);
tmp2:=(c1*b2-c2*b1);
if(tmp=0) then begin end;
sXf := tmp2/tmp;
if (sXf > cX1) and (sXf > cX2)
or (sXf > lX1) and (sXf > lX2)
or (sXf < cX1) and (sXf < cX2)
or (sXf < lX1) and (sXf < lX2) then exit(false);
sYf := (a1*c2-a2*c1)/tmp;
Result:=true;
end; |
funktioniert in der Theorie. (skalarprodukte usw. vektorrechnung lässt grüßen)
problem dabei: ich habe ein koordinatensystem mit punkten in der größe von 15000
durch die ganzen multiplikationen sprengt es mir den integer bereich und ich bekomme bei tmp(2):=... nen IntOverFlow
ich könnte das ganze zwar als Int64 oder Float rechnung machen, aber da würde die performance ziemlich sinken. (der code wird SEHR oft aufgerufen, geht nicht anders)
gibt es noch eine andere möglichkeit, oder komm ich um den int64 nicht herum?
Horst_H - Mo 26.10.09 23:14
Hallo,
Wer behauptet denn, das double-Berechnungen langsam sind?.
Musst Du die Daten so gigantisch übergeben?.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| type
tKoor = record
x,
y :integer
end;
tStrecke = record
P1,
P2: tKoor;
end;
function LineIntersect(const S1,S2:tStrecke,var S:tkoor;):boolean; |
Vielleicht hilft es durch tauschen von P1,P2 dafür zu sorgen, das P1 immer den linken Punkt darstellt.Also immer P1.x<P2.x
Wenn
S1.P2.x < S2.P1.x //S1 liegt rechts von S2
oder
S1.P1.x > S2.P2.x //S1 liegt links von S2
ist schon Schluss
jetzt das selbe indem man jetzt dafür sorgt, das P1 immer den unteren Punkt darstellt.
Wenn
S1.P2.y < S2.P1.y //S1 liegt unterhalb von S2
oder
S1.P1.y > S2.P2.y //S1 liegt oberhalb von S2
ist schon wieder Schluss.
Sonst Verschiebst du alle Punkte , also Ursprungsverschiebung P(0,0)-> P0(?,?)
P0.X = Min(x aller Punkte ) und wenn das nicht hilft P0.x = (Max(x aller Punkte)-Min(x aller Punkte)) Div 2
analog für y.
p1-> p1 - p0
Sei P0.x= Min(x aller Punkte ) und zufällig Cx1
c1 := a1*cX1 + b1*cY1; wäre dann
c1 := a1*0 + b1*(cY1-CX1); Wenn sich alles in einem Quadranten abspielt wird es also kleiner
Am Ende addierst Du P0 auf die Lösung und hast die Koordinaten wieder zurück geschoben
Gruß Horst
EDIT:
Du willst ja eine große Menge an Strecken verarbeiten.
Dann musst Du den Ansatz ändern.
Suche mal nach plane sweep schnittpunkt
http://www.informatik.uni-leipzig.de/~jaenicke/Vorlesung/AG_WS08-09/AG_2.2.pdf
http://www.ads.tuwien.ac.at/docs/lva/mmgdv/k3___003.htm