Quadtree erstellen und Punkte in einem bestimmten Radius suchen

S

StangelLata

Mitglied
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

Robat

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

StangelLata

Mitglied
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
Zum Vergrößern anklicken....
Java: 
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!
 

Aktuelle Jobs

Neue Themen


Oben