# Quadtree erstellen und Punkte in einem bestimmten Radius suchen



## StangelLata (5. Mai 2018)

Hallo!

Es geht darum in java einen Quadtree zu implementieren und eine vorhandene Datei mit Bushaltestellen und Bahnhöfen miteinzubinden (indem man
QuadTree quad = new QuadTree(readJunctions()); aufruft)
. Es soll eine Methode implementiert werden, welche einen frei gewählten Punkt in der  Ebene und einen Radius die Anzahl der Bushaltestellen und Bahnhöfe berechnet, die sich innerhalb dieses Radius befinden. Leider komme ich bei dieser Methode kaum weiter, da mir der Ansatz fehlt. 

Ich hoffe Ihr könnt mir erklären wie ich zu beginnen habe und worauf ich achten muss. 
MfG
Lars


----------



## Robat (6. Mai 2018)

Zeig doch am Besten mal deinen Code und erklär genau wo es hängt.
Zu QuadTree gibt es ja genug Referenzen im Netz


----------



## StangelLata (6. Mai 2018)

Robat hat gesagt.:


> Zeig doch am Besten mal deinen Code und erklär genau wo es hängt.
> Zu QuadTree gibt es ja genug Referenzen im Netz




```
import java.util.ArrayList;
import java.util.List;

public class QuadTree implements JunctionSolver {

    Point topLeft = new Point(0.0, 0.0);
    Point botRight = new Point(0.0,0.0);
    Junction j;
    QuadTree children[] = new QuadTree[4];
    //children[0] = QuadTree topLeftTree;
    //children[1] = QuadTree topRightTree;
    //children[2] = QuadTree botLeftTree;
    //children[3] = QuadTree botRightTree;
    private List<Junction> junctions;
    List<List<Junction>> found = new ArrayList<>();

    QuadTree(List<Junction> junctions) {
        this.junctions = junctions;
    }
    QuadTree() {
        topLeft = new Point(0, 0);
        botRight = new Point(0, 0);
        j = null;
        children[0]  = null;
        children[1]  = null;
        children[2]   = null;
        children[3] = null;
    }

    QuadTree(Point topL, Point botR) {
        j = null;
        children[0]  = null;
        children[1] = null;
        children[2]  = null;
        children[3] = null;
        topLeft = topL;
        botRight = botR;
    }

    boolean inBoundary(Point p)
    {
        return (p.getX() >= topLeft.getX() &&
                p.getX() <= botRight.getX() &&
                p.getY() >= topLeft.getY() &&
                p.getY() <= botRight.getY());
    }

    void insert(Junction junc)
    {
        if (junc == null)
            return;

        // Current quad cannot contain it
        if (!inBoundary(junc.getLocation()))
            return;

        // We are at a quad of unit area
        // We cannot subdivide this quad further
        if (Math.abs(topLeft.getX() - botRight.getX()) <= 1 &&
                Math.abs(topLeft.getY() - botRight.getY()) <= 1)
        {
            if (j == null)
                j = junc;
            return;
        }

        if ((topLeft.getX() + botRight.getX()) / 2 >= junc.getLocation().getX())
        {
            // Indicates topLeftTree
            if ((topLeft.getY() + botRight.getY()) / 2 >= junc.getLocation().getY())
            {
                if (children[0] == null)
                    children[0]= new QuadTree(
                            new Point(topLeft.getX(), topLeft.getY()),
                            new Point((topLeft.getX() + botRight.getX()) / 2,
                                    (topLeft.getY() + botRight.getX()) / 2));
                children[0].insert(junc);
            }

            // Indicates botLeftTree
            else
            {
                if (children[2] == null)
                    children[2] = new QuadTree(
                            new Point(topLeft.getX(),
                                    (topLeft.getY() + botRight.getY()) / 2),
                            new Point((topLeft.getX() + botRight.getX()) / 2,
                                    botRight.getY()));
                children[2].insert(junc);
            }
        }
        else
        {
            // Indicates topRightTree
            if ((topLeft.getY() + botRight.getY()) / 2 >= junc.getLocation().getY())
            {
                if (children[1] == null)
                    children[1]= new QuadTree(
                            new Point((topLeft.getX() + botRight.getX()) / 2,
                                    topLeft.getY()),
                            new Point(botRight.getX(),
                                    (topLeft.getY() + botRight.getY()) / 2));
                children[1].insert(junc);
            }

            // Indicates botRightTree
            else
            {
                if (children[3] == null)
                    children[3] = new QuadTree(
                            new Point((topLeft.getX() + botRight.getX()) / 2,
                                    (topLeft.getY() + botRight.getY()) / 2),
                            new Point(botRight.getX(), botRight.getY()));
                children[3].insert(junc);
            }
        }

    }



   public List<List<Junction>> findJunctions(Point p, double radius){

        if ((p.getX()>=topLeft.getX()+radius) || p.getY()>=topLeft.getY()+radius || p.getX() < botRight.getX()-radius ||p.getY()< botRight.getY()-radius){
            return null;
        }

        if (children == null){
            for (Junction j : junctions) {
                if (Math.abs(j.getLocation().getX()-p.getX())<=radius && Math.abs(j.getLocation().getX()-p.getX())<= radius){
                    if (j.withinRadius(p, radius)) {
                        int i = j.isAirport() ? 0 : 1;
                        found.get(i).add(j);
                    }
                }
            }
        }else {
            children[0].findJunctions(p,radius);
            children[1].findJunctions(p,radius);
            children[2].findJunctions(p,radius);
            children[3].findJunctions(p,radius);
        }
        return found;
    }
```
Quelle https://www.geeksforgeeks.org/quad-tree/ angepasst auf mein Problem

Die Methode findJunctions macht mir Probleme, habe es auf unterschiedliche Weise probiert, aber ich denke, dass der Ansatz schon falsch ist.
Hoffe Ihr könnt mir helfen!


----------



## Robat (6. Mai 2018)

Vielleicht bringt dich das ja auf den richtigen Pfad.


----------



## StangelLata (6. Mai 2018)

Robat hat gesagt.:


> Vielleicht bringt dich das ja auf den richtigen Pfad.


Habe mir das schon mehrmals angeschaut und auch ausprobiert, aber ich komme bei der Implementierung aufgrund meiner mangelnden Programmierkenntnisse nicht weiter


----------

