Calculate Euclidean distance on a torus

Question

Euclidean distance between two lattice points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ on a plane is: \$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\$.

Imagine now a lattice N x N replicated infinitely many times next to itself. The two points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ also get replicated. Euclidean distance on a torus is then the minimal distance between all these points.

Input: x1, y1, x2, y2 and N. Arrange these in any convenient order or way (e.g. represent \$(3,4)\$, \$(5,6)\$ as 4 arguments 3, 4, 5, 6, two complex numbers \$3+4j\$, \$5+6j\$, a list [[3,4],[5,6]], a list [3,4,5,6] or anything that's not too bizarre). Coordinates must be integers in the range 0..N-1 or 1..N. The size of the torus (N) must be an integer (you can assume 1 < N < 100).

Output: a real number, with precision better than \$1\%\$.

Test cases:

x1	y1	x2	y2	N	Result
1	0	1	1	2	1.00
2	3	2	3	4	0.00
0	0	2	2	4	2.83
0	9	1	1	10	2.24
9	0	9	8	10	2.00
12	34	56	78	99	62.23
0	0	98	98	99	1.41

Answer 1

R, 40 bytes

\(a,b,N)sum(pmin((d=a-b)%%N,-d%%N)^2)^.5

Attempt This Online!

Input the two points as vectors a and b.

Answer 2

K (ngn/k), 18 16 bytes

-2 bytes thanks to @ngn.

Function taking input as f[N;(x1,y1;x2,y2)].

{%+/&/x*x!:y-|y}

Try it online!

y-|y Subtract the reversed list of points from the list of points. This results in component-wise distances in both directions.
x!: Take all values mod N. Updates x.
x* Square each value.
&/ take the element-wise minimum between positive and negative difference.
%+/ Sum, then take the square root.

Answer 3

Jelly,  8  7 bytes

ạ/«ạ¥ÆḊ

A dyadic Link that accepts the coordinates as a pair of pairs* of integers** on the left and the size as an integer** on the right and yields the Euclidean toroidal distance.

* I guess this will work in any integer number of dimensions too.

** Will work with floats too (up to floating point inaccuracies, of course).

Try it online! Or see the test-suite.

How?

\$\text{Distance} = \sqrt{\left (|x_1-x_2| \land ||x_1-x_2|-N| \right )^2 + \left (|y_1-y_2| \land ||y_1-y_2|-N| \right )^2}\$

ạ/«ạ¥ÆḊ - Link: Coordinates=[[x1, y1], [x2, y2]]; Size=N
 /      - reduce (Coordinates) by:
ạ       -   ([x1, y1]) absolute difference ([x2, y2])
              -> D = [|x1-x2|, |y1-y2|]
    ¥   - last two links as a dyad - f(D, N):
   ạ    -   (D) absolute difference (N) (vectorises)
              -> D2 = [||x1-x2|-N|, ||y1-y2|-N|]
  «     -   (D) minimum (D2) (vectorises)
              -> M = [min(|x1-x2|, ||x1-x2|-N|), min(|y1-y2|, ||y1-y2|-N|)]
     ÆḊ - norm = vector_length = square_root(sum(squared_values)))
            -> (min(|x1-x2|, ||x1-x2|-N|)^2 + min(|y1-y2|, ||y1-y2|-N|)^2)^(1/2)

Answer 4

julia, 43 bytes

Notice that for any point \$x\$, the \$N\$-toroidal distance from \$x\$ to \$(N/2, N/2)\$ is the Euclidean distance from \$\mathrm{mod}(x, N)\$ to \$(N/2, N/2)\$.

Hence, we can find the \$N\$-toroidal distance between \$a\$ and \$b\$ by computing the Euclidean distance from \$\mathrm{mod}(a-b+(N/2, N/2), N)\$ to \$(N/2, N/2)\$.

d(a,b,N)=sum(@. (mod1(a-b+N/2,N)-N/2)^2)^.5

Attempt This Online!

Answer 5

Wolfram Language (Mathematica), 38 33 bytes

