Schnittpunkt 2er Strecken

Flamefire · Verfasst: Di 08.09.09 20:22

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

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:
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:

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:

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 · Verfasst: Di 08.09.09 21:11

Der Code ist etwas merkwürdig, schau dir lieber diese Erklärung an: ozviz.wasp.uwa.edu.a...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 · Verfasst: 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 · Verfasst: Di 08.09.09 22:18

Ich hab da mal eine Methode geschrieben, du findest sie in diesem Thema (im ersten Post ganz unten).

Ich kopiere sie zur Sicherheit nochmal hier rein:

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:

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;

  // Beginn 3D
  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:

markieren

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 · Verfasst: 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

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:
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 //Lines parallel
    if(tmp2=0) then begin//Lines on 1 Line
      //Test P1
      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
          //TestP2
          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)//Lines not overlapping
          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 · Verfasst: 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 · Verfasst: 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

_________________
Wo andere aufhören, fange ich erst an..

Flamefire · Verfasst: Mi 09.09.09 15:14

hm...nja so gehts recht schnell...
der einzige grund, das zu ändern, wäre geschwindigkeit

JDKDelphi · Verfasst: 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ß

_________________
Wo andere aufhören, fange ich erst an..

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme