Geometry Boost List: Re: [geometry] Reliable invariants of geometry representation? Validation tests?

Subject: Re: [geometry] Reliable invariants of geometry representation? Validation tests?
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-02-09 14:11:42

Hi Volker,

On 9-2-2012 18:01, Volker Schöch wrote:
>
> Hi again,
>
> Is there a guarantee that the intersection of two disjunct polygons is 
> an empty multi container?
>

Of course. Yes.

That's to say, the intersection currently appends to a container.

If it is empty before the call, and the polygons are disjoint, it is 
empty after the call.

> I.e., is it fair game to check for multi_polygon::empty()? I don't 
> want to use the intersects algorithm b/c if the polygons intersect, I 
> need the result of the intersection anyway. Thus I can as well 
> calculate the intersection in the first place and then test the result 
> for emptyness, if this can be done efficiently (calling area is not 
> considered efficient).
>

This is a valid approach.

One addition: intersects calls disjoint, and disjoint stops at the first 
segment intersection. But if you want to have the result of an 
intersection anyway, indeed, just call it. Is faster.

> Can you point me to a documentation (kidding...) or maybe just explain 
> which invariants of geometry representation your algorithms rely on, 
> and on which invariants I can rely with regard to your algorithms? Is 
> there any validation function available that I could use, e.g., in 
> debug builds, to check whether these invariants hold at specific 
> times? Is there a check for orientation? For closedness? For 
> overlapping multi-polygons or overlapping holes?
>

The input should be valid. Valid means valid w.r.t. OGC requirements: a 
so-called simple (multi)polygon, not self-intersecting, self-tangencies 
are allowed, correct orientation of exterior ring, and interior rings, 
correct closure.

All this is not checked before (reason: performance).

I deliberately stated: the input "should" be valid. Because it is 
invalid, and the invalidities do not interfere with the intersection, 
the output is still valid.

So a self-intersecting polygon can be unioned with another one, and the 
output is as invalid as the input was, but there is output (as long as 
the self-intersections do not disturb the union process - and they could...)

> What is the area of a polygon that does not have begin==end, if 
> explicitly using a closed polygon model (specified by way of template 
> parameter)? Is the result well-defined? Why doesn't this trigger some 
> assert/throw some exception in the first place? I understand that you 
> probably avoid checking for performance reasons.
>

Yes

> However, do you have the means for me to perform the checks when I 
> decide it's appropriate (see above)? I am aware of the correct() 
> algorithm, but I don't want to have problems silently fixed -- I want 
> to be made aware and fix them at their origin.
>

There will be an is_valid algorithm. Currently indeed: use correct. 
Which corrects orientation and closure but not self-intersections.

> I just came across my first GGL exception. Entirely unsuspectingly. 
> Nowhere is it mentioned that has_self_intersections throws (which is 
> called by top level algorithm intersection). I miss information in the 
> documentation, but even more I miss a corresponding throw(...) 
> declaration in the source code.
>

OK, the has_self_intersections had been added just before release to 
avoid many reports on non-working overlays due to incorrect input. After 
that a performance comparison was done and exactly the 
has_self_intersections was the culprit then, behaved very slow. That has 
been solved, but also the has_self_intersections is made optional.

If it returns always false - OK that is part of the hastily last-day 
insertion. Will be looked at, thanks for the message.

> Therefore please give me some guidance: Can all algorithms throw?
>

Good question

The aswer is no. num_points will never throw, for example.

But we currently don't have a definitive answer.

Think of calculating the distance between two empty multi-polygons. That 
distance is "null" but we don't support that. 0.0 is  wrong. So there we 
throw an exception.

We also threw an exception at calculating an area of an empty 
(multi)polygon in 1.49 but that has been disabled, it is too breaking. 
We've to make a final decision first. So it now returns 0.0.

Which is expected if you state "area(a & b)" (where you define & as 
intersection operator yourself - not supported) - you (probably) don't 
want an exception here, just 0.

> Is there a way to turn off exceptions globally (for the GGL)? And why 
> do you call has_self_intersections at all, if performance is your 
> primary objective and the caller is responsible for well-formed input 
> (as seems to be the case with regard to begin==end)?
>

To avoid too many reports about non-working overlays.

> <philosophy warning>
>
> Fun side note: has_self_intersections never returns true -- only 
> throws or returns false. If BOOST_GEOMETRY_OVERLAY_NO_THROW is 
> defined, it still returns false even if it has detected 
> self-intersections.
>
> And by the way, what's the reason why you chose clockwise as your 
> default orientation when the convention is to view a counter-clockwise 
> oriented polygon as filled on the inside? Is this computer science way 
> of thinking with the origin of the coordinate system in the upper left 
> corner of the screen? ;-)
>

It has always been. No, it is not a computer science way - I have a GIS 
origin.

> Along the same lines -- I know you're not going to change this design 
> any time soon, but why did you choose to require closed polygons 
> having begin==end?
>

It is not required. This is optional either. Opened/closed. Most 
(probably all) algorithms are checked on this.

> One more thing to go wrong. One more line of glue code to ensure that 
> this holds. And how do you ensure that those points don't drift apart, 
> e.g, due to floating point rounding issues...? Looking at the surface 
> this approach seems to create more problems than it solves.
>

That is true. But such a polygon is not "correct".

> </philosophy warning>
>
> As I said before, I am glad that the GGL is available for me to use. 
> There are just a few things that strike me as odd, but I'll get over it...
>

Good to hear again ;-)

Thanks for your input.

Regards, Barend