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.