Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-03-10 19:34:45

Simonson, Lucanus J wrote:
> Thomas Klimpel wrote:
> > So following "floating point rules" for
> > 2D geometry problems will probably often be inappropriate.)
> >
> Hmm, if I move a point during the algorithm I move its edges
> laterally and propigate the badness throughout the network.
> We do have to keep in mind the fact that there is a floating point
> grid and not pretend that floating point is continuous.

Questioning whether talking about a floating point grid is appropriate is not the same thing as pretending that floating point is continuous. It's more about the statement: "A computed floating point coordinate would simply be allowed to have a tolerance of epsilon." When this tolerance is not an option, using fixed point should be considered. (Using fixed point, the same program compiled with two different compilers will (should) yield exactly identical results, which is not true when using floating point.)

> > It may be OK in a floating point context to break this invariant, if
> > enough information is given to downstream code that it can avoid
> > breakage. If this is not an option, conversion of the initial input
> > to fixed-point may be the more appropriate way to go. (Remember that
> > it is often OK to modify floating point input slightly, so the
> > inexact conversion to fixed-point is not necessarily a problem). A
> > computed floating point coordinate would simply be allowed to have a
> > tolerance of epsilon.
>
> This might be true in the case that I were writing the downstream code.
> However, if the downstream code is inside Abaqus or a solid modeling
> program such as ACIS, or a mesher I have to meet their requirements
> for well formed inputs, which means no monkey buisness.

The monkey business here is that the typical downstream code (written by others) doesn't clearly define what it considers as well formed inputs. (Are keyholes allowed? Are overlapping edges that don't share common endpoints allowed?) As soon as there is a clear definition of the requirements for well formed inputs (of a particular downstream code), one can try to conform to these requirements. If I would implement a Bentley-Ottmann line-intersection algorithm along the way I suggested to Brandon, it would probably not conform to all commonly occurring requirements of downstream code. However, I don't think that such an implementation would be "monkey business", because of that.

> >> I'm much happier with integer coordinates.
> >
> > I find it a bit difficult to understand which output is considered
> > valid in an integer coordinates context.
>
> Whatever the algorithm does is right by its own definition of "right".

The cited example looked like a severe change of topology without any good reason to me, and the authors weren't yet talking about algorithms at all. They just showed the example and the expected result (which was quite unexpected to me). However, it was not just that paper, but that I wondered before about the question how to characterize the expected result in an integer coordinates context.

When I suggested a to Brandon how I think a Bentley-Ottmann line-intersection algorithm could be implemented for floating point, I was mostly concerned with the internal consistency of the implementation itself, not about special requirements on the generated output. However, the typical paper talking about issues of inexact arithmetic for geometric algorithms is more concerned about accuracy requirements of the output than about a fast and consistent implementation without using multiple precision libraries. And the typical paper often takes a fixed-point/integer number point of view. I understand that there are good reasons for this, but I still don't understand why a severe change of topology should be OK, but the (nearly) unavoidable "tolerance of epsilon" of a floating point result should be "monkey business".

Regards,
Thomas