Calculating the Distance Between Points in Wrap Around (Toroidal) Space

https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/

by Atrix256 • 9 years ago

106 39 9 years ago

blog.demofox.org

herbstein• 9 years ago

I really enjoy this kind of post. It's short, simple and something most people could figure out by looking at the problem. Even then, it's still something that makes you go 'huh, how would you do that?'. Until the intuition about toroidal space kicks in, that is.

yosyp• 9 years ago

Isn't the topological manifold of the "wrap around" space described in the post spherical? A toroidal manifold would more complicated since the two generalized coordinates do not commute (order matters).

delinka2• 9 years ago

When wrapping rectangular sections, you create a torus. Spherical wraparound requires trapezoids.

tgb4• 9 years ago

I think you're mistaken. Torii come from non-rectangular regions, too, though they'll always be parallelograms. Spheres cannot arise like this from any shape.

Mathematically, you'd say that a sphere is simply connected and hence is its own universal cover and hence is not the quotient of a plane. Meanwhile, the universal cover of a torus is a plane and the fundamental domain of that covering can always be taken to be a parallelogram. The study of all possible such parallelograms is the standard example of a Teichmuller space [1] which is well-known recently due to both the use of the idea in "inter-universal Teichmuller theory" developed for the famous ABC conjecture work in 2012 as well as for being the subject of study of a winner of the most recent Fields medal [2] who is especially notable for being the first female recipient and was in the news again recently sadly for having died of cancer at a young age.

[1] https://en.wikipedia.org/wiki/Teichm%C3%BCller_space [2] https://en.wikipedia.org/wiki/Maryam_Mirzakhani

davidmanescu• 9 years ago

That manifold is a torus - you can walk in circles by walking West-East or North-South, each of which repeats every 1 distance unit. If you walk along the diagonal you get a repeating path every 1.4 distance units. All "great circle" paths (straight lines on a manifold) on a sphere repeat every 1 unit of distance.

SomeStupidPoint3• 9 years ago

I'm not sure what you mean, could you elaborate?

The post says that for a torus, which is a product space of two (or more?) circles, we can analyze the the distance "along each circle" from a shared origin for a chosen basis. One circle is our "x" and the other is our "y". (Contrast with a plane and two lines.)

This seems reasonable if the objects we're looking to measure our distance to are expressed in terms of those circles as well, since this allows us to simply put a measure on each circle and get a distance formula for any two points that behaves the way we would like.

Atrix256• 9 years ago

I'm out of my depth but I believe it's a torus because it's 2 cylinders, not circles?

amelius• 9 years ago

You cannot take a piece of paper (of any size) and wrap it around part of a donut.

vinchuco• 9 years ago

you're thinking of all boundaries mapping to a point.

in your interpretation, the red circle moving to the boundary would look like this https://cdn.pixabay.com/photo/2013/03/08/05/53/frame-91452_9...

Instead, look at how the arrow types match here: https://upload.wikimedia.org/wikipedia/commons/3/37/Projecti...

the side you choose to glue first matters (compare before/after) https://upload.wikimedia.org/wikipedia/commons/b/ba/Inside-o...

and the orientation of the arrows https://upload.wikimedia.org/wikipedia/commons/6/64/Klein_Bo... also matters https://upload.wikimedia.org/wikipedia/commons/5/5c/Klein_bo...

gus_massa2• 9 years ago

This example is not the surface of a real donut. It's an abstract surface.

In the surface of a real donut you have a lot of problems due to the curvature and the different sizes, so the calculation is very complicated. For example, in a real donut the circle at the top and at the bottom of the donut have different length that the two circles at the equator. In the torus in this page all the horizontal circles have the same length.

This is a magical torus, where all the horizontal and vertical circles have the same length. It also has no Gaussian curvature. You can't construct one of this magical torus as a surface in the 3D space, but you can construct one as a surface in the 4D space.

alde• 9 years ago

A flat torus can be isometrically embedded in 3D space with a continuously differentiable embedding. Visualising this embedding using computer graphics was the aim of a French project, completed in 2012. Turned out a flat torus in 3D has cool looking fractal structure. http://www2.cnrs.fr/en/2027.htm

ealloc• 9 years ago

A trick for dealing with periodic coordinates, not discussed in the article, is to convert each periodic coordinate (eg, an angle theta) into a pair of cartesian coordinates (x,y) on the circle, and then compute the distance in cartesian space. Ie, convert to x = cos(theta), y = sin(theta).

