search

TaipanRex / pyvisgraph

Given a list of simple obstacle polygons, build the visibility graph and find the shortest path between two points
MIT License
221 stars 45 forks source link

Performance hit & js port #46

Closed rowanwins closed 5 years ago

rowanwins commented 5 years ago

Hi there @TaipanRex

I just wanted to say thanks for this awesome library and the associated blog writeups! I've been porting it across to js here

In doing so I was tinkering with the performance and found that the int() operation this line made a significant difference to my performance. On data with 1400 points calculating the graph takes either 4 seconds (using the existing float) vs 30 seconds (converting on the integer). I don't know if it's just the js parseInt function that is super slow but just thought I'd give you a heads up.

Anyway thanks again :) Rowan

TaipanRex commented 5 years ago

Hi,

I am not sure you can just remove the int(). The int(area)*T/T2 is code to truncate the resulting number. This is to avoid floating point representation errors (see #19 ). With python, int() is faster than round().

rowanwins commented 5 years ago

Thanks for the tip @TaipanRex - turns out I was using the slowest option, I'll try and reimplement with one of the other options and see how it fairs. Is there are rule of thumb as to the precision of the input data as to when floating point errors might appear?

rowanwins commented 5 years ago

Yep looks like Math.round is substantially faster than parseInt so I've re-added it in my version.