Boost logo

Boost :

Subject: [boost] [geometry] [impl] Concepts
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-03-13 11:11:39


Hi,

This still waited an answer.
> When you say refinements seem not applicable, do you mean refinements in general, or just in the case of rectangle/polygon? I have been curious about how you might implement refinement in your tag dispatching based API as I understand it, and I couldn't come up with an answer. If refinement used/supported by your API, or do you think it is not needed except for Const/non Const? I'm curious to hear you elaborate on that.
>
One (the main?) of the related topics here (on concept refinements) was
to limit the number of implementations and combinations. As I've
mentioned earlier, we try to limit the geometries such that they are as
orthogonal as possible. However, some geometries of course have some
common properties.

A linestring is, like a linear_ring, a sequence of points. Simple
calculations, such as the number of points of them, can share their
implementations. With help of a few meta-functions they can also share
tag dispatching.

Then take for example the "selected" algorithm. It uses the
"topological_dimension" (TD) meta-function, which is 0 for points, 1 for
lines (or segment), 2 for polygons (and in general everything with an
area). The "selected" algorithm specializes on this TD meta-function and
everywhere where it is 2 it uses "within".

Then for example: calculate distance between two geometries. TD does not
make sense here. We will have in the end the ortogonal geometries point,
linestring, polygon, multi-point, multi-linestring, multi-polygon, that
is 6. Plus the supporting ones segment,box,linear_ring. 6 geometries
make already 36 combinations. We now also implemented the reverse tag
dispatchings, so point-linestring and linestring-point are implemented
as one tag dispatching struct. Bruno implemented this, it uses a
Reversable boolean template parameter. So this saves 15 combations, 21
left. (This reversability is applicable to all tag dispatching
constructs taking two geometries.)

As soon as we have multi-geometries (multi-point for e.g. a fleet,
multi-linestring for e.g. a highway, multi-polygon for e.g. France and
Corsica), and we want to calculate the distance between them, the
process is always the same. They are all vectors (containers), walk
through the vectors, check the distance between the entries, if it is
shorter than any other memorize that one, etc, straightforward. So the
implementation can be the same for all of them (of course using spatial
index/sections or similar to do it fast). So we add a meta-function
"is_multi", returning false for normal geometries, true for
multi-geometries, and we can (partly) specialize on them. There will
then only two (one for single-multi, one for multi-multi) dispatch
structs handling them all. This saves another 12 combinations. So 9
left, which can be overseen easily (and probably there are more
combinations which can be harmonized). (Note that all multi-ones are not
yet implemented, they are skipped until all concepts are clear.)

So these are all really different cases, distinguishing on linearity,
multi-ness, topological dimension.

This is not concept refinement, or it would be a complex system of tags
multiple inherited by other ones. We limit our dispatch cases in a
finetuned way, so no "concept refinement" but "meta-function finetuning"...

Regards, Barend
https://svn.boost.org/svn/boost/sandbox/ggl
<https://svn.boost.org/svn/boost/sandbox/ggl/>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk