I am analyzing the interaction of graphics primitives (rect, line, circle, etc.) and computing the overlap, relative orientation, merging, etc. This is quoted as a prime example of Double Dispatch (e.g. Wikipedia)
Adaptive collision algorithms usually require that collisions between different objects be handled in different ways. A typical example is in a game environment where the collision between a spaceship and an asteroid is computed differently than the collision between a spaceship and a spacestation.1
but I haven't understood the main explanations and I also don't generally understand the answers on SO.
My current code (Java) uses a superclass Shape and is something like:
for (int i = 0; i < shapes.size() - 1; i++) {
for (int j = i + 1; j < shapes.size(); j++) {
Shape shape = shapes.get(i).intersectionWith(shapes.get(j));
}
}
with specific implementations in subclasses (here Rect) such as
public class Rect extends Shape {
public Shape intersectionWith(Shape shape) {
if (shape instanceof Rect) {
return this.getCommonBoundingBox((Rect)shape);
} else if (shape instanceof Line) {
return this.intersection((Line)shape);
} else if (shape instanceof Text) {
return this.intersection((Text) shape);
}
}
}
I have to write all the n*(n-1)/2
methods anyway (and have done so). I also have to have extensible code to accommodate (say) at a later date:
} else if (shape instanceof Circle) {
return this.intersection((Circle)shape);
I don't see how to use, or the value of, the double dispatch pattern and would appreciate a concrete example using Java graphics primitives or similar pseudocde.
UPDATE: I have accepted @Flavio as (I think) it answers the exact question asked. However I have actually implemented @Slanec as it solves my problem and (to me) is simpler and easier to read. I have a subsidiary question "Do the solutions depend on the relationship being symmetric?".
"A intersects B" is usually identical to "B intersects A" but "A collides with B" is not always the same as "B collides with A". (A == car, B == cyclist). It is conceivable that my intersections may not be symmetric in futute (e.g. "Rect partially obscures Circle" is not symmetric and may have different semantics.
@Flavio addresses the maintenance problem well, and points out that the compiler can check for problems. @Slanec does this through reflection which looks as if it is a useful maintenance aid - I don't know what the performance hit is.
You can implement double dispatch in Java through the Visitor
pattern.
public interface ShapeVisitor<P, R> {
R visitRect(Rect rect, P param);
R visitLine(Line line, P param);
R visitText(Text text, P param);
}
public interface Shape {
<P, R> R accept(P param, ShapeVisitor<? super P, ? extends R> visitor);
Shape intersectionWith(Shape shape);
}
public class Rect implements Shape {
public <P, R> R accept(P param, ShapeVisitor<? super P, ? extends R> visitor) {
return visitor.visitRect(this, param);
}
public Shape intersectionWith(Shape shape) {
return shape.accept(this, RectIntersection);
}
public static ShapeVisitor<Rect, Shape> RectIntersection = new ShapeVisitor<Rect, Shape>() {
public Shape visitRect(Rect otherShape, Rect thisShape) {
// TODO...
}
public Shape visitLine(Line otherShape, Rect thisShape) {
// TODO...
}
public Shape visitText(Text otherShape, Rect thisShape) {
// TODO...
}
};
}
When you add a new Shape
subclass, you must add a new method to the ShapeVisitor
interface, and you get compile errors for all the methods you are missing. This is useful, but can become a big problem if you are writing a library and your users are allowed to add Shape
subclasses (but clearly can not extend the ShapeVisitor
interface).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments