Detecting Singularities in a Graph

Question

I am creating a graphing calculator in Java as a project for my programming class. There are two main components to this calculator: the graph itself, which draws the line(s), and the equation evaluator, which takes in an equation as a String and... well, evaluates it.

To create the line, I create a Path2D.Double instance, and loop through the points on the line. To do this, I calculate as many points as the graph is wide (e.g. if the graph itself is 500px wide, I calculate 500 points), and then scale it to the window of the graph.

Now, this works perfectly for most any line. However, it does not when dealing with singularities.

If, when calculating points, the graph encounters a domain error (such as 1/0), the graph closes the shape in the Path2D.Double instance and starts a new line, so that the line looks mathematically correct. Example:

However, because of the way it scales, sometimes it is rendered correctly, sometimes it isn't. When it isn't, the actual asymptotic line is shown, because within those 500 points, it skipped over x = 2.0 in the equation 1 / (x-2), and only did x = 1.98 and x = 2.04, which are perfectly valid in that equation. Example:

In that case, I increased the window on the left and right one unit each.

My question is: Is there a way to deal with singularities using this method of scaling so that the resulting line looks mathematically correct?

I myself have thought of implementing a binary search-esque method, where, if it finds that it calculates one point, and then the next point is wildly far away from the last point, it searches in between those points for a domain error. I had trouble figuring out how to make it work in practice, however.

Thank you for any help you may give!

Answer 1

I think you are mostly on the right track.

1. I don't think figure 2 is mathematically incorrect.
2. For bonus points, you should have a routine which checks the diff between two consecutive values y1 & y2, and if it is greater than a threshold, inserts more points between y1 and y2, until no diff is greater than the threshold. If this iterative rountine is unable to get out of the while loop after 10 iterations or so, then that indicates presence of a singularity, and you can remove the plot between y1 and y2. That will give you figure 1.

Answer 2

You could use interval arithmetic ( http://en.wikipedia.org/wiki/Interval_arithmetic ) and calculate the interval of the function on each interval [x(i), x(i+1)]. If the resulting interval is infinite, skip that line segment. Speed-wise this should only be a couple times slower than just evaluating the function.

Answer 3

If morpehus's solution is too slow for you, you can consider all the absolute values of jumps between two consecutive function values, and try to identifies large outliers -- these will be the infinite jumps.

If you decide to try this, and need help, leave a comment here.

Answer 4

I finally figured out a way to have singularities graphed properly.

Essentially what I do is for every point on the graph, I check to see if it is inside the visible graphing clip. If I hit a point on the graph that is outside the visible clip, I graph that first point outside the clip, and then stop graphing any invisible points after that.

I keep calculating points and checking if they are inside the visible clip, not graphing ones that are outside the clip. Once I hit a point that is inside the clip again, I graph the point before that point, and then graph the current point.

I keep doing this until I've graphed the entire line. This creates the illusion that the entire line is begin drawn, when only the visible parts are.

This won't work if the window is large and the actual graph size in pixels is small, but it does suffice for me.