Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Graphen finden
Martok - So 16.11.08 16:12
Titel: Graphen finden
Hi!
In der SB ist es schon angeklungen, ich brauche mal wieder einen Ansatz von euch. Bzw. ich hab sogar schon einen, aber bevor ich da weiter mache möchte ich erstmal wissen was das eigentlich ist ;)
Aaaalso.
Es gibt eine Menge Punkte. Jeder dieser Punkte ist durch X,Y und eine 'Farbe' definiert.
Ich möchte jetzt eine Art 'Umrisse' finden, so dass folgendes passiert:
- Jeder Umriss enthält möglichst viele Knoten gleicher Farbe und
- keinen Knoten einer anderen Farbe
- Kein Knoten ist weiter als $limit vom nächsten im zugehörigen Umriss entfernt
- ist eins davon nicht möglich, muss ein neuer Umriss begonnen werden
- Umrisse können daher auch aus 1..2 Elementen bestehen, obwohl beides eigentlich keine Flächen beschreibt.
Im Anhang findet man einige Beispiele.
Rot und grün sind wegen 3. gespalten. Im Grunde auch wegen 2.
Gelb ist nichtkonvex, da blau eine direkte Verbindung verhindert. Durch 3. und 5. steht unten ein einzelner gelber Punkt.
Grün demonstriert Regel 1, also dass der größte Umkreis gesucht ist,
in dem andere Punkte gleicher Farbe liegen.
 Gausi in der SB hat folgendes geschrieben: |
| Meinst du die konvexe Hülle einer Punktmenge? |
Fällt mir grade auf... eigentlich nicht, siehe Gelb.
Klingt eigentlich nach einer Paranuss... hoffentlich hab ich hier nicht grade durch Zufall eine erwischt ;)
cu
Martok
Gausi - So 16.11.08 16:22
Da hast du in der SB aber nach dem falschen Gebiet gefragt. Mit Graphalgorithmen kommt man hier nicht weit, das ist ein gemetrisches Problem. Einen Ansatz habe ich auf Anhieb nicht, und auch keinen Namen für das Problem, der einem dabei weiterhelfen könnte. :nixweiss:
Martok hat folgendes geschrieben  : |
| Klingt eigentlich nach einer Paranuss... hoffentlich hab ich hier nicht grade durch Zufall eine erwischt ;) |
Ne, sowas einfaches machen wir da nicht. :twisted:
Wolle92 - So 16.11.08 16:25
Du weißt nicht, wie es heißt, aber es ist dir zu einfach?!?
Martok - So 16.11.08 17:25
Delphi-Quelltext
1:
| Wolle92.IronieDetektor.CheckFuntionality; |
Mein Ansaz wäre irgendwie so:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
| AlleKnoten:= array of Punkt(x,y,Farbe)
solange AlleKnoten nicht leer:
Neuer Graph
Nimm Knoten aus alleKnoten;
graph.farbe := dieserKnoten.Farbe
solange AlleKnoten nicht leer:
nimm knoten aus alleKnoten where farbe = graph.farbe; //hups, zu viel SQL gemacht...
wäre graph immer noch gültig?
ja:
knoten einfügen
knoten aus alleKnoten entfernen
sonst:
schleife verlassen
wiederhole
wiederhole |
Oder irgendwie so.
Okay, ist tatsächlich geometrisch.
miniC# - So 16.11.08 19:16
brauchen die farben für eine einfache lösung nicht eine zeichenfolge, bzw prioritäten ?
diese punktmenge:
hat zwo lösungen :
ohne prioritäten müssest du bei jedem schritt den ganzen baum erstellen und ihn mit dem alternativbaum in der anzahl der verbleibenden punkte vergleichen.
also entweder prios oder lookahead, oder verstehe ich da was falsch ?
edit : wo ich es grade poste , sehe ich , dass lösung 2 nicht ganz korrekt verbunden ist :)
Wolle92 - So 16.11.08 20:23
ne, lösung 2 ist schon ok so...
es können auch Umrisse mit einem Knoten existieren, aber Lösung 1 hat den Fehler, das im Rot-Umriss nen blauer Punkt steckt...
miniC# - So 16.11.08 20:35
| Wolle92 hat folgendes geschrieben : |
| ne, lösung 2 ist schon ok so... |
naja der dritte rote punkt ist verbindbar (angenommen erliegt innerhalb der maximalreichweite) und es sollen immer alle möglichen verbindungen gefunden werden.
| Wolle92 hat folgendes geschrieben : |
| aber Lösung 1 hat den Fehler, das im Rot-Umriss nen blauer Punkt steckt... |
das war doch meine frage/hinweis. ich seh nämlich keine regel, die die verkettungspriorität der farben bestimmt. das beispiel ist etwas
unglücklich gewählt von mir. verschiebe den in beispiel 2 von mir nicht verbundenden roten punkt 1 cm hoch in das blaue rechteck, dann
hast du es deutlicher :
l1 = {rot1,rot2,rot3} & {blau1,blau2} & blau3
l2 = {b1,b2,b3} & {r1,r2} & r3
edit : ah , ok jetzt verstehe ich , es soll keine verkettung gleichfargbiger punkte sein , sondern inselchen :)
Wolle92 - So 16.11.08 20:48
genau, und in den inseln sollen sich dann, wenn möglich, möglichst viele gleichfarbige punkte befinden...
Martok - Mo 17.11.08 00:13
Genau... möglichst wenige möglichst große Inselchen ;)
freedy - Di 18.11.08 09:48
Hi,
gibt es inzwischen eigentlich ein bisschen Code. Würde mich sehr interessieren, wie und ob ihr das Problem gelöst habt.
Grüße,
Martok - Di 18.11.08 23:45
Naja, Pseudocode gibts ja oben... zum implementieren fehlt mir im Moment die Zeit... unter anderem, weil in dem Browsergame für das das eigentlich ist uns grad der Krieg erklärt wurde xD
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!