# Kubische Suche um ein Element in array[][][]



## Ark (30. Mrz 2007)

Ich kriege noch eine Meise! >_< Folgendes:

Es gibt ein dreidimensionales Array a beliebiger Größen xa, ya und za in allen Dimensionen. Außerdem existiert in a an beliebiger Stelle ein Element e, dessen Koordinaten xe, ye und ze gegeben sind.

Nun sollen alle Elemente in a auf eine spezielle Eigenschaft hin durchsucht werden. Falls diese Eigenschaft festgestellt wurde, kann die Suche abgebrochen werden.

Allerdings kann dabei aus Performancegründen a nicht einfach mit drei Schleifen durchsucht werden. Stattdessen soll zunächst der direkt um e liegende „Würfelmantel“ durchsucht werden, anschließend dieser Würfel vergrößert und da weitergesucht werden. Dies soll so lange durchgeführt werden, bis die Seiten des Würfels eine gewisse Länge l inklusive erreicht haben. Natürlich soll dabei kein Element zweimal untersucht und im Falle einer drohenden ArrayIndexOutOfBoundsException der logischerweise nicht mehr in a liegende Bereich nicht durchsucht werden.

Ich versuche schon die ganze Zeit, einen Ansatz zu finden, aber ich kriege das maximal noch für den eindimensionalen Fall hin. :lol: Kann mir da jemand weiterhelfen? Es würde mich sehr freuen. 

Ark

P.S.: Hoffentlich ist mein Threadtitel einigermaßen aussagekräftig/richtig gewählt.


----------



## Leroy42 (30. Mrz 2007)

Ark hat gesagt.:
			
		

> P.S.: Hoffentlich ist mein Threadtitel einigermaßen *aussagekräftig*/richtig gewählt.


 :shock: Nicht mehr oder weniger als der eigentliche Postinhalt! :shock:


----------



## Wildcard (30. Mrz 2007)

Vom Algo her ist das ja nicht so schlimm:
Du brauchst 
-eine Methode die 'n' Werte zeilenweise untersucht
-eine Methode die 'n' 'Zeilen' von der ersten Methode überprüfen lässt
-eine Methode die 'n' 'Flächen' von der zweiten Methode überprüfen lässt.
Muss man nur noch Coden  :wink:


----------



## Ark (30. Mrz 2007)

Ich habe mal das hier skizziert für eine Kantenlänge 5. Gezeigt sind die einzelnen Seiten des Würfels, eben die Elemente der Mantelfläche. Jeder neue Buchstabe bedeutet eine neue Fläche von Elementen, die zu bearbeiten sind:

```
Ausgangsansicht

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA

nach "unten" gekippt

BBBBB
BBBBB
BBBBB
BBBBB
AAAAA

weiter nach "links" gekippt

BCCCC
BCCCC
BCCCC
BCCCC
AAAAA

weiter nach "unten" gekippt

BDDDD
BDDDD
BDDDD
BDDDD
BCCCC

weiter nach "links" gekippt

DEEEA
DEEEA
DEEEA
DEEEA
CCCCA

weiter nach "unten" gekippt

BBBBA
DFFFA
DFFFA
DFFFA
DEEEA
```
Trotzdem ist mir das gerade noch immer nicht so klar. Vor allem fragt mich, was ich mache, wenn der Würfel an die Grenzen des Arrays stößt!?

Ark


----------



## SlaterB (30. Mrz 2007)

bei 5x5 etwas einfacher:
oben und unten komplett 5x5,
2 längliche Seiten 5x3,
2 kleine Quadratseiten 3x3 

du brauchst also eine Operation
pruefeWuefelseite(Mittelpunkt, Radius, Richtung,Länge,Breite)
wobei die Umrechnung in 3D leicht fusselig wird,

da die Richtungen mit der Flächengröße korrelieren (oben + unten 5x5, links + rechts 5x3, vorne + hinten 3x3)
darf man in diesem Fall vielleicht ausnahmsweise dreimal den gleichen Code angepasst nehmen

Arraygrenze:
zum einem am Anfang jeder Seiten-Bearbeitung prüfen, ob die ganze Seite draußen ist 
(hängt von einer Dimension ab, die Richtung vom Mittelpunkt aus),

dann prüfen, ob bestimmte waagerechte oder senkrechte Zeilen wegfallen (in alle vier 2D-Richtungen), 
mit den verbleibenen sicheren 2D-Indexen die Seitenfläche durchlaufen

wenn man sich allein schon diese Prüfungen anschaut, die bei allen Flächen nötig sind,
dann ist eine zentrale Operation pruefeWuefelseite(..) doch wirklich sehr zu empfehlen


----------



## Marco13 (31. Mrz 2007)

Hey - interessante Aufgabe. 

Aber deutlich schwieriger, als sie sich im ersten Moment anhört. Da kann man richtig Gehirnschmalz reinstecken. 

Mein erster Ansatz war folgender:
Man hat eine Start-Zelle gegeben, und soll "die Oberfläche" eines Würfels der Größe n überprüfen, dessen Mitte bei der Start-Zelle liegt. Dabei läuft n von 3 beginnend in 2er-Schritten: 3,5,7...

Um die Oberfläche eines Würfels zu überprüfen, überpüft man einfach alle "Flächen" des Würfels, und danach die "Kanten" - dadurch wird es _wesentlich_ leichter, sicherzustellen, dass keine Zellen doppelt geprüft werden, und alle Flächen sind Quadrate mit gleichen Größe (nämlich Kantenlänge-2)! Man prüft also 
die vordere und hintere Fläche 
die linke und die rechte Fläche
die untere und die obere Fläche
Dann prüft man die "Kanten"
Die "Säulen" in den 4 Ecken, jeweils von yMin bis yMax
Die "Querstreben" oben vorne, oben hinten, unten vorne und unten hinten, jeweils von xMin+1 bis xMax-1
EDIT: Die "Längsstreben" oben links, oben rechts, unten links und unten rechts, jeweils von zMin+1 bis zMax-1

Das an sich ist erstmal ziemlich trivial, und schnell hingeschrieben (trotz der fortgeschrittenen Uhrzeit :wink: )


```
Längsstreben testen!


class CubeSearch
{
    public static void main(String args[])
    {
        CubeSearch cubeSearch = new CubeSearch(10);
        cubeSearch.search(3+" "+4+" "+5, 1,2,3);
    }

    private Object cube[][][];
    private int size;
    public CubeSearch(int size)
    {
        this.size = size;
        cube = new Object[size][size][size];
        init();
    }

    private void init()
    {
        for (int x=0; x<cube.length; x++)
        {
            for (int y=0; y<cube[x].length; y++)
            {
                for (int z=0; z<cube[x][y].length; z++)
                {
                    cube[x][y][z] = x+" "+y+" "+z;
                }
            }
        }
    }

    public void search(Object element, int x, int y, int z)
    {
        for (int n=1; n<size-1; n++)
        {
            System.out.println("Checking cube of size "+(2*n+1));
            if (search(element, x-n, y-n, z-n, x+n, y+n, z+n)) return;
        }
    }


    private boolean search(Object element, int x0, int y0, int z0, int x1, int y1, int z1)
    {
        // Vordere und hintere Fläche
        for (int x=x0+1; x<=x1-1; x++)
        {
            for (int y=y0+1; y<=y1-1; y++)
            {
                if (check(element, x,y,z0)) return true;
                if (check(element, x,y,z1)) return true;
            }
        }

        // Linke und rechte Fläche
        for (int y=y0+1; y<=y1-1; y++)
        {
            for (int z=z0+1; z<=z1-1; z++)
            {
                if (check(element, x0,y,z)) return true;
                if (check(element, x1,y,z)) return true;
            }
        }

        // Untere und obere Fläche
        for (int x=x0+1; x<=x1-1; x++)
        {
            for (int z=z0+1; z<=z1-1; z++)
            {
                if (check(element, x,y0,z)) return true;
                if (check(element, x,y1,z)) return true;
            }
        }

        // Vier "Säulen" in den Ecken
        for (int y=y0; y<=y1; y++)
        {
            if (check(element, x0,y,z0)) return true;
            if (check(element, x0,y,z1)) return true;
            if (check(element, x1,y,z0)) return true;
            if (check(element, x1,y,z1)) return true;
        }

        // Vier "Querstreben"
        for (int x=x0+1; x<=x1-1; x++)
        {
            if (check(element, x,y0,z0)) return true;
            if (check(element, x,y0,z1)) return true;
            if (check(element, x,y1,z0)) return true;
            if (check(element, x,y1,z1)) return true;
        }

        // Vier "Längsstreben"
        for (int z=z0+1; z<=z1-1; z++)
        {
            if (check(element, x0,y0,z)) return true;
            if (check(element, x0,y1,z)) return true;
            if (check(element, x1,y0,z)) return true;
            if (check(element, x1,y1,z)) return true;
        }

        return false;
    }

    private boolean check(Object element, int x, int y, int z)
    {
        if (x < 0 || x >= size) return false;
        if (y < 0 || y >= size) return false;
        if (z < 0 || z >= size) return false;

        System.out.println("Checking "+x+" "+y+" "+z);
        if (cube[x][y][z].equals(element))
        {
            System.out.println("Found at "+x+" "+y+" "+z);
            return true;
        }
        return false;
    }

}
```

Das ganze hat aber einen Haken: Es ist grottenscheiße :roll:

In der check-Methode wird überprüft, ob das gesuchte Element gefunden wurde. Aber DORT wird auch die Überprüfung der Array-Grenzen gemacht  Es werden SEHR viele Überprüfungen durchgeführt, obwohl man _eigentlich_ schon viel früher hätte erkennen können, dass die Überprüfungen überflüssig sind. Wenn ein Würfel mit Kantenlänge 5 aus dem Array hinausragt, dann ragt ein Würfel mit Kantenlänge 7 noch viel weiter aus dem Array hinaus - es wird aber trotzdem stupide jede "potentielle" Zelle getestet. 

Man kann glaubich (etwas plakativ, aber nicht ganz falsch) sagen: Je früher man die Zusicherung des Einhaltens der Arraygrenzen machen will, umso komplizierter wird es.

Wenn man sozusagen die "optimale" Lösung finden will (also genau alle Zellen testen, die getestet werden müssen, keine doppelt testen, und nie überprüfen will, ob eine Zelle außerhalb des Arrays liegt) dann wird das ganze _deutlich_ aufwändiger. Vielleicht nicht wirklich "schwierig", aber ziemlich fummelig, kompliziert und es wird VIEL mehr code. 

Trotzdem interessant.  

Wenn mir mal irgendwan langweilig ist ...  :lol: ... :wink:


----------



## Marco13 (31. Mrz 2007)

EDIT: Ich bin so kleinlich, und habe einen Fehler im Code korrigiert...


----------



## SlaterB (31. Mrz 2007)

ich glaube meine Flächen-Idee ist besser 

die Flächen kann man ja auch noch besser aufteilen:
zweimal 5x5 + viermal 4x3 (deswegen noch ein Post von mir)


----------



## Ark (31. Mrz 2007)

@alle, bes. SlaterB: Danke für die Ansätze. 

@Marco13: Deinen Ansatz mit der Unterteilung in Flächen, Kanten und Ecken habe ich auch gehabt. Allerdings finde ich SlaterBs Ansatz einfacher. Ich glaube, ich sollte zunächst davon ausgehen, dass die Arraygrenzen nicht überschritten werden. Inzwischen habe ich auf dem Papier folgendes rausgekriegt (jetzt weiß ich, wozu analytische Geometrie gut ist :lol: ):