nNorm[Min[#,n-#]&/@Abs[#-#2]]&

Thanks to @att!
Where  stands for \[Function]

Try it online!

Input: [N][{x1,y1}, {x2,y2}]

Answer 6

05AB1E, 11 10 bytes

αDŠ-ø€ßnOt

Try it online!

-1 thanks to @KevinCruijssen

Explanation

αDŠ-ø€ßnOt  # Implicit input
α           # Absolute difference between the first two inputs
 D          # Duplicate this pair
  Š         # Triple swap so the input is second
   -        # Subtract the absolute difference between the
            # first two inputs from the third input
    ø       # Zip this with the absolute difference
     ۧ     # Minimum of each inner pair
       n    # Square each
        O   # Sum the list
         t  # Square root the sum
            # Implicit output

Answer 7

JavaScript (ES7), 64 bytes

Expects (x1,y1,x2,y2,N).

(x,y,X,Y,n)=>((g=d=>(d*=d)<(q=n-d**.5)*q?d:q*q)(X-x)+g(Y-y))**.5

Try it online!

Commented

( x, y,       // (x, y) = coordinates of the 1st point
  X, Y,       // (X, Y) = coordinates of the 2nd point
  n           // n = size of the torus
) => (        //
  ( g = d =>  // g is a helper function taking d
    (d *= d)  // square d
    <         // and compare it with
    ( q =     // q defined as:
      n -     //   the difference between n and
      d ** .5 //   the square root of d (which is the
              //   absolute value of the original d)
    ) * q     // multiplied by itself
    ?         // if d is less than q²:
      d       //   return d
    :         // else:
      q * q   //   return q²
  )(X - x) +  // 1st call to g with d = X - x
  g(Y - y)    // 2nd call to g with d = Y - y
) ** .5       // square root of the sum

Answer 8

Factor, 52 bytes

[ v- 2dup n-v rot '[ [ _ rem ] map ] bi@ vmin norm ]

Try it online!

Takes input as N { x1 y1 } { x2 y2 }.

                   ! 10 { 9 0 } { 9 8 }
v-                 ! 10 { 0 -8 }
2dup               ! 10 { 0 -8 } 10 { 0 -8 }
n-v                ! 10 { 0 -8 } { 10 18 }
rot                ! { 0 -8 } { 10 18 } 10
'[ [ _ rem ] map ] ! { 0 -8 } { 10 18 } [ [ 10 rem ] map ]
bi@                ! { 0 2 } { 0 8 }   (apply quot to both points)
vmin               ! { 0 2 }
norm               ! 2.0

Answer 9

Python, 63 59 57 bytes

Edit: -4 bytes thanks to @Neil and -2 thanks to @xnor.

lambda x,y,X,Y,N:abs((x-X+(k:=N/2))%N-k+((y-Y+k)%N-k)*1j)

Attempt This Online!

Port of Damian Pavlyshyn's comment.

Answer 10

Ruby, 60 56 bytes

->a,b,n{(-4..4).map{|c|(a-b-n*(c%3-1+1i*c/=3)).abs}.min}

Try it online!

How?

Input as complex numbers.

(a-b).abs is the distance between a and b on the complex plane. We have to move b into the 8 adjacent spaces, and calculate distance between the original a and the new b, then take the minimum.

Iterating from -4 to +4 we get the offset table using c%3-1 for the real part, and c/3 for the imaginary part:

+-----+-----+-----+
| -4  | -3  | -2  |
|-1-i | -i  | 1-i |
+-----+-----+-----+
| -1  |  0  |  1  |
| -1  |  0  |  1  |
+-----+-----+-----+
|  2  |  3  |  4  |
|-1+i |  i  | 1+i |
+-----+-----+-----+

Answer 11

Python3, 79 bytes:

lambda x,y,X,Y,n:(min(abs(x-X),n-abs(x-X))**2+min(abs(y-Y),n-abs(y-Y))**2)**0.5

Try it online!

Answer 12

Thunno 2, 9 bytes

-AD⁶_Ọ²Sƭ

Explanation

-AD⁶_Ọ²Sƭ  # Implicit input
-A         # Absolute difference between first two inputs
  D        # Duplicate the pair
   ⁶_      # Subtract from the third input
     Ọ     # Elementwise dyadic minimum
      ²    # Square each
       S   # Sum the list
        ƭ  # Square root the sum
           # Implicit output

Screenshot

Answer 13

Vyxal ḋ, 10 9 bytes

ε:?$-Þ∵∆/

Thanks @TheThonnu!

Try it Online!

Input: [x1, y1] \n [x2, y2] \n N

Answer 14

Charcoal, 19 bytes

Ｉ₂ΣＥθ⌊Ｘ⁻↔⁻ι§ηκ⟦⁰ζ⟧²

Try it online! Link is to verbose version of code. Takes input as two pairs of coordinates and a number. Explanation:

    θ               First input
   Ｅ                Map over coordinates
          ι         Corrent coordinate
         ⁻          Subtract
            η       Second input
           §        Indexed by
             κ      Current index
        ↔           Absolute value
       ⁻            Vectorised subtract
              ⟦  ⟧  List of
               ⁰    Literal integer `0` and
                ζ   Third input
      Ｘ             Vectorised raise to power
                  ² Literal integer `2`
     ⌊              Take the minimum
  Σ                 Take the sum
 ₂                  Take the square root
Ｉ                   Cast to string
                    Implicitly print

Answer 15

SAS 4GL, 71 bytes (or 57)

1. The answer (in short, just "the point"):

data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

---

2. The answer and all details [with details ;-)]:

Input:

data input;
/* x1 y1 x2 y2 N Result */
input x y p q n r;
cards;
1   0   1   1   2   1.00
2   3   2   3   4   0.00
0   0   2   2   4   2.83
0   9   1   1   10  2.24
9   0   9   8   10  2.00
12  34  56  78  99  62.23
0   0   98  98  99  1.41
;
run;
/* to print input data */
proc print data=input;
run;

Immediately after "input code" run: Code:

data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

The:

data;set;...run;

part is mandatory for every SAS 4GL code so if we select only the "calculation" part:

a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);

it is 57 bytes ;-)

