4 ms·

They seem to have come with some nice algorithm to connect the graph dots. The problem: When you draw the graph using a naive formula putPixel(x, y(x)) you get

by zoul 15y ago

They seem to have come with some nice algorithm to connect the graph dots. The problem: When you draw the graph using a naive formula putPixel(x, y(x)) you get isolated dots. Therefore you have to draw tiny lines between the points to get a nice smooth curve instead of isolated dots. But then there is the question of which points to connect – for example in tan(x) you can’t connect the last point on the ‘upper right hand’ with the first one coming from the bottom. This is surprisingly hard to solve simply (at least it was for me). Most packages simply resign – try zooming out a tan(x) to see the erroneous vertical connecting lines. Google does it right even in high zoom ratios. How do they do it?

benjoffe 15y ago
Google fails after a few zoom outs for me, screenshot: http://i.imgur.com/Kss1x.png http://i.imgur.com/Kss1x.png One way is to set a threshold for whether or not to join the dots, if it's above the threshold perform a search between those points to see if they are between the dots or if they diverge, this search can be complicated or simple, google seems to use a fair bit of cpu power when zooming out on tan(x) so I'm guessing they're using a search here rather than some alternative 'clever' induction from the nature of the curve itself.
numlocked 15y ago
I got this message after zooming out tan(x) a ways: http://www.google.com/support/websearch/bin/answer.py?answer=1688281 http://www.google.com/support/websearch/bin/answer.py?answer... "Try to pan or zoom the function to a different region. The plotting algorithm detected one of the following: - Too many asymptotes - Too many transitions of the function from defined to undefined regions - Too many points on the graph that might not represent the function value currently due to high volatility" It looks like can actually detect when their graphing algo starts to break down.
nitrogen 15y ago
If you're using a CAS in your graphing system you can probably decompose the function, identify potentially problematic components (e.g. tan(x^2/5+2x)), and identify asymptotes or undefined areas directly using a database of undefined-generating functions. This would produce a list of X values for which the overall function is not defined. When your pixel plotting passes one or more of those X values, don't draw a line. If you pass several in a single pixel, give up.

by zoul 15y ago

benjoffe 15y ago

Google fails after a few zoom outs for me, screenshot: http://i.imgur.com/Kss1x.png http://i.imgur.com/Kss1x.png One way is to set a threshold for whether or not to join the dots, if it's above the threshold perform a search between those points to see if they are between the dots or if they diverge, this search can be complicated or simple, google seems to use a fair bit of cpu power when zooming out on tan(x) so I'm guessing they're using a search here rather than some alternative 'clever' induction from the nature of the curve itself.

numlocked 15y ago

I got this message after zooming out tan(x) a ways: http://www.google.com/support/websearch/bin/answer.py?answer=1688281 http://www.google.com/support/websearch/bin/answer.py?answer... "Try to pan or zoom the function to a different region. The plotting algorithm detected one of the following: - Too many asymptotes - Too many transitions of the function from defined to undefined regions - Too many points on the graph that might not represent the function value currently due to high volatility" It looks like can actually detect when their graphing algo starts to break down.

nitrogen 15y ago

If you're using a CAS in your graphing system you can probably decompose the function, identify potentially problematic components (e.g. tan(x^2/5+2x)), and identify asymptotes or undefined areas directly using a database of undefined-generating functions. This would produce a list of X values for which the overall function is not defined. When your pixel plotting passes one or more of those X values, don't draw a line. If you pass several in a single pixel, give up.