Re: [boost] [Review] GGL review starts today, November 5th

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-12 09:12:06

Hi Luke,

Herewith the answers on (most of) your questions (the rest wil come soon 
now).

First, I added two additional pages of documentation, to not make this
answering mail too long.
- one about intersections (overlay): http://tinyurl.com/ggl-sets
- one with custom polygon: http://tinyurl.com/ggl-c06

The first one should give the necessary theoretical background and
implementation overview of the overlay algorithms.

> 1. Does the library support other Boolean operations between pairs of polgyons than intersection?
> 	Union
> 	XOR
> 	AND NOT
>   

union (or): yes, supported
intersection (and): yes

We splitted here, we considered that for most users, most use cases, and 
for Formal Review purposes this would be enough. However, the other 
functions are actually already implemented because it's all the same 
source code. The doc-page I mentioned above will give the necessary 
background for this. But there are currently no free functions for 
(symmetric) difference.

symmetric difference (xor): so: it is supported by the algorithm but has 
to be fit in, see the doc-page for backgrounds on this
difference (and not): idem

These are OGC-operations (and names) and they are all planned as we want 
to support the full OGC set.

> 2. If so, does the library support the union of more than two overlapping polygon simultaneously (three or more mutually overlapping polygons)?
>   

Similar story: three (or more) polygons is supported by the algorithm 
itself, but has to be implemented (see doc-page) as a separate (or 
overloaded) function.

> 3. Does the library support map overlay operations of two layers?  Of more than two layers simultaneously?
>   

The GGL is geometry-oriented. All algorithms work on one or two
geometries, and it is possible and useful for some algorithms to support
more than two (e.g. your question 2), but it is not layer oriented.

Layers can be processed by the code using the library, and it is
advisible that they consider their envelopes (bboxes) as well.

> 4. If the non-self-intersecting invariant is violated at the input of the polygon pair intersection algorithm what does the algorithm do?
>   

This depends on how the polygon self-intersects, and how the 
self-intersection intersects with the other polygon. If the 
self-intersection is untouched by the other polygon, you'll get exactly 
that self-intesection back (for a union) or it is discarded (for an 
intersection).

The self-intersections are not even tried to be detected. This is on 
purpose because it saves another call of get_intersection_points, which 
is the most time-consuming in the current implementation.

If the self-intersection interferes with the other polygon, you can get 
  an invalid polygon back. As the input was already considered as 
invalid, this is what is to be expected.

We've researched this recently because it occured in practice. The 
algorithm will find an invalid path, detect that and skip that output 
built up so far.

> 5. Is there a way to check self-intersecting invariant before attempting an intersection operation?
>   

Yes. The function "intersects" can work on one geometry and returns true
if it is self-intersecting.

> 6. Is there a way to fix a polygon that is self-intersecting to be non-self intersecting?
>   

This is actually the same story as for (symmetric) difference and for 
intersection/union of more than two polygons. We have all the tools for 
this but it is currently not provided. I mean by this: it is possible to 
detect self-intersections, the traversal can walk through this and split 
it in an outer polygon and holes.

It is not subscribed by the OGC interface (which assumes always valid
input).
It occurs to me now that we could also give an extra boolean flag to let
the algorithm know that self-intersections should be considered as well.
That would probably be a sufficient solution.

> 7. [...] FP
>   

I will come back to FP/precision later.

> 8. What is the algorithmic complexity of the polygon intersection algorithm?
>   

As the algorithm is splitted into some parts, the complexity also is. 
This is described in more detail in the doc-page.

> 9. Could you please provide the community with a description of the polygon intersection algorithm?
>   

This is described in the doc-page

> 10. Is the polygon intersect bounding box algorithm linear time?
>   

This is described in the doc-page.

> 11. [...] FP
> 12. Is the distance algorithm implemented for linestring pairs?  For polygon pairs?  If so, what algorithmic complexity does it have, and can you describe the algorithm for the community?
>   

Sorry, this had to be postponed. I planned to do this for the review but
you know, all those documentation, unit-tests, examples, etc. It will be
there.

> 13. Why is there no custom polygon example in the documentation?
>   

Good question (as all your questions, by the way), so it's provided now.

> 14. Why do you need interior_type for the polygon concept traits?  What requirements does the interior_type need to satisfy?  Is it expected to be an stl container?
>   

- interior_type is there a polygon may have holes. If library users use
polygons without holes, they can take a ring (or, stated more precisely:
a type fulfilling the Ring Concept)
- interior_type is expected to be a Boost.Range (for a read-only
polygon) and to be STL container-conformant (for a mutable polygon).

> 15. What happens if you instantiate the polygon pair intersection algorithm with integer coordinates?
>   

GGL is designed such that the input types and output types not need to
be the same.
You can therefore, for example, calculate the distance between an point
with integers and a point with doubles.

This is designed to be everywhere (though it might be that it is not yet
applied in all algorithms). In intersection/union, it is the case.

So the result of the intersection of two integer polygons can be a
double polygon.

The result of two integer polygons can also be an integer polygon. In
that case all intersection points are rounded to integer.

It is therefore the same as normal arithmetics:

int d = sqrt(2) will deliver 1
double d = sqrt(2) will deliver 1.41

There is one mechanism more. In strategies you can add an optional
CalculationType as an optional template parameter. If that is specified,
that one is used. You can see that e.g. in the area strategy. This one
is not yet in the intersection (strategy). But the mechanism works like 
this:
- define a strategy with a double (or long double, or
high-precision-number) as the last optional template parameter
- input is two integer polygons, output are integer polygons
- during all calculations, doubles are used (so intersection points are
not rounded, or rounded to the precision the number is in)
- in the very last phase, during the output, coordinates are rounded
back to integer. Yes, this will lose precision, but that is what the
library user asks for in this use case.

> 16. [...] FP
> 17. [...] FP
>   

So sorry for the time it took me to answer, and the FP part will come asap.

Regards, Barend