Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Beman Dawes (bdawes_at_[hidden])
Date: 2009-03-14 22:38:32

On Sat, Mar 14, 2009 at 2:26 PM, Fernando Cacciola
<fernando.cacciola_at_[hidden]> wrote:
>...
> For many many geometric applications, it is the topology what needs to be
> correct, not the geometry.

In the early years of digital geography, it was not understood that
the topology had to be correct, and virtually every digital mapping
project turned into a disaster. Once it became known (in the late
1960's) that the topology had to always be totally correct (no
topological errors whatsoever, no matter how large the database) then
it became possible to build large scale digital maps, and digital
mapping became a reality.

> If you do clipping for instance, it might very
> well not matter at all (for instance in drawing applications) if the
> vertices are slightly off.

In commercial digital mapping, data like water features are often
"cartooned" to save memory and speed processing. In effect,
intermediate coordinates are deliberately distorted, but only when it
does not break the topology.

> But if an entire region is included in the result
> when it should not, then that is a disaster for whatever application.

The GIS industry has a bunch of colorful names for such topological
errors; zingers, leaks, etc, based on the appearance of map plots with
various characteristic mistakes.

And, yes, once the underlying rules were understood, most or even all
of the geometric computation code had to be not just rewritten, but
usually thrown in the trash and a fresh start made. It was actually
possible to reduce the precision of coordinates and yet produce far
more robust code.

--Beman