Algorithm/principle of plotting implicit dependence f(x,y) = 0?

Question

infographics

Habralyudi! Let me know, give me ideas!
Draw on canvas, c++, pascal, etc. the graph of the function y = f(x) is as easy as shelling pears. We find out the ODZ of the argument and calculate y(x) with a certain step. We put a point, and so on.
But what about the graph f (x, y) = 0, if y (x) is not expressed? I understand that in the general case, probably, it can be solved only by enumeration of values ​​along the plane. What are the private solutions? Something like a brainstorm is needed. Thanks in advance!
I'll start the list:

• Iterating over x and y values ​​with a certain step. Long, but 100% :-)
  
• Finding the dependency y(x). Appropriate only when it can be expressed.
  
• Transition to polar coordinates, expression of radius from corner. Angle run from 0 to 2pi. Not always suitable, but it happens when y(x) is difficult to express.
  
• Tupper, Jeff. "Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables" www.dgp.toronto.edu/people/mooncake/papers/SIGGRAP...
  Thanks gribozavr. (for some reason it didn't work to insert a link in the question)
  
• finding function zeros by gradient method (descent)
  Thanks Lerq
  

Answer 1

It turns out that you need to find the intersection of the surface z \u003d f (x, y) with the plane z \
u003d 0. I know there are special numerical methods for finding these intersection contours, you need to look them up on the net.

Answer 2

I can suggest slightly changing the approach described above with gradients and a 3D description of the problem. Take XZ slices for each Y that corresponds to the pixels on the screen (keep in mind that we don't need to calculate the result with an accuracy that exceeds the resolution of the monitor). Then each slice will be a standard task for solving the equation f (x) = 0, here you can use some standard numerical iterative methods (Newton's method for example or something else) (which, in fact, use gradients in some that sense). The problem with such slices is that horizontal lines will not display well. You can try to consistently do with fixed X and Y, then it should turn out better. But all this is thinking out loud, so to speak, how I would approach the problem.

Answer 3

The best method from my point of view is
Tupper, Jeff. "Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables" www.dgp.toronto.edu/people/mooncake/papers/SIGGRAPH2001_Tupper.pdf

Answer 4

You can do so. If at least one pair of neighboring raster points is known, on which the function has different signs (for example, f(x,y)>0, f(x+1,y)<0), then the line passes between them. You can take one of the squares that bound this segment (for example, (x,y)-(x+1,y)-(x+1,y+1)-(x,y+1) ), and by checking the signs of the function f(x+1,y+1) and f(x+1,y), find out which second side of the square the graph will cross. Continue the process until the graph reaches the border of the area or closes.
To search for starting points, you can take values ​​at points (Nx,Ny) for some N, and already on this raster look for neighboring points with different signs: the graph will most likely pass between them. Small components may be lost in this case, but very serious methods would have to be used to find them - for example, solving the system f(x,y)=0, df(x,y)/dx=0 (its solutions will give the extreme points of all components) . You can apply Newton's method for this (also starting from all points (Nx, Ny)).

Answer 5

There is another interesting consideration for the 3D solution, inspired by the Hooke-Jeeves method.
Let us find one point of our graph (for example, by considering the section x = const and applying the Piyavsky method in it). Let's call this point the reference point. If we assume that we are looking for one continuous curve, then it can be argued that next to the found point there are others belonging to this curve. Let's take some step h and calculate the value of the function F(x, y) at several points at a distance h from the first one. Let's select a point with a value as close as possible to 0 for the next reference point and repeat the steps. Thus, we will, as it were, walk along the bottom of the ravine (if we take the F module) or simply along the slope, maintaining the height.
If you think carefully about how to look for the next point, then you can figure out how to go from the starting point in two directions at once (it will not necessarily be on the border, and the method described above will find the curve only on one side of the point).
Once we have an array of points, we can apply gradient descent to each of them to get a more accurate result. Since the points are already close to the curve, the possibility of rolling into local minima is practically excluded.
In general, in global optimization methods, it is customary to first localize the minimum points, and then run local optimization methods in the found areas. This works well here too.

Answer 6

Thanks everyone for the replies! It's a pity, as a solution, you can only put one post!