Array Nachbarpositionen berechnen

[Se7en]

Hi Leute,

also ich habe folgendes Problem ich habe ein zweidimensionales Array zufällig mit true oder false initialisiert. Ich soll nun zu jeder Position berechnen wieviele direkte Nachbarn auf "true" gesetzt sind. Das Array soll dabei als Kugel angesehen werden also als Beispiel:

0 1 2 3 4
0 x
1
2
3
4

Die Position 0/0 hat die direkten Nachbarn 1/0, 0/1, 4/0 und 0/4.

Jetzt hab ich aber kein Plan wie ich dies erreiche, ich hab schon ein bisschen rumprobiert in dem ich mit for-Schleifen das Array durchgegangen bin, aber ich weiß nicht genau wie ich die Überprüfung mit einbaue.

Ich hoffe es ist einigermaßen klar geworden was das Problem ist, ich bin dankbar für jede Hilfe !

MfG
Se7en

 

[Marco13]

Für eine Position (x,y) gibt es 4 Nachbarn
(x+1,y)
(x,y+1)
(x-1,y)
(x,y-1)
Diese Koordinaten kann man ausrechnen. Das "Kugel"-Verhalten kann man erreichen, indem man ungültige Indizes korrigiert:
if (x<0) x=width-1;
if (x>=width) x=0;
if (y<0) y=height-1;
if (y>=height) y=0;

 

[Se7en]

Oh, man manchmal ist man echt blind vor Augen :lol: , ich danke dir vielmals für den Tipp !

MfG
Se7en

 

[0x7F800000]

Diese Koordinaten kann man ausrechnen. Das "Kugel"-Verhalten kann man erreichen, indem man ungültige Indizes korrigiert:
if (x<0) x=width-1;
if (x>=width) x=0;
if (y<0) y=height-1;
if (y>=height) y=0;

zwei mal "pfui" Marco13 !

Wenn du die Ränder des rechteckigen Arrays auf diese Art und weise zusammenklebst, erhälst du keine Kugel sondern einen Torus .

Eine Kugel kannst du daraus gar nicht bauen.

________________________

(edit: schlechte) Begründung: Stelle dir dieses 2D-Array als ein recheteckiges gitter vor. Die arrayelemente sind "Knoten" die "Nachbar-Beziehungen" sind kanten, und darzwischen bleiben noch viereckige Flächen. Dabei enden die "Nachbar-Beziehungen" nicht an den rändern, sondern "springen" wieder zum gegenüberliegenden Rand des "array-rechtecks".

Jetzt kannst du dir vorstellen, dass du zu jedem Knoten genau eine Fläche und zwei Kanten zuordnen kannst, ohne dass irgendwelche Konflikte entstehen. Ist dein Array n*m elemente Groß, so erhälst du für die Euler-Charakteristik dieses Gitters:

X=n*m*(1 [Knoten] + 1 [Fläche] + 2 [Kanten])=n*m*(1+1-2)=n*m*0=0

Aus dem Eulerschen Polyedersatz, bzw aus dem allgemeineren Satz über Planare Graphen weißt du, dass bei konvexen Polyedern #Knoten+#Flaechen-#Kanten=2 gelten muss (per Induktion elementar in 2 minuten beweisbar)

Also:
2 != 0

Deswegen kannst du dieses Gitter unmöglich auf eine Kugel legen. Auf ein Torus natürlich schon, denn Torus hat ja grade die Charakteristik 0.

______________________

Und im übrigen: im code würde ich auch nicht empfehlen, so viele if-anweisungen reinzubauen. Definiere doch einfach:

public static int mod(int x, int n){
  return Math.abs(x)%n;
}

und schreibe dann:

(mod(x+1,width),y)
(x,mod(y+1,height))
(mod(x-1,width),y)
(x,mod(y-1,height))

dadurch erhälst du so etwas wie einen zu (Z/widthZ x Z/heightZ) isomorphen "diskreten Torus".

 

[0x7F800000]

Hm... ???:L Ne, verdammt, was wollte ich da eigentlich beweisen? Also, ich müsste da doch noch ein wenig präzisieren: 2x3 Punkte kann man zum beispiel schon ganz gut zu einem Oktaeder verbinden, dann treffen sich auch vier kanten in einem Knoten.

Aber dreiecksfrei ist es dann nicht mehr, d.h. es wird nicht mehr "schön rechteckig" bleiben, insbesondere lässt sich das dann nur sehr umständlich bis gar nicht auf rechteckige arrays übertragen, diese "Nachbarrelation" zu definieren wird ein ziemlicher Krampf.

Also, um genau zu sein, müsste man da schon ein wenig mehr arbeit investieren. Vor allem bräuchte man da eine genaue Definition für "umständlich"...

 

[Marco13]

ICH hatte das Wort "Kugel" ja auch in Anführungszeichen gesetzt :meld: Mir war natürlich klar, dass das nicht gehen kann ( :wink: )

Und zu den if-Abfragen... das war ja nur Pseudocode :roll: dafür eine Hilfsmethode zu machen - klar, warum nicht, aber das abs und mod erscheint mir komplizierter, ineffizienter und weniger intuitiv als zwo if-Abfragen ....

 

[0x7F800000]

ICH hatte das Wort "Kugel" ja auch in Anführungszeichen gesetzt :meld: Mir war natürlich klar, dass das nicht gehen kann ( :wink: )

iss gut, wollte hier nur ein wenig klugscheißern zur Abwechslung

 

[Gast2]

ICH hatte das Wort "Kugel" ja auch in Anführungszeichen gesetzt :meld: Mir war natürlich klar, dass das nicht gehen kann ( :wink: )

iss gut, wollte hier nur ein wenig klugscheißern zur Abwechslung

ist Dir gelungen :? ... ich weis schon wieso ich mit Maschinenbau aufgehört habe

hand, mogel