Schnittpunkte von Strecken

[AlexanderVieth]

Hallo Allezusammen.

Ich versuche eine function zu schreiben, die Schnittpunkte von Strecken ermittelt (und ob sie sich überhaupt schneiden, da die strecken ja begrenzt lang sind),
und einen kleinen Bogen einzeichnet (um den schnittpunkt).
Ich erhalte aus einer anderen procedure einen Array, der Punktepaare enthält, d.h. auf Array[0].A befindet sich Punkt A und auf Array[0].B befindet sich Punkt B.
Die Punkte besitzen jeweils X und Y koordinaten.

Mein Problem ist jetzt folgendes:
Der Array ist nur begrenzt gefüllt, da für jede linie die neu gezeichnet wird, überprüft wird ob sie eine bereits gezeichnete Linie schneidet. Wenn ja, soll ein brückchen darüber gezeichnet werden (Canvas.Arc).
Aus Mathematischer sicht habe ich noch ein Problem, und zwar, den Sonderfall einer Senkrechten und einer Horizontalen strecke. so erhalte ich eine Divison durch 0 und somit einen Fehler.

Das hier habe ich bis jetzt:

Delphi-Quellcode:

function CheckCross(Canvas: TCanvas;LinArr: Array of TLine; Run: Integer): boolean;
var
  t, s, A, B, C, D, E, F, G, H: real;
  i: Integer;
  VRun, VNorm, Vi, ViN: TVector;
  OVA, OVB, OVM: TPoint;

begin
  if Run <= 2 then
  begin
    Result := False;
    exit;
  end else
  begin
    for i := Run - 1 downto 0 do
    begin

      VRun := VRoute(GetVector(LinArr[Run].A),GetVector(LinArr[Run].B));
      VNorm := Normalize(VRun);
      Vi := VRoute(GetVector(LinArr[i].A),GetVector(LinArr[i].B));
      A := GetVector(LinArr[Run].A).X;
      B := GetVector(LinArr[Run].A).Y;
      C := VRun.X;
      D := VRun.Y;
      E := GetVector(LinArr[i].A).X;
      F := GetVector(LinArr[i].A).Y;
      G := VRoute(getvector(LinArr[i].A), getvector(LinArr[i].B)).X;
      H := VRoute(getvector(LinArr[i].A), getvector(LinArr[i].B)).Y;
      if ((H*C)-(G*D)) <> 0 then
      s := ((G * (B - F)) - (H * (A - E))) / ((H*C)-(G*D))
      else
      exit;
      if (s < 1) and (s > 0) then
      begin
      OVM.X := round(GetVector(LinArr[Run].A).X + s * VRun.X);
      OVM.Y := round(GetVector(LinArr[Run].A).Y + s*VRun.Y);
      OVA := GetPoint(Add(GetVector(OVM), (mult(VNorm, -20))));
      OVB := GetPoint(Add(GetVector(OVM), (mult(VNorm, 20))));
      Canvas.LineTo(OVA.X, OVA.Y);
      Canvas.Arc(OVM.X - 20, OVM.Y - 20, OVM.X + 20, OVM.Y + 20, OVA.X, OVA.Y, OVB.X, OVB.Y);
      Canvas.MoveTo(OVB.X, OVB.Y);
      LinArr[Run].A := OVB;
      end;
      
    end;
  end;
end;

LinArr stellt meinen Array von Punktepaaren dar, (Array of TLine)
Run steht für die nummer der linie die ich gerade zeichne

Ich wäre dankbar für schnelle hilfe.

[jfheins]

Das Problem hatte ich auch mal.

Ic habe keinen Algorithmus gefunden, der aus der Begrenzung der Strecke noch etwas rausgeholt hat. Also Strecken als Gerade behandeln, und schauen, ob der Schnittpunkt auf beiden Strecken liegt.

Du solltest evtl. den "Prüfen ob Strecken sich schneiden"-Teil in eine eigene Prozedur auslagern. Ach un deine Bezeichner sind nicht unbedingt besonders aussagekräftig - wäre nett, wenn du das noch etwas erklären könntest.

[AlexanderVieth]

Mit den Bezeichnern hast du wohl recht.
Also A - H stehen für die verschiedenen Variablen in den beiden vektorgleichungen der Variablen.

Aber die Schnittpunktfunktion da rauszuziehen, klingt nach einer guten idee.
ich werde das mal ausprobieren.
Ich muss die schnittpunkte ja eh noch sortieren, da die Brückchen sonst falsch gezeichnet werden...

Vielen Dank für den Tipp erstmal.....
Das sollte glaube ich schon weiterhelfen.

[Medium]

Man kann durch die Begrenzung nur noch auf eine Weise was raus holen, die allerdings ist wenn man seeeehr viel schneiden muss echt gut: Bounding-Box Intersektion.

Die Bounding-Box ist ein die Strecke genau einfassendes Rechteck, was bei Strecken super einfach zu erledigen ist, da ein (zum Koordinatensystem orthogonales) Rechteck durch eben zwei Punkte genau definiert ist.

Sei Strecke 1 gegeben durch P1A, P1B und Strecke 2 durch P2A, P2B. Du musst nun prüfen ob ein Punkt P2* in dem Rechteck P1A, P1B liegt, was folgender Bedingung entspricht:
MinX = min(P1A.x, P1B.x)
MinY = min(P1A.y, P1B.y)
MaxX = max(P1A.x, P1B.x)
MaxY = max(P1A.y, P1B.y)
(P2*.x >= MinX) and (P2*.x <= MaxX) and (P2*.y >= MinY) and (P2*.y <= MaxY)

Wenn dieser Term für mindestens einen der beiden Punkte der Strecke 2 true ist, könnten die Strecken sich schneiden, ansonsten auf keinen Fall. Im Fall "true" muss man dann eben genauer nachsehen, auf genau die Weise wie du es schon tust. Das wäre also eine vorgeschaltete Prüfung, die schon mal grob guckt ob es sich lohnt zu rechnen.
Man handelt sich damit zwar ein paar Vergleiche mehr ein, die sind aber im Vergleich zur Fließkommaarithmetik bei der genauen Berechnung extrem fix erledigt. Das heisst es lohnt sich insbesondere dann, wenn es um recht viele, vor allem kurze Strecken geht, wo die Wahrscheinlichkeit dass sich zwei schneiden recht gering ausfällt.

Und wenn man es dann noch weiter spinnt - aber das lohnt nun wirklich erst ab ein paar hundert tausend Strecken - ist der Einsatz eines Octrees. Das ist aber schon ganz erheblicher Overhead, auch in der Implementierung, der z.B. in 3D oft und gern in Spielen eingesetzt wird um Kollisionserkennung (die ja letztlich nichts weiter als Schnittoperationen ist) effizient zu halten, und ein bewegtes Objekt wirklich nur mit nahen grob in Frage kommenden anderen tatsächlich ganz ausrechnen zu müssen.


Was dein Problem mit der Division durch 0 angeht: Rechne den Term unter dem Bruchstrich als erstes aus. Wenn der 0 ist, tausche die Strecken gegeneinander aus. Das sollte schon genügen.

[AlexanderVieth]

Habs geknackt.... vielen Dank an Alle.