# Array Nachbarpositionen berechnen



## Se7en (14. Dez 2008)

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 (14. Dez 2008)

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 (14. Dez 2008)

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

MfG
Se7en


----------



## 0x7F800000 (14. Dez 2008)

Marco13 hat gesagt.:
			
		

> 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 (14. Dez 2008)

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 (15. Dez 2008)

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 (15. Dez 2008)

Marco13 hat gesagt.:
			
		

> 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 (16. Dez 2008)

Andrey hat gesagt.:
			
		

> Marco13 hat gesagt.:
> 
> 
> 
> ...


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

hand, mogel


----------

