Hey all, I'm working on a project for school and I'd appreciate it if I could bounce a few ideas around.

Part of the project requires taking in a list of data with each value consisting of an xyz position in space and a uvw magnitude. The initial part of the project I'm concerned with is how to represent each point's uvw gradient.
As far as calculating the gradient goes, I think (though I'm not sure) that just taking the n most significant points for the gradient, up to all of the other points if desired, would be correct. However, would the gradient then be the sum of all the gradients, or the average?

Past that, I'm not sure how to deal with the data. I suppose I'd need a nested data structure, such as arrays of arrays or trees of trees to handle it. With arrays, I could make a 3 dimensional array and insert each value in its order positioned, and I think the only downside would be the poor insertion performance of arrays. On top of that, I think I'd need arrays for each point from there storing at least the n most significant points. I think this would allow me to quickly access any points, as well as compute the gradient for up to n-neighbors.

Alternatively, I could do binary search trees, but other than avoiding the insertion penalty of arrays they don't seem to offer most benefit, from what I can tell anyhow. It seems that in any case, they'll take significantly longer to access data than arrays would. If this was an optimization problem I suppose they'd be superior, but it doesn't seem there's any other way to approach this than brute force.

9 Years
Discussion Span
Last Post by Fox5

Take a look at the kd-tree and octree datastructures on Wikipedia. I think a kd-tree or octree would work for you. I'm assuming you have randomly scattered pairs of points, not some lattice of calculated values. (Which do you have?)

Be more clear in your description. First of all, why would you have trouble representing your gradient? It's a triple of real numbers. I don't know what language you're using, but this is easy to do.

As for calculating the gradient, I take it you mean you want to interpolate. Search for interpolation methods online. If linear interpolation is sufficient, you'd want to find the four nearest neighbors and use them to get a linear function of gradient w.r.t. position. (It's just solving a linear system of equations.) If you need some other kind of interpolation (approximating second derivatives, etc), I don't really know anything about those methods (I could make up a few on the spot that would work, but wouldn't be ideal), but if you told me what you were thinking, I could tell you if it makes sense.


Actually, the kd-tree looks great for what I'm doing.

As far as the gradient goes, I'm just not sure what the correct procedure for calculating it is. A gradient points in the direction of greatest change (and has the greatest magnitude of any direction), but I'm assuming to find this at a point you would have to treat your point as being part of many two particle systems. That is, find the gradient of the point you're interested in and every other point and then sum those gradients to find the true gradient.

Also, since it's 6 dimensional, 3d dimensional position plus 3 dimensional magnitude, would you take the gradient of the 6d vector or you take the gradient of just the uvw magnitudes, and weight those with respect to the distance (say using linear interpolation)?
Using the definition of the gradient I'd think the former, but it doesn't make logical sense to me. If two points are equal magnitude, the closer one should have a greater effect than the one farther away...actually I think I'm thinking about this wrong.
Rather than 6-dimensional, I should probably be thinking of the xyz position as x-initial, y-initial, z-initial, so the equations I'm interested in are:
(x-a_i)/u = (y-y_i)/v = (z-z_i)/w


I wouldn't say it's 6-dimensional. What does dimension even mean in this context? You have pairs of three-dimensional points.

What do you mean by 'gradient'? Do you know what you mean? The term 'gradient' generally refers to functions that map values in R^n into R (where R is the set of real numbers, R^n the set of n-tuples of real numbers). For functions that map value in R^3 into R^3 (which your set of points represents?) there is no such thing as the 'gradient'. There is however, the generalization of the gradient, known as the Jacobian (which is more like a generalization of the derivative of a single-variable function). You'd get a 3x3 matrix for the Jacobian of a function f : R^3 -> R^3.

So is your set of points a set of gradients of some other implicit function? Or is it a function of which you want to take the Jacobian? You seem to be unclear about what you want.


I'm honestly not sure what I want myself.

I have data with a bunch of points with associated strengths in each direction. I'm supposed to output an image of velocity vectors. I was thinking velocity in terms of rate of change and thus assumed the goal was to find the rate of change at any point, but now I'm not so sure. It may very well be that the uvw values are the velocity values of something, and all I'm required to do is plot the values. It hasn't been made clear to me one way or the other, all I know is that the data consists of points with associated magnitudes that may be actual velocities, temperatures, or whatever other measurements are taken.

This is for a course/internship I'm taking that's roughly on information visualization, and this is the first part of a larger project.

And from this wikipedia page on the gradient
The 2d fields at the top seem to be what I want to do, but extended to 3d. However, I'm not sure how to do that without a function but with just data.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.