2

I have a Position class with int x and int y fields. I have a bunch of points and some of them need to know the distance to all other points. Does it make sense to store it in Map<Position, float> distances (this is another field in the Position class)? Other points don't need that information, so their distances field is null.

Is there anything obviously wrong with this, i.e. bad design? Calculating the distance in this case is quite complex, so it certainly makes sense to store the results in a collection instead of calculating it on the fly.

  • 3
    I don't think we can answer this until we know why some points need that information and others don't, and more importantly, what is that information being used for and by whom. To me this sounds extremely suspicious and is probably information that belongs outside the points themselves, but I can't say that for sure without more context. Also, why is calculating the distance between two 2D points "complex"? Have you left out something about how distance is defined in your program? – Ixrec Mar 30 '16 at 13:02
  • 4
    How often do distances change? (i.e., are your points moving?) How often do you need to look them up? – Dan Pichelman Mar 30 '16 at 13:16
  • Distance is usually predicated on have a starting point. Often, that starting point changes during the execution of your program. What happens when you calculate distance from point a but also want to show distance from point b? – Adam Zuckerman Mar 30 '16 at 13:22
  • Simply because the points represent different places ike a house or office. It doesnt make sense to create multiple classes for this. You can think of cars as points too. Every building needs to know the distance to the cars, but cars themselves dont need any such info and the map will be empty. Yes, calculating distance is complex and thats all you need to know really, just accept it. – user5539357 Mar 30 '16 at 14:00
7

The distance between two Positions is really not an attribute of either of them. If calculating the distance is so heavy that caching the results would be beneficial, then you should probably introduce a DistanceCalculator with a function

float calculateDistance(Position a, Position b)

This would allow you to hide all optimization tricks in the DistanceCalculator object. This would also allow you to easily take advantage of the fact that distance is symmetric: dist(a, b) = dist(b, a).

If your Positions are mutable, then the function should really be of form

float calculateDistance(Location a, Location b)

with immutable Locations as parameters. It's not preferable to have mutable objects as keys of a Map or even as parameters of a pure function (or something that really should be a pure function). You don't want to deal with questions like "What if the Position a changes while I'm calculating the distance between a and b?".

If you'd still like your Position objects to provide a distance function to the rest of your app, then you could even include the DistanceCalculator object as a class level object inside the Position class and use it when providing the distance:

float distanceTo(Position anotherPosition) {
    return distanceCalculator.calculateDistance(this, anotherPosition);
}

Edit: Here's some points about calculating and caching distances.

First of all it's important to notice that a distance between to 2d points is equal to -- or rather the same thing as -- the length of their difference vector. Second, the lenght of any 2d vector (a, b) is equal to the length of the vector (abs(a), abs(b)) and the vector (abs(b), abs(a)). Thus you really only need to store the lengths of vectors with positive components a > 0, b > 0, having a > b. You'll get the distance of many possible pairs of points on 2d plane by calculating the length of a single vector.

If your coordinates fall into a fairly limited range and getting the distance between points needs to be done very efficiently, then I'd suggest storing the distances in a 2d array and perhaps even precalculating all of them at once. If calculating square roots is the part you'd like to avoid, then perhaps you could just use a table for square roots. Also note that it's not neccessary to calculate square roots at all when only comparing distances.

If your coordinates have a too wide range for any table based cache, then you could try using a map (int, int) -> float. You'd need a class for that pair of ints in Java with equals and hashCode implemented. Alternatively you could try using Long as a key, packing x to high int and y to low int. Unfortunately the hashCode() implementation of Long could prove a little problematic for this approach. You'd also need to decide how many results you'd like to store should there be a risk of filling the memory with cached results.

I wonder what you mean by saying "calculating distance is complex" in you case? I don't think fetching a value from a map is necessarily any faster than just crunching a few numbers, namely doing sqrt(dx*dx + dy*dy). You could probably avoid collisions very well with a good hash function (see https://stackoverflow.com/questions/5928725/hashing-2d-3d-and-nd-vectors), but storing and fetching values from a map is still relatively complicated.

It should be easy to try out different approaches. Introduce the DistanceCalculator as an interface and write a couple of implementations: one without any caching, one with a map and perhaps one with a table. Switching between implementations should require at most one little change in your Point class.

What ever is the optimal solution for your case, it could be hidden in the implementation of DistanceCalculator:

class CachingDistanceCalculator implements DistanceCalculator {

    // Whatever proves an effective way to cache the lengths of vectors:
    //
    // private float[][] lengthTable;
    // or 
    // private Map<IntVector2, Float> lengthMap;
    // or
    // private Map<Long, Float> lengthMap;

    public float distance(Position a, Position b) {
        int dx = Math.abs(a.getX() - b.getY());
        int dy = Math.abs(a.getY() - b.getY());
        return dx >= dy ? length(dx, dy) : length(dy, dx);
    }

    private float length(int dx, int dy) {
        if (isCached(dx, dy)) {
            return cached(dx, dy); 
         } else {
            float length = calcLength(dx, dy);
            cacheLength(length, dx, dy);
            return length;
        }
    }

}

public class Point {

   private static DistanceCalculator distanceCalculator;

   ...

   public distanceTo(Point anotherPoint) {
       return distanceCalculator.distance(this, anotherPoint);
   }

}

