C# Generic Math: A Convex Hull with Static Interfaces
Static abstract interface members let a C# algorithm depend on operations instead of concrete numeric types. A convex-hull implementation is a good stress test: its coordinate type must support comparison, addition, negation, and multiplication, but the algorithm should not care whether those operations come from int, double, or a domain-specific number.
This article connects algebraic rings to the Graham scan convex-hull algorithm and shows how C# 11 expresses the required capabilities through Generic Math contracts.
Algebraic Rings and C# Generic Math
My previous articles on this topic came out almost a year ago. They included some experiments in designing algebraic structures, but I will not reuse those designs here because a lot has changed since then.
In particular, C# 11 introduced a rather interesting language feature: static abstract interface members. You can read more about static abstract members in interfaces here.
As a reminder, a ring is a structure that forms an Abelian group under addition and a monoid under multiplication. Multiplication must also be distributive over addition.
Previously, the algebraic structure itself had to be modeled as a separate type. Now we can instead say that the structure can be defined over the type itself. I will demonstrate this with a ring, leaving its relationship to other structures aside.
Before:
public interface IRing<T>
{
T Plus(T left, T right);
T Zero { get; }
T Inverse(T item);
T Times(T left, T right);
T One { get; }
}
After:
public interface IRing<T>
where T : IRing<T>
{
static abstract T operator +(T x, T y);
static abstract T Zero { get; }
static abstract T operator -(T x);
static abstract T operator *(T x, T y);
static abstract T One { get; }
}
The abstraction over the operations is now part of the type definition instead of living in a separate data structure. The next question is how to use these constructs.
If you are creating a custom data type, nothing stops you from implementing IRing<T> and calling it a day. That trick does not work with system types such as int and double, however.
The .NET team anticipated this problem so thoroughly that the standard library now contains contracts describing the very same algebraic structures I am writing about for the third time.
To see this for ourselves, let us look inside the source code for int.
The Int32 struct now implements many new interfaces. Among them is the generic ISignedNumber<T> interface, which extends INumberBase<T>. This contract describes the abstraction of a number and assembles the properties we already know through interfaces such as IAdditionOperators<T, T, T>, IAdditiveIdentity<T, T>, IMultiplicativeIdentity<T, T>, and others.
Each of these types represents one atomic abstract property belonging to some algebraic structure. You can find all of them in the System.Numerics namespace.
For compatibility with the C# standard library, we can therefore describe a ring as follows:
public interface IRing<T> :
IAdditionOperators<T, T, T>,
IAdditiveIdentity<T, T>,
IUnaryNegationOperators<T, T>,
IMultiplyOperators<T, T, T>,
IMultiplicativeIdentity<T, T>
where T :
IAdditionOperators<T, T, T>,
IAdditiveIdentity<T, T>,
IUnaryNegationOperators<T, T>,
IMultiplyOperators<T, T, T>,
IMultiplicativeIdentity<T, T>
{
}
This lets us create custom data types that support ring operations while also using system types that already provide those operations. There is one catch, though: when designing consumers of those types, we cannot use our interface as a generic constraint.
That is because C# has no intersection types.
Implementing IRing<T> implies implementing a collection of other interfaces, but implementing each of those interfaces separately is not considered equivalent. This subject has even been discussed in a proposal thread in the dotnet/csharplang repository.
For example, let us rewrite the endomorphism ring from one of the previous articles. The new implementation represents an endomorphism itself as a wrapper around Func<T, T>. For the reason described above, however, the constraint that these mappings can exist only over Abelian groups is not especially concise.
public class Endomorphism<TGroup> : IRing<Endomorphism<TGroup>>
where TGroup :
IAdditionOperators<TGroup, TGroup, TGroup>,
IAdditiveIdentity<TGroup, TGroup>,
IUnaryNegationOperators<TGroup, TGroup>
{
private readonly Func<TGroup, TGroup> _func;
private Endomorphism(Func<TGroup, TGroup> func) =>
_func = func;
public TGroup At(TGroup x) =>
_func(x);
public static implicit operator Endomorphism<TGroup>(Func<TGroup, TGroup> func) =>
new(func);
public static Endomorphism<TGroup> operator +(Endomorphism<TGroup> left, Endomorphism<TGroup> right) =>
(Func<TGroup, TGroup>)(x => left.At(x) + right.At(x));
public static Endomorphism<TGroup> AdditiveIdentity =>
(Func<TGroup, TGroup>)(_ => TGroup.AdditiveIdentity);
public static Endomorphism<TGroup> operator -(Endomorphism<TGroup> value) =>
(Func<TGroup, TGroup>)(x => -value.At(x));
public static Endomorphism<TGroup> operator *(Endomorphism<TGroup> left, Endomorphism<TGroup> right) =>
(Func<TGroup, TGroup>)(x => left.At(right.At(x)));
public static Endomorphism<TGroup> MultiplicativeIdentity =>
(Func<TGroup, TGroup>)(x => x);
}
Implementing Graham Scan with Generic Math
Continuing with the idea of generalizing algorithms through algebraic structures—rings in particular—I want to focus on constructing a convex hull. Wikipedia offers a good explanation, including the familiar board, nails, and rubber-band analogy.
The black outline is the board and the points are nails. The blue line is the rubber band—our convex hull.
There are many algorithms for constructing a convex hull. We will look at one of the most popular, Graham scan, because it is relatively efficient while remaining straightforward to implement.
The implementation needs to determine the turn formed by three points and sort points on a plane by increasing polar angle. Put it all together, and we get something like this:
public record Point2D(int X, int Y)
{
public static Point2D operator -(Point2D p1, Point2D p2) =>
new(p1.X - p2.X, p1.Y - p2.Y);
public static int operator *(Point2D p1, Point2D p2) =>
p1.X * p2.X + p1.Y * p2.Y;
public static int operator ^(Point2D p1, Point2D p2) =>
p1.X * p2.Y - p1.Y * p2.X;
}
public enum Turn : byte
{
ClockWise,
Collinear,
CounterClockWise
}
public class TurnCalculator : ITurnCalculator
{
public Turn GetTurn(Point2D p1, Point2D p2, Point2D p3)
{
var crossProduct =
(p2.X - p1.X) * (p3.Y - p1.Y) -
(p2.Y - p1.Y) * (p3.X - p1.X);
return crossProduct switch
{
< 0 => Turn.ClockWise,
> 0 => Turn.CounterClockWise,
_ => Turn.Collinear
};
}
}
public class GrahamScan : IConvexHullFinder
{
private readonly ITurnCalculator _calculator;
public GrahamScan(ITurnCalculator calculator) =>
_calculator = calculator;
public IEnumerable<Point2D>? GetConvexHull(IList<Point2D>? points)
{
if (points is null or { Count: < 3 })
return null;
var p0 = points.OrderBy(p => p.X).ThenBy(p => p.Y).First();
points = points.OrderBy(p => p, new PolarOrderComparer(p0)).ToList();
var hull = new Stack<Point2D>();
hull.Push(points[0]);
hull.Push(points[1]);
hull.Push(points[2]);
for (var i = 3; i < points.Count; i++)
{
while (_calculator.GetTurn(hull.NextToTop(), hull.Peek(), points[i]) != Turn.CounterClockWise)
hull.Pop();
hull.Push(points[i]);
}
return hull;
}
}
The implementation begins by finding the leftmost and lowest point in the set. It then sorts the remaining points by increasing polar angle, measured between the X-axis and a vector originating at the lowest point. This sorting step guarantees that the algorithm visits each point counterclockwise.
Next, it initializes a stack with the first three points to hold the hull. The algorithm walks through the remaining points counterclockwise, adding each to the hull and removing any points that violate the polygon's convexity.
At the heart of the algorithm is the while loop. It keeps removing points from the hull until the current point makes a counterclockwise turn with the last two points already in the hull.
For example, given the following set of points:
IConvexHullFinder.Instance.GetConvexHull(new List<Point2D>
{
new(0, 3),
new(1, 1),
new(2, 2),
new(4, 4),
new(0, 0),
new(1, 2),
new(3, 1),
new(3, 3)
})?.ToList().ForEach(Console.WriteLine);
We get the hull formed by the points below:
Point2D { X = 0, Y = 3 }
Point2D { X = 4, Y = 4 }
Point2D { X = 3, Y = 1 }
Point2D { X = 0, Y = 0 }
A graphical representation of the result
Look closely at the implementation and you will notice that we can define a ring over the point coordinates. The cross product used to determine the turn direction indeed relies on every property of this algebraic structure. We also need to require the coordinate type to implement IComparable<T>. The modified point class looks like this:
public record Point2D<TRing>(TRing X, TRing Y)
where TRing :
IComparable<TRing>,
IAdditionOperators<TRing, TRing, TRing>,
IAdditiveIdentity<TRing, TRing>,
IUnaryNegationOperators<TRing, TRing>,
IMultiplyOperators<TRing, TRing, TRing>,
IMultiplicativeIdentity<TRing, TRing>
{
public static Point2D<TRing> operator -(Point2D<TRing> p1, Point2D<TRing> p2) =>
new(p1.X + -p2.X, p1.Y + -p2.Y);
public static TRing operator *(Point2D<TRing> p1, Point2D<TRing> p2) =>
p1.X * p2.X + p1.Y * p2.Y;
public static TRing operator ^(Point2D<TRing> p1, Point2D<TRing> p2) =>
p1.X * p2.Y + -(p1.Y * p2.X);
}
The same generic constraints then need to be propagated to the corresponding methods, replacing 0 with TRing.AdditiveIdentity. Subtraction can likewise be replaced with a combination of addition and unary negation, or you can use the ISubtractionOperators<T, T, T> contract.
When Generic Math Improves an Algorithm
The convex-hull algorithm no longer depends on a specific coordinate type. Convex hulls also appear beyond computational geometry, including finance, machine learning, and text analysis.
For example, define an operation that tests whether a point lies inside the hull, and you already have a basic classifier.
The broader lesson is not that every algorithm needs a ring abstraction. Generic constraints are valuable when they state the minimum operations an algorithm genuinely requires and when multiple useful types can satisfy that contract. Otherwise, a concrete numeric type will be easier to read and maintain.
The source code used in this article is available on GitHub: github.com/StefanioHabrArticles/generalize-this-and-that.
Continue with StepOne C# Content
Follow StepOne on GitHub for open-source C#/.NET projects, compiler experiments, production-focused examples, and new releases.
