4
\$\begingroup\$

I have created a QuadTree in Java and would like a general code review or suggestions.

import java.util.ArrayList;


public class QuadTree
{
    private QuadTree root, parent, northEast, southWest, northWest, southEast;
    Point center;
    Double halfDimension;
    Double northBound, eastBound, southBound, westBound;
    ArrayList<iCollider> Objects;

    public QuadTree(Point center, Double halfDimension, QuadTree parent)
    {
        this.center = center;
        this.halfDimension = halfDimension;
        northBound = center.y + halfDimension;
        southBound = center.y - halfDimension;
        eastBound = center.x + halfDimension;
        westBound = center.x - halfDimension;
        this.parent = parent;
        northEast = null;
        southWest = null;
        northWest = null;
        southEast = null;
        Objects = new ArrayList<iCollider>();
        if (this.parent == null)
        {
            root = this;
        }
        else
        {
            root = parent.root;
        }
    }

    public ArrayList<iCollider> getColliders(Circle area)
    {

        ArrayList<iCollider> results = new ArrayList<iCollider>();
        for (iCollider c : Objects)
        {
            if (Point.getDistanceBetweenPoints(area.center, c.getBody().center) < (area.radius + c.getBody().radius))
            {
                results.add(c);
            }
        }
        if (area.center.x + area.radius > center.x)
        {
            if (area.center.y + area.radius > center.y && northEast != null)
            {
                results.addAll(northEast.getColliders(area));
            }
            if (area.center.y - area.radius < center.y && southEast != null)
            {
                results.addAll(southEast.getColliders(area));
            }
        }
        if (area.center.x - area.radius < center.x)
        {
            if (area.center.y + area.radius > center.y && northWest != null)
            {
                results.addAll(northWest.getColliders(area));
            }
            if (area.center.y - area.radius < center.y && southWest != null)
            {
                results.addAll(southWest.getColliders(area));
            }
        }
        return results;
    }

    ArrayList<QuadTree> getChildren()
    {
        ArrayList<QuadTree> children = new ArrayList<QuadTree>();

        for (Quadrant q : Quadrant.values())
        {
            if (this.getSubQuadTree(q) != null)
            {
                children.add(this.getSubQuadTree(q));
            }
        }
        return children;
    }

    public ArrayList<iCollider> getAllColliders()
    {
        ArrayList<iCollider> results = new ArrayList<iCollider>();
        results.addAll(Objects);

        for (QuadTree child : getChildren())
        {
            results.addAll(child.getAllColliders());
        }
        return results;
    }

    Quadrant getQuadrant(Point p)
    {
        if (p.x > center.x)
        {
            if (p.y > center.y)
            {
                return Quadrant.NORTHEAST;
                // return northEast;
            }
            else
            {
                return Quadrant.NORTHWEST;
                // return northWest;
            }
        }
        else
        {
            if (p.y > center.y)
            {
                return Quadrant.SOUTHEAST;
                // return southEast;
            }
            else
            {
                return Quadrant.SOUTHEAST;
                // return southWest;
            }
        }
    }

    void createQuadTreeForQuadrant(Quadrant q)
    {
        switch (q)
        {
        case NORTHEAST:
            northEast = new QuadTree(new Point((center.x + halfDimension), (center.y + halfDimension)), (halfDimension / 2), this);
        case NORTHWEST:
            northWest = new QuadTree(new Point((center.x - halfDimension), (center.y + halfDimension)), (halfDimension / 2), this);
        case SOUTHWEST:
            southWest = new QuadTree(new Point((center.x - halfDimension), (center.y - halfDimension)), (halfDimension / 2), this);
        case SOUTHEAST:
            southEast = new QuadTree(new Point((center.x + halfDimension), (center.y - halfDimension)), (halfDimension / 2), this);
        default:
            assert (false);
        }
    }

    QuadTree getSubQuadTree(Quadrant q)
    {

        switch (q)
        {
        case NORTHEAST:
            return northEast;
        case NORTHWEST:
            return northWest;
        case SOUTHWEST:
            return southWest;
        case SOUTHEAST:
            return southEast;
        default:
            assert (false);
            return null;
        }
    }

    void removeChild(Quadrant quadrant)
    {
        switch (quadrant)
        {
        case NORTHEAST:
            northEast = null;
        case NORTHWEST:
            northWest = null;
        case SOUTHWEST:
            southWest = null;
        case SOUTHEAST:
            southEast = null;
        default:
            assert (false);
        }
    }

    public int numColliders()
    {
        return Objects.size();
    }

    public boolean insert(iCollider c)
    {
        if (fitsWithin(c.getBody()))
        {
            if (Objects.size() < SFAServer.quadCapacity)
            {
                return Objects.add(c);
            }
            else
            {
                Quadrant quadrant = getQuadrant(c.getBody().center);
                QuadTree subQuadTree = getSubQuadTree(quadrant);
                if (subQuadTree == null)
                {
                    createQuadTreeForQuadrant(quadrant);
                }
                if (subQuadTree.fitsWithin(c.getBody()))
                {
                    return subQuadTree.insert(c);
                }
                else
                {
                    // object does not fit within any of the child QuadTrees
                    this.balance();
                    return Objects.add(c);
                }
            }
        }
        else
        {
            if (parent != null)
            {
                return parent.insert(c);
            }
            else
            {
                System.out.println("Error: unable to insert into QuadTree");
                return false;
            }
        }
    }

