Schnittpunkte beliebiger Polygone mit einem beliebigem Achsen-parallelem Rechteck

[ohkay]

Zitat:

Zitat von schlagzu (Beitrag 1172400)

nochmal erklärt:
der rest macht sin und cos

danke für den ansatz un die bilder aber zeig mir mal bitte eine formel wie ich das mache

[Furtbichler]

Dein Rechteck ist durch 4 Strecken definiert (die Kanten).
Dein Polygon ist durch N Strecken definiert.

Du gehst nun alle Strecken p des Polygons durch und prüfst für jedes p, ob sie sich mit einer der 4 Strecken r des Rechteckes schneidet.

Wenn Du weißt, wie man
1. aus zwei Punkten eine Geradengleichung macht,
2. den Unterschied zwischen Gerade und Strecke kennst sowie
3. ausrechnen kannst, ob und wo sich zwei Strecken schneiden

dann sollte es kein Problem sein, das hinzubekommen, sofern du
4. programmieren kannst

[bernhard_LA]

hier ist mal ein Code fragment zum Ergänzen , kannst Du damit etwas anfangen ?

Delphi-Quellcode:

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    btntest: TButton;
    procedure btntestClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;



tLineType = (Horizontal, Vertikal, unbekannt);


tSimpleLine = record
        StartPunkt : TPoint;
        EndPunkt : TPoint;
        LineType : TLineType;
end;



function  Line_Intersection ( Line1 , Line2 : tSimpleLine) : Boolean;





var
  Form1: TForm1;

implementation



///
///      Linie1 ist eine Linie des Rechtecks
///      Linie2  kommt vom Polygon
///
function  Line_Intersection ( Line1 , Line2 : tSimpleLine) : Boolean;
begin

     case Line1.LineType of


     Horizontal:  begin



     end;


     Vertikal:  begin


     end;



     unbekannt:  begin


     end;

     end;


end;





{$R *.dfm}

procedure TForm1.btntestClick(Sender: TObject);
var   a, b :  tSimpleLine;
begin
      a.StartPunkt.x :=  0;
      a.StartPunkt.y :=  10;

      a.EndPunkt.x :=  10;
      a.EndPunkt.y :=  10;

      a.LineType :=  Horizontal;

      b.StartPunkt.x :=  5;
      b.StartPunkt.y :=  5;

      b.EndPunkt.x :=  12;
      b.EndPunkt.y :=  15;

      b.LineType :=  unbekannt;


      if Line_Intersection(a,b) then
         Memo1.Lines.Add('Line schneidet PolyGon')
         else
         Memo1.Lines.Add('Line schneidet PolyGon NICHT ')


end;

end.

[schlagzu]

Vergiss meine Idde viel zu umständlich.
Was die andere Betrifft, du hast 4 Geraden von deinem Viereck,
und hast n geraden von deinem Polygon.

jetzt vergleichst du alle n Geraden mit den 4 (also hast du 4*n Abfragen).

Diese Funktion sollte es tun: http://www.swissdelphicenter.ch/de/showcode.php?id=2075

[Namenloser]

Zitat:

Zitat von schlagzu (Beitrag 1172444)

Vergiss meine Idde viel zu umständlich.
Was die andere Betrifft, du hast 4 Geraden von deinem Viereck,
und hast n geraden von deinem Polygon.

jetzt vergleichst du alle n Geraden mit den 4 (also hast du 4*n Abfragen).

:hi:

Zitat:

Zitat von schlagzu (Beitrag 1172444)

Diese Funktion sollte es tun: http://www.swissdelphicenter.ch/de/showcode.php?id=2075

Die berechnet leider nur, ob zwei Geraden sich schneiden, nicht wo. Kann man vielleicht anpassen, aber weiß ich nicht... Determinanten haben wir in der Schule leider nie gemacht :(

[schlagzu]

ich hatte Determinanten leider schon -.-

ne ner 2x2 Matrix wirds einfach so berechnet http://upload.wikimedia.org/wikipedi...2f486b4902.png

Nur wie man ne schöne Funktion aus den Punkten bekommt (in Form f(x)=a*x+b) wüste ich jetzt keinen Ansatz
Zum weiter lesen, hab jetzt keine Zeit mehr dazu: http://www.xnamag.de/forum/viewtopic.php?t=2674

[Namenloser]

Zitat:

Zitat von schlagzu (Beitrag 1172479)

Nur wie man ne schöne Funktion aus den Punkten bekommt (in Form f(x)=a*x+b) wüste ich jetzt keinen Ansatz

Das ist einfach mit der Punkt-Steigungs-Form, siehe mein Bild oben ;)

[schlagzu]

Ja klar, aber kann man die Determinante auch mit Komma zahlen berechnen? Ich hatte Mathe-LK und muss sagen ich kann mich an keine erinnern. Wobei wir die Determinante nie bei Geometrie eingesetzt haben, sondern bei dem Krempel Bild Uhrbild Kern etc von Matrizen.

[Iwo Asnet]

Zwei Geraden schneiden sich? G1 = Ax+B, G2 = Mx+N
Ergo setzen wir G1=G2 (Y-Werte sind ja gleich) und suchen dazu das X...
Ax+B = Mx+N
Ax-Mx = N-B
x(A-M) = N-B
x = (N-B)/(A-M)

Fein. Wir können als X ausrechnen und dann setzen wir das in (z.B.) G1 ein und erhalten den Schnittpunkt S = (X,A*X+B)

Eigentlich haben wir ja keine Geraden, sondern Strecken. G1 wird also durch p1 und p2 begrenzt, G2 durch q1 und q2.
Der Punkt S befindet sich auf der Strecke (p1-p2) genau dann, wenn?.... Sx zwischen p1x und p2x und Sy zwischen p1y und p2y liegt.

Eigentlich popeleinfach.

[schlagzu]

Nur noch sonderfall G1 = G2 und G1 || G2 beachten, sonst gibts n Division by Zero.
abfangen durch vergleichen der Steigung.

Aber ja stimmt, eigentlich müsste es so gehen :D