Boost logo

Boost :

From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2006-07-31 08:25:05

Arash Partow wrote:
> Mateusz Loskot wrote:
> >>Yes, there were a few discussions on the list.
> >>Here is a list of threads I've saved:
> >>
> >>This is one of the latest and very interesting:
> >>
> >>
> >>and other:
> >>
> >>
> >>
> >>
> >>Also, there are some prototypes:
> >>
> I've had a read of articles, and I like some of the ideas that have
> been presented and proposed. Its a shame that some of the better
> ideas haven't come to fruition as of yet. But heres hoping that
> will change sometime soon.


IMO the idea seems to be quite new, so there is more manpower needed.

> >>I have no knowledge about any other efforts than listed above.
> >>I'm very interested in robust computational geometry library
> >>in Boost. So, I'd be also interested in some constributions.
> >>
> >>For last 6 months, I was working on the GEOS library:
> >>
> I had a look and it seems you've made a lot of progress, it would be
> good to begin integrating things at some point soon for an initial
> review submission.

Yes, that's my idea too.

> >>which is a *direct* port of JTS:
> >>
> >>Unfortunately, GEOS follows JTS design and implementation almost step by
> >>step, so performance is not good.
> >>Note, GEOS is a library for GIS and it follows the OpenGIS Simple
> >>Features specification (
> >>
> >>I think, this specification may be interesting to read about
> >>"The Dimensionally Extended Nine-Intersection Model - DE-9IM"
> >>as a nice model of spatial/geometric relation operators.
> I had a quick read, isn't this all just some glorified minkowski
> difference thing?

Hmm, I've not analysed it from Minkowski's point of view, interesting.

> >>> > As for a preliminary library design I propose the following:
> >>> >
> >>> > * primitive geometric structures 2D/3D only
> >>> > (point,line,segment,triangle...)
> >>> > * operations between primitives (intersection, distance, inclusion...)
> >>> > * higher level algorithms in a structured fashion similar to BGL:
> >>> > * hulls, rotating caliper
> >>> > * triangulation (point sets, polygons)
> >>> > * boolean operations over polygons
> >>
> >>
> >>Boolean operations could be provided for every geometry type,
> >>see DE-9IM.
> Some geometric operations just don't make sense for certain pairs of
> types, hence not all geometric operations can be defined, all one can
> do is define/implement operations that do make sense.

The intersection matrix operations apply to all planar geometries.

> >>> > * precision related issues to be dealt with mainly by user
> >>> > specified floating point type, and partially at the algorithm level
> >>
> >>
> >>JTS and GEOS have quite good example of precision model.
> looked at it, seems like standard epsilon/fuzzy arithmetic - nothing special
> there.


> I believe one either needs to go down the path of "exact arithmetic" or to
> delegate the precision issues to the type the "user" chooses.

The latter is seems to be a good idea.

> From a "good library design" POV I believe that for the majority of
> things precision should be delegated to the users choice of type,
> and to hence maintain the simplicity of the calculation/algorithm's
> implementation. Say for example the closest point on a line from
> an external point is merely the dot product of the tangent from the
> external point and line, which is a very trivial thing. If one were to
> go down the path of exact arithmetic and you fall into problems such
> as determining the machine's FPU, its floating point precision etc...

That's right.
We're still struggling with machine related and optimization related
problems in GEOS.

> why not let the type take care of that, for most things double and float
> will be more than enough, for other things people may decided to use
> their own extended or arbitrary precision number types, such as the
> various rational and integer kernel types that come with CGAL, I
> believe the BOOST mathematics library will some day have its own
> extended precision real, rational and integer (bigint) types.

I agree with this concept.

> >>Extension idea:
> >>I'd also have an idea about extension for data (de)serialization.
> >>In GIS, there are two major formats to save/read geometries WKT -
> >>Well-Known Text and WKB - Well-Known Binary.
> >>Both have been invented by OpenGIS Consortium.
> >>
> >>Here are good examples of WKT:
> >>
> >>and WKB:
> >>
> >>
> >>I have some prototype of Spirit based parser to read WKT.
> Anything is possible, it just requires that knowledgeable
> people in the field be willing to chip-in.


Best regards

Mateusz Loskot

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