How to define a method that makes assumptions about object state?

Question

In our geometry library, we have a Polygon class, containing (amongst many others, of course) a method which checks if this polygon contains another polygon:

public bool Contains(Polygon other) {
    //complex containment checking code goes here
}

Other important things to note are that the polygon is mutable, and that there is no way to be notified of when its shape changes.

Now, in one of our projects, we have a validation function, which checks for a huge number of polygons whether they are all contained within a single outer boundary.

Polygon boundary = ...;
foreach (var poly in _myMassiveListOfPolygons)
    if (!boundary.Contains(poly))
        //error handling code goes here

Profiling has determined this to be quite a bottleneck. Fortunately there is a way to vastly speed up the calculation. We know that the boundary polygon is always convex, so instead of using the general Contains method, we can write a specialized method that assumes the outer polygon is convex.

Initially I added something like this to the client code:

Func<Polygon, bool> containsFunc;
// Keep both options, in case my assumption about being always convex is wrong
if (boundary.IsConvex())
{
    containsFunc = p => { ... }; //efficient code for convex boundary goes here
}
else
{
    containsFunc = p => boundary.Contains(p);
}
foreach (var poly in _myMassiveListOfPolygons)
    if (!containsFunc(poly))
        //error handling code goes here

Joy all around! Performance has increased tenfold!

However, it doesn't seem right that the code for this alternative Contains method is located in the client project, where it can't be reused by others.

So I tried to move it to the Polygon class itself.

public bool Contains(Polygon other) {
    if (this.IsConvex())
        return ConvexContains(other);
    else
        return GenericContains(other);
}
private bool GenericContains(Polygon other) { ...}
private bool ConvexContains(Polygon other) { ...} 

With this method, the client code returns back to the original. Unfortunately, there is one big difference compared to the previous code: Before there was one call to boundary.IsConvex() to select the correct function to use, where now this method is called for every invocation of Contains! Although this is still faster than using the generic Contains method, most of the performance improvements are lost again (not to mention performance decreases for concave polygons).

A third possibility would be to have two public methods to check containment, where one of them assumes that the polygon is convex (without doing the check itself, of course, otherwise we're back to the previous overhead problem). This doesn't seem like a good idea, since calling it by accident with a concave polygon could give unexpected results, making for hard to find bugs.

So finally, my question is, is there any good way to deal with this situation? Where should we put the alternative Contains method, and how should we call it?

Edit

I like the idea of caching whether or not a polygon is convex. But I cannot change the interface nor the behavior of the class, which is problematic in a case such as this:

//relevant part of the polygon interface
public List<Point> Points { get; set; }


//client code
var poly = new Polygon();
var list = new List<Point> 
{
    new Point(0,0),
    new Point(10,0),
    new Point(0,10)
};
poly.Points = list;
list.Add(new Point(1, 1));

This last line of code is executed on a regular List<Point>, there is nothing I can do about that. However, there would now be 2 requirements:

1. The polygon must now contain the added point. This is to ensure existing code doesn't break. This means that we cannot copy the Points into our own, observable list.
2. We must get notified of this change to the list of points (because our polygon has turned from convex to concave). This means that we cannot wrap the list by our own, observable list, because only changes made through the wrapper would cause a notification.

Answer 1

Okay...you guys really shot yourselves in the foot by using List in your public interface. Here is how you can try to solve it (there is a small non-zero chance that this will incorrectly cache, but its a 1 in (1 <<32 ) chance.

As you have noted, we could cache the polygon's Convexness...but the problem then becomes a case of Cache invalidation.

Without being able invalid cache on object change. You would have to check for cache coherence on each call. This is where hashing comes in.

By default the hash for list is quite useless, you want to use a this solution for getting a usable hash.

So what you want to do is to add a nullable<int> _cachedHashCode on your polygon. When you call Polygon.IsConvex, you hash your List<Point>, compare with your _cachedHashCode, and if they don't equal, recompute your IsConvex.

Answer 2

One option is to create another concept in the geometry library, say FixedBoundary, which could encapsulate that logic. It would be immutable so that you could safely cache the convexity. An example:

public class FixedBoundary
{
    private Polygon boundary;
    private bool isConvex;

    public FixedBoundary(Polygon boundary)
    {
        // deep clone so we don't have to worry about the boundary being modified later.
        this.boundary = boundary.Clone(); 
        this.isConvex = this.boundary.IsConvex();
    }

    public bool Contains(Polygon p)
    {
        if (isConvex)
        {
            // efficient convex logic here
        }
        else   
        {
            return this.boundary.Contains(p);
        }
    }
}

This of course adds some conceptual weight to the geometry library. Another option would be to add an ImmutablePolygon (and by extension ImmutablePoint) which could do the same, however conversions may be cumbersome and affect performance as well.

Answer 3

You could replicate what you've done already with the Func<T, bool> delegate.. internal to the Polygon.. perhaps like this?

private Func<Polygon, bool> _containsFunc;

// ...

public bool Contains(Polygon other) {
    if (_containsFunc == null) {
       if (this.IsConvex())
           _containsFunc = ConvexContains;
        else
            _containsFunc = GenericContains;
    }

    return _containsFunc(other);
}

Each call to Contains after the first will not call IsConvex. Unless I have misunderstood you.. that sounds like what you're after.