Boost logo

Geometry :

Subject: [ggl] what is an algorithm
From: Mateusz Loskot (mateusz)
Date: 2009-04-25 16:14:43

Barend Gehrels wrote:
> Now we've update the structure, I was thinking about the algorithm
> folder. To crowded or fine?

A little :-) and there is potential it will get crowded in future.

> It is sometimes hard to decide what is what.

For some of them it is not enough to decide their place based on
algorithm defined as a procedure provided to operate on GGL
data and types.

Second issue is to help users to recognize algorithms
easier by proper structure of folders.

> Is "loop" an algorithm? Now in util.

It's unclear to me how it's different to for_each.

> OGC distinguishes algorithms:
> - "query" contains within, touches, overlaps, disjoint, etc. This makes
> sense to me

Aren't they called spatial predicates or just predicates?
They return binary answer, so perhaps "predicate" is a good name for
directory. Predicate is used in C++ std library terminology.

> - "analysis" contains distance, buffer, ConvexHull, intersection, union.


> This is also useful, there are two kinds:
> - pointset spatial relationships (and, or, xor, not -->
> intersection, union, sym_difference)
> - other things as distance and buffer
> - other, uncategorized such as envelope, dimension

All of them here and above are geometry algorithms - this could be
an indicator for selecting how to structure them.

> GGL:
> I've put some in core (e.g. topological_dimension, because it is
> completely compiletime), some in util (loop) and most in algorithms.

for_each is also a general purpose algorithm, similar to loop.

> Besides OGC algorithms we have and get more:
> - simplify
> - spline
> - diameter (defined by the most furthest point-pair of a polygon,
> linestring, etc)
> - closest_pair (idem but most closest point-pair)
> - combine a bounding box growing if points are added)
> - etc.
> The easiest is to have them all in one folder algorithms, users then
> don't have to think about what kind it is. Do you agree with that? The
> folder will have dozens of files, but that is how it is, the boost/mpl
> folder contains 182 files.

It would be good to have it scattered in some categories, but on the
other hand if categories are not obvious (or natural), then possible
structure may be ambiguous to users.
Looks like this is an issue in GGL, so I like the idea of single
collection of files as you are suggesting.
Or, may be a few obvious categories could be identified like
OGC algorithms. This way GIS-oriented users could easily identify
where to look for what they need.

> I'm using the GGL more and more in projects and have several pieces in
> different states which will go there, coming time. As mentioned earlier:
> touches, relate, disjoint, buffer, union but also diameter (see above),
> remove_indentations, remove_small_holes (this last one should be
> templatized by a selection struct), ...

I'm still familiarizing with GGL, but next I'd like to get into WKB IO.
What you think?

Best regards,

Mateusz Loskot,
Charter Member of OSGeo,

Geometry list run by mateusz at