```
Der Würfelmantel nach SlaterB mit r=1
(die kleinen Buchstaben zeigen an, dass die jeweilige Achse
in Richtung der anliegenden Kante orientiert ist):

         x

        BBB
      z CED z
        AAA

   z     x     z     x

  BCA   AAA   ADB   BBB
y BCA y AAA y ADB y BBB y
  BCA   AAA   ADB   BBB

   z     x     z     x

        AAA
      z CFD z
        BBB

         x



Die Flächen (nur zur Orientierung):

von A und B: (2*r+1)*(2*r+1)
von C und D: (2*r+1)*(2*r-1)
von E und F: (2*r-1)*(2*r-1)



Die Koordinaten der Elemente
in den Flächen A und B:

x = xe + (-r ... +r)
y = ye + (-r ... +r)
z = ze + (A ? +r : -r)


Die Koordinaten der Elemente
in den Flächen C und D:

x = xe + (C ? +r : -r)
y = ye + (-r ... +r)
z = ze + (-r+1 ... +r-1)


Die Koordinaten der Elemente
in den Flächen E und F:

x = xe + (-r+1 ... +r-1)
y = ye + (E ? +r : -r)
z = ze + (-r+1 ... +r-1)
```
EDIT:
So, nun habe ich auch die restlichen Flächen nach SlaterBs ersten Ansatz beschrieben. Frage: Stimmt das so, oder fallen schon Ungereimtheiten auf?

Allerdings sind noch immer die Arraygrenzen nicht berücksichtigt …

Aber ich bedanke mich noch einmal für die vielen Ideen.  Vorschläge oder hinweise sind natürlich herzlich willkommen!

Ark


----------



## Marco13 (31. Mrz 2007)

@SlaterB: Ich finde meinen Ansatz besser, weil man damit "alles gleich" behandeln kann - das ist oft günstig, um den Code einfacher zu gestalten ... und es erklärt auch die "übersichtliche" Formatierung des unten stehenden Codes... :wink: 

Die Arraygrenzen werden jetzt geprüft, _bevor_ man die jeweiligen Flächen/Kanten prüft. Damit ist sichergestellt, dass die Überprüfungen der Arraygrenzen so früh wie nötig durchgeführt werden (und natürlich dass man keine Zellen doppelt testet). Es wird jetzt also GENAU das getestet, was getestet werden muss.

Wenn jemand durch das Überschreiben des Teils hinter der ----- Trennlinie ----- eine schnellere (oder auch nur "kompaktere" oder "elegantere") Lösung findet, möge er sie hier posten.  Und wer den Code in einem Projekt o.ä. verwendet (*zu Ark rüber schiel*) soll bitte erwähnen, wo er ihn herhat   :wink:


```
import java.util.*;

class CubeSearch3
{
    private static final boolean trace = false;
    private static final boolean verify = false;

    public static void main(String args[])
    {
        CubeSearch3 cubeSearch = new CubeSearch3(64);

        if (trace && verify)
        {
            cubeSearch.search(3+" "+4+" "+5, 3,4,4); // Gefunden im 3er
            cubeSearch.search(3+" "+4+" "+5, 2,3,3); // Gefunden im 5er
            cubeSearch.search(3+" "+4+" "+5, 1,2,2); // Gefunden im 7er
            cubeSearch.search(3+" "+4+" "+5, 0,1,1); // Gefunden im 9er
            cubeSearch.search(3+"x"+4+"x"+5, 0,7,1); // Nie gefunden
        }
        else
        {
            cubeSearch.benchmark();
        }
    }

    // NUR verwendet wenn verify==true, um zu verifizieren,
    // dass nie eine Zelle doppelt geprüft wird
    private HashSet checked = new HashSet();

    private Object cube[][][];
    private int size;

    public CubeSearch3(int size)
    {
        this.size = size;
        cube = new Object[size][size][size];
        init();
    }

    private void init()
    {
        System.out.println("Initializing...");
        for (int x=0; x<cube.length; x++)
        {
            for (int y=0; y<cube[x].length; y++)
            {
                for (int z=0; z<cube[x][y].length; z++)
                {
                    cube[x][y][z] = x+" "+y+" "+z;
                }
            }
        }
        System.out.println("Initializing... DONE");
    }

    public void benchmark()
    {
        int runs = 100;
        long startTime = System.currentTimeMillis();
        for (int i=0; i<runs; i++)
        {
            int x = (int)(Math.random() * size);
            int y = (int)(Math.random() * size);
            int z = (int)(Math.random() * size);
            int xStart = (int)(Math.random() * size);
            int yStart = (int)(Math.random() * size);
            int zStart = (int)(Math.random() * size);
            if (x==xStart && y==yStart && z==zStart)
            {
                i--;
                continue;
            }
            Object element = x+" "+y+" "+z;
            if (!search(element, xStart, yStart, zStart))
            {
                System.out.println("Error: Element "+element+" not found!");
                if (verify)
                {
                    verifyChecked();
                }
            }
        }
        long endTime = System.currentTimeMillis();
        float avgTime = (float)(endTime-startTime)/runs;
        System.out.println("Average time "+avgTime+" ms");
    }


    private boolean search(Object element, int x, int y, int z)
    {
        Object start = x+" "+y+" "+z;
        if (verify)
        {
            checked.clear();
            checked.add(start);
        }
        System.out.println("Searching for "+element+" starting at "+start);

        return searchImpl(element, x,y,z);
    }


    private void verifyChecked()
    {
        for (int x=0; x<cube.length; x++)
        {
            for (int y=0; y<cube[x].length; y++)
            {
                for (int z=0; z<cube[x][y].length; z++)
                {
                    Object e = x+" "+y+" "+z;
                    if (!checked.contains(e))
                    {
                        System.out.println("Did not check "+e);
                    }
                }
            }
        }
    }

    //------------------------------------------------------------------------

    // Wird aufgerufen, um die gegebene Zelle zu überprüfen

    private boolean check(Object element, int x, int y, int z)
    {
        if (verify)
        {
            if (x < 0 || x >= size || y < 0 || y >= size || z < 0 || z >= size)
            {
                System.out.println("Should not check "+x+" "+y+" "+z);
                return false;
            }
            if (checked.contains(cube[x][y][z]))
            {
                System.out.println("Checked twice: "+cube[x][y][z]);
            }
            checked.add(cube[x][y][z]);
        }

        if (trace) System.out.println("Checking "+x+" "+y+" "+z);

        if (cube[x][y][z].equals(element))
        {
            System.out.println("Found at "+x+" "+y+" "+z);
            return true;
        }
        return false;
    }


    //------------------------------------------------------------------------

    public boolean searchImpl(Object element, int x, int y, int z)
    {
        for (int n=1; n<size; n++)
        {
            if (trace) System.out.println("Checking cube of size "+(2*n+1));
            if (search(element, x-n, y-n, z-n, x+n, y+n, z+n)) return true;
        }
        return false;
    }

    private boolean search(Object element,
                           int sx0, int sy0, int sz0,
                           int sx1, int sy1, int sz1)
    {
        if (trace) System.out.println("Search "+sx0+" "+sy0+" "+sz0+" to "+sx1+" "+sy1+" "+sz1);

        int x0 = Math.max(sx0, 0);
        int y0 = Math.max(sy0, 0);
        int z0 = Math.max(sz0, 0);
        int x1 = Math.min(sx1, size-1);
        int y1 = Math.min(sy1, size-1);
        int z1 = Math.min(sz1, size-1);

        // Kanten entlang X
        if (trace) System.out.println("Edges X");
        if (sy0 >= 0   && sz0 >= 0   && checkEdgeX(element, x0, x1, sy0, sz0)) return true;
        if (sy0 >= 0   && sz1 < size && checkEdgeX(element, x0, x1, sy0, sz1)) return true;
        if (sy1 < size && sz0 >= 0   && checkEdgeX(element, x0, x1, sy1, sz0)) return true;
        if (sy1 < size && sz1 < size && checkEdgeX(element, x0, x1, sy1, sz1)) return true;

        if (sx0 >= 0)   x0++;
        if (sy0 >= 0)   y0++;
        if (sz0 >= 0)   z0++;
        if (sx1 < size) x1--;
        if (sy1 < size) y1--;
        if (sz1 < size) z1--;

        // Kanten entlang Y
        if (trace) System.out.println("Edges Y");
        if (sx0 >= 0   && sz0 >= 0   && checkEdgeY(element, y0, y1, sx0, sz0)) return true;
        if (sx0 >= 0   && sz1 < size && checkEdgeY(element, y0, y1, sx0, sz1)) return true;
        if (sx1 < size && sz0 >= 0   && checkEdgeY(element, y0, y1, sx1, sz0)) return true;
        if (sx1 < size && sz1 < size && checkEdgeY(element, y0, y1, sx1, sz1)) return true;

        // Kanten entlang Z
        if (trace) System.out.println("Edges Z");
        if (sx0 >= 0   && sy0 >= 0   && checkEdgeZ(element, z0, z1, sx0, sy0)) return true;
        if (sx0 >= 0   && sy1 < size && checkEdgeZ(element, z0, z1, sx0, sy1)) return true;
        if (sx1 < size && sy0 >= 0   && checkEdgeZ(element, z0, z1, sx1, sy0)) return true;
        if (sx1 < size && sy1 < size && checkEdgeZ(element, z0, z1, sx1, sy1)) return true;

        // Linke und rechte Fläche
        if (trace) System.out.println("Left and right face");
        if (sx0 >= 0   && checkFaceX(element, y0, z0, y1, z1, sx0)) return true;
        if (sx1 < size && checkFaceX(element, y0, z0, y1, z1, sx1)) return true;

        // Untere und obere Fläche
        if (trace) System.out.println("Bottom and top face");
        if (sy0 >= 0   && checkFaceY(element, x0, z0, x1, z1, sy0)) return true;
        if (sy1 < size && checkFaceY(element, x0, z0, x1, z1, sy1)) return true;

        // Vordere und hintere Fläche
        if (trace) System.out.println("Front and back face");
        if (sz0 >= 0   && checkFaceZ(element, x0, y0, x1, y1, sz0)) return true;
        if (sz1 < size && checkFaceZ(element, x0, y0, x1, y1, sz1)) return true;

        return false;
    }


    private boolean checkEdgeX(Object element, int x0, int x1, int yn, int zn)
    {
        if (trace) System.out.println("Edge X from "+x0+" "+yn+" "+zn+" to "+x1+" "+yn+" "+zn);
        for (int x=x0; x<=x1; x++)
        {
            if (check(element, x,yn,zn)) return true;
        }
        return false;
    }

    private boolean checkEdgeY(Object element, int y0, int y1, int xn, int zn)
    {
        if (trace) System.out.println("Edge Y from "+xn+" "+y0+" "+zn+" to "+xn+" "+y1+" "+zn);
        for (int y=y0; y<=y1; y++)
        {
            if (check(element, xn,y,zn)) return true;
        }
        return false;
    }

    private boolean checkEdgeZ(Object element, int z0, int z1, int xn, int yn)
    {
        if (trace) System.out.println("Edge Z from "+xn+" "+yn+" "+z0+" to "+xn+" "+yn+" "+z1);
        for (int z=z0; z<=z1; z++)
        {
            if (check(element, xn,yn,z)) return true;
        }
        return false;
    }

    private boolean checkFaceX(Object element, int y0, int z0, int y1, int z1, int xn)
    {
        if (trace) System.out.println("Face X from "+xn+" "+y0+" "+z0+" to "+xn+" "+y1+" "+z1);
        for (int y=y0; y<=y1; y++)
        {
            for (int z=z0; z<=z1; z++)
            {
                if (check(element, xn,y,z)) return true;
            }
        }
        return false;
    }

    private boolean checkFaceY(Object element, int x0, int z0, int x1, int z1, int yn)
    {
        if (trace) System.out.println("Face Y from "+x0+" "+yn+" "+z0+" to "+x0+" "+yn+" "+z1);
        for (int x=x0; x<=x1; x++)
        {
            for (int z=z0; z<=z1; z++)
            {
                if (check(element, x,yn,z)) return true;
            }
        }
        return false;
    }

    private boolean checkFaceZ(Object element, int x0, int y0, int x1, int y1, int zn)
    {
        if (trace) System.out.println("Face Z from "+x0+" "+y0+" "+zn+" to "+x1+" "+y1+" "+zn);
        for (int x=x0; x<=x1; x++)
        {
            for (int y=y0; y<=y1; y++)
            {
                if (check(element, x,y,zn)) return true;
            }
        }
        return false;
    }

}
```


