Union, Tangencies and Colors

I like the picture below very much.

What you see here are, more or less, pink, green and blue. The colors are chosen as such that they always form distinct colors, regardless of how you combine them. There are of course other combinations with these properties, but... this is at least one of them.

When the pink layer is slightly moved to the right, you see better how the image is constructed:

The pink (transparent) layer is the union of the two underlying (multi-)polygons, the green one and the blue one. It has one hole, one kind of indentation and for the rest it is square. The underlying multi-polygons are better seen if the pink one is removed:

So this is clear: there are two multi-polygons here, complete with holes and self-tangencies. These multi-polygons have overlap in some places, no overlap in other places. They nearly fill the area, there are only three "boxes" free. The blue and green colors nicely mix into blue-green. The colors and transparencies are selected for that. SVG definitions are:

Green: style="fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:3"

Blue: style="fill-opacity:0.3;fill:rgb(51,51,153);stroke:rgb(51,51,153);stroke-width:3"

I like this combination.

And with the pink style on top of it...

Pink: style="fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);stroke:rgb(255,0,255);stroke-width:8"

...all colors change, however, they are still clearly distinct. Yellow-orange like for green+pink; lila for blue+pink; and brown for the blue+green+pink. So we have seven unique distinct colors now, which happens to be the ideal number of colors for a map.

By the way, this image is created using Boost.Geometry. Boost.Geometry can easily create SVG images. And Boost.Geometry can overlay multi-polygons (already possible for a long time) having all kinds of self-tangencies (new!). A self-tangency in a multi-polygon is a place where two polygon-members touch each other (orange dots in the map below), or where a polygon touches itself (the red dot in the map).

Actually... this could also be a polygon, having five interior rings (holes) which might be mutually tangent and tangent to they exterior ring.

OK, one more image...

Tag Dispatching and Inheritance

In the previous blog we described Tag Dispatching by Type.

Though very convenient, when many classes (tagged by as many tags) share the same implementation, we get as many dispatch structs with the same implementation (or, better, forwarding to the same struct). This can be avoided by using similarities between classes, or between tags. In Boost.Geometry, for example, some geometries are single while others are multi. That multi-ness can be recognized by the metafunction is_multi which results in true for a multi-polygon and in false for a single polygon. We can include an IsMulti boolean template parameter in the dispatch structure, so that it is selected not only on tag dispatching, but also in is_multi.

This similarity can also be implemented using a tag hierarchy and inheritance.

Let's go back to the fruit example. All citrus fruit species have pulp vesicles. There are many citrus fruits species. And, of course, we don't want to repeat the dispatch structure has_vesicles so many times. So we try to define our tag hierarchy:

struct citrus_tag {};
struct pome_tag {};

struct apple_tag : pome_tag {};
struct pear_tag : pome_tag {};

struct banana_tag {};

struct orange_tag : citrus_tag {};
struct lemon_tag : citrus_tag {};
struct lime_tag : citrus_tag {};

And then we couple the tags, like we did in previous blog:

template <typename T> struct tag {};
template <> struct tag<apple> { typedef apple_tag type; };
template <> struct tag<pear> { typedef pear_tag type; };
template <> struct tag<orange> { typedef orange_tag type; };
template <> struct tag<lime> { typedef lime_tag type; };
template <> struct tag<banana> { typedef banana_tag type; };

The new thing, besides the inheritance in the tags above, is that we now define a tag_cast metafunction:

template
<
    typename Tag, typename BaseTag,
    typename BT2 = void, typename BT3 = void, typename BT4 = void,
    typename BT5 = void, typename BT6 = void, typename BT7 = void
>
struct tag_cast
{
    typedef typename boost::mpl::if_
        <
          typename boost::is_base_of<BaseTag, Tag>::type,
          BaseTag,
          // Try next one in line:
          typename tag_cast<Tag, BT2, BT3, BT4, BT5, BT6, BT7, void>::type
        >::type type;
};

template <typename Tag>
struct tag_cast<Tag, void, void, void, void, void, void, void>
{
    // If not found, take specified tag, so do not cast
    typedef Tag type;
};

We can now check if a tag is a citrus tag, by calling defining a new tag as tag_cast<tag, citrus_tag>::type. This new tag is either a citrus tag, or it is the tag it already was.

And we can dispatch by this tag as well. So it looks like:

namespace dispatch
{
    template <typename T> struct has_vesicles : boost::false_type {};
    template <> struct has_vesicles<citrus_tag> : boost::true_type {};
}

template <typename Fruit>
std::string has_vesicles(Fruit const& fruit)
{
    // (Potentially) go up in hierachy: take tag corresponding to Fruit,
    // downcast to citrus_tag if possible
    typedef typename tag_cast<typename tag<Fruit>::type, citrus_tag>::type tag;

    return std::string("has vesicles: ")
        + (dispatch::has_vesicles<tag>::value ? "true" : "false");
}

This tag_cast, as proposed above, can not only cast to one base-class, but also to a range of base-classes. The definition

 typedef typename tag_cast<typename tag<Fruit>::type, citrus_tag, pome_tag>::type tag;

will result in a citrus_tag if it is a citrus, a pome_tag if it is a pome, and otherwise it results in the input tag. Besides this, it also walks through a tag hierarchy, so if citrus_tag and pome_tag were both derived from, e.g., a rosid_tag, and rosid_tag was specified in this call, it would result in a rosid_tag.

The sample program here shows two base classes, not listed here.

Our main program now displays correctly if the specific fruits have vesicles or not

