如何使用双重调度分析图形基元的交集？ [英] How do I use double dispatch to analyze intersection of graphic primitives?

问题描述

我分析了图形基元（矩形，直线，圆等）与计算重叠，相对方向，合并等的交互作用。这被称为Double Dispatch的一个主要例子（例如 Wikipedia ）

自适应碰撞算法通常要求以不同方式处理
个不同对象之间的冲突。一个典型的例子是在游戏环境中
，其中太空船和
小行星之间的碰撞计算与
太空船和太空站之间的碰撞不同。 /en.wikipedia.org/wiki/Double_dispatchrel =nofollow> 1

但我没有理解了主要的解释，我也一般不了解SO的答案。

我的当前代码（Java）使用超类Shape，如下所示：

 <$对于（int j = i + 1; j  
 Shape shape = shapes.get（i）.intersectionWith（shapes.get（j））; 
 
 
 
 
 
 
 $ b 
在子类（这里是Rect）中有特定的实现，例如 
 
 
  public class Rect extends Shape {
 
 public shape intersectionWith（Shape shape）{
如果（形状instanceof Rect）{
返回this.getCommonBoundingBox（（Rect）shape）; 
} else if（shape instanceof Line）{
 return this.intersection（（Line）shape）; 
} else if（shape instanceof Text）{
 return this.intersection（（Text）shape）; 
} 
} 
} 
  
我必须写下所有无论如何（并且已经这么做了） n *（n-1）/ 2 方法。我还必须有可扩展的代码来适应（比如说）在以后的日子：
 } else if（shape instanceof Circle）{ 
返回this.intersection（（Circle）shape）; 
  
我没有看到如何使用或双重调度模式的值，一个使用Java图形原语或类似伪代码的具体例子。 
 
 
更新：我接受@Flavio（我认为）它回答了所问的确切问题。不过，我已经实现了@Slanec，因为它解决了我的问题，并且（对我而言）更简单，更易于阅读。我有一个附属问题解决方案取决于关系是对称的吗？。
 
 
交点B通常与B交点A相同，但A碰撞B并不总是与B碰撞A相同。 （A ==车，B ==骑自行车者）。可以想象的是，我的交叉点可能不是对称的（例如Rect部分模糊Circle不是对称的，并且可能有不同的语义。 
 
 
 @Flavio解决了维护问题并指出编译器可以检查问题@Slanec通过反射来做到这一点，它看起来好像是一种有用的维护辅助工具 - 我不知道性能如何。
 
 <您可以通过访问者模式在Java中实现双重调度。
  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 {
 
公众< 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 ... 
} 
}; 
} 
  
当您添加新的 Shape 子类，您必须向 ShapeVisitor 界面添加一个新方法，并且您将缺少所有方法的编译错误。这很有用，但如果您正在编写一个库并允许用户添加 Shape 子类（但显然无法扩展 ShapeVisitor 界面）。
 
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).

                        
这篇关于如何使用双重调度分析图形基元的交集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！