Koordinate mit meisten Überlappungen in 3D-Raum finden

[lennero]

Hallo.
Ich habe eine Input-Datei die folgendermaßen aussieht:

<22, 37, 68>, R:48
<24 5, 2>, R:200
<29, 1, 6>, R:57
...

Das sind kartesische Koordinaten mit einer Reichweitenangabe. Wenn man sich das bildlich vorstellt, ist das eine Ansammlung von Oktaedern im Raum.

Meine Aufgabe ist es, die Koordinate herauszufinden, welche am nächsten zum Ursprung liegt und von den meisten Oktaedern erfasst wird.

Das Problem ist, dass die Koordinaten in der Input-Datei extrem groß sind (im Milliardenbereich) und sehr weit außeinander liegen. Die Reichweiten sind ebenso extrem hoch. Eine (brute force) Suche nach jedem einzelnen Punkt wäre somit nicht möglich.

Ich habe mir gedacht, dass ich einen Octree benutzen könnte, aber wie finde ich damit den Punkt, den ich Suche? Ich müsste ja theoretisch den Raum in 8 teilen bis dieser eine Länge und Breite von 1 hat. Wenn ich dann jedesmal den "richtigen" Raum zum Teilen aussuche, würde ich irgendwann an dem Punkt ankommen.

Ich fange quasi mit dem ganzen Bereich an und stecke diesen in eine priority queue. Dann teile ich den Bereich in 8 Teile und berechne die Anzahl an Oktaederüberschneidungen in jedem der 8 Bereiche und wähle immer den Bereich, mit der größten Anzahl an Überschneidungen.

Quasi wie eine Binärsuche in 3D. Kennt jemand einen einfacheren weg? Die Koordinaten wurden ja nicht ohne Grund so hoch gewählt, gibt es hier einen mathematischen Trick mit dem man das ganze einfacher lösen kann?

 

[mihe7]

Wenn man sich das bildlich vorstellt, ist das eine Ansammlung von Oktaedern im Raum.

Nur zum Verständnis: warum Oktaeder und keine Kugeln?

 

[lennero]

Nur zum Verständnis: warum Oktaeder und keine Kugeln?

Ich hab einen Punkt im Raum und eine Reichweite die ich mir als Geraden vorstelle die vom Punkt in alle 6 Richtungen ausgehen, quasi so:

Um es anders auszudrücken, bei einem Punkt bei 0, 0, 0 mit einer Reichweite von 1 erreicht der Punkt die Koordinaten

1, 0 ,0
0, 1, 0
0, 0, 1
-1 0 0
0 -1 0
0, 0, -1

Und keine anderen

 

[mihe7]

OK, die Reichweite wäre aber doch eigentlich in alle Richtungen gültig, oder ist das auf die sechs beschränkt?

Wie auch immer:

Meine Aufgabe ist es, die Koordinate herauszufinden, welche am nächsten zum Ursprung liegt und von den meisten Oktaedern erfasst wird.

Nehmen wir mal an, es gäbe keine zwei Punkte, die vom Ursprung gleich weit entfernt wären. Dann gibt es einen Punkt A, der dem Ursprung am nächsten liegt. Dieser Punkt sei nur von einem Oktaeder erfasst. Des weiteren soll es einen Punkt B geben, der aufgrund der Annahme weiter vom Ursprung entfernt sein muss als A. Dieser Punkt sei nun aber von zwei Oktaedern erfasst. Welcher der beiden Punkte soll dann geliefert werden und warum?

 

[lennero]

OK, die Reichweite wäre aber doch eigentlich in alle Richtungen gültig, oder ist das auf die sechs beschränkt?

Wie auch immer:

Nehmen wir mal an, es gäbe keine zwei Punkte, die vom Ursprung gleich weit entfernt wären. Dann gibt es einen Punkt A, der dem Ursprung am nächsten liegt. Dieser Punkt sei nur von einem Oktaeder erfasst. Des weiteren soll es einen Punkt B geben, der aufgrund der Annahme weiter vom Ursprung entfernt sein muss als A. Dieser Punkt sei nun aber von zwei Oktaedern erfasst. Welcher der beiden Punkte soll dann geliefert werden und warum?

Ja genau, die Reichweite ist nur auf diese 6 Richtungen beschränkt.

Zweite Frage: in dem Fall soll Punkt B geliefert werden. Wenn es zwei Punkte gibt die von der selben Anzahl an Oktaedern erfasst werden, soll der Punkt der am nächsten zum Ursprung liegt gewählt werden (anhand der Manhattan Distanz vom Ursprung zum Punkt). Ansonsten wird immer der Punkt gewählt der von den meisten Oktaedern erfasst wird, ganz egal wie weit dieser entfernt ist.

 

[lennero]

Ich denke ich hab die Lösung gefunden. Hab das ganze der Einfachheit halber in 2D per Hand durchgespielt.



Ich teile die gesamte Suchumgebung, wie beim Quadtree, immer in 4 Teile und stecke diese in eine priority queue. Hierbei wird immer zuerst die Umgebung gewählt, welche die meisten Oktaeder enthält. Wenn es mehrere Umgebungen mit der gleichen Anzahl gibt, wird der Bereich gewählt, welcher näher an der Startposition 0,0,0 liegt.

Sobald die Umgebung = 1 groß ist, habe ich meine Koordinate, oder wenigstens hab ich es soweit eingegrenzt, dass der Punkt einfach gefunden wird.

Jetzt muss ich das nur irgendwie ins 3-dimensionale übertragen.

 

[mihe7]

Hm... ich hätte eher an einen Sweep gedacht. Bei dem 2D-Fall ist es relativ einfach, wenn Du das Koordinatensystem um 45° drehst.

 

[lennero]

Hm... ich hätte eher an einen Sweep gedacht. Bei dem 2D-Fall ist es relativ einfach, wenn Du das Koordinatensystem um 45° drehst.

Kannst du das näher beschreiben? Soll das sowas ähnliches wie ein Voronoi Diagramm werden?

 

[mihe7]

Nein. Bevor ich das lange beschreibe, habe ich mal was rausgesucht: https://core.ac.uk/download/pdf/82018244.pdf

 

[lennero]

Konnte das Problem lösen, allerdings nicht durch sweepen sondern Aufteilung des Raumes (wie beim Octree). Die Methode gibt die Distanz zum gesuchten Punkt aus.

 public void run2() {
    //find the bounding box
    int xMin = Integer.MAX_VALUE;
    int xMax = Integer.MIN_VALUE;
    int yMin = Integer.MAX_VALUE;
    int yMax = Integer.MIN_VALUE;
    int zMin = Integer.MAX_VALUE;
    int zMax = Integer.MIN_VALUE;

    for (Nanobot bot : nanoBots) {
        if (bot.position().x() < xMin)
        xMin = (int) bot.position().x();
        if (bot.position().x() > xMax)
        xMax = (int) bot.position().x();
        if (bot.position().y() < yMin)
        yMin = (int) bot.position().y();
        if (bot.position().y() > yMax)
        yMax = (int) bot.position().y();
        if (bot.position().z() < zMin)
        zMin = (int) bot.position().z();
        if (bot.position().z() > zMax)
        zMax = (int) bot.position().z();
    }

    // turn bounding box into a cube
    int maxPowTwo = nextPower(getMax(xMax, yMax, zMax));
    xMax = maxPowTwo + xMin;
    yMax = maxPowTwo + yMin;
    zMax = maxPowTwo + zMin;

    Cube current = new Cube(xMin, xMax, yMin, yMax, zMin, zMax);

    //priority queue with descending ordering based on intersections inside cubes
    Queue<Cube> cubes = new PriorityQueue<Cube>(10, new CubeComparator());
    cubes.add(current);

    int currentMaxIntersections = 0;
    int currentMaxDistance = Integer.MAX_VALUE;
    while (!cubes.isEmpty()) {

        current = cubes.poll();

        xMin = current.xMin();
        xMax = current.xMax();
        yMin = current.yMin();
        yMax = current.yMax();
        zMin = current.zMin();
        zMax = current.zMax();

        boolean isUnitCube = xMax - xMin <= 1 && yMax - yMin <= 1 && zMax - zMin <= 1;
        List<Cube> splitCubes = new ArrayList<Cube>();
        // cube can't be split anymore
        if (isUnitCube) {
        // check all 8 points of the unit cube
        splitCubes.add(new Cube(xMin, xMin, yMin, yMin, zMin, zMin));
        splitCubes.add(new Cube(xMax, xMax, yMin, yMin, zMin, zMin));
        splitCubes.add(new Cube(xMin, xMin, yMax, yMax, zMin, zMin));
        splitCubes.add(new Cube(xMax, xMax, yMax, yMax, zMin, zMin));
        splitCubes.add(new Cube(xMin, xMin, yMin, yMin, zMax, zMax));
        splitCubes.add(new Cube(xMax, xMax, yMin, yMin, zMax, zMax));
        splitCubes.add(new Cube(xMin, xMin, yMax, yMax, zMax, zMax));
        splitCubes.add(new Cube(xMax, xMax, yMax, yMax, zMax, zMax));

        Cube bestCube = null;
        int maxIntersections = 0;
        // calculate amount of intersections of all 8 points (smallest possible cubes)
        for (Cube cube : splitCubes) {
            int intersections = 0;
            for (Nanobot bot : nanoBots) {
            if (cube.containsBot(bot)) {
                cube.incrIntersections();
                intersections++;
            }
            }

            if (intersections > maxIntersections) {
            maxIntersections = intersections;
            bestCube = cube;
            }

        }
        currentMaxIntersections = bestCube.getIntersections();
        currentMaxDistance = Math.abs(bestCube.xMin()) + Math.abs(bestCube.yMin()) + Math.abs(bestCube.zMin());

        } else {
        // split cube into 8 equal pieces
        splitCubes.add(new Cube(xMin, (xMin + xMax) / 2, yMin, (yMin + yMax) / 2, zMin, (zMin + zMax) / 2));
        splitCubes.add(new Cube(xMin, (xMin + xMax) / 2, (yMin + yMax) / 2, yMax, zMin, (zMin + zMax) / 2));
        splitCubes.add(new Cube((xMin + xMax) / 2, xMax, yMin, (yMin + yMax) / 2, zMin, (zMin + zMax) / 2));
        splitCubes.add(new Cube((xMin + xMax) / 2, xMax, (yMin + yMax) / 2, yMax, zMin, (zMin + zMax) / 2));
        splitCubes.add(new Cube((xMin + xMax) / 2, xMax, (yMin + yMax) / 2, yMax, (zMin + zMax) / 2, zMax));
        splitCubes.add(new Cube(xMin, (xMin + xMax) / 2, (yMin + yMax) / 2, yMax, (zMin + zMax) / 2, zMax));
        splitCubes.add(new Cube((xMin + xMax) / 2, xMax, yMin, (yMin + yMax) / 2, (zMin + zMax) / 2, zMax));
        splitCubes.add(new Cube(xMin, (xMin + xMax) / 2, yMin, (yMin + yMax) / 2, (zMin + zMax) / 2, zMax));
        }


        // calculate amount of intersections of all 8 sub-cubes
        for (Cube cube : splitCubes) {
        for (Nanobot bot : nanoBots) {
            if (cube.containsBot(bot)) {
            cube.incrIntersections();
            }
        }

        if (cube.getIntersections() > currentMaxIntersections && !isUnitCube) {
            cubes.add(cube);
        }
        }


    }
    System.out.println(currentMaxDistance);
    }