int main()
{
    using namespace fruit;

    apple a("my apple");
    pear p("my pear");
    orange o("my orange");

    std::cout << has_vesicles(a) << std::endl;
    std::cout << has_vesicles(p) << std::endl;
    std::cout << has_vesicles(o) << std::endl;

    return 0;
}

Back to Boost.Geometry. Until now it is not done, but we might depricate the is_multi meta-function and replace it by this:

struct multi_tag;
struct multi_point_tag : multi_tag {};
struct multi_linestring_tag : multi_tag {};
struct multi_polygon_tag : multi_tag {};

And instead of calling is_multi, we call tag_cast<tag, multi_tag>. We then know if it is a multi and can dispatch on it. The same for linear. This will probably be very convenient, it has to be worked out a little more.


Casting and (multiple) inheritance
The tag_cast as implemented above casts to specified tags. We can not just call the parent-tag. One of the reasons for this is multiple inheritance.
Tag inheritance can be multiple. This is convenient because, of course, there can be different tag classifications for the same set of tags. For example: if a geometry contains segments, or is linear, or is areal. So we might get:

struct multi_tag;
struct multi_point_tag : multi_tag {};
struct multi_linestring_tag : multi_tag, linear_tag {};
struct multi_polygon_tag : multi_tag, areal_tag {};

When calling tag_cast, the results depends on the order of the specified base tags. And so does the dispatching.

Tag Dispatching by Type

Tag Dispatching (TD) is a Generic Programming (GP) technique for C++. It is well explained in this blog. Google Hit Number one (GH#1) is this site, where the example of the STL function advance is given. Tag Dispatching is not described a lot; GH#7 is from ggl (= Boost.Geometry), as is GH#8..

Nearly all TD descriptions I know of use the example of STL-advance. But in Boost.Geometry TD is done in another way: not by instance, but by type. The difference is explained in this blog.

Suppose you make a generic program doing something with fruit. An apple is normally being eaten differently than a banana or an orange. So if we program a generic function eat, giving it any type of fruit, it should redirect this to an implementation specific to that kind of fruit, so for apple differently than for a banana.

We first implement the tags. Tags are completely empty structures. But (of course) not completely useless.

struct apple_tag {};
struct banana_tag {};
struct orange_tag {};

We then create some sample implementations. Most properties are not used, it is just to show there are (sometimes completely) different classes which can be handled genericly.

struct apple
{
    double radius;

    std::string name;
    apple(std::string const& n) : name(n) {}
};

struct banana
{
    double length;

    std::string name;
    banana(std::string const& n) : name(n) {}
};

All this is quite simple C++ code, though you have to understand templates (generics) and specialization.

OK, now we implement Tag Dispatching by Instance:

namespace dispatch
{
    void eat(apple const& a, apple_tag)
    {
        std::cout << "bite" << std::endl;
    }

    void eat(banana const& b, banana_tag)
    {
        std::cout << "peel" << std::endl;
    }
}

template <typename T>
void eat(T const& fruit)
{
    typename tag<T>::type the_tag;
    dispatch::eat(fruit, the_tag);
}

The function eat at the bottom first declares an instance of the tag. If an apple is entered in this function, it will be an instance of the apple_tag. If a banana is entered, it is a banana_tag. Then it forwards its call to the eat function in the namespace dispatch. There are two versions (overloads) there, one specified with an apple_tag, one with a banana_tag. The compiler selects, based on the tag the right function. Quite easy, and quite powerful, this tag dispatching system.

As said, within Boost.Geometry it is not applied like this. One of the reasons is that the instance of the tag is not necessary at all. If the dispatch::eat function would be implemented within a struct, as a static method, the tag dispatching can be done by type and not by instance. This is still tag dispatching!

So the piece above can be replaced by this Tag Dispatching by Type:

namespace dispatch
{
    template <typename Tag> struct eat {};

    template <> struct eat<apple_tag>
    {
        static void apply(apple const& a)
        {
          std::cout << "bite" << std::endl;
        }
    };

    template <> struct eat<banana_tag>
    {
        static void apply(banana const& b)
        {
          std::cout << "peel" << std::endl;
        }
    };
}

template <typename T>
void eat(T const& fruit)
{
    dispatch::eat<typename tag<T>::type>::apply(fruit);
}

So no instance at all, type only. Boost.Geometry has this structure everywhere, and all static dispatching methods are called apply.

For completeness we list the main program as well here:

int main()
{
    apple a("my apple");
    banana b("my banana");
    eat(a);
    eat(b);

    return 0;
}

It is the same for the instance-version and the type-version.

More advantages of the Tag Dispatching by Type approach are that arguments can be reversed, so you can call distance(point, polygon) and distance(polygon, point) but there is only one implementation with point_tag, polygon_tag necessary. With instances (and function overloads) this is not possible, or at least not that easy. Furthermore, tag dispatching by type can be used to define types, or define constants, as well. Suppose you need to define a constant value dependant on a type. We approach geometry now and want to define if a specific fruit-type is spherical or not. So we define this structure, specialized by tag:

    template <typename Tag> struct spherical {};

    template <> struct spherical<apple_tag>
    {
        static const bool value = true;
    };

    template <> struct spherical<banana_tag>
    {
        static const bool value = false;
    };

We can create a generic structure, which calls this dispatch, just like the free function eat, but now with a struct (or meta-function):

template <typename T>
struct spherical
{
    static const bool value = dispatch::spherical<typename tag<T>::type>::value;
};

Next blog will handle Tag Dispatching and Inheritance.