# Efficiently computing the distance from a point to a set

I'm working on a 3d vector field, where the derivative at each point is determined by a series, and each term of the series requires computing the distance from the point to a torus. Right now I'm only using 2-3 tori, and am discretizing each one, then computing a list of distances and taking the minimum. This is taking a really long time to run, and still isn't giving me the accuracy I need. Is there any way to improve efficiency in something like this?

The tori are defined via parametric equations, changing for each torus, and with moving centers.

Let c(n) = 2/3(4*(r+1)-4)

For every non-negative integer n, i,j in the range (0,2*pi), and k in {1/10, 2/10,...,9/10,1}, T_n is given by

x = 4^n*(2 + cos(j)*cos(i)
y = 4^n*(2 + cos(j))*sin(i) - c(n)
z = 4^n*k*sin(j)


if n is even and

x = 4^n*k*sin(j)
y = 4^n*(2 + cos(j))*sin(i) - c(n)
z = 4^n*(2 + cos(j)*cos(i)


if n is odd.

So far, I've been discretizing the tori using these equations, computing a list of Euclidean distances, and taking the minimum.

Here's the full equations for determining the vector field. First, I make a list of points for each torus. For any p = (x,y,z) in R^3, define a sequence of functions, with

h_0(p) = min(1, 1-d(p,T_0))
h_n(p) = min(1, d(p,T_(n-1)), 1-d(p,T_n))


G_n(p) = (y,-x,0)


if n is even and

G_n(p) = (0,-z,y)


if n is odd.

Finally, for each point p in R^3, the derivative at p is given by

dp = sum(G_n(p - (0,c(n),0))*h_n(p))


over all non-negative integers n. So far I've been restricting myself to the n = 0,1,2 case, but even then, I generally can't get the field to display unless I make the discretization really large, and that doesn't show the detail I need to help me find out where the alpha and omega limit sets are.

I'm not having any problems writing the code that will make these calculations, I'm just wondering if there is a more efficient way, rather than taking a list of points for the torus, and just computing the minimum over and over again.

edit retag close merge delete

Sort by » oldest newest most voted

You should give more details, since the answer depends on how your torus is defined. Is it smooth ? Is it given by some equation ? Cartesian or parametric ? Then you could think of computing derivatives and use some variational principle to find the distance analytically.

more