Generic shape design

Question

I've been trying to come up with a generic shape design that would support shape-shape interactions (like Intersect), based on the shape's type.

So a common class/interface was needed, but a problem arises from shape types since not all shapes have common properties (eg. Circle is composed of a point and a radius, while polygons are composed of multiple points) so each pair of shape types has to have their own Intersect method.

After a lot of reading up on the subject of generics (and the like), i've come up with the following structure:

Collection class for storing delegates to shape Intersect methods

class IRdelegateCollection<T> // IntersectResult delegate collection
{
    public delegate IntersectResult IntersectAction<in U>(T a, U b);

    Dictionary<Type, Delegate> _jumpTable;
    public IRdelegateCollection()
    {
        _jumpTable = new Dictionary<Type, Delegate>();
    }
    public IRdelegateCollection(Dictionary<Type, Delegate> jumpTable)
    {
        _jumpTable = jumpTable;
    }
    public void Set<U>(IntersectAction<U> action)
    {
        if (_jumpTable.ContainsKey(typeof(U)))
            _jumpTable[typeof(U)] = action;
        else
            _jumpTable.Add(typeof(U), action);
    }
    public IntersectAction<U> Get<U>()
    {
        if (!_jumpTable.ContainsKey(typeof(U)))
        {
            return null;
        }
        return _jumpTable[typeof(U)] as IntersectAction<U>;
    }
}

Interfaces

interface IShape
{
    IntersectResult Intersects(IShape shape, out bool flipped);
    IntersectResult Intersects<T>(IShape<T> shape, out bool flipped);
}
interface IShape<T> : IShape
{
    T Instance { get; }
    IRdelegateCollection<T> IC { get; }
}

Base Shape class (all shapes will derive from this, although i guess they don't have to as long as they have their own IShape interface implementation)

abstract class Shape<T> : IShape<T>
{
    public abstract T Instance { get; } // shape instance
    public abstract IRdelegateCollection<T> IC { get; } // shape type's intersection delegate collection                

    public IntersectResult Intersects(IShape shape, out bool flipped)
    {
        IntersectResult r = shape.Intersects<T>(this, out flipped); // call the other shape's intersect method, specifying our type
        flipped = !flipped; // results are flipped since we're calling the other shape's method
        return r;
    }
    public IntersectResult Intersects<T2>(IShape<T2> shape, out bool flipped)
    {
        flipped = false;
        var del1vs2 = IC.Get<T2>();
        if (del1vs2 != null) // we have the intersection delegate
            return del1vs2(Instance, shape.Instance);

        var del2vs1 = shape.IC.Get<T>(); // we dont have the delegate, try get the other shape's intersection delegate
        if (del2vs1 != null)
        {
            flipped = true; // we're returning the results of other shape's delegate, mark it as flipped
            return del2vs1(shape.Instance, Instance);
        }

        // neither of the two shapes have the intersection delegate
        return new IntersectResult();
    }        
}

Some concrete shape definitions. (ShapeA does not have delegate for ShapeA-ShapeB intersection, but since ShapeB has one for ShapeB-ShapeA thats the one that gets called when intersecting ShapeB on ShapeA)

class ShapeA : Shape<ShapeA>
{
    static IRdelegateCollection<ShapeA> _ic =
        new IRdelegateCollection<ShapeA>(
            new Dictionary<Type, Delegate>()
            {
                { typeof(ShapeA), new IRdelegateCollection<ShapeA>.IntersectAction<ShapeA>(MathCol.AIntersectsA) }
            }
        );
    public override ShapeA Instance { get { return this; } }
    public override IRdelegateCollection<ShapeA> IC { get { return _ic; } }
}
class ShapeB : Shape<ShapeB>
{
    static IRdelegateCollection<ShapeB> _ic =
       new IRdelegateCollection<ShapeB>(
           new Dictionary<Type, Delegate>()
           {
                    { typeof(ShapeB), new IRdelegateCollection<ShapeB>.IntersectAction<ShapeB>(MathCol.BIntersectsB) },
                    { typeof(ShapeA), new IRdelegateCollection<ShapeB>.IntersectAction<ShapeA>(MathCol.BIntersectsA) }
           }
       );
    public override ShapeB Instance { get { return this; } }
    public override IRdelegateCollection<ShapeB> IC { get { return _ic; } }
}

With this kind of structure i can have a list of shapes and be able to intersect them appropriately without having to manually check their types.

ShapeA a = new ShapeA();
ShapeB b = new ShapeB();
bool flipped = false;

// These are called via .Intersects<T>(T shape, out bool flipped)
a.Intersects(a, out flipped); //calls AintersectsA, flipped: False
a.Intersects(b, out flipped); //calls BintersectsA, flipped: True
b.Intersects(a, out flipped); //calls BintersectsA, flipped: False
b.Intersects(b, out flipped); //calls BintersectsB, flipped: False

List<IShape> shapes = new List<IShape>();
shapes.Add(a);
shapes.Add(b);
// These are called via .Intersects(IShape shape, out bool flipped)
shapes[0].Intersects(shapes[0], out flipped); //calls AintersectsA, flipped: True
shapes[0].Intersects(shapes[1], out flipped); //calls BintersectsA, flipped: True
shapes[1].Intersects(shapes[0], out flipped); //calls BintersectsA, flipped: False
shapes[1].Intersects(shapes[1], out flipped); //calls BintersectsB, flipped: True

So there it is, now what i would like to know is:

1. Is this design appropriate for my requirement (having base shape that can intersect other shapes based on their subtype)?
2. The double interface - is this considered bad design (since IShape's method accepts IShape<T> argument and IShape<T> is derived from IShape)? Note: i've also tried an alternative design where the IShape.Intersect<T> parameter was the abstract class Shape<T> but that didn't seem right as well.
3. I've had constraints where T : IShape on both the interface, abstract class Shape<T> and IRdelegateCollection<T> since i was trying to avoid the T Instance which is used in the Intersection<T>() method, but the compiler still had problems converting Shape<T> to T.
   • Is there a way to use the sahpes directly in the delegate invokation of the Shape<T>.Intersects<T2> method? (preferably: del1v2(this, shape) - was throwing the above mentioned error, even with the constraints all over the place)
   • Should there be constraints of where T : IShape on all the Ts? (There does not appear to be any advantage to constraining it)
4. Class IRdelegateCollection<T> uses a "jump table". My implementation needs a _jumpTable.ContainsKey(typeof(U)) check for both setting and getting. Is there a better way of making this kind of jump table?

---

EDIT: after reading @Theraot's answer, and finding out that non-static classes can also have a static constructor, i've arrived at the following stucture:

delegate IntersectResult IntersectAction<in T, in U>(T a, U b);
interface IShape
{
    IntersectResult Intersects(IShape shape, out bool flipped);
    IntersectResult Intersects<T>(Shape<T> shape, out bool flipped);
}
abstract class Shape<T> : IShape
{
    public static class Interactor<U>
    {
        public static IntersectAction<T, U> Intersect { get; set; }
    }
    public abstract T Instance { get; } // shape instance     

    public IntersectResult Intersects(IShape shape, out bool flipped)
    {
        IntersectResult r = shape.Intersects<T>(this, out flipped); // call the other shape's intersect method, specifying our type
        flipped = !flipped; // results are flipped since we're calling the other shape's method
        return r;
    }
    public IntersectResult Intersects<T2>(Shape<T2> shape, out bool flipped)
    {
        flipped = false;
        if (Interactor<T2>.Intersect != null)
            return Interactor<T2>.Intersect(Instance, shape.Instance);
        if (Shape<T2>.Interactor<T>.Intersect != null)
        {
            flipped = true; // results are flipped since we're calling the other shape's method
            return Shape<T2>.Interactor<T>.Intersect(shape.Instance, Instance);
        }
        return new IntersectResult();
    }
}    
class ShapeA : Shape<ShapeA>
{
    static ShapeA()
    {
        Interactor<ShapeA>.Intersect = MathCol.AintersectsA;
        Interactor<ShapeB>.Intersect = MathCol.AintersectsB;
    }
    public override ShapeA Instance { get { return this; } }        
}

I've decided to nest the static Interactor class inside the Shape because it didn't feel right having it completely decoupled from the Shape class.
I'm still not happy about public abstract T Instance { get; } but i guess it is required if I'm doing the work in the abstract class.
I'll leave the question open for a bit to see if someone else might have some more insight on the whole matter.

Answer 1

---

Selecting the Intersection Method

4. Class IRdelegateCollection uses a "jump table". My implementation needs a _jumpTable.ContainsKey(typeof(U)) check for both setting and getting. Is there a better way of making this kind of jump table?

You need to:

1. Discover the delegates
2. Populate the delegate cache
3. Invoke the delegate from the delegate cache

1. Discover the delegates

You may choose not to discover the delegates, but instead to write them by hand in whatever code you are using to populate your delegate cache or directly where invoked.

If you want code to discover the delegates, you can use Reflection to find the right method to call from your MathCol class.

You can, for example, select a method by its name and call it:

var method = typeof(MathCol).GetMethod("AIntersectsA");
method.Invoke(a, b);

By building the string you pass to GetMethod you can then select the appropriate method to call.

If needed, you can specify the parameters types:

var method = typeof(MathCol).GetMethod("BIntersectsA", new Type[]{typeof(ShapeB), typeof(ShapeA)});
method.Invoke(b, a);

2. Populate the delegate cache

You can use dictionaries to store the delegates, or you can consider the following: you can create a class with the type parameters and a holder for the delegate.

Something similar to this:

public delegate IntersectResult IntersectAction<in T, in U>(T a, U b);

public static class Intersection<T, U>
{
    public static IntersectAction<T, U> Action {get; set;}
}

You will get complains because of the use of a static member with generic parameters. This is because each time you use this class with a different combination of type parameters you will be creating a new field with those parameters... and it will never be garbage collected.

Why is this better? Because it will take advantage of the CLR type resolution to find the right instance and at the same time it will make for cleaner code.

You will able to type something like this to store the delegate:

Intersection.Action = new IntersectAction<ShapeB, ShapeA>(MathCol.BIntersectsA)

---

To populate the Intersection<T, U>, I would suggest to do it during the application load. If you can't do that, consider a static constructor in a non-generic class, that will run only once (just note that if you don't interact with that class, it may not run).

In particular, you can do the following:

internal delegate IntersectResult IntersectAction<in T, in U>(T a, U b);

internal static class Intersection<T, U>
{
    public static IntersectAction<T, U> Action {get; set;}
}

public static class Intersection
{
    static Intersection()
    {
        // you can populate here, this code will run only once
    }
}

3. Invoke the delegate from the delegate cache

As for the interface to call the delegate consider that you may use operators in your classes. For example you may overload & for intersection, | could be union, etc... or you could have named Intersects method (static or not).

If you do something like that you will have a method for each combination of shapes distributed among the classes. You already have all those methods but they are in MathCol, you may move them or call them from there... of course that would be highly coupled.

So, we come to the current idea of using a delegate cache. Following the idea above, you can add this method to the non-generic Intersection class:

    public IntersectResult Invoke<in T, in U>(T a, U b)
    {
        var action = Intersection<T, U>.Action;
        if (action != null)
        {
            return action(a, b);
        }
        return new IntersectResult();
    }

The code above will allow you to write:

var result = Intersection.Invoke<ShapeA, ShapeB>(a, b);

We may include the flipped logic in there too:

    public IntersectResult Invoke<in T, in U>(T a, U b, out bool flipped)
    {
        flipped = false;
        var action = Intersection<T, U>.Action;
        if (action != null)
        {
            return action(a, b);
        }
        action = Intersection<U, T>.Action;
        if (action != null)
        {
            flipped = true;
            return action(b, a);
        }
        return new IntersectResult();
    }

Using this, you don't even need to expose an Intersects method in your shapes.

---

This is part of your example code:

ShapeA a = new ShapeA();
ShapeB b = new ShapeB();
bool flipped = false;

// These are called via .Intersects<T>(T shape, out bool flipped)
a.Intersects(a, out flipped); //calls AintersectsA, flipped: False
a.Intersects(b, out flipped); //calls BintersectsA, flipped: True
b.Intersects(a, out flipped); //calls BintersectsA, flipped: False
b.Intersects(b, out flipped); //calls BintersectsB, flipped: False

It would become:

ShapeA a = new ShapeA();
ShapeB b = new ShapeB();
bool flipped = false;

Intersection.Invoke(a, a, out flipped); //calls AintersectsA, flipped: False
Intersection.Invoke(a, b, out flipped); //calls BintersectsA, flipped: True
Intersection.Invoke(b, a, out flipped); //calls BintersectsA, flipped: False
Intersection.Invoke(b, b, out flipped); //calls BintersectsB, flipped: False

---

Type inheritance suggestion

1. Is this design appropriate for my requirement (having base shape that can intersect other shapes based on their subtype)?

Yes, this would work. I'd suggest having two levels of shape class inheritance. In particular if you have PolygonShape, CurveShape and BoxShape, and then your particular shapes (such as Circle, Triangle, etc...) can inherit form those.

The idea is that the first level will handle the different intersection algorithms you have (eg: segment shape to segment shape), while the lower level can be particular shapes (eg: star, triangle, etc...).

The simplest case would be of dealing with rectangles (BoxShape). You could use it for shapes made of single rectangle. You could consider generalizing it for shapes made of multiple rectangles, but PolygonShape should be able to deal with that too. The case of a single rectangle is worth to optimize, you'll see below why.

The second case would be describing shapes as a set of segments. These are the PolygonShape. Their intersection is relatively simple, and you can use the rectangle intersection for optimization (use the bounding box of the shape to check if they are close enough, and use the bounding box of the segments to check if they are close enough).

The third case would be describing curves, that is CurveShape. This can be done as a set of Bezier curves. To do work with these you can use the bounding box of the Bezier curves (you may have it pre-calculated), intercept the bounding boxes (simple rotated box interception) and if they do, you can use a Bezier interception algorithm.

Those should be enough for most cases (unless you need curves or higher order, or if you need fractals or anything else crazy like that). In this order of ideas, you won't need a large number of algorithms to deal with the different shapes. You may even consider to fallback to a simple switch statement instead of using a dictionary or the shenanigans I described above.

---

Generic typing concern

2. The double interface - is this considered bad design (since IShape's method accepts IShape<T> argument and IShape<T> is derived from IShape)? Note: i've also tried an alternative design where the IShape.Intersect<T> parameter was the abstract class Shape<T> but that didn't seem right as well.

3. I've had constraints where T : IShape on both the interface, abstract class Shape and IRdelegateCollection since i was trying to avoid the T Instance which is used in the Intersection() method, but the compiler still had problems converting Shape to T.

   • Is there a way to use the sahpes directly in the delegate invokation of the Shape.Intersects method? (preferably: del1v2(this, shape) - was throwing the above mentioned error, even with the constraints all over the place)

   • Should there be constraints of where T : IShape on all the Ts? (There does not appear to be any advantage to constraining it)

It is not technically wrong, although I have to point that the circular references (eg: ShapeA : Shape<ShapeA>) may not be handled well by old compilers and generally are not encoraged.

I'd suggest to get rid of IShape<T> and instead use Shape as base. I'm unsure if you can get rid of the generic constraint.