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:

1. Jeder Umriss enthält möglichst viele Knoten gleicher Farbe und
   
2. keinen Knoten einer anderen Farbe
   
3. Kein Knoten ist weiter als $limit vom nächsten im zugehörigen Umriss entfernt
   
4. ist eins davon nicht möglich, muss ein neuer Umriss begonnen werden
   
5. 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

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.

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.

Du weißt nicht, wie es heißt, aber es ist dir zu einfach?!?

Mein Ansaz wäre irgendwie so:

Oder irgendwie so.

Okay, ist tatsächlich geometrisch.

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

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...

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

genau, und in den inseln sollen sich dann, wenn möglich, möglichst viele gleichfarbige punkte befinden...

Genau... möglichst wenige möglichst große Inselchen

Hi,

gibt es inzwischen eigentlich ein bisschen Code. Würde mich sehr interessieren, wie und ob ihr das Problem gelöst habt.

Grüße,

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