Forum: Algorithmen, Datenstrukturen und Klassendesign
by Blup,
22. Aug 2013
Muss man nicht, man kennt aus der Reihenfolge in der Y-Liste in welcher Reihenfolge von Oben nach Unten die Linien durch die Sweep-Linie geschnitten werden.
So wie ich die Beschreibungen verstanden habe ist bei der Y-Liste nie von Punkten die Rede.
Der Algo sieht vor das Linien eingefügt, innerhalb der Liste getauscht oder entfernt werden.
In der X-Liste werden allerdings tatsächlich...
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Blup,
22. Aug 2013
Die Neuberechnung betrifft nur die Linien, mit denen tatsächlich verglichen wird.
Die Steigung jeder Linie muss man nur einmal je Linie vorberechnen.
Dann beschränkt sich die Neuberechnung auf eine Multiplikation und eine Addition.
Vergleicht man jeweils die neue Linie in der Mitte der Menge der Linien, halbiert sich die für den Vergleich relevante Menge durchschnittlich mit jedem Vergleich....
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Blup,
21. Aug 2013
Nein, in den Y-Baum (eigentlich eine Liste) fügt man Linien ein, nicht einzelne Punkte.
Beim Einfügen einer Linie vergleicht man den linken Punkt dieser Linie mit dem aktuellen Schnittpunkt der anderen Linien der Liste an dieser X-Position ("Sweep-Linie").
Dadurch wird die Einfügeposition in der Liste bestimmt.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Blup,
20. Aug 2013
Die Y-Liste enthält die "aktiven Linien" sortiert nach dem Schnittpunkt mit der "Sweep-Linie".
Soll eine neue Linie hinzugefügt werden, müssen die Schnittpunkte der vorhandenen Linien mit der "Sweep-Linie" neu bestimmt werden, damit die neue Linie an der richtigen Stelle eingefügt werden kann.
In diesem Fall wird b unter a eingefügt.