Schnittpunkte beliebiger Polygone mit einem beliebigem Achsen-parallelem Rechteck

[ohkay]

Hey

ich sitze in ner Sackgasse Hilfe.

in Image:
Ich habe ein Rechteck welches Achsen-parallel durch (xmin,ymin) und (xmax,ymax) def. ist.
Nun setz ich Polygon punkte (belibig viel) und lasse diese Polygone dann in der Reinfolge verbinden.

jetzt kommt das problem, : jede der Polygonstrecken soll drauf untersucht werden ob sie das Rechteck schneiden wenn ja, soll der Schnittpunkt gekennzeichnet werden.

wenn wer ne Lösung hat die ich verstehe bin ich sehr dankbar

mfg Martin



Ich dank allen für ihre hilfe hir miene Lösung nach 2 tagen ...

[Delphi]
procedure Schnittpunkt(x1,y1,x2,y2,x3,y3,x4,y4:integer;var xs,ys:integer; var ok:boolean);
var
d:integer; t1,t2:real;
function det (a,b,c,d:integer):integer;
begin
det:=a*d-b*c;
end;
begin
d:= det(x2-x1,x3-x4,y2-y1,y3-y4);
ok:= false;
if d<>0 then
begin
t1:=det(x3-x1,x3-x4,y3-y1,y3-y4)/d;
t2:=det(x2-x1,x3-x1,y2-y1,y3-y1)/d;
if (t1>=0) and (t1<=1) and (t2>=0) and (t2<=1) then

begin
xs:=x1+round(t1*(x2-x1));
ys:=y1+round(t1*(y2-y1));
ok:=true;
end;
end;
end;

//die anwendung der funktion für mein problem
{procedure TForm1.Button3Click(Sender: TObject); //schnittpunkte anzeigen
var
i:integer;
xs,ys:integer;
ok:boolean;

begin
xp[n+1]:=xp[1];
yp[n+1]:=yp[1];
for i := 1 to n do
begin
image1.Canvas.Pen.Color:=clred;
Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmin,ymin,xmax,ymin,xs,ys,ok); //schnitpunkte oben
if ok then
begin
image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
end;
Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmax,ymin,xmax,ymax,xs,ys,ok); //schnitpunkte rechts
if ok then
begin
image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
end;
Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmax,ymax,xmin,ymax,xs,ys,ok); //schnitpunkte unten
if ok then
begin
image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
end;
Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmin,ymax,xmin,ymin,xs,ys,ok); //schnitpunkte links
if ok then
begin
image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
end;
end;
end;}
end.
[Delphi]

[schlagzu]

testen ob der erste Punkt in dem Rechteck liegt und der zweite nicht (oder umgekehrt).
Das nächste wäre dann die die diagonal durch gehen und beide außerhalb liegen und trotzdem schneiden.

Dann denn Schnittpunkt berechnen mit Dreieck (Rechtwinklig)

PS:

die die diagonal gehen so abfangen: 1 Punkt x liegt zwischen xmin xmax, 2Punkt y liegt zwischen ymin ymax

[schlagzu]

Mal zur Anschauung
PS: der eine strich sollte noch rot sein

[Namenloser]

Überprüfe doch einfach für jede Linie des Polygons einzeln, wo sie sich mit den vier Seiten des Rechtecks, die ja ebenfalls Strecken sind, schneidet.

Hier findest du einige Lösungen, um Schnittpunkte von Strecken zu berechnen.

Die Tatsache, dass das Rechteck achsenparallel ist, könnte man allerdings ausnutzen und damit einfacheren Code erzeugen. Du kannst dir die diagonale Strecke (bzw. Gerade) als lineare Funktion und die achsenparallele Strecke als Y-Achse auf einem Funktionsgraphen denken. Dann kannst du leicht den Schnittpunkt ausrechnen – dann musst du noch schauen, ob der Schnittpunkt im Bereich der Strecke liegt.

Für die andere Achse musst du die Koordinaten vertauschen.

[ohkay]

also ich bin so weit (als neuling) gekommen

