jim@pcad.UUCP (James Kuzeja) (10/24/90)
I would like some advice on techniques for handling the interaction of
two objects, or in general, n objects, whose exact types are not known
until run time. I have provided a quite lengthy example of the problem,
but it boils down to this: How can the useful abstraction supplied by
virtual functions be extended to interactions of several objects?
The premise is this: I need to determine if two shapes
intersect. Of course, the exact type of shape is not known at compile
time, and extensibility of the shape class is a must.
So far, my solution has been to establish several conventions that new
shapes must follow to allow intersection tests to work. The first
is that a new shape must provide methods for determining if it
intersects any existing shape (including itself). The second is that
it must provide methods (which are "keyed" with a protected enum) that
are sufficient to allow future shapes to determine intersections.
All shapes are derived from a common class Shape. It is NOT desirable to
derive each new shape from the preceding shape (too many wasted data
members). Thus, all derived shapes are in a brother-sister relationship,
not parent-child.
Here is an example:
typedef int Boolean; typedef int Vector; typedef int Coord; // dummy types
class Shape {
public:
// The next member function reverses the input args.
// With message passing, I think this would solve my problem, as
// after two reversals, both shape types would be "known".
virtual Boolean hit (const Shape &x) const { return x.hit(*this); }
virtual Draw () const = 0;
protected:
enum ShapeKey { key }; // allow children to share "secrets"
};
class Circle : public Shape {
Vector _center;
Coord _radius;
public:
// handle intersections for all existing shapes (Circle)
Boolean hit (const Circle &x);
Draw();
// allow ONLY brothers to access internals
Vector center(ShapeKey x) { return _center; }
Coord radius(ShapeKey x) { return _radius; }
};
class Box : public Shape {
Vector _lowerleft;
Vector _upperright;
public:
// handle intersections for all existing shapes (Circle, Box)
Boolean hit (const Circle &x);
Boolean hit (const Box *x);
Draw();
// allow ONLY sisters to access internals
Vector lowerleft(ShapeKey x) { return _lowerleft; }
Vector upperright(ShapeKey x) { return _upperright; }
};
My original thinking was this: to intersect shape C (a circle) with
shape B (a box), while not knowing either type (because they were in
a list of Shapes, for instance), call
C.hit(B) . This would resolve to
Circle::hit (const Shape &B) . This then calls
B.hit (const Circle &(*this)) , [and *this == C], which resolves to
Box::hit (const Circle &C) <=== WRONG! (but what I expected).
The last statement won't work because Box::hit (const Circle &C) is not
virtual. So, here are my options as far as I and my colleagues have been
able to determine:
0) Whenever a new shape is added, go back to all the other shapes and
teach them how to intersect with the new shape. I am only stating
this for completeness. If I wanted to do this, I would be using
C, not C++.
1) Whenever a new shape is added (e.g., Polygon), derive it from the last
defined shape, and add a virtual function to intersect with each
existing shape (including itself). This is unacceptable, because
there would be too much unused data space in objects at the end of
the hierarchy.
2) Whenever a new shape is added, modify the base Shape class to contain
a virtual "hit" function that takes the new shape type as an argument.
This also is unacceptable, because it would require a recompile of the
shape library, and this would not be feasible for most library users.
Also, it seems to go against the grain of "virtual-ness".
3) All shapes could be required to produce a common, say polygonal,
representation of themselves for purposes of intersection. This
is unacceptable, because too much precision would be lost by
using polygonal approximations of the actual shape. However, this
technique might be applicable in other circumstances.
4) Provide an "is-a" member function for each shape. Only use this
to resolve the type of the second argument. If the type is
recognized, handle the intersection; otherwise, reverse the
arguments and recall the function. The newer shape should always
recognize the older shape. One implementation:
typedef int Boolean; typedef int Vector; typedef int Coord; // dummy types
class Shape {
public:
virtual int IsA () const = 0;
virtual Boolean hit (const Shape &x) const = 0;
virtual void Draw () const = 0;
protected:
enum ShapeKey { key }; // allow children to share "secrets"
};
const int SH_CIRCLE = 0; // avoid enums here - not extensible
class Circle : public Shape {
Vector _center;
Coord _radius;
public:
int IsA() const { return SH_CIRCLE; }
// handle intersections for all existing shapes (Circle)
Boolean hit (const Shape &x) const {
switch (x.IsA()) {
case SH_CIRCLE: return hit((Circle &)x); break; // ugh!
default: return x.hit(*this); break; // try other shape
}
}
Boolean hit (const Circle &x);
void Draw();
// allow ONLY sisters to access internals
Vector center(ShapeKey x) const { return _center; }
Coord radius(ShapeKey x) const { return _radius; }
};
const int SH_BOX = SH_CIRCLE + 1; // avoid enums here - not extensible
class Box : public Shape {
Vector _lowerleft;
Vector _upperright;
public:
int IsA() const { return SH_BOX; }
// handle intersections for all existing shapes (Circle, Box)
Boolean hit (const Shape &x) const {
switch (x.IsA()) {
case SH_CIRCLE: return hit((Circle &)x); break; // ugh!
case SH_BOX: return hit((Box &) x); break; // ugh!
default: return x.hit(*this); break; // try other shape
}
}
Boolean hit (const Circle &x);
Boolean hit (const Box *x);
void Draw();
// allow ONLY brothers to access internals
Vector lowerleft(ShapeKey x) const { return _lowerleft; }
Vector upperright(ShapeKey x) const { return _upperright; }
};
(Another implementation could use arrays of function pointers in each
class, and index them with the IsA function result.) In either case,
the IsA function is a kludge at best. However, this solution DOES
allow extension without recompilation.
I would appreciate any thoughts on this problem, as well as the multiple-
unknown-interacting-objects problem in general. I would also appreciate
references to treatments of this topic in the literature. Thanks.
Jim Kuzeja Personal CAD Systems
Voice: (508) 692-8843 One Technology Park Drive
FAX: (508) 692-9261 Westford, MA 01886