C++ – Intersection of Geometric Entities

I was trying to design a small C++ geometric API for learning purposes, but came across a problem when dealing with intersections of geometric entities. For example, the intersection of a line and a sphere can have three different types: a couple of points, a point or nothing at all. I found several ways to deal with this problem, but I don't know which of them seems to be the best:

CGAL Object return type

I first tried to see what was done in other geometric libraries. The most complete I can found was CGAL. In CGAL, intersection functions return an Object which is a generic type that can hold anything (like boost::any). Then, you try to assign the Object to a value of another type, here is an example:

void foo(CGAL::Segment_2<Kernel> seg, CGAL::Line_2<Kernel> line)
{
    CGAL::Object result;
    CGAL::Point_2<Kernel> ipoint;
    CGAL::Segment_2<Kernel> iseg;

    result = CGAL::intersection(seg, line);
    if (CGAL::assign(ipoint, result)) {

        // handle the point intersection case.

    } else if (CGAL::assign(iseg, result)) {

        // handle the segment intersection case.

    } else {

       // handle the no intersection case.
    }
}

By the way, the assign function uses dynamic_cast to check whether the two variables are assignable (everybody loves RTTI).

Union return type

A union can also be used as a return type, but it means using an id for every geometric type and having some kind of variant type to cover all the problems.

struct Variant
{
    int id;
    union
    {
        Point point;
        std::pair<Point, Point> pair;
    };
};

int main()
{
    Point point;
    std::pair<Point, Point> pair;

    Variant v = intersection(Line{}, Sphere{});
    if (v.id == ID_POINT)
    {
        point = v.point;
        // Do something with point
    }
    else if (v.id == ID_VARIANT)
    {
        pair = v.pair;
        // Do something with pair
    }
    else
    {
        // No intersection
    }
}

Avoiding the "no intersection" problem

In order to split the "no intersection" case from the main problem, some libraries used to require the user to check whether there was an intersection before trying to find what was the intersection return type. It looked like this:

Line line;
Sphere sphere;

if (intersects(line, sphere))
{
    auto ret = intersection(line, sphere);
    // Do something with ret
}

Another way to split the "no intersection" case from the rest of the problem would be to use an optional type:

std::optional<...> ret = intersection(Line{}, Sphere{});
if (ret)
{
    // Do something with ret
}

Using exceptions to control the "return" type

I can already see some of you crying.

Yet another way to handle that problem of having different return types would be to throw the results instead of returning them. The "no intersection" return could still use one of the techniques from the previous paragraph:

try
{
    intersection(Line{}, Sphere{});
}
catch (const Point& point)
{
    // Do something with point
}
catch (const std::pair<Point, Point>& pair)
{
    // Do something with pair
}
// Can still catch errors (or "no intersection" special type?)

Having a "main" return type, throwing the other ones

Another way would be to have a "main" return type for the intersection, let's say std::pair<Point, Point> and considering the other return types as "exceptional"; it gives more meaning to the use of exceptions while this is still not quite an error gestion. On the other hand, it could seem strange to handle a "main" type differently than the others…

try
{
    auto pair = intersection(Line{}, Sphere{});
    // Do something with pair
}
catch (const Point& point)
{
    // The chances for a sphere and a line to meet at
    // a single point are so small that the case can
    // already be considered exceptional.
    // ...
}

I purposedly left the errors gestion and the "no intersection" case out of this last example since many techniques already described could be used to handle it and I don't want the number of examples to be exponential. Here is one though:

try
{
    // res is optional<pair<Point, Point>>
    if (auto res = intersection(Line{}, Sphere{}))
    {
        std::cout << "intersection: two points" << '\n'
                  << std::get<0>(*res).x() << " "
                  << std::get<0>(*res).y() << '\n'
                  << std::get<1>(*res).x() << " "
                  << std::get<1>(*res).y() << '\n';
    }
    else
    {
        std::cout << "no intersection" << '\n';
    }
}
catch (const Point& point)
{
    // Exceptional case
    std::cout << "intersection: one point" << '\n'
              << point.x() << " "
              << point.y() << '\n';
}

Since the cases where the result is thrown are exceptional, it should not add any runtime overhead to the program if the underlying system uses zero cost exceptions instead of the old SJLJ exceptions system.

The actual question

Well, that was a pretty long introduction, so here is the question: is there an idiomatic solution to the problem in these examples? And if not, are there at least some of the examples which could be banned without a second thought (well, you could give a second thought to the exception examples though…)?

Note: something seemed evident to me but apparently is not: the entity returned by intersection between two geometric entities is not limited to a nothing, a point or a set of point. An intersection can pretty much return any geometric entity. Therefore, using a container to hold the values does not sound like a good idea.

Note 2: time machine note, it happens. After having given it some thought, I would ban exceptions (as most people would do), not because exceptions are inherently bad or not designed for this, but because it makes the expression intersection(...) == SomeShape throw an exception even when the both operands should be equal, which isn't elegant. I guess that I would use a bastard child of a variant instead.