Delphi-Quellcode:

var
    n,m,xmin,ymin,xmax,ymax:integer;
    p1:boolean;
    xp,yp:array  [1..100] of integer;

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
          Shift: TShiftState; X, Y: Integer);
  begin                                                                         //Recheck zeichnen
      if button=mbleft then
      if radiogroup1.ItemIndex=0 then
      begin
          if p1 then
          begin
              xmin:=x;
              ymin:=y;
              p1:=false;
              image1.Canvas.Rectangle(x-3,y-3,x+3,y+3);
          end
          else
          begin
              xmax:=x;
              ymax:=y;
              p1:=true;
              image1.Canvas.Rectangle(xmin,ymin,xmax,ymax);
              image1.Canvas.Rectangle(x-3,y-3,x+3,y+3);
          end;
      end
      else
      begin                                                                     //Poligohnpunkte
          n:= n+1;
          xp[n]:=x;
          yp[n]:=y;
          image1.Canvas.Rectangle(x-3,y-3,x+3,y+3);                             
      end;
  end;

procedure TForm1.Button1Click(Sender: TObject);                                 //poligon zeichnen

  var
      i,s: Integer;
      sr: real;
  begin
      for i := 1 to n-1  do
      begin
          image1.Canvas.MoveTo(xp[i],yp[i]);
          image1.Canvas.LineTo(xp[i+1],yp[i+1]);
      end;
      image1.Canvas.LineTo(xp[1],yp[1]);
      image1.Canvas.Pen.Color:=clblack;
  end;

procedure TForm1.Button3Click(Sender: TObject);                    //berechnung und ausgabe visuel

  var
      x1,y1,x2,y2,x3,y3,x4,y4: integer;   //...
      x5,y5: integer;                     //...
      ok: boolean;                        //...
  begin
          ????
  end;

end.

aber was du jetzt genau willst, was ich machen soll versteh ich net bzw ich weiß was du mienst aber ich kann das nicht umsetzen

[ohkay]

ok ich versuchs

[ohkay]

mhh klappt net so ganz

[schlagzu]

Also bekannt bei den dreiecken ist dir eine Seite und die Winkel (durch Polygon Hausrechenbar)zudem eine Koordinate. Das hat nichts mit Delphi zutun sondern Geometrie

[schlagzu]

nochmal erklärt:
der rest macht sin und cos
und die andere Idee ist leichter :D da hast du sogar die Funktion gegeben

[Namenloser]

Im Anhang findest du eine Skizze und eine Herleitung für den Schnittpunkt mit den horizontalen Seiten des Rechtecks. x0 und y0 beschreiben einen beliebigen Punkt auf der blauen Geraden (also z.B. die Koordinaten von P1 oder P2).

Die Mathematik kannst du eigentlich 1:1 in Source Code umsetzen.

Am Ende musst du noch prüfen, ob der Schnittpunkt auf der grünen und der blauen Strecke liegt, was einfach zu erledigen ist, indem du die X-Koordinaten vergleichst.

Sonderfall:
Δx = 0 → entweder kein Schnittpunkt oder unendlich Schnittpunkte. Muss auf jeden Fall abgefangen werden, weil sonst eine Division durch 0 entsteht.

[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

[ohkay]

:-D:-D

danke für eure hilfe ich habe eine elegante lösung gefunden dank euch


:-D:-D

Delphi-Quellcode:

procedure Schnittpunkt(x1,y1,x2,y2,x3,y3,x4,y4:integer;var xs,ys:integer; var ok:boolean);
  var
      d:integer; t1,t2:real;
 function det (a,b,c,d:integer):integer;
  begin
      det:=a*d-b*c;
  end;
  begin
      d:= det(x2-x1,x3-x4,y2-y1,y3-y4);
      ok:= false;
      if d<>0 then
      begin
          t1:=det(x3-x1,x3-x4,y3-y1,y3-y4)/d;
          t2:=det(x2-x1,x3-x1,y2-y1,y3-y1)/d;
          if (t1>=0) and (t1<=1) and (t2>=0) and (t2<=1) then

          begin
              xs:=x1+round(t1*(x2-x1));
              ys:=y1+round(t1*(y2-y1));
              ok:=true;
          end;
      end;
  end;

//die anwendung der funktion für mein problem
{procedure TForm1.Button3Click(Sender: TObject);                                 //schnittpunkte anzeigen
 var
    i:integer;
    xs,ys:integer;
    ok:boolean;

  begin
      xp[n+1]:=xp[1];
      yp[n+1]:=yp[1];
      for i := 1 to n do
      begin
      image1.Canvas.Pen.Color:=clred;
          Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmin,ymin,xmax,ymin,xs,ys,ok);  //schnitpunkte oben
          if ok  then
          begin
              image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
          end;
          Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmax,ymin,xmax,ymax,xs,ys,ok);  //schnitpunkte rechts
          if ok  then
          begin
              image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
          end;
          Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmax,ymax,xmin,ymax,xs,ys,ok);   //schnitpunkte unten
          if ok  then
          begin
              image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
          end;
          Schnittpunkt(xp[i],yp[i],xp[i+1],yp[i+1],xmin,ymax,xmin,ymin,xs,ys,ok);   //schnitpunkte links
          if ok  then
          begin
              image1.Canvas.Rectangle(xs-3,ys-3,xs+3,ys+3)
          end;
      end;
  end;}
end.

das wars schon, ich hoffe es hilft auch mal anderen
dank noch mal an alle



:-D
mfg martin

[Bummi]

Funktioniert einwandfrei Martin, ich hätte noch eine Version mit einer leicht geänderten Schreibweise

Delphi-Quellcode:

Function Schnittpunkt(v1, b1, v2, b2: TPoint; var ResultPoint: TPoint): Boolean;

  function det(a, b, c, d: Integer): Integer;
  begin
    Result := a * d - b * c;
  end;

var
  d: Integer;
  t1, t2: Double;
begin
  d := det(b1.X - v1.X, v2.X - b2.X, b1.Y - v1.Y, v2.Y - b2.Y);
  if d <> 0 then
  begin
    t1 := det(v2.X - v1.X, v2.X - b2.X, v2.Y - v1.Y, v2.Y - b2.Y) / d;
    t2 := det(b1.X - v1.X, v2.X - v1.X, b1.Y - v1.Y, v2.Y - v1.Y) / d;
    Result := (t1 >= 0) and (t1 <= 1) and (t2 >= 0) and (t2 <= 1);
    if Result then
    begin
      ResultPoint.X := v1.X + round(t1 * (b1.X - v1.X));
      ResultPoint.Y := v1.Y + round(t1 * (b1.Y - v1.Y));
    end;
  end;
end;

procedure TForm2.FormMouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if Tag = 0 then
  begin
    P1.X := X;
    P1.Y := Y;
  end
  else
  begin
    p3.X := X;
    p3.Y := Y;
  end;
end;

procedure TForm2.FormMouseMove(Sender: TObject; Shift: TShiftState;
  X, Y: Integer);
begin
  if ssLeft in Shift then
  begin
    if Tag = 0 then
    begin
      p2.X := X;
      p2.Y := Y;
    end
    else
    begin
      p4.X := X;
      p4.Y := Y;
    end;
  end;
  invalidate;
end;

procedure TForm2.FormMouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if Tag = 0 then
    Tag := 1
  else
    Tag := 0;

end;

procedure TForm2.FormPaint(Sender: TObject);
var
  sp: TPoint;
begin
  Canvas.MoveTo(P1.X, P1.Y);
  Canvas.LineTo(p2.X, p2.Y);
  Canvas.MoveTo(p3.X, p3.Y);
  Canvas.LineTo(p4.X, p4.Y);
  if Schnittpunkt(P1, p2, p3, p4, sp) then
  begin
    Canvas.Ellipse(sp.X - 5, sp.Y - 5, sp.X + 5, sp.Y + 5);
  end;
end;