_edge() Comparison of numbers is unsafe

[martinfrances107]

I am slowly porting this module to rust ( rustlang )

https://github.com/martinfrances107/rust_d3_delaunay

and so I have had reason to go over this modules code line by line.

looking at the _edge method in src/voronoi.js ( line 264 )

For me rust's linting and checking tooling ( clippy ) are throwing up warning about a common problem, the unsafe comparison of floating point numbers. The problems are 'upstream' so I want to make changes here.

Cutting and pasting from my debugging of the java script version of the module.

I see that P[j] can be 187.84146341463415

In my port P is a vector of f64's -- a 64 bit float point number.

Comparing floats a, b is a bit tricky, formally this

a===b or a !== b

is incorrect

The textbook way of comparing floats is

Math.abs( a - b ) < epsilon or Math.abs( a - b ) >= epsilon

where this module uses epsilon = 1e-6

In short I propose making a whole series of change of the form below to make things safe.

•  if ((P[j] !== x || P[j + 1] !== y) && this.contains(i, x, y)) {
  

•  if ((Math.abs(P[j] - x) >= epsilon || Math.abs(P[j + 1] - y ) >= epsilon) && this.contains(i, x, y)) {
     P.splice(j, 0, x, y), j += 2;
   }
  

When I have a PR I will post it... But I am just raising this issue here .. just so other readers will be away of it.

[martinfrances107]

For all points I can see .. I have refactored the comparison of floats

https://github.com/martinfrances107/d3-delaunay/tree/Make_compare_of_floats_safe

It does not pass tests... yet.

[Fil]

Are we comparing values that can be created by different paths (like a *b versus b * a), or are they created by the same path. If this is the second case, I don't see that we would have an issue?

[martinfrances107]

"created by different paths"... I am not sure I understand what you mean

So I am just going to describe a scenario and you can tell me if it meets your thinking..

So I am thinking of user code making use of our library code.

In this scenario the user algorithms, are subject to numerical computation errors but always, in this event, result in a clipping bounds of a unit square.

clipping bound (A) xmin = 0, xmax = 1, ymin = 0, ymax = 1

because of numerical inaccuracies the user code on successive requestAnimationFrame events feed in the following identical clipping bounds into out library code.

so (A) = (B) = (C)

B) xmin=-0.000000001, xmax=0.999999999, ymin = 0.000000001, ymax = 0.9999999

C) xmin= +0.000000001, xmax=+1.00000001, ymin =+0.000000001, ymax = 1.000001

Looking at our edgecode() function - different codes are going to be return and visually I think you may see some jitter as the generated polygons incorrectly change over time.

return (x === this.xmin ? 0b0001 : x === this.xmax ? 0b0010 : 0b0000) | (y === this.ymin ? 0b0100 : y === this.ymax ? 0b1000 : 0b0000);

return (Math.abs(x - this.xmin) < epsilon ? 0b0001 : Math.abs(x - this.xmax) < epsilon ? 0b0010 : 0b0000) | (Math.abs(y - this.ymin) < epsilon ? 0b0100 : Math.abs(y - this.ymax) < epsilon ? 0b1000 : 0b0000);

[Fil]

I'm sorry I don't understand the problem you are trying to solve. Is there a specific array of point coordinates where the current code fails?

The two first tests you propose to change are here to avoid duplicated points: #83 and #88

The edgecode compares S —the result of _clipSegment which returns one of this.xmin, this.ymin this.xmax, this.ymax— with this.xmin &c. So it sounds fair to compare with strict equality?

[Fil]

closing due to inactivity; please don't hesitate to comment if this is still an issue