Eine Art Polygon

[gauo]

Hallo, danke schonmal für jeden tipp und jede Hilfe ^^.

Also für ein Strategiespiel von mir brauche ich die möglichkeit die Fläche der Kontrollierten Fläche zu berechnen.
Das problem ist meine einteilung der Spielfläche,
und zwar sind die Objekte die die ausschlaggebend für die Kontrolle sind, mehr oder weniger wahllos platziert,
haben weder eine feste größe oder ähnliches (Galaxy->Sonnensystem) und können auch geteilt werden falls sie noch umstritten sind.
Die Fläche an sich brauche ich für eine Faktoren für die KI, sowie für die Anzeige und wahscheinlich eine Art erhaltungskosten/bzw auch Handelsgewinn für das Imperium.

An sich muss ich diese nur für die umstrittenen Sonnensysteme(entweder mit einem anderen Imperium, oder
umstritten mit Neutral, also noch am aufdecken) berechnen.
Ich dachte daran für die in dem Sonnensystem vorhandenen Fraktionen, jeweils eine Ansammlung von
Punkten zu haben(Koord. der Stelaren Objekte) und dann die größt mögliche Fläche zu berechnen die von
diesen Pkt aufgespannt wird ohne einen pkt der anderen zu beinhalten.

Gibt es eine möglichkeit das effizient zu berechnen bzw kann mir einer ne idee geben, ich habs bereits mit
Polygon versucht, aber das problem ist, dass er halt nicht die größte Fläche liefert die aufgespannt wird, und
ich dann halt immer die Pkt in der richtigen reihenfolge liefern müsste.


am ende nochmals danke für jegliche hilfe.

 

[Marco13]

Klingt als wolltest du ein http://de.wikipedia.org/wiki/Voronoi-Diagramm erstellen!?

 

[gauo]

Wow, danke das ist tatsächlich die beschreibung von dem was ich brauche...
ich müsste wahrscheinlich nur noch eine metrik definieren, damit der nähe
begriff wirklich passt :/...naja wie man das umsetzt ist wohl die größte frage für mich ^^

 

[0x7F800000]

Naja, da es dir ja um ein Weltraum-Strategie spiel geht, wäre die stinknormale euklidische Metrik wohl die sinnvollste wahl?

aber ehrlichgesagt verstehe ich nicht wirklich, was du mit irgendwelchen flächen anfangen willst? zähl doch einfach die objekte, die irgendeine bedeutung haben... Was bringt mir ein kubik-lichtjahr für vorteile, wenn es nur mit staub und nem paar ausgebrannter sterne gefüllt ist?

 

[Marco13]

Naja, in 2D könnte man ja "erstmal" einfach die "normale" Entfernung (Euklidische Distanz) nehmen. Bei sowas wie http://www.google.com/search?hl=en&q=java+voronoi+class&btnG=Google+Search&aq=f&oq= findet man auch schnell source code, den man mal verwenden kann, um zu sehen, ob die gewünschten Ergebnisse erreicht werden.

 

[gauo]

Hm...ich muss mir doch nochmal überlegen, ob dies das richtige ist.
Unabhängig davon wie ich die fläche im spiel verwende, kann ich ja mich auf die graphische Darstellung der Kontrollierten Fläche
beziehen.
Voronoi-Diagramme lösen dann nur das Problem, die Fläche um ein relevantes Objekt zu beschreiben, dass sich am Rand der kontrollierten Fläche befindet.

Eine Lsg so wie ihr es meint wäre dann doch alle kontrollierten Objekte durchzugehen und ihre Umgebungen zu zerlegen, und dann
diese Flächen für die jeweiligen Spieler zu vereinigen,...
Das Voronoi-Diagramm ist dann noch abhängig davon, dass es
die Menge der Pkt ist die mehreren "Zentren" von unterschiedlichen Imperien kontrolliert werden.