In the 2d example in the post, you would rescale the coordinates so the unit cell is from (-pi,pi) in both dimensions, and then the distance formula would be

    sqrt(((cos(x1) - cos(x2))**2 + ((sin(x1) - sin(x1))**2 + ((cos(y1) - cos(y2))**2 + ((sin(y1) - sin(y1))**2)

This works well for doing things like determining the "nearest" point to another point, and similar operations, and has some other nice properties.

(I forget the name of this system, but it is commonly used for calculations involving dihedral angles in MD simulations)

coherentpony• 9 years ago

It depends on how you define "distance". My initial thought when reading your comment was that you couldn't possibly use the Euclidean distance because you'd be drawing a path between two points on the circle that involves points _not_ on the circle.

taneq• 9 years ago

Using the Euclidean distance (Cartesian distance? I dunno) works because it's a monotonic underestimate of the distance along the circle. So you know if cartesian_dist(A, B) > cartesian_dist(A, C) then circle_dist(A, B) > circle_dist(A, C).

jacobolus• 9 years ago

For anyone curious, I’m guessing “MD simulation” means https://en.wikipedia.org/wiki/Molecular_dynamics

Folks who use this kind of distance measure might note that it also works well as a metric between angles (i.e. rotations) or between points on the projective line. For instance, see https://www.youtube.com/watch?v=oJAn--vsAzc (unfortunately not too self-contained a source)

phkahler2• 9 years ago

The may be a simpler way yet. If the coordinates are normalized from [0..1) and represented as 16bit integers with all bits fractional, you can simply take the difference x1-x2 and treat the result as signed. The result will be in the range [-0.5 .. 0.5). If you then square that number to get a 32bit result it will be correct for that component of the distance formula with no conditional code at all. Representation can be everything.

hexane360• 9 years ago

x1 = 0.9

x2 = 0

x1-x2 = 0.9 => -0.4

I don't see how this works.

pdkl95• 9 years ago

Add 0.5 to the result to convert the result in [-0.5 .. 0.5) back to [0..1)

    -0.4 + 0.5 => 0.1

phkahler2• 9 years ago

No, don't subtract 0.5. Just reinterpret (through a cast) the MSB as a sign bit: 0.9 => -0.1

gravypod• 9 years ago

You could also possibly use BAMS and ignore a negative space. You'd also likely save a few bytes on your location data as well (unsigned short instead of float).

hellofunk• 9 years ago

This is one of my favorite things to do on the train while on the way to work. I select two random passing objects out the window, and use a general assumption about the train's speed. Then I visualize these objects on a toroidal space, and after a few minutes, I draw the rest of the owl.

tomahunt• 9 years ago

This type of calculation is used on a very regular basis in molecular dynamics simulation. The wrap-around space is implemented using periodic boundary conditions. Calculating the distance between points is most often done using what is called the minimum image convention. In one dimension for a "box" of length L the minimum image distance between particles i and j: xij = xj - xi can be calculated through xij <- xij - L*nint(xij/L). This avoids any if statements.

vog• 9 years ago

This article essentially describes a modulo (%) operator for floats, which is well-defined and completely analogous to the integer modulo operation. I always wondered why these aren't part of the FPU command set, or at least part of modern programming languages, e.g.:

   1.0 % 5.0 = 1.0
   6.0 % 5.0 = 1.0
   7.0 % 5.0 = 2.0
   7.4 % 5.0 = 2.4
   7.4 % 1.0 = 0.4

With that in place, the torodial distance becomes a one-liner without any case distinctions (i.e. without ifs).

mkl• 9 years ago

I always wondered why these aren't part of the FPU command set, or at least part of modern programming languages

They are a part of modern (and not-so-modern) programming languages (% in Python, Rust, etc.). Even C from quarter of a century ago supports them (fmod). There are also at least two CPU instructions on x86, fprem and fprem1.

sp3322• 9 years ago

I couldn't even find an integer modulus operation when I was porting my fractal code to WebGL. https://www.shadertoy.com/view/MdSXWc

TrinaryWorksToo• 9 years ago

Did the % operator not work? I just tested 1 % 10 and it seemed to compile. I used the % operator in other shaders. Remember that WebGL is ultimately a sub and superset of C.

Calculating the Distance Between Points in Wrap Around (Toroidal) Space

Related Stories