    private void balance()
    {

        for (iCollider c : Objects)
        {
            relocate(c);
        }
    }

    public boolean remove(iCollider c)
    {
        // not sure if the best case is for it to check itself first or to check
        // the children first
        if (Objects.remove(c))
        {
            return true;
        }
        else
        {
            if (getSubQuadTree(getQuadrant(c.getBody().center)) != null)
            {
                return getSubQuadTree(getQuadrant(c.getBody().center)).remove(c);
            }
        }
        return false;
    }

    public void relocate(iCollider c)
    {
        if (fitsWithin(c.getBody()))
        {
            if (numColliders() < SFAServer.quadCapacity)
            {
                return;
            }
        }
        else
        {
            assert (remove(c));
            insert(c);
        }
    }

    public boolean fitsWithin(Circle c)
    {
        if ((c.center.x + c.radius > eastBound) || (c.center.x - c.radius < westBound) || (c.center.x + c.radius > northBound) || (c.center.x + c.radius < southBound))
        {
            return false;
        }
        return true;
    }

    public boolean fitsWithin(Point p)
    {
        if ((p.x > eastBound) || (p.x < westBound) || (p.y > northBound) || (p.x < southBound))
        {
            return false;
        }
        return true;
    }

}

enum Quadrant
{
    NORTHEAST(1), NORTHWEST(2), SOUTHWEST(3), SOUTHEAST(4);
    int value;

    private Quadrant(int value)
    {
        // not sure what the point of this is
        this.value = value;
    }
}


class Circle
{

    public Point center;
    public Double radius;

    public Circle(Point center, Double radius)
    {
        this.center = center;
        this.radius = radius;
    }

    public double getArea()
    {
        return Math.PI * radius * radius;
    }

    public double getCircumference()
    {
        return Math.PI * 2 * radius;
    }
}

class Point
{
    public double x, y;

    public Point(double x, double y)
    {
        this.x = x;
        this.y = y;
    }

    public static double getAngleBetweenPoints(Point point1, Point point2)
    {
        double angle = Math.toDegrees(Math.atan2(point1.x - point2.x, point1.y - point2.y));
        if (angle < 0)
        {
            angle += 360;
        }
        return angle;
    }

    public static double getDistanceBetweenPoints(Point point1, Point point2)
    {
        Double dx = point1.x - point2.x;
        Double dy = point1.y - point2.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    public static Point getPointfromOffset(Point p, double distance, double offsetAngle)
    {
        double xOffset = Math.sin(offsetAngle) * distance;
        double yOffset = Math.cos(offsetAngle) * distance;
        Point result = new Point((p.x + xOffset), (p.y + yOffset));
        return result;
    }
}

public interface iCollider
{
    void update(double delta, QuadTree current);

    void resetUpdate();

    Circle getBody();

    ColliderType getType();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, and welcome to Code Review. Recommendations on how best to test your code are off-topic here. I'm going to update your title accordingly. \$\endgroup\$ – rolfl Jul 28 '14 at 15:54
2
\$\begingroup\$

This code is difficult to review for many reasons:

  • It's not following standard formatting
  • It's not following standard naming, for example: iCollider, Objects
  • There are some unknown external elements, for example: ColliderType, SFAServer
  • Almost half of the methods are unused (not referenced within your post)

It would be better to post your best attempt, something you already cleaned up and criticized yourself.

Make fields private

As much as possible, make all fields private, and add some getters and setters when necessary

Make fields immutable

Classes with immutable fields are great. Immutable things are the least troublesome elements, they are robust, and inherently thread-safe. For example all these fields could be declared final:

  • x and y in Point
  • center and radius in Circle
  • center, halfDimension, northBound, ..., objects in QuadTree

Use interface types

Use interfaces in variable and method declarations as much as possible. Don't do this:

public ArrayList<iCollider> getColliders(Circle area) {
    ArrayList<iCollider> results = new ArrayList<iCollider>();

Do like this instead:

public List<iCollider> getColliders(Circle area) {
    List<iCollider> results = new ArrayList<iCollider>();

About Quadrant.value

To answer your question in this code:

enum Quadrant {
    NORTHEAST(1), NORTHWEST(2), SOUTHWEST(3), SOUTHEAST(4);
    int value;

    private Quadrant(int value) {
        // not sure what the point of this is
        this.value = value;
    }
}

If you're not sure what the point is, then delete it and see what breaks. In any case, the code you posted is not using it.

Pointless comments

Don't comment like this:

if (p.y > center.y) {
    return Quadrant.NORTHEAST;
    // return northEast;
} else {
    return Quadrant.NORTHWEST;
    // return northWest;
}

Actually, it's not good to comment in general.

Many more...

IDEs usually warn you about things that are not so good. I'm using the community edition of IntelliJ and your code is full of many more warnings that are easy to fix. I'm sure Eclipse and others would give you many warnings too. In Eclipse I would especially recommend the FindBugs plugin. By following the advices of these tools, you can learn a lot and naturally avoid the most common mistakes.

\$\endgroup\$
  • \$\begingroup\$ Actually eclipse (Luna) doesn't have any warnings with the code.. but I will try the FindBugs \$\endgroup\$ – user2813274 Jul 28 '14 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.