Euclidean distance on projective plane

Question

Motivated by this challenge

Background

Let we have a square sheet of flexible material. Roughly speaking, we may close it on itself four ways:

enter image description here

Here the color marks the edges that connect and the vectors indicate the direction. The sphere and torus are obtained without flipping the sides, Klein bottle — with one flipping edge, and projective plane with both.

Surprisingly torus, not a sphere, in many senses is the simplest construct. For example, you can't comb a hairy ball flat without creating a cowlick (but torus can).
This is why torus is often used in games, puzzles and research.

Specific info

This is a separate picture for fundamental polygon (or closing rule) of projective plane (for 1..N notation):
enter image description here

Neighborhood of [1, 1] cell for N x N lattice:
enter image description here

Example how to find distance for points (2, 4) and (5, 3) in 5 x 5 projective plane:
enter image description here
Green paths are shortest, so it is the distance.

Task

For given two points and size of lattice,
find euclidean distance between points on the projective plane.

I/O

Flexible, in any suitable formats

Test cases

For 1..N notation
N, p1, p2 → distance For a better understanding, also indicated distance on torus (for same points and size):

5, [1, 1], [1, 1] → 0.0 (0.0)
5, [2, 4], [5, 3] → 2.24 (2.24)
5, [2, 4], [4, 1] → 2.0 (1.41)
10, [2, 2], [8, 8] → 4.12 (5.66)
10, [1, 1], [10, 10] → 1.0 (1.41)
10, [4, 4], [6, 6] → 2.83 (2.83)

• Neil: In your diagram, I think the (2, 4) and (5, 3) on the right are in the wrong place - the (5, 3) should be on the same row as the one on the left and the (2, 4) doesn't fit on the diagram because it's not wide enough.
• lesobrod: @Neil Yes, it looks like that, I’ll check and fix

Answer 1

julia, (削除) 104 (削除ここまで) 97 bytes

