Effektiver Weg um "Kollision" zu bestimmen
-
Hallo, derzeit arbeite ich an einem Petrinetz und natürlich hat dieses auch eine graphische Komponente. Nun möchte ich verhindern, dass beim Erstellen des Netzes mehrere Stellen den gleichen Platz einnehmen dürfen, sieht ja auch blöd aus. Die Frage ist wie man die Stellen am effektivsten speichert/organisiert, damit man beim setzen einer neuen Stelle schnell kontrollieren kann, ob dieser Platz schon belegt ist(Die Stellen sind Kreise mit einem gewissen Radius).
Ist natürlich nicht zeitkritisch, daher eigentlich nicht so wichtig, aber würde gerne n paar Ideen haben für mögliche spätere Projekte.
Weiß da jemand was? Vielen dank
Zur zeit hab ich einfach alle Stellen in einen Vector gespeichert und würde dann(ist noch nicht fertig) einfach den bei jedem setzen einer neuen Stelle immer durchlaufen, aber das ist natürlich für ne größere Anzahl relativ zeitintensiv.
-
Idee: Teil deine "Displayfläche" in nn Boxen in die jeweils ein Knoten passt, numerier die Fortlaufend und nimm den Index als Identifyer in ner std::map.
Dann hast du keine Kollisionen, schön wirds aber nicht.Dafür bräuchtest du warscheinlich sowas wie "Magnetismus", jeder Knoten stößt jeden anderen ab, die Ränder stoßen auch Knoten ab und du minimierst die Summe der Abstoßungen ... sowas gibts vielleicht auch schon fertig - such doch mal nach Netz-Visualisierungs-Bibs.
-
Eine gängige Struktur für Kollisionserkennung im 2D-Raum ist ein Quadtree: http://de.wikipedia.org/wiki/Quadtree
Die Frage ist jedoch, ob sich das wirklich bei dir lohnt (~ >1000 Elemente), denn erst dann würde man es also von der Performance her merken.
-
Danke schonmal, naa lohnen sicher nicht, ist sowieso nur ein kleines Projekt, aber wollte bei anderen Projekten nicht ganz "hilflos" sein.
Den Quadtree schau ich mir aufjedenfall an, danke
Noch andere Ideen?
Das mist der Displayfläche ist zwar einfach aber sieht in der tat n bisschen doof aus, wenn man nicht frei setzen kann
-
http://de.wikipedia.org/wiki/Graphentheorie
Kannst dich ja mal inspirieren lassen:
unter Links:
http://www.graphviz.org/
http://www.absint.de/aisee/index_de.htm
http://pigale.sourceforge.net/
http://pigale.sourceforge.net/images.html
