Search code examples
c#mathsurface

Find integer X and Y closest to a Z plane intersecting a nonlinear surface

For a nonlinear function f(x,y) I need to find the integer x and y that is closest to any real number plane along the f(x,y) axis that intersects the surface. x has a range from 0 to 255 and y has a range from 0 to 1023.

One way to accomplish this would be evaluate all 262,144 values for f(x,y) s.t. x and y are integers, sort it, and then do an efficient search but I was hoping for a more elegant solution in calculus or geometry.

My initial thought is to extract the curve that is created by the plane and the surface intersecting so that I can work in two dimensions, and then search along that curve for an x and y integer value that gets me closest to the curve. The problem is I don't know an efficient way to both determine which points are close and then which is closest.

Figure

This will need to be accomplished for about 32000 different f(x,y) values as quickly as possible so I am trying to find the most efficient way possible to calculate this on the fly. For example: the plane in the image is f(x,y)=3500.6 and the closest integer coordinate might be (112,432). Note: the axes x*8 and y*8

Solution

  • I think pre-computing is the way to go.

    Given a function f(x,y), compute all the z values and sort them:

    var xrange = Enumerable.Range(0, 256);
var yrange = Enumerable.Range(0, 1024);
var xyzValues = xrange.SelectMany(x => yrange.Select(y => new { x, y, z = f(x, y) })).OrderBy(xyz => xyz.z).ToList();

    Now use an extension method to binary search (taking Log2(262,144) = 18 comparisons) for each possible value stored in planes:

    var ans = planes.Select(p => new { Plane = p, xyz = xyzValues.BinaryFindDoubleBy(p, xyz => xyz.z) });

    Here is the extension method:

    public static class ListExt {
    public static T BinaryFindDoubleBy<T>(this List<T> src, double key, Func<T, double> selectorFn) {
        var lower = 0;
        var upper = src.Count;
        do {
            var pos = (lower + upper) / 2;
            var posKey = selectorFn(src[pos]);
            if (key < posKey)
                upper = pos;
            else
                lower = pos;
        } while (lower < upper - 1);

        return Math.Abs(selectorFn(src[lower])-key) < Math.Abs(selectorFn(src[upper])-key) ? src[lower] : src[upper];
    }
}