----------



## Ark (31. Mrz 2007)

@Marco13: Ich glaube, ich hab's! 

Ich habe mir extra verkniffen, Deinen Code anzusehen.  Ich arbeite mal an meiner Version weiter, weil ich glaube, jetzt doch alles zu haben. Dann stelle ich meinen Code auch hier rein! Danach kann ja eine Umfrage feststellen, welcher Code beliebter ist. :lol:

Ark


----------



## Ark (31. Mrz 2007)

So, ich hoffe, dies ist ein Doppelpost wert. ^^


```
final int XA=dn.xl;//Arraygrößen
final int YA=dn.yl;
final int ZA=dn.zl;
final int XE=dn.cx;//aktuelle Elementkoordinaten
final int YE=dn.cy;
final int ZE=dn.cz;
int x,y,z;//zu untersuchen
int x1,y1,z1;//untere Grenze
int x2,y2,z2;//obere Grenze
int r;//Radius
final int L=1000;//maximaler Radius

for(r=1;r<L;r++){
	/* A */
	if((z=ZE+r)<ZA){
		if((x1=XE-r)<0) x1=0;
		if((x2=XE+r)>=XA) x2=XA;
		if((y1=YE-r)<0) y1=0;
		if((y2=YE+r)>=YA) y2=YA;
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* B */
	if((z=ZE-r)>=0){
		if((x1=XE-r)<0) x1=0;
		if((x2=XE+r)>=XA) x2=XA;
		if((y1=YE-r)<0) y1=0;
		if((y2=YE+r)>=YA) y2=YA;
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* C */
	if((x=XE+r)<XA){
		if((y1=YE-r)<0) y1=0;
		if((y2=YE+r)>=YA) y2=YA;
		if((z1=ZE-r+1)<0) z1=0;
		if((z2=ZE+r-1)>=ZA) z2=ZA;
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* D */
	if((x=XE-r)>=0){
		if((y1=YE-r)<0) y1=0;
		if((y2=YE+r)>=YA) y2=YA;
		if((z1=ZE-r+1)<0) z1=0;
		if((z2=ZE+r-1)>=ZA) z2=ZA;
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* E */
	if((y=YE+r)<YA){
		if((x1=XE-r+1)<0) x1=0;
		if((x2=XE+r-1)>=XA) x2=XA;
		if((z1=ZE-r+1)<0) z1=0;
		if((z2=ZE+r-1)>=ZA) z2=ZA;
		for(x=x1;x<=x2;x++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* F */
	if((y=YE-r)>=0){
		if((x1=XE-r+1)<0) x1=0;
		if((x2=XE+r-1)>=XA) x2=XA;
		if((z1=ZE-r+1)<0) z1=0;
		if((z2=ZE+r-1)>=ZA) z2=ZA;
		for(x=x1;x<=x2;x++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
}
```
Da gibt es nur ein Problemchen: Ich habe das noch nie getestet. :lol:
Könnte das mal jemand überprüfen? Tipp: A und B gleichen sich, lediglich die erste Zeile (das if) ist anders. Entsprechendes gilt für C und D bzw. E und F.

Vielen Dank schon mal, auch für die bisherige Hilfe zu diesem Problem. 

Ark

EDIT: Ha! Ich sehe doch schon wieder Verbesserungsmöglichkeiten!  Moment, das wird jetzt ein wenig komplizert.


EDIT2: So, hier eine andere Version; sie sollte genauso arbeiten wie die drüber. Würde da bitte jemand einen vergleichenden Blick drauf werfen? Danke.


```
final int XA=dn.xl;//Arraygrößen
final int YA=dn.yl;
final int ZA=dn.zl;
final int XE=dn.cx;//aktuellen Elements Koordinaten
final int YE=dn.cy;
final int ZE=dn.cz;
final int L=1000;//maximaler Radius
int r;//Radius
int x,y,z;//zu untersuchen

int x1,y1,z1;//temp.
int x2,y2,z2;//temp.
int x3,x4;//temp.

for(r=1;r<L;r++){
	if((x1=XE-r)<0) x1=0;//AB
	if((x2=XE+r)>=XA) x2=XA;//AB
	if((y1=YE-r)<0) y1=0;//ABCD
	if((y2=YE+r)>=YA) y2=YA;//ABCD
	if((z1=ZE-r+1)<0) z1=0;//CDEF
	if((z2=ZE+r-1)>=ZA) z2=ZA;//CDEF
	if((x3=XE-r+1)<0) x3=0;//EF
	if((x4=XE+r-1)>=XA) x4=XA;//EF
	
	/* A */
	if((z=ZE+r)<ZA){
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* B */
	if((z=ZE-r)>=0){
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* C */
	if((x=XE+r)<XA){
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* D */
	if((x=XE-r)>=0){
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* E */
	if((y=YE+r)<YA){
		for(x=x3;x<=x4;x++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
	/* F */
	if((y=YE-r)>=0){
		for(x=x3;x<=x4;x++){
			for(z=z1;z<=z2;z++){
				;// meine Operationen an a[x][y][z]
			}
		}
	}
}
```
Zwar könnte man hier noch immer etwas rausholen, aber das wird dann sehr unübersichtlich und ist es wahrscheinlich auch nicht wert. Ich habe aber noch immer diesen Code nicht praktisch geprüft. :lol:

