Schnittpunkte beliebiger Polygone mit einem beliebigem Achsen-parallelem Rechteck

[Namenloser]

Zitat von 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).

Zitat von schlagzu:

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

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

[ohkay]

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

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




mfg martin