This solution uses the quotient space metric. For the projective plane, if \$\sim\$ is the equivalence relation induced by the edge identification (i.e. \$(p, 0) \sim (N-p, N); (0, p) \sim (N, N-p)\$) and \$d\$ is the Euclidean metric, then the projective plane metric is $$ d'(a, b) = \min_{w \sim w'} [d(a, w) + d(b, w')]. $$

To implement this, we create two grids \$x\$ and \$y\$ spanning \$[0, N]^2\$ such that \$x_{ij} \sim y_{ij}\$ and compute \$d(a, x_{ij}) + d(b, y_{ij})\$ for each corresponding pair of grid entries.

We make the vertical spacing between grid points \0ドル.005\$ to make sure that the result is correct to two decimal places.

u&v=((h=u-v.-.5)'h)^.5
g(N,a,b)=minimum(w->a&w+b&((N.-2w)any(w.%N.==0)+w),vcat.((r=0:.005:N)',r))

Attempt This Online!

Thanks to MarcMush for a 7-byte improvement!

How?

# u&v is the distance between u-0.5 (centre of cell u) and v.
u&v = ((h = u - v .- .5)'h)^.5
# Minimise the function w -> d(a, w) + d(b, w')
g(N, a, b) = minimum(
 # (N .- 2w)any(w .% N .== 0) + w is N-w on the edges of x and w otherwise.
 w -> a&w + b&((N .- 2w)any(w .% N .== 0) + w),
 
 # Map over a grid of pairs [x1, x2] spanning [0, N]^2.
 vcat.((r = 0:.005:N)', r)
)

• lesobrod: Very interesting approach! Looks like it's suitable for more complicated topologies
• MarcMush: 97 bytes

Answer 2

Jelly, 20 bytes

_~jUŒHƲ€N9ṭ"_þ/ẎÆḊ€Ṃ

A dyadic Link that accepts the size on the left and a pair of pairs (the points) on the right and yields the Euclidean distance of the projective plane.

Try it online! Or see the test-suite.

How?

_~jUŒHƲ€N9ṭ"_þ/ẎÆḊ€Ṃ - Link: Size = S; Points = [[x1, y1], [x2, y2]]
_ - {Size} subtract {Points} -> [[S-x1, S-y1], [S-x2, S-y2]]
 € - for each of these pairs, [a, b]:
 Ʋ - last four links as a monad:
 ~ - bitwise NOT (vectorises) -> [-1-a, -1-b]
 U - upend -> [b,a]
 j - join -> [-1-a, b, a, -1-b]
 ŒH - halve -> [[-1-a, b], [a, -1-b]]
 N - negate -> [[a+1, -b], [-a, b+1]]
 9 - chain's right argument -> [[x1, y1], [x2, y2]]
 " - zip with:
 ṭ - tack -> [[[S-x1+1, y1-S], [x1-S, S-y1+1], [x1, y1]],
 [[S-x2+1, y2-S], [x2-S, S-y2+1], [x2, y2]],
 ]
 / - reduce by:
 þ - table with:
 _ - subtraction
 Ẏ - tighten
 ÆḊ€ - vector norm of each
 Ṃ - minimum

Answer 3

Python 3, 94 bytes

lambda n,X,Y,x,y:min(abs(X-a+(Y-b)*1j)for k in[-n,n]for a,b in[(x,y),(n+1-x,y+k),(x+k,n+1-y)])

Try it online!

Easier to understand as:

lambda n,X,Y,x,y:min(abs(X-a+(Y-b)*1j)for a,b in[(x,y),(n+1-x,y-n),(n+1-x,y+n),(x-n,n+1-y),(x+n,n+1-y)])

Try it online!

Fixes one point in place, and picks the closest version of the other point out of 5 options -- the original and the four reflections across the edges of the square. There's no need to consider diagonally-adjacent copies because they're always further from the fixed point than the original.

Answer 4

Python, 83 bytes (-35 thanks to @xnor)

lambda N,A,B:min(map(abs,(B-A,C:=B-1j*N-~N-2*B.real-A,D:=1+1j-C-2*A,C+2j*N,D+2*N)))

Attempt This Online!

Obsolete Python, 118 bytes

lambda N,A,B,o=.5+.5j:min(map(lambda x:abs(A-o-x),[B:=B-o,C:=N/o+B-2*B.real,-B,2*N-B,2j*N-B,4*N*o-B,-C,C+2j*N,2*N-C]))

Attempt This Online!

Expects input coordinates as complex numbers.

• xnor: It looks like your code checks 9 options, which I'll venture are a 3x3 box around the original square? If so, I think you don't have to check the diagonally-adjacent ones because the original copy of the point is always closer.
• loopy walt: Thanks, @xnor. I'm having a hard time getting intuition for this parameterization.

Answer 5

Python3, 458 bytes

R=range
E=enumerate
def T(d,x,y,X,Y):
 if y%2:d=[[(*a,W+Y*len(d),k)for k,(*a,_,_)in E(i[::-1])]for W,i in E(d)]
 if x%2:d=[[(*a,W,k+X*len(i))for k,(*a,_,_)in E(i)]for W,i in E(d[::-1])]
 return[j for k in d for j in k]
def f(n,p,P):
 d=[[(i,j,i-1,j-1)for j in R(1,n+1)]for i in R(1,n+1)];O=[*T(d,0,0,0,0),*T(d,0,1,0,-1),*T(d,1,0,1,0),*T(d,0,1,0,1),*T(d,1,0,-1,0)]
 return min(((X-x)**2+(Y-y)**2)**0.5 for a,b,x,y in O for A,B,X,Y in O if[a,b]==p and[A,B]==P)

Try it online!

• ceilingcat: 433 bytes

Answer 6

Charcoal, 41 bytes

⊞υηF⟦θ±θ⟧F2⊞υEη⎇=κμ−⊕θλ+λιI2⌊EυΣXEι−λ§ζμ2

Try it online! Link is to verbose version of code. Takes the size and the two points as input. Explanation:

⊞υη

Push the first point to the predefined empty list.

F⟦θ±θ⟧F2

Loop over each orthogonal direction.

⊞υEη⎇=κμ−⊕θλ+λι

Push the transform of the point in that direction to the list.

I2⌊EυΣXEι−λ§ζμ2

Output the minimum Euclidean distance from the second point to any of the five points inthe list.

I tried writing it as a single expression but it still came out to 41 bytes:

I2⌊E⊞OE4Eη⎇%+ιμ2−⊕θλ⎇÷ι2+λθ−λθηΣXEι−λ§ζμ2

Try it online! Link is to verbose version of code.

Answer 7

JavaScript (ES6), 104 bytes

Saved 9 bytes by refactoring in a way similar to what xnor did

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

(N,x,y,X,Y)=>Math.min(...(g=q=>[x,x+q,N-x].map((v,i)=>Math.hypot(X-v,Y-[y,N-y,y+q][i])))(N++),...g(1-N))

Try it online!

Answer 8

Scala, 168 bytes

Golfed version. Try it online!

def f(N:Int,x:Int,y:Int,X:Int,Y:Int)={val(a,b)=(x-X,Y+y-N-1);(Seq(a,a-N,X+x-N-1,X+x-N-1,X+x-N-1,a+N)zip Seq(y-Y,b,y-Y-N,N-b,y-Y+N,b)).map{case(i,j)=>sqrt(i*i+j*j)}.min}

Ungolfed version. Try it online!

import scala.math.{sqrt, min}
object Main {
 def f(N: Int, x: Int, y: Int, X: Int, Y: Int): Double = {
 val a = Array(x - X, x - X - N, X + x - N - 1, X + x - N - 1, X + x - N - 1, x - X + N)
 val b = Array(y - Y, Y + y - N - 1, y - Y - N, N - (Y + y - N - 1), y - Y + N, Y + y - N - 1)
 val distances = (a zip b).map{ case (i, j) => sqrt(i*i + j*j) }
 distances.min
 }
 def main(args: Array[String]): Unit = {
 println(f(5, 1, 1, 1, 1)) // 0.0
 println(f(5, 2, 4, 5, 3)) // 2.24
 println(f(5, 2, 4, 4, 1)) // 2.0
 println(f(10, 2, 2, 8, 8)) // 4.12
 println(f(10, 1, 1, 10, 10)) // 1.0
 println(f(10, 4, 4, 6, 6)) // 2.83
 }
}