Geometry :

Subject: Re: [geometry] "covered_by" for polygons
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-02-16 09:19:51

Hi Volker,

>> The equals-test will cost you more than the area-test.
> That's a detail I wasn't aware of. I'll prefer the A-B implementation then. Given that A and B are multi-polygons, and based on your reply to my earlier post< http://lists.boost.org/geometry/2012/02/1818.php> I assume that I can simply check for empty() and skip the area test altogether. In other words: Is there a guarantee that if A is covered by B, (A-B) will be an empty container, rather than a container that contains one or more empty polygons?

That is how it should be. So nearly a guarantee. If it is not like this,
it is a bug.

I did not check it right now. I'm a little careful because most
unit-tests we have check on area and/or number of output points, so this
will not detect a container of empty polygons. But difference tests on
number-of-output-geometries too so yes, it should work.

>> But area(A-B)==0 is not always a good test. Suppose A is empty. Than A-B = empty as well. But A is not covered by B
> Sure. We will have to decide what we need in these corner cases and treat them explicitly if need be. What is your approach? Will an empty (multi-)polygon be a valid input to a (currently hypothetical) implementation of covered_by?

Yes. The reason is that you want to do (later) things as:
covered_by(a+b, c-d)

it should then not be throw on empty input.

All empty geometries (except point/segment which cannot be empty) are
basically valid. Only for distance and centroid we have a "problem" then
because a null-output should be detectable.

>
>>> Do you think there are any optimization opportunities in a dedicated covered_by algorithm?
>> The intersection or difference operations are not necessary. Getting intersection points and some additional logic should be enough.
> Ok then, I'm looking forward to a dedicated implementation some day! :-)

We planned to implement more combinations for 1.50 so this should be one
of them.

Regards, Barend

Geometry list run by mateusz at loskot.net