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.

Since you are working on a geometric API, I guess you are not only
interested in intersection of lines and spheres, but have also more
exciting projects.

A natural approach to solve your problem of representing values for
intersection would be to define a type for geometric figures so that
you can represent:

Points
Lines
Spheres
Intersections that you cannot compute (kind of symbolic intersection)
Union of figures

Once you have done that, your intersection algorithm can gobble two
figures and return a figure, computed by using

(A + B + …).(C + D + …) = A.C + A.D + B.C + B.D + …

where I denote the union by + and the intersection by . and where
A, B, C, D and the dots can be a point, a sphere, a line or an
intersection you cannot compute.

To some extent, this approach gives satisfying results and may give
the feeling that it is the right solution to the problem.

There are however a lot of problems with this approach, that you
should be aware of:

Intersection that you cannot compute tend to absorb everything,
i.e. intersecting anything with an intersection that you cannot can
yield an intersection that you cannot compute.
If you intersect two spheres, it yields a circle, that you cannot
compute, not because you cannot find which circle it is, but
because you cannot represent circles. If you choose to add circles
to your vocabulary, you have to figure out how to compute
intersections with all other figures you may have. So if you have
n base figures you should deal with n^2 type of
intersections. So, choosing a rich vocabulary of figures without
relying on “intersections you cannot compute” is not an option.
Even if you restrict yourself to the rassuring realm of algebraic
figures (defined by polynomial equations), computing intersections
is far from trivial. What you are trying to do is to compute a
minimal set of generators of the reduced ideal defined by your
intersection, so do not expect to be able to do this on more than a
few examples. You should regard anything you are able to compute as
a lucky accident.

the solutions that I would use or have seen used are:

use a container to return intersection points

more expandable for other geometric entities that may have more intersections but has more overhead
return invalid points when no intersection

you need have a concept of validness for the data type, or have an optional type
use a callback function that gets called each time an intersection is found

this one allows for specific processing without needing to collect all points

the ones I would BAN out of hand are the ones using exceptions, exception handling is slow and many people with crucify you for doing this

You have listed many valid alternatives, however the straightforward one is missing:

Just return the count of intersections, and return the points via an array argument. The array argument, of course, has a size to fit the maximum count of intersections. Something like this:

size_t getIntersections(const Sphere& sphere, const Ray& ray, std::array<Point, 2>* intersections);

This is just as safe or unsafe as the union approach or the one that returns illegal points. However, it has one clear advantage: You do not force user code to differentiate between the three cases. I. e., instead of having an if-else ladder along the lines

auto result = intersections(...);
if(/*no intersection*/) {
    ...
} else if(/*one intersection*/) {
    ...
} else /*two intersections*/ {
    ...
}

the calling site may choose to say

arrays<Point, 2> points;
for(size_t i = getIntersections(..., &points); i--; ) {
    /*code to handle points[i]*/
}

That is not possible if the count of intersections is somehow encoded in the return type of the function.

And, yes, I would also discard anything with exceptions without a second thought. They are brutally slow unless they are optimized away. And for optimization you would need to disclose the intersection calculating code to the calling site.

Filed under: softwareengineering - @ 18:15

Thẻ: c++, c++11, geometry, idioms, return-type

Thiết kế website giá rẻ

Danh mục

Intersection of geometric entities

CGAL `Object` return type

Union return type

Avoiding the “no intersection” problem

Using exceptions to control the “return” type

Having a “main” return type, throwing the other ones

The actual question

Danh mục

CGAL Object return type

Union return type

Avoiding the “no intersection” problem

Using exceptions to control the “return” type

Having a “main” return type, throwing the other ones

The actual question

CGAL `Object` return type