Code formatted:

data;
  set;
  a = abs(x - p);
  b = abs(y - q);

  d = sqrt(                   
            (a >< (N - a))**2 
          + (b >< (N - b))**2 
          );
run;

Comments:

• i><j is minimum of i and j, i**j is i to power j
• sqrt(expression) is the same number of bytes as (expression)**.5,
• brackets arounf N-b are necessary because >< takes precedence over substraction,
• result dataset is named DataX where X is the first integer not yet used for naming default dataset.

Log:

1    data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

NOTE: There were 7 observations read from the data set WORK.INPUT.
NOTE: The data set WORK.DATA4 has 7 observations and 9 variables.
NOTE: DATA statement used (Total process time):
      real time           0.00 seconds
      cpu time            0.00 seconds

---

Answer 16

Scala, 137 96 bytes

Saved 41 bytes thanks to the comment of @corvus_192

---

Try it online!

import math._
(x,y,X,Y,n)=>sqrt(pow(min(abs(x-X),n-abs(x-X)),2)+pow(min(abs(y-Y),n-abs(y-Y)),2))

Answer 17

Japt, 13 bytes

íaV ËmDaWÃx²¬

Try it

íaV ËmDaWÃx²¬     :Implicit input of arrays U=[x1,y1] & V=[x2,y2] and integer W=N
í V               :Interleave U & V
 a                :  Reducing each pair by absolute difference
    Ë             :Map each D
     m            :  Minimum with
      DaW         :    Absolute difference of D & W
         Ã        :End map
          x       :Reduce by addition after
           ²      :  Squaring each
            ¬     :Square root

Answer 18

Arturo, 57 bytes

$=>[x:abs&-&y:abs&-&n:&sqrt+^min@[x,n-x]2(min@[y,n-y])^2]

Try it

Takes input as x1 x2 y1 y2 N.

$=>[                 ; a function
    x:abs&-&         ; assign absolute value of first arg minus second arg to x
    y:abs&-&         ; assign absolute value of third arg minus fourth arg to y
    n:&              ; assign fifth arg to n
    (min@[y,n-y])^2  ; minimum of y and n-y squared
    ^min@[x,n-x]2    ; minimum of x and n-x squared
    +                ; add
    sqrt             ; square root
]                    ; end function

Answer 19

BQN, 17 bytes

{√+´×˜⌊´𝕨|-⊸⋈-´𝕩}

Try it at BQN REPL

{√+´×˜⌊´𝕨|-⊸⋈-´𝕩}  # function taking N as left arg (𝕨)
                    # and [[x1,y1],[x2,y2]] as right arg (𝕩):
              -´𝕩   # vectorized fold-subtract: [x1-x2,y1-y2]
          -⊸⋈      # joined to negative of itself: [[x1-x2,y1-y2],[x2-x1],[y2-y1]]
        𝕨|          # all modulo N
      ⌊´            # vectorized fold-minimum
    ט              # vectorized multiply each element by itself
  +´                # sum (fold-addition)
 √                  # square-root

Answer 20

Scala, 104 bytes

Golfed version. Try it online!

(a,b,N)=>{val d=a.zip(b).map{case(p,q)=>(p-q+N)%N};math.sqrt(d.map(r=>math.pow(math.min(r,N-r),2)).sum)}

Ungolfed version. Try it online!

object Main {

  def main(args: Array[String]): Unit = {
    println(toroidal_dist(Array(1, 0), Array(1, 1), 2))    // 1
    println(toroidal_dist(Array(2, 3), Array(2, 3), 4))    // 0
    println(toroidal_dist(Array(0, 0), Array(2, 2), 4))    // 2.83
    println(toroidal_dist(Array(0, 9), Array(1, 1), 10))   // 2.24
    println(toroidal_dist(Array(9, 0), Array(9, 8), 10))   // 2
    println(toroidal_dist(Array(12, 34), Array(56, 78), 99)) // 62.23
    println(toroidal_dist(Array(0, 0), Array(98, 98), 99)) // 1.41
  }

  def toroidal_dist(a: Array[Int], b: Array[Int], N: Int): Double = {
    val d = a.zip(b).map { case (ai, bi) => (ai - bi + N) % N }
    math.sqrt(d.map(di => math.pow(math.min(di, N - di), 2)).sum)
  }
}