Metaman hat geschrieben:Derzeit ist es so, das über eine Simple Zufallsfunktion die Platzierung der Einträge ermittelt wird.
das hat aber zur folge das selbst bei nur zwei Einträgen auf der Seite diese übereinander liegen können.
Da der Zufall logischerweise nicht steuerbar ist, kannst Du Kollisionen nur verhindern, indem Du belegte Pixel protokollierst.
Ansatz:
Um zu verhindern, dass zigmal gewürfelt werden muss, weil immer wieder eine belegte Position rauskommt, würde ich eine sortierte Liste verwenden, in der die belegten Pixel oder besser noch Pixelbereiche eingetragen sind. Zur Positionierung
eine Zahl zwischen 0 und Gesamtzahl_freier_Pixel-1 auswürfeln und dann quasi von links nach rechts, oben nach unten über die Fläche wandern, dabei belegte Pixel nicht mitzählen. Wenn unten rechts angekommen, oben links bei Pixel 0 weitermachen.
Der freie Platz zwischen den belegten Pixeln ergibt sich aus der Differenz zweier benachbarter Listeneinträge; diese Differenz ist bei jedem Schritt von einem zum nächsten Listeneintrag von der Zufallszahl abzuziehen, sofern sie dadurch nicht kleiner als 0 wird.
Auf diese Weise gelangt man am Ende der Tour definitiv an zumindest einen freien Pixel. Reicht der nachfolgende Platz nicht aus, von dort einfach weitergehen, bis genügend gefunden (dann Grafik einfügen) oder man wieder am ausgewürftelten Platz angekommen ist (kein Platz mehr für Grafik, abbrechen).
Grafik einfügen, neu belegte Pixelbereiche in die Liste eintragen (auf Sortierung achten), benachbarte Pixelbereiche zusammenfassen und Summe neu belegter Pixel von Gesamtzahl_freier_Pixel abziehen.
Da in der Liste nur belegte Pixel stehen, überspringt man automatisch die freien Plätze und spart sich die Prüfung jedes einzelnen Pixel, wie es bei einem Feld der Fall wäre. Bei einer Fläche von zum Beispiel 600x300 Pixeln sind das maximal 180.000 gesparte Prüfungen.
Zur Optimierung könnte man dafür sorgen, dass Grafiken sich bei der Platzierung "anziehen". Ist der Abstand zwischen zwei Grafiken kleiner als zum Beispiel 20 Pixel, wird die neue Grafik direkt an die bestehende angedockt. Den Wert könnte man der Anzahl der Grafiken anpassen - je mehr Grafiken, desto "magnetischer" werden sie.
Ob man damit die Platzverschwendung tatsächlich wirksam verringert, kann ich allerdings nur vermuten.
