Schnittpunkt 2er Strecken -->Bereichsproblem

Flamefire · Verfasst: Mo 26.10.09 17:30

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:

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:

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 //Lines parallel
//...check if 1 line usw.
  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 · Verfasst: Mo 26.10.09 23:14

Hallo,

Wer behauptet denn, das double-Berechnungen langsam sind?.
Musst Du die Daten so gigantisch übergeben?.

markieren

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
www.informatik.uni-l...G_WS08-09/AG_2.2.pdf
www.ads.tuwien.ac.at...a/mmgdv/k3___003.htm

Flamefire · Verfasst: Mi 28.10.09 11:45

ich brauche jeweils nur den schnittpunkt zwischen einer strecke und einigen anderen. vorher prüfe ich mittels hitboxes auf mögliche schnittpunkte.
und ja ich habe es auf double umgestellt mit mäßigem speedverlust. ist verschmerzbar.
hätte ich nicht gedacht

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme