>
> > 2) in trunk/lib/nn/nncommon.c : circle_contains()
> >
> > line 90 : return hypot(c>x  p>x, c>y  p>y) <= c>r;
> >
> > should be changed to
> >
> > line 90 : return hypot(c>x  p>x, c>y  p>y) < c>r + 0.000001;
> >
> >
> > This is just a standard floating point equality checking bug. It surfaces
> > when asking to interpolate on one of the given x,y coordinates. It gives
> the
> > result of delaunay_xytoi returning a certain triangle for the point, but
> > then the circle_contains() function says this point is no part of the
> > circumcircle.
>
> This is not quite a "standard" floating point equality check since we're
> looking at <= not ==. Whether you consider this a bug depends on how
> important it is that the == case is included, or that points ever so
> slightly outside are excluded. Anyway, I have committed a slightly
> modified version of your fix which checks against <= c>r*(1.0*EPSILON)
> where EPSILON is 1.0e8. This looks at the relative error since we don't
> know what the magnitude of the radius will be.
I agree that's a better solution, however the "<=" might be changed in "<"
then ?
> This makes no difference
> (checked with diff) for example 21. Can you give an example where this
> is actually important?
I don't have a quick example, but what I noticed was this :
1. Create a delaunay triangulation for a bunch of points
2. Call nppi_interpolate_point(...) on one of the "given" points
3. eventually you reach the delaunay_circles_find() function.
> with delaunay_xytoi() you get one of the triangles that have the
"question" point as a vertex.
> further down, the cirlce_contains() function is called on this triangle
and returns false.
I noticed this problem when an interpolation request for some points gives a
valid "d>first_id" triangle just before /* main cycle */, but the
delaunay_circles_find() function still returned 0 circles.
This was caused by circle_contains() returning false on *some* triangles'
vertices.
> Of course it will be architecture / compiler
> dependent... The comments above this line suggest that quite a bit of
> work went into finding this formulation to minimise such errors.
Yes, I was hesitant because of that comment too. I assume the fact there is
<= in the code means circle_contains should return true for the vertices of
the triangle. However, floating point comparison doesn't work that way, and
in a lot of cases the result of hypot() in circle_contains was not equal to
the value stored in c>r, but a little bit bigger.
Kind regards,
PieterJan