EDIT2: Ok, since the problem could be more about tracking the distances of a limited amount of constantly moving objects, here's another crude sketch.

When keeping record of distances between a relatively small set of objects, a symmetric matrix comes handy. You need an index for each object to use a matrix.

It's still very important to only calculate distances between fixed points. To safely handle the change of locations, an immutable Location object as a mutable property of a moving object works well. It's important that both coordinates get changed at once.

The below approach calculates distances lazily, only when they're asked for, not every time an object moves. Movement only triggers clearing of previously calculated distances for the particular object. Some synchronization may be added if it's important to block simultaneous calculations and movements. The distance tracking logic could be moved to a class and used through a static instance of that class.

public class MovingObject {

    private static int nextObjectIndex = 0;
    private static DynamicSymmetricMatrix<Float> distanceMatrix 
                       = new DynamicSymmetricMatrix<>(Float.class);

    private Location location;
    private int index;

    public MovingObject(Location initialLocation) {
        this.location = initialLocation;
        this.index = nextObjectIndex++;
    }

    public float distanceTo(MovingObject anotherObject) {
        return getDistance(this, anotherObject);
    }

    public Location getLocation() {
        return location;
    }

    public void moveTo(Location newLocation) {
        this.location = newLocation;
        updateDistanceMatrix();
    }

    private void updateDistanceMatrix() {
        distanceMatrix.clearRowAndColumn(getIndex());
    }

    private int getIndex() {
        return index;
    }

    private static float getDistance(MovingObject a, MovingObject b) {
        Float distance = distanceMatrix.get(a.getIndex(), b.getIndex());
        if (distance == null) {
            distance = calcDistance(a, b);
            distanceMatrix.set(a.getIndex(), b.getIndex(), distance);
        }
        return distance;
    }

    private static float calcDistance(MovingObject a, MovingObject b) {
        return a.getLocation().distanceTo(b.getLocation());
    }
}
  • Okay, and how should I store those distances assuming I want to store them? You only mentioned a calculator class. – user5539357 Mar 30 '16 at 14:31
  • 2
    I'd suggest a map (point, point) -> float. Just make sure you don't calculate and store both dist(a, b) and dist(b, a). And make sure the key of the map is not mutable. – COME FROM Mar 30 '16 at 14:35
  • @user5539357 Actually, (int, int) -> float is a lot better. You just need to calculate the difference between two positions first. I'll improve my answer as soon as possible. – COME FROM Mar 30 '16 at 14:45
  • Thanks. It's not preferable to have mutable objects as keys of a Map or even as parameters of a pure function (or something that really should be a pure function). You don't want to deal with questions like "What if the Position a changes while I'm calculating the distance between a and b?. But the same issue appears if I get the int coordinates of my object first and then call the function. During the calculations the position of my object might still change, so the result will no longer be valid. – user5539357 Mar 30 '16 at 19:35
  • @user5539357 The result will be the correct distance between the points you've given as arguments. Whether or not some objects move during the calculation is a whole different problem. You need to avoid getting totally incorrect distances like what you could get if the x coordinate of an object gets updated before the calculation and the y coordinate gets updated after that. This is why you need immutable Locations as parameters of a distance function. Mutable MovingObjects as parameters will result in serious bugs. – COME FROM Mar 30 '16 at 20:19
1

A distance is calculated between two points. I don't think a map where the key is a Point object is going to work. You really need a tuple of two Points and the associated distance. Even then, you could use a map of sorts to cache the distance calculations, maybe as x1 + "," + y1 + "|" + x2 + "," + y2. Two points: x:3, y:5 and x:6, y:12 would be stored in the distance cache with a key of 3,5|6,12.

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

    private int x;
    private int y;

    private static Map<String, float> cachedDistances = new Map<String, float>();

    public float calculateDistance(Point other) {
        String key = getDistanceCacheKey(other);

        if (!cachedDistances.containsKey(key)) {
            // Calculate distance and save to cache
        }

        return cachedDistances[key];
    }

    private String getDistanceCacheKey(Point other) {
        return this.x + "," + this.y + "|" + other.getX() + "," + other.getY();
    }
}

Now the challenge becomes keeping the cache in sync with the point objects, and removing keys when point objects are destroyed. If the x or y coordinates of a point object changes, you need to delete any distance cache values that contain the old x and y coordinates. This becomes even more challenging if two or more points exist at the same coordinates.

This also might be a case of premature optimization. I would just calculate the distance every time. Only after encountering a performance problem would I try to implement a caching mechanism, which to be honest would be better off as its own class and each Point object should get its own unique identifier.

1

It can make sense to do this if the number of times the distance will be retrieved is a lot more than one time per distance change. First of all, hide this behind a method in the Position class e.g. distance(Position other) so that the rest your code doesn't need to know about how the sausage is made. The real consideration is going to be around making sure the cache of distances is kept up to date. You need to make sure that you update (or at least invalidate) the entry in the map every time the position is changed. If you are multi-threading, this gets way more complicated. That's probably the biggest issue here.

You may want to consider using a class level map here. Since the distance from A->B presumably is the same as B->A, there's a potential optimization there (use a order-free tuple as a key.) Also, it make it easier to make sure that you've updated all the distances when a a position changes. If you leave it on the object, you need to know when the other positions changed, not just this one and that can get tricky. You potentially introduce more contention but getting it right is your primary concern here.

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.