
Boost : 
Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Barend Gehrels (barend_at_[hidden])
Date: 20091112 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/gglsets
 one with custom polygon: http://tinyurl.com/gglc06
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 docpage 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 docpage for backgrounds on this
difference (and not): idem
These are OGCoperations (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 docpage) 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 geometryoriented. 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 nonselfintersecting invariant is violated at the input of the polygon pair intersection algorithm what does the algorithm do?
>
This depends on how the polygon selfintersects, and how the
selfintersection intersects with the other polygon. If the
selfintersection is untouched by the other polygon, you'll get exactly
that selfintesection back (for a union) or it is discarded (for an
intersection).
The selfintersections are not even tried to be detected. This is on
purpose because it saves another call of get_intersection_points, which
is the most timeconsuming in the current implementation.
If the selfintersection 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 selfintersecting invariant before attempting an intersection operation?
>
Yes. The function "intersects" can work on one geometry and returns true
if it is selfintersecting.
> 6. Is there a way to fix a polygon that is selfintersecting to be nonself 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 selfintersections, 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 selfintersections 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 docpage.
> 9. Could you please provide the community with a description of the polygon intersection algorithm?
>
This is described in the docpage
> 10. Is the polygon intersect bounding box algorithm linear time?
>
This is described in the docpage.
> 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, unittests, 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 readonly
polygon) and to be STL containerconformant (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
highprecisionnumber) 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk