eins muss ich vorher wissen sind polygone immer konvex?

ich werd nochmal genauer antworten aber man kann alle auf einmal vergleichen und es ist keine infinitesimalrechnung es nutzt nur ein verständnis was anstieg bedeutet, und auch das nur für linien ale lineare gleichungen. du berechnest den anstieg delta y / delty x um diesen wert, egal ob positiv oder negativ jede runde auf den schnittpunkt mit senkrechten zu addieren. denn alles was uns interessiert sind die beiden bunkte des polygons wo es auf der aktuellen senkrechten anfängt und wo aufhört. (wenn wir die auch noch sortiert halten bemerkst du kollisionen sehr einfach) und durch addition der
anstiege gehen wir quasi einen schritt nach rechts.

eins noch zur datenstruktur der punkte, enschuldige ich meinte doppelt verkettete liste. das het ganz einfach in dem du einmal linear durch alle punkte durchgehst und

ich halt das für einfacher als bei eigentlichen berechnung jedes mal die liste durchzugehen um zu schaun wohin die kante führt, da du vorher nicht weisst in welche richtung du sie abtasten wirst. das polygon ist rechtsherum im urzeigersinn definiert, aber wir gehen dann strict von links nach rechts weiss bei unteren kanten gegen uhrzeigersinn gehen wird.

kannst natürlich auhc fertige sachen nehmen, das ganze heisst sweep test.

und wenn auf wx umsteigen willst wir hatten neulich erst einen thread der die sache mit der PainDC erklärte.
Last edited: 2010-12-12 15:35:02 +0100 (CET)