Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Schnittpunkt 2er Strecken
Flamefire - Di 08.09.09 20:22
Titel: Schnittpunkt 2er Strecken
Nun stehe ich vor dem problem den Schnittpunkt 2er Strecken zu berechnen
und das möglichst effektiv
habe jetzt schon vieles gesucht und gefunden, aber nichts gefällt mir so richtig, bzw verstehe es nicht ganz
z.B. das hier
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:
| function LineIntersects(LineA, LineB: TLine): boolean;
var
p1, p2,
q1, q2: TDot;
a1, b1, c1,
a2, b2, c2: Single;
s: TDot;
begin
p1.X := LineA.A.X; p2.X := LineA.B.X;
q1.X := LineB.A.X; q2.X := LineB.B.X;
p1.Y := LineA.A.Y; p2.Y := LineA.B.Y;
q1.Y := LineB.A.Y; q2.Y := LineB.B.Y;
a1 := p2.y - p1.y; b1 := p1.x - p2.x; c1 := a1*p1.x + b1*p1.y;
a2 := q2.y - q1.y; b2 := q1.x - q2.x; c2 := a2*q1.x + b2*q1.y;
s.x := (c1*b2-c2*b1)/(a1*b2-a2*b1); s.y := (a1*c2-a2*c1)/(a1*b2-a2*b1);
Schnittpunkt.X := S.X;
Schnittpunkt.Y := S.Y;
Result := True;
if (s.y > p1.y) and (s.y > p2.y) then Result := False;
if (s.y > q1.y) and (s.y > q2.y) then Result := False;
if (s.y < p1.y) and (s.y < p2.y) then Result := False;
if (s.y < q1.y) and (s.y < q2.y) then Result := False;
if (s.x > p1.x) and (s.x > p2.x) then Result := False;
if (s.x > q1.x) and (s.x > q2.x) then Result := False;
if (s.x < p1.x) and (s.x < p2.x) then Result := False;
if (s.x < q1.x) and (s.x < q2.x) then Result := False;
end; |
ok...es wird der Schnittpunkt der 2 geraden berechnet und dann geprüft ob er auf den strecken liegt
wie funktioniert das?
c1 und c2 scheint das skalarprodukt der richtungsvektoren zu sein. aber wozu?
dann habe ich das ganze umgesetzt und etwas optimiert:
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:
| function LineIntersect(cX1,cY1,cX2,cY2,lX1,lY1,lX2,lY2:Integer; var sX,sY:Integer): boolean;
var a1,a2,b1,b2,c1,c2,tmp:Single;
begin
a1 := cY2-cY1;
b1 := cX1-cX2;
c1 := a1*cX1 + b1*cX2;
a2 := lY2-lY1;
b2 := lX1-lX2;
c2 := a2*lX1 + b2*lX2;
tmp:=(a1*b2-a2*b1);
sX := Round((c1*b2-c2*b1)/tmp);
if (sX > cX1) and (sX > cX2)
or (sX > lX1) and (sX > lX2)
or (sX < cX1) and (sX < cX2)
or (sX < lX1) and (sX < lX2) then exit(false);
sY := Round((a1*c2-a2*c1)/tmp);
if (sY > cY1) and (sY > cY2)
or (sY > lY1) and (sY > lY2)
or (sY < cY1) and (sY < cY2)
or (sY < lY1) and (sY < lY2) then exit(false);
Result:=true;
end; |
Ergebnis: funktioniert nicht mehr...
und ich bin zu doof den fehler zu finden :-(
kann mir jemand weiterhelfen?
BTW: hier werden parrallele (und möglicherweise aufeinanderliegende) strecken/geraden ignoriert richtig?
wie kann ich parrallele strecken erkennen? dürfte mit dem kreuzprodukt der RV gehen. wenn das =0 ist dann sind die parallel, hab ich das richtig in erinnerung?
Kha - Di 08.09.09 21:11
Der Code ist etwas merkwürdig, schau dir lieber diese Erklärung an:
http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
 Flamefire hat folgendes geschrieben  : |
| dürfte mit dem kreuzprodukt der RV gehen. wenn das =0 ist dann sind die parallel, hab ich das richtig in erinnerung? |
Wenn du "Kreuzprodukt" durch "Skalarprodukt" ersetzt, dann ja ;) .
Flamefire - Di 08.09.09 22:07
hab den Fehler gefunden:
bei c1/c2:=... muss es hinten jeweils Y sein
dann klappt das
um parallele abzufangen reicht eine abfrage von tmp auf 0
vorteil an dem ganzen: ich brauche den single typ gar nicht
geht alles auf integer basis
wodurch es ziemlich schnell sein sollte
was mich noch etwas stört sind die vielen abfragen, um zu prüfen, ob ein punkt auf den strecken liegt.
geht das noch zu optimieren?
Yogu - Di 08.09.09 22:18
Ich hab da mal eine Methode geschrieben, du findest sie in
diesem Thema [
http://www.delphi-forum.de/viewtopic.php?t=77227] (im ersten Post ganz unten).
Ich kopiere sie zur Sicherheit nochmal hier rein:
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:
| type
TGSValue = Double;
TGSVector = record
X: TGSValue;
Y: TGSValue;
Z: TGSValue;
end;
function GSIntersectionPoint(V1, V2, V3, V4: TGSVector): TGSVector;
var M1, M2, C1, C2: TGSValue;
begin
if V1.X-V2.X = 0 then M1 := NAN else M1 := (V1.Y-V2.Y)/(V1.X-V2.X);
if V3.X-V4.X = 0 then M2 := NAN else M2 := (V3.Y-V4.Y)/(V3.X-V4.X);
C1 := V1.Y-M1*V1.X;
C2 := V3.Y-M2*V3.X;
if M1-M2 = 0 then Result.X := NAN else Result.X := (C2-C1)/(M1-M2);
if M1-M2 = 0 then Result.Y := NAN else Result.Y := M1*(C2-C1)/(M1-M2)+C1;
if V1.X-V2.X = 0 then M1 := NAN else M1 := (V1.Z-V2.Z)/(V1.X-V2.X);
if V3.X-V4.X = 0 then M2 := NAN else M2 := (V3.Z-V4.Z)/(V3.X-V4.X);
C1 := V1.Z-M1*V1.X;
C2 := V3.Z-M2*V3.X;
if M1-M2 = 0 then Result.Z := NAN else Result.Z := M1*(C2-C1)/(M1-M2)+C1;
end; |
Zuerst berechne ich die Steigung (M) und den Y-Achsen-Abschnitt (C) der Geraden. Den zweiten Block brauchst du ja nicht mehr, das ist nur für 3D. Die ganzen Abfragen auf Null könntest du vielleicht auch weglassen, wenn du Fließkommazahlen verwendest. Also gekürzt:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| function GSIntersectionPoint(V1, V2, V3, V4: TGSVector): TGSVector;
var M1, M2, C1, C2: TGSValue;
begin
M1 := (V1.Y-V2.Y)/(V1.X-V2.X);
M2 := (V3.Y-V4.Y)/(V3.X-V4.X);
C1 := V1.Y-M1*V1.X;
C2 := V3.Y-M2*V3.X;
Result.X := (C2-C1)/(M1-M2);
Result.Y := M1*(C2-C1)/(M1-M2)+C1;
end; |
Edit: Ich sehe gerade, du suchst den Schnittpunkt zweier Strecken, nicht Geraden :autsch: Aber vielleicht hilft dir mein Code ja trotzdem.
Grüße,
Yogu
Flamefire - Di 08.09.09 22:46
jo danke aber ich glaube dein code würde für senkrechte strecken nicht funktionieren, da du über den anstieg gehst...
alles was ich noch brauchen könnte, wäre eine optimierung meiner function (oder eine von vornherein bessere)
aber ich denke, mehr geht nicht
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:
| 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;
begin
a1 := cY2-cY1;
b1 := cX1-cX2;
c1 := a1*cX1 + b1*cY1;
a2 := lY2-lY1;
b2 := lX1-lX2;
c2 := a2*lX1 + b2*lY1;
tmp:=(a1*b2-a2*b1);
tmp2:=(c1*b2-c2*b1);
if(tmp=0) then begin if(tmp2=0) then begin if(cX1>lX1) and (cX1>lX2)
or (cY1>lY1) and (cY1>lY1)
or(cX1<lX1) and (cX1<lX2)
or (cY1<lY1) and (cY1<lY1) then begin
if(cX2>lX1) and (cX2>lX2)
or (cY2>lY1) and (cY2>lY1)
or(cX2<lX1) and (cX2<lX2)
or (cY2<lY1) and (cY2<lY1) then exit(false) else begin
sX:=cX2;
sY:=cY2;
exit(true);
end;
end else begin
sX:=cX1;
sY:=cY1;
exit(true);
end;
end else exit(false);
end;
sX := Round(tmp2/tmp);
if (sX > cX1) and (sX > cX2)
or (sX > lX1) and (sX > lX2)
or (sX < cX1) and (sX < cX2)
or (sX < lX1) and (sX < lX2) then exit(false);
sY := Round((a1*c2-a2*c1)/tmp);
if (sY > cY1) and (sY > cY2)
or (sY > lY1) and (sY > lY2)
or (sY < cY1) and (sY < cY2)
or (sY < lY1) and (sY < lY2) then exit(false);
Result:=true;
end; |
Yogu - Di 08.09.09 23:34
| Flamefire hat folgendes geschrieben : |
| jo danke aber ich glaube dein code würde für senkrechte strecken nicht funktionieren, da du über den anstieg gehst... |
Doch, das geht auch - und zwar ist die Steitung dann einfach Unendlich. Und das wird abgefangen.
JDKDelphi - Mi 09.09.09 09:47
Schnittpunkt zweier Graden
Hallo,
ich hatte da vor Monaten mal ne ganze Komponente ins Forum gestellt,
die auch funktioniert.
Gruss
Flamefire - Mi 09.09.09 15:14
hm...nja so gehts recht schnell...
der einzige grund, das zu ändern, wäre geschwindigkeit
JDKDelphi - Mi 09.09.09 18:49
Hallo Flamefire,
hat man denn mal meine Unit runtergeladen??
die Unit/Komponente ist zwar nicht durchoptimiert, aber wirksam!
In PPS-Systemen werden damit Massenermittlungen bzw. CAD-Daten aus verschiedenen Systemen für Bertonverarbeitende Betriebe
ausgeführt, wo ggf. Bewehrungen berechnet werden.
Ein Beispiel kann ich mal posten
vielen Gruß
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!