Da das dreidimensional ist, kann man das auf dem Bildschirm leider nur schlecht mit einfachen mitteln veranschaulichen. Wie sonst kann ich rauskriegen, dass der Code wirklich so arbeitet wie gewünscht?

Ark


----------



## Marco13 (1. Apr 2007)

Jaja - es IST kompakter :? also wird mein Name doch nicht in einem fremden Projekt verewigt  :cry: *flenn* :wink: Trotzdem hätte ich das nicht gemacht, wenn ich nicht glauben würde, dass es in Zukunft mal hilfreich sein könnte, so ein Programmschnipsel in der Schublade parat zu haben   

Verifizieren kann man das Programm entweder durch einen streng formalen Beweis, mit Preconditions, Postconditions, Schleifeninvarianten usw :wink: oder (wenn man faul ist, und nicht ein paar Jahre dafür Zeit hat) mit einigen repräsentativen Testfällen...

Irgendwo greifst du bei einem Array der Größe n noch auf das Element n (statt max. n-1) zu (besonders, wenn das gesuchte Element nicht gefunden wurde). Hier mal der Teststub. Kannst ja ggf. noch "if (trace) ..." -Ausgaben reinmachen, um die letzte Indexüberschreitung leichter zu finden. 

Wenn verify true ist, wird überprüft, ob man alle nötigen Zellen testet und innerhalb der Arraygrenzen bleibt.
Wenn trace und verify false sind, wird ein Benchmark durchgeführt.


```
import java.util.*;

class CubeSearchTest
{
    private static final boolean trace = true;
    private static final boolean verify = true;

    public static void main(String args[])
    {

        if (trace && verify)
        {
            CubeSearchTest cubeSearch = new CubeSearchTest(10);
            cubeSearch.search(3+" "+4+" "+5, 3,4,4); // Gefunden im 3er
            cubeSearch.search(3+" "+4+" "+5, 2,3,3); // Gefunden im 5er
            cubeSearch.search(3+" "+4+" "+5, 1,2,2); // Gefunden im 7er
            cubeSearch.search(3+" "+4+" "+5, 0,1,1); // Gefunden im 9er
            cubeSearch.search(9+" "+9+" "+9, 0,0,0); // Gefunden im 19er
            cubeSearch.search(3+"x"+4+"x"+5, 0,7,1); // Nie gefunden
        }
        else
        {
            CubeSearchTest cubeSearch = new CubeSearchTest(48);
            cubeSearch.benchmark();
        }
    }

    // NUR verwendet wenn verify==true, um zu verifizieren,
    // dass nie eine Zelle doppelt geprüft wird
    private HashSet checked = new HashSet();

    private Object cube[][][];
    private int size;

    public CubeSearchTest(int size)
    {
        this.size = size;
        cube = new Object[size][size][size];
        init();
    }

    private void init()
    {
        System.out.println("Initializing...");
        for (int x=0; x<cube.length; x++)
        {
            for (int y=0; y<cube[x].length; y++)
            {
                for (int z=0; z<cube[x][y].length; z++)
                {
                    cube[x][y][z] = x+" "+y+" "+z;
                }
            }
        }
        System.out.println("Initializing... DONE");
    }

    public void benchmark()
    {
        int runs = 100;
        long startTime = System.currentTimeMillis();
        for (int i=0; i<runs; i++)
        {
            int x = (int)(Math.random() * size);
            int y = (int)(Math.random() * size);
            int z = (int)(Math.random() * size);
            int xStart = (int)(Math.random() * size);
            int yStart = (int)(Math.random() * size);
            int zStart = (int)(Math.random() * size);
            if (x==xStart && y==yStart && z==zStart)
            {
                i--;
                continue;
            }
            Object element = x+" "+y+" "+z;
            if (!search(element, xStart, yStart, zStart))
            {
                System.out.println("Error: Element "+element+" not found!");
                if (verify)
                {
                    verifyChecked();
                }
            }
        }
        long endTime = System.currentTimeMillis();
        float avgTime = (float)(endTime-startTime)/runs;
        System.out.println("Average time "+avgTime+" ms");
    }


    private boolean search(Object element, int x, int y, int z)
    {
        Object start = x+" "+y+" "+z;
        if (verify)
        {
            checked.clear();
            checked.add(start);
        }
        System.out.println("Searching for "+element+" starting at "+start);


        return searchImplArk(element, x,y,z);
    }


    private void verifyChecked()
    {
        for (int x=0; x<cube.length; x++)
        {
            for (int y=0; y<cube[x].length; y++)
            {
                for (int z=0; z<cube[x][y].length; z++)
                {
                    Object e = x+" "+y+" "+z;
                    if (!checked.contains(e))
                    {
                        System.out.println("Did not check "+e);
                    }
                }
            }
        }
    }


    //=================== Wird aufgerufen, um die gegebene Zelle zu überprüfen

    private boolean check(Object element, int x, int y, int z)
    {
        if (verify)
        {
            if (x < 0 || x >= size || y < 0 || y >= size || z < 0 || z >= size)
            {
                System.out.println("Should not check "+x+" "+y+" "+z);
                return false;
            }
            if (checked.contains(cube[x][y][z]))
            {
                System.out.println("Checked twice: "+cube[x][y][z]);
            }
            checked.add(cube[x][y][z]);
        }

        if (trace) System.out.println("Checking "+x+" "+y+" "+z);

        if (cube[x][y][z].equals(element))
        {
            System.out.println("Found at "+x+" "+y+" "+z);
            return true;
        }
        return false;
    }



    //------------------------------------------------------------------------

    public boolean searchImplArk(Object element, int sx, int sy, int sz)
    {
        /*
        final int XA=dn.xl;//Arraygrößen
        final int YA=dn.yl;
        final int ZA=dn.zl;
        final int XE=dn.cx;//aktuellen Elements Koordinaten
        final int YE=dn.cy;
        final int ZE=dn.cz;
        */
        final int XA=size;
        final int YA=size;
        final int ZA=size;
        final int XE=sx;
        final int YE=sy;
        final int ZE=sz;

        final int L=1000;//maximaler Radius
        int r;//Radius
        int x,y,z;//zu untersuchen

        int x1,y1,z1;//temp.
        int x2,y2,z2;//temp.
        int x3,x4;//temp.

        for(r=1;r<L;r++){
           if((x1=XE-r)<0) x1=0;//AB
           if((x2=XE+r)>=XA) x2=XA;//AB
           if((y1=YE-r)<0) y1=0;//ABCD
           if((y2=YE+r)>=YA) y2=YA;//ABCD
           if((z1=ZE-r+1)<0) z1=0;//CDEF
           if((z2=ZE+r-1)>=ZA) z2=ZA;//CDEF
           if((x3=XE-r+1)<0) x3=0;//EF
           if((x4=XE+r-1)>=XA) x4=XA;//EF

           /* A */
           if((z=ZE+r)<ZA){
              for(x=x1;x<=x2;x++){
                 for(y=y1;y<=y2;y++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
           /* B */
           if((z=ZE-r)>=0){
              for(x=x1;x<=x2;x++){
                 for(y=y1;y<=y2;y++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
           /* C */
           if((x=XE+r)<XA){
              for(y=y1;y<=y2;y++){
                 for(z=z1;z<=z2;z++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
           /* D */
           if((x=XE-r)>=0){
              for(y=y1;y<=y2;y++){
                 for(z=z1;z<=z2;z++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
           /* E */
           if((y=YE+r)<YA){
              for(x=x3;x<=x4;x++){
                 for(z=z1;z<=z2;z++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
           /* F */
           if((y=YE-r)>=0){
              for(x=x3;x<=x4;x++){
                 for(z=z1;z<=z2;z++){
                    if (check(element, x,y,z)) return true;// meine Operationen an a[x][y][z]
                 }
              }
           }
        }
        return false;
    }

}
```


