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());
}
}