covered_by not implemented for (Box, MultiPolygon)

[vschoech]

Any chance this gets implemented any time soon? See our conversation here: https://lists.boost.org/geometry/2012/02/1838.php

[barendgehrels]

Right, thanks for the reminder, that is a long time ago indeed. From my side I still have to postpone this until rescaling removal is finished. But thanks for opening the issue, it has a greater visibility than the mailing list.

[digu-007]

covered_by is implemented for (Polygon, Multipolygon), can't we just make use of this and convert Box into the rectangle (which is a Polygon) out of the given two corners of Box, and then solve this query for (Box, MultiPolygon).

If that's the case I would like to contribute towards the issue. :)

[vissarion]

covered_by is implemented for (Polygon, Multipolygon), can't we just make use of this and convert Box into the rectangle (which is a Polygon) out of the given two corners of Box, and then solve this query for (Box, MultiPolygon).

Box is a Polygon only in cartesian for other coordinate systems it cannot represented as a polygon since polygon's segments are geodesics (e.g. great circles for spherical) but box's segments are not.

[digu-007]

Box is a Polygon only in cartesian for other coordinate systems it cannot represented as a polygon since polygon's segments are geodesics (e.g. great circles for spherical) but box's segments are not.

Oh ok, I just now realized that we have four different kinds of coordinate systems here, I'll study them.

[vschoech]

Still missing implementations for covered_by in boost 1.72.0.

[vschoech]

Still missing implementations for covered_by in boost 1.73.0.

[vschoech]

Still missing implementations for covered_by in boost 1.75.0.

[awulkiew]

@vschoech out of curiosity, why do you need this combination for? Wouldn't checking

covered_by(box, return_envelope<Box>(multi_polygon));

be enough?

[vschoech]

@awulkiew

covered_by(box, return_envelope<Box>(multi_polygon));

I don't think so, unless I'm missing something. In case of a non-convex polygon, as illustrated on the bottom of this man page, there are a lot of boxes that are covered by the envelope, but not covered by the polygon. The same for a multi-polygon with at least two disjunct polygons.

Note the definition of covered_by(geometry1, geometry2): The free function covered_by checks if the first geometry is inside or on border the second geometry.

Does this make sense? Otherwise, please explain in more detail.

[awulkiew]

@vschoech Sorry, may bad. I confused the covered with the covering geometry. Yes, I can see that this may be useful in particular with relatively big concave polygons.

In general I tend to think that there is no need to mix bounding geometries with geometries which they represent. That relational operations should be done for Boxes vs Boxes and then corresponding geometries should be processed. It's because the space partitioning/indexing is designed around trivial geometries. But if you work on Boxes specifically and they do not correspond to any other geometry this is a different story I guess. How it is in your case?

I can imagine that for a specific case one could design a specific algorithm that would be more efficient than e.g. simply calling covered_by for each Box and a MultiPolygon.

[vschoech]

@awulkiew Thank you for the clarification. In my case I have text labels that are approximated by boxes, and that I need to clip against the polygon shape of an area chart (basically a line chart with color between the lines):

[awulkiew]

@vschoech Ok, got it.

Note that technically this is not a use case for covered_by(box, multi_polygon) since what you really need is to check on which side of a linestring a box is. It's more complex if points can be duplicated, lines going backwards, spikes, etc. But in the most simple case this could be checked by calling side strategy for each segment of a linestring and for each point of a box, e.g. something like this:

    box b{ {0, 0}, {1, 1} };
    linestring ls{ {0, 2}, {1, 3}, {2, 4} };
    point points[4];
    bg::detail::assign_box_corners_oriented<false>(b, points);
    bool result = bg::all_segments_of(ls, [&](auto const& s)
    {
        for (int i = 0; i < 4; ++i)
        {
            // assuming points are sorted by x (so linestring going left to right)
            if (bg::get<0>(s.first) <= bg::get<bg::max_corner, 0>(b)
                && bg::get<0>(s.second) >= bg::get<bg::min_corner, 0>(b))
            {
                int side_val = bg::strategy::side::side_by_triangle<>().apply(s.first, s.second, points[i]);
                if (side_val > 0) // point is on the left side of the segment
                    return false;
            }
        }
        return true;
    });

EDIT: Actually you'd have to do this only for segments that have overlapping x cordinates to box coordinates. It's because one of the next/previous segments of a linestring could have such a slope so the box would be on a different side. I updated the example above.

And then if you'd like to make it even more efficient you could create the y intervals for linestrings (min and max y coordinate, 1-d bounding boxes of linestrings, or simply 2-d bounding boxes and take the y cooridnates of corners), create a 1-d r-tree or something like that and only check the linestrings for boxes that fall into these intervals because for coordinates outside of them you know the result.

[vschoech]

We have just updated our code base to boost 1.79.0. Apparently, there still is no covered_by(box, multi_polygon) in 1.79.0.

@awulkiew I carefully re-read your detailed reply above. I admittedly fail to map your suggested solution to my problem: The way text labels are displayed, wether or not they are boxed, which color is used for boxing, and which color is used for text -- it all depends on the box's relation to the colored areas, which have polygon shape. Comparing to an ordered linestring doesn't seem to do the trick.

[vissarion]

@vschoech https://github.com/boostorg/geometry/pull/1046 fixes this issue.

[vschoech]

It is great to see that covered_by(box, multi_polygon) is now implemented (boost 1.83.0)! 👍

However, for empty boxes it returns false which, according to my email conversation with @barendgehrels (2018-04-18), is questionable. What is the perspective on this issue?

[awulkiew]

@vschoech What do you mean by empty box? AFAIU in Boost.Geometry a box can be degenerated to a point (min == max) or invalid (max < min) but never empty. Could you give an example?

[vschoech]

@awulkiew thank you for clarification. In our terminology, a box is "empty" when !(min < max).

Does "invalid" imply that the result of covered_by(box, multi_polygon) is meaningless/unusable?