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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-10 13:24:43

Thomas Klimpel wrote:
> It is an interesting question whether talking about a floating point
> coordinate grid is appropriate. An important difference between
> integer coordinates and floating point coordinates is that integer
> coordinates input must often be treated as exactly given, while it is
> often OK to modify floating point input slightly. (But this is
> problem dependent, and 2D geometry problems are probably more
> naturally associated with fixed-point/integer coordinates than with
> floating point coordinates. 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.

>> Because snapping moves the edge laterally by some small amount
>> it may cause it to cross to the other side of a vertex than the
>> original segment, leading to the invariant that all output segments
>> are non-intersecting and touch only at their end points being
>> violated, 
>> which breaks downstream code.
> 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 requriements for well formed inputs, which means no monkey buisness.

We actually do convert floating point to fixed point, perform the geometry operations and convert back.  This could be problematic if the fixed point had a finer resolution than floating point.  However, if your input extents is bounded to 32bit integer domain and you use double for floating point there is no approximation needed to convert integer to floating point, and so nothing goes wrong in that step.

> 
>> This is a bad problem in floating point because the amount the
>> segment moves laterally depends on where the intersection point was
>> snapped in the floating point domain, 
>> and can become arbitrarily large.  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".  No approximation is correct in a pedantically strict sense of the word, meaning both floating point and integer operations will produce artifacts when things are happening below the threshold of the coordinate grid.

Regards,
Luke