Ask Your Question

Efficiently computing the distance from a point to a set

asked 2015-08-08 06:57:41 -0600

jford1906 gravatar image

updated 2015-08-09 08:19:58 -0600

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))

Additionally, define

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2015-08-08 11:03:18 -0600

tmonteil gravatar image

updated 2015-08-08 11:04:12 -0600

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2015-08-08 06:57:41 -0600

Seen: 56 times

Last updated: Aug 09 '15