> 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.0e-8. 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,

Pieter-Jan