finding contour lines by exploring minimum number of points in 2D space

7 views (last 30 days)
I have a 2D graph with dim1 and dim2 represented as X and Y respectively. The range of X and Y are 1 to 100 with step size = 1. Hence there are 10000 points in the 2D space. Each point in the space is some function of X and Y values. Its not a linear or simple function. But the function is monotonically non-decreasing wrt X and Y. Since computing function value is time-consuming, I could not pre-compute function value of all 10000 points in advance. In this scenario, How to find all the points(x,y) which will give function value as some K by exploring only minimum points in the space and checking their function values in Matlab? Can it be solved using any optimization techniques?

Answers (2)

John D'Errico
John D'Errico on 25 Jun 2014
Edited: John D'Errico on 25 Jun 2014
This is something you will need to write. But it is not difficult.
1. So choose some line of points to evaluate the function at, a set of points that fall along a straight line that is parallel to one of the axes. If the function is known to be monotonic, then you know that any given contour crosses this line in at most ONE location. Essentially, you are creating a set of line segments defined by the points
z(i) = f(x0,y(i))
where x0 is some fixed value, and y(i) is a list of points in sequence.
2. For a given contour level, identify the line segment that it crosses from the above set of segments.
3. Determine by linear interpolation exactly where the contour crosses that line segment. If the set of points y(i) is reasonably closely spaced, linear interpolation will be adequate. If it is not, then you did not choose the set y(i) closely enough together.
4. Now choose ONE more point on each side of the line. I would recommend choosing the points to create equilateral triangles. Evaluate the function at the new point for each of these triangles. Determine where the contour crosses. It MUST cross on one side or the other, along one of the edges of the triangle. In the rare event the contour crossed at EXACTLY the vertex of that triangle, just be arbitrary and pick one of those edges. Again, interpolate the function linearly to find the point of intersection of the contour along that edge.
5. Now repeat the process, walking away. Essentially you can view this as flipping the equilateral triangle over and over again. The contour MUST cross one of the new edges at every step, until it falls off the edge of the world, or at least the region you care about.
When you are done, you will have created a set of line segments that describe the contour. Plot them, and go on to the next contour level.
Note that since the function is known to be "well-behaved" we need not worry about the contour crossing itself, or doing anything strange. And since we chose equilateral triangles of a fixed size, flipping them at each step, the algorithm must terminate after a reasonable time for any given contour.
As I said, pretty easy to do. Just follow my "flow chart" above. This algorithm will use a minimal set of new points, since each new triangle requires the evaluation of your function at exactly one new point, and it yields a new line segment along the contour at each step. Instead of 10000 function evaluations, we might be looking here at several hundred function evaluations to create a contour. Be careful of course to always re-use the information about the function that you have previously gained.
  1 Comment
The Game
The Game on 26 Jun 2014
Edited: The Game on 26 Jun 2014
Thank you Mr. John D'Errico for the nice and elaborate answer. But can you kindly explain the 4th point little further or can you give me a small example?

Sign in to comment.


Image Analyst
Image Analyst on 24 Jun 2014
I'm going to assume your values are in an array with the x value in column 1, the y value in column 2, and the function value in column 3.
column3 = yourArray(:, 3); % Extract the function values.
rowsToSelect = column3 == K; % Find rows where column 3 equals "some K"
% Now get the selected X and Y
xSelected = yourArray(rowsToSelect, 1); % Extract the selected X values.
ySelected = yourArray(rowsToSelect, 2); % Extract the selected Y values.
If the values are not integers, you should read the FAQ : http://matlab.wikia.com/wiki/FAQ#Why_is_0.3_-_0.2_-_0.1_.28or_similar.29_not_equal_to_zero.3F and change the code to be like this:
column3 = yourArray(:, 3); % Extract the function values.
% Find rows where column3 is within some tolerance value of "K".
rowsToSelect = abs(column3 - K) < someTolerance;
% Now get the selected X and Y
xSelected = yourArray(rowsToSelect, 1); % Extract the selected X values.
ySelected = yourArray(rowsToSelect, 2); % Extract the selected Y values.
  1 Comment
The Game
The Game on 24 Jun 2014
Edited: The Game on 24 Jun 2014
Thanks for your reply. But the point to note is I dont have function values precomputed for any X,Y combinations. Since function value computation takes lot of time, my question is provided the function value will be monotonically non-decreasing in the space, how can we check minimum number of points(by checking I mean here calculating function value at that point and checking whether it is equal to K) to identify points with same function value? The solution must not check function value of all points and it must utilize the fact that function values are monotonically non-decreasing in the space somehow.

Sign in to comment.

Categories

Find more on Contour Plots in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!