Boost logo

Boost :

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

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

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

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

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
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

> 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
- 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at