schneidet eine Strecke ein Polygon

[Robert Marquardt]

Hast du dich auch mit nicht-konvexen Polygonen beschaeftigt? Die Entscheidung was dabei innen und aussen ist, ist garnicht so leicht.

[Flogo]

Ja! Meine Polygone sind nicht immer konvex. Bis jetzt lief die fehlerhafte Prozedur ungefähr so:

Code:

Innen := false;
für alle Linien im Polygon
  wenn die Linie[i] und die Linie((Punkt.X, 0), (Punkt.X, MaxY)) sich schneiden dann
  begin
    wenn Schnittpunkt.Y > Punkt.Y dann
      Innen := not Innen;
    wenn Abs(Schnittpunkt.Y - Punkt.Y) < Abs(Bester.Y - Punkt.Y) then
      Bester := Schnittpunkt;
  end;
Wenn Innen dann 
  Result := Punkt
sonst
  Result := Bester;

Das ganze hat dann noch - wenn kein Schnittpunkt in der Spalte war - solange in beide Richtungen die Nachbarspalten ausprobiert, bis ein Punkt gefunden wurde.

Leider liefert der Schnittpunkt, der gespeichert wird, ungenaue, gerundete Werte, di nicht immer im Polygon liegen.