Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Kai Benndorf (kai.benndorf_at_[hidden])
Date: 2009-09-02 04:16:44

John Phillips schrieb:
> Simonson, Lucanus J wrote:
>>
>> I can implement a transparent floating point to fixed point
>> conversion wrapping the algorithm that is integer only.  This should
>> allow transparent use of the algorithm with floating point
>> coordinates and no more loss of precision than floating point
>> calculations themselves would produce.
>>
>>
>> Thanks Jeff, Luke
> 
>   Luke,
> 
>   You have made variations of this assertion a few times in this thread, 
> and I wanted to point out one problem with it.
> 
>   The distribution of the integers is not the same as the distribution 
> of the floating point numbers. It is true that an x-bit integer has 
> about as many distinct values as an x-bit floating point number. (Even 
> more, depending on the representation used.) However, those integers are 
> evenly distributed along the number line, and the floating point values 
> are not. This will not cause a problem in many applications, but in any 
> setting where large and small scales mix (such as polygons that are just 
> off of regular, but need to be precisely defined; or systems that mix 
> large and small polygons) there will be no scaling for the integers that 
> both preserves the needed dynamic range and the needed precision. So the 
> user will be forced to choose between overflow errors or lost precision.
> 
>             John

Hi there,

as indicated by Lucanus a mapping from float to int (or equivalently 
from double to int64)
can be performed without loss of accuracy. The transformation is however 
not linear.
A potential possibility to keep track of the mappings over various scale 
levels could be
easily established for data that support the ieee floating point standard:

Since there are only a finite number of floats and the number of steps 
between 2 given floats
is the same as the number of steps between the corresponding integers the
transform for a polygon would start out by determination of the centroid 
of the bounding box.
 From this centroid any point of the polygon contour may be measured in 
terms of
floating point numbers between the corresponding x y positions.
Thus the distance is based on the metric of "how many times do I have to 
increment my
floating point to reach a coordinate given the origin" NOT based on a 
scaling.

Accordingly, the integer representation may be obtained by "casting" 
float to int data
and determination of the numbers inbetween:
essentially given 2 doubles

    double originX = ...;
    double pointX= ...;

// convert to float and determine number of steps between the 2 floats :
     float  oX = (float)(originX);
     float pX = (float)(pointX);
     int x = numbersBetween(oX,pX);
     ....
// now obtain some new integer by
    int newx = anyfunction(x);
    ...
// while the floating point data MUST be retrieved via
    float newX = advance(oX,newx);

with numbersBetween and advance something  like that:

  /*!
   * interpret storage of a float number as integer (same size in memory)
   * and return as lexigographically ordered two complement int,
   * i.e. +0.0 and -0.0 are viewed as same number
   */
  inline int const intValue(float const &argValue) {
    return ( *(reinterpret_cast<int const *>(&argValue)) < 0 )
      ? (INT_MIN - *(reinterpret_cast<int const *>(&argValue)) )
      : *(reinterpret_cast<int const *>(&argValue));
  }

/*!
* determine number of discrete floating points that may live between 2 
given floats
*/
    inline int const numbersBetween(float const &argA, float const &argB) {
      return (intValue(argA) - intValue(argB));
   }

/*!
  * given a float a the number of floats that are possible between another
  * float than determine and return that float
  */
  inline float advance(float &argValue, int argSteps) {
    int intdelta = intValue(argValue) +argSteps;
    return *(reinterpret_cast<float *>(&(intdelta)));
  }

Regards

Uwe