gorhill / Javascript-Voronoi

A Javascript implementation of Fortune's algorithm to compute Voronoi cells
http://www.raymondhill.net/voronoi/
Other
1.02k stars 166 forks source link

mixing text and floats can cause wrong operations on user's code #39

Closed wassfila closed 4 years ago

wassfila commented 4 years ago

edges va and vb do mix text and float, this caused my center function to return wrong values (huge numbers)

image

function center(he){
    return ({x:(he.edge.va.x+he.edge.vb.x)/2,y:(he.edge.va.y+he.edge.vb.y)/2})
}

when adding this sanatizing function after calling compute, it does solve the issue :

        this.res.edges.forEach((edge)=>{
            edge.va.x = parseFloat(edge.va.x)
            edge.va.y = parseFloat(edge.va.y)
            edge.vb.x = parseFloat(edge.vb.x)
            edge.vb.y = parseFloat(edge.vb.y)
        })

The reason why I did not want to add the parseFloat on the center function, is that I might be calling it a high number of times, it is therefore for my use case more efficient to run it once on the output results. In case you think it makes sense for a more homogeneous types of the output, I would recommend to integrate this inside the compute function. I know that you might be looking to reduce cpu time and this might increase it, that is why the decision for this change is a compromise of for and against.

wassfila commented 4 years ago

by the way, your library is amazing, here's a link if you'd like to see what I made out of it: https://websvg.github.io/voronoi/

gorhill commented 4 years ago

edges va and vb do mix text and float

It's a long while since I worked on this code... I find it strange that the code would somehow use stringified values.

How can I reproduce this?

wassfila commented 4 years ago

It's easy to reproduce, here's an example image

I deactivated the cleaning and enabled log conditional on type instead

        this.res.edges.forEach((edge)=>{
            console.log(edge.va)
            console.log(edge.vb)
            if(typeof(edge.va.x)=="string"){
                console.log(`edge.va.x is a string = '${edge.va.x}'`)
            }
            //edge.va.x = parseFloat(edge.va.x)
            if(typeof(edge.va.y)=="string"){
                console.log(`edge.va.x is a string = '${edge.va.y}'`)
            }
            //edge.va.y = parseFloat(edge.va.y)
            //edge.vb.x = parseFloat(edge.vb.x)
            //edge.vb.y = parseFloat(edge.vb.y)
        })

if you don't luckily or unluckily manage to have seeds coordinates that do generate integers as results, then you can have this seeds export example. the window, here (715 x 419)

[
    {
        "id": 0,
        "x": 295.9294875321498,
        "y": 177.16672522330165
    },
    {
        "id": 1,
        "x": 492.8195605177235,
        "y": 284.3893154108223
    },
    {
        "id": 2,
        "x": 107.4175783265607,
        "y": 293.26401451534616
    }
]
wassfila commented 4 years ago

or to make it easier, I pushed a version with the log and debug enabled (and types cleaning disabled) on a branch that you could clone or download, then serve and open a chrome debug window (ctrl+j) https://github.com/WebSVG/voronoi/tree/issue_demo you should see the logs I posted on the previous comment.

gorhill commented 4 years ago

I git-cloned and loaded index.html in Chromium from localhost:8000, and the only thing I see at the console is:

same version 9, loading
index.js:241 set svg ( 400 , 200 )
index.js:278 update_seeds: 4.35986328125ms
index.js:225 voronoi: 4.722900390625ms
index.js:182 draw cells: 2.341064453125ms
index.js:169 draw path: 0.356201171875ms
index.js:211 storing config version 9
gorhill commented 4 years ago

Never mind, I was testing master. I will test with issue_demo.

gorhill commented 4 years ago

The issue is that you are passing string values in the bbox parameter to Voronoi.compute():

voronoi.compute(this.seeds,{xl:0, xr:this.width, yt:0, yb:this.height})

this.width is "715" and this.height is "419", this should be 715 and 419.

https://github.com/WebSVG/voronoi/blob/8d65c1aeef43a24243b6fb51fe656add8e94546a/src/index.js#L218

wassfila commented 4 years ago

well done, you are right, I suspected it when figuring out that all seeds had float coordinates, but didn't expect that all of your code could handle it without complaining and then give it back, but it was the case. I fixed it now by simply parsing once for each width and height :

this.res = voronoi.compute(this.seeds,{xl:0, xr:parseFloat(this.width), yt:0, yb:parseFloat(this.height)})

I'm picking the width from an svg.clientWidth, but good to know. Thanks a lot, I'm really impressed, very quick resolution and your library has probably gone through a lot of testing and is quite solid. Thanks again !!!!