----------



## Ark (1. Apr 2007)

Ich habe noch eine Variante entwickelt, die gegenüberliegende Seiten zwar langsamer abarbeitet, wenn nur eine von beiden durchsucht werden muss, aber sonst schneller ist.


```
final int XA=dn.xl,YA=dn.yl,ZA=dn.zl;//Arraygrößen
final int XE=dn.cx,YE=dn.cy,ZE=dn.cz;//aktuellen Elements Koordinaten
final int L=1000;//maximaler Radius

int r;//Radius
int x, y, z;//zu untersuchen

int x1,x2,x3,x4 , y1,y2 , z1,z2,z3,z4;//temp.
boolean doA,doB,doC,doD,doE,doF;//Schalter

for(r=1;r<L;r++){
	/* Grenzen feststellen */
	if( (x1=XE-r)   < 0) {x1=   0; doD=false;} else doD=true;//AB
	if( (x2=XE+r)  >=XA) {x2=XA-1; doC=false;} else doC=true;//AB
	if( (y1=YE-r)   < 0) {y1=   0; doF=false;} else doF=true;//ABCD
	if( (y2=YE+r)  >=YA) {y2=YA-1; doE=false;} else doE=true;//ABCD
	if( (z1=ZE-r+1) < 0)  z1=   0;                           //CDEF
	if( (z2=ZE+r-1)>=ZA)  z2=ZA-1;                           //CDEF
	if( (x3=XE-r+1) < 0)  x3=   0;                           //EF
	if( (x4=XE+r-1)>=XA)  x4=XA-1;                           //EF
	doB=(z3=ZE-r)  >= 0;
	doA=(z4=ZE+r)   <ZA;
	
	/* Jetzt geht's richtig los! */
	/* A und B */
	if(doA||doB){
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				if(doA);// meine Operationen an a[x][y][z4]
				if(doB);// meine Operationen an a[x][y][z3]
			}
		}
	}
	/* C und D */
	if(doC||doD){
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				if(doC);// meine Operationen an a[x2][y][z]
				if(doD);// meine Operationen an a[x1][y][z]
			}
		}
	}
	/* E und F */
	if(doE||doF){
		for(x=x3;x<=x4;x++){
			for(z=z1;z<=z2;z++){
				if(doE);// meine Operationen an a[x][y2][z]
				if(doF);// meine Operationen an a[x][y1][z]
			}
		}
	}
}
```

Was ich aber immer noch nicht weiß: Ob mein Code überhaupt funktioniert. :lol:
@alle: Inwiefern erscheint mein jetziger Code logisch? Soll heißen: Würdet ihr den kapieren, wenn ihr unvemittelt vor ihn gesetzt werdet?

Ark

P.S.@Marco13: :bae:

EDIT: Hey, danke! Ich habe den Fehler gefunden. Moment, den korrigiere ich gleich mal …
EDIT2: So, korrigiert. Das Ding sollte jetzt laufen.
@Marco13: Du kupferst gefälligst nicht meinen Code ab! :bae:


----------



## Marco13 (1. Apr 2007)

Hmja - offenbar ist die Trennung von Flächen und Kanten doch nicht sooo sinnvoll - die hat meinen Code um mehr als das Doppelte aufgebläht, und erübrigt sich eigentlich schon dadurch, dass man _sowieso_ sie Grenzen für die Schleifen einzeln bestimmen muss - dann kann man (mit einer etwas "mächtigeren" checkFace-Methode) auch die Kanten gleich mit abarbeiten. Hm. Es heißt ja immer: "Aus Fehlern lernt man.". Was kann es dann für ein anderes Ziel geben, als möglichst viele Fehler zu machen? :wink:
Das einzige, was mich jetzt noch beruhigt, ist, dass deine Methode immernoch die Arraygrenzen überschreitet, und damit unbrauchbar ist  :meld:  :wink: (Ich befürchte nur, dass du das mit geringem Aufwand korrigieren können wirst... :roll: )
EDIT: Was mit dem EDIT2 vermutlich passiert ist.


----------



## Ark (1. Apr 2007)

So, ich habe den Code noch ein ganz kleines bisschen verbessert. Wenn er funktioniert (was, wie ich annehme, Marco13 gleich testen wird), wäre dies ein Schmuckstück für die Nachwelt. 


```
/* Randelemente Koordinaten */
final int XA=dn.xl-1,YA=dn.yl-1,ZA=dn.zl-1;
/* aktuellen Elements Koordinaten */
final int XE=dn.cx,  YE=dn.cy,  ZE=dn.cz;
/* maximaler Radius */
final int L=1000;

int r;//Radius
int x, y, z;//zu untersuchen

int x1,x2,x3,x4 , y1,y2 , z1,z2,z3,z4;//temp.
boolean doA,doB,doC,doD,doE,doF;//Schalter

for(r=1;r<L;r++){
	/* Grenzen feststellen */
	doB=(z1=ZE-r)  >= 0;
	doA=(z2=ZE+r)  <=ZA;
	if( (x1=XE-r)  <  0) {x1= 0; doD=false;} else doD=true;//AB
	if( (x2=XE+r)  > XA) {x2=XA; doC=false;} else doC=true;//AB
	if( (y1=YE-r)  <  0) {y1= 0; doF=false;} else doF=true;//ABCD
	if( (y2=YE+r)  > YA) {y2=YA; doE=false;} else doE=true;//ABCD
	if( (z3=ZE-r+1)<  0)  z3= 0;                           //CDEF
	if( (z4=ZE+r-1)> ZA)  z4=ZA;                           //CDEF
	if( (x3=XE-r+1)<  0)  x3= 0;                           //EF
	if( (x4=XE+r-1)> XA)  x4=XA;                           //EF
	
	/* Jetzt geht's richtig los! */
	/* A und B */
	if(doA||doB){
		for(x=x1;x<=x2;x++){
			for(y=y1;y<=y2;y++){
				if(doA);// meine Operationen an a[x][y][z2]
				if(doB);// meine Operationen an a[x][y][z1]
			}
		}
	}
	/* C und D */
	if(doC||doD){
		for(y=y1;y<=y2;y++){
			for(z=z1;z<=z2;z++){
				if(doC);// meine Operationen an a[x2][y][z]
				if(doD);// meine Operationen an a[x1][y][z]
			}
		}
	}
	/* E und F */
	if(doE||doF){
		for(x=x3;x<=x4;x++){
			for(z=z1;z<=z2;z++){
				if(doE);// meine Operationen an a[x][y2][z]
				if(doF);// meine Operationen an a[x][y1][z]
			}
		}
	}
}
```

Es gilt natürlich für alle Codes von mir: Ich habe die Urheberrechte. :meld:

@SlaterB: Danke noch einmal für den Ansatz. 
@Marco13: Jupp, aus Fehlern lernt man. Das kann ich nur bestätigen.  Läuft mein Code überhaupt? *lach*

Ark


----------



## Jango (1. Apr 2007)

Ark hat gesagt.:
			
		

> So, ich habe den Code noch ein ganz kleines bisschen verbessert. Wenn er funktioniert (was, wie ich annehme, Marco13 gleich testen wird), *wäre dies ein Schmuckstück für die Nachwelt*.
> ...
> ...
> Es gilt natürlich für alle Codes von mir: Ich habe die Urheberrechte.



Sorry, Ark - aber wie erträgst du dich eigentlich selber?  :roll:


----------



## Marco13 (1. Apr 2007)

Naja - da steckt jetzt schon ein ziemliches Stück Arbeit drin. Ich glaube, wirkliche "Rechte" hat man nichtmehr an seinem Code, wenn man ihn einmal in einem Forum gepostet hat, aber in einem Kommentar einen ein Link hierher einzufügen, wenn jemand diesen Code in einem Programm verwendet, sollte schon drin sein... Wer es drauf anlegt, sich mit fremden Federn zu schmücken, kann es aber auch sein lassen. Die Alternative wäre ja, selbst eine Lösung zu suchen. Auch wenn man nicht so viel Zeit für Optimierungen hat, und die Lösung dann vielleicht nicht so gut (kompakt) ist   *pfeif*  

Ansonsten: Die letzte Version hat wohl einen Bug, aber die vorletzte lief ohne Fehler.


----------



## Ark (1. Apr 2007)

Tausend Dank an Marco13 (für die Testklasse) und SlaterB (für den Ansatz)! 

Ich meine, den Fehler inzwischen gefunden und beseitigt zu haben. (@Marco13: Läuft's bei Dir auch?)

Ark


----------

