Distance Between Two Points Travelling on a Polar Graph Chart

Question

Brief Problem Explanation

Write a program to find the minimum distance between two points traveling only on rays emanating from the origin and circles centered on the origin.

Explanation of Premise

Now let's imagine we are on a plane, and on this plane we are only allowed to travel in special ways. We are allowed to travel on any ray emanating from the origin.

We can also travel on any circle centered at a circle

Now our goal is to travel from one point on this plane to another. However, we can't just travel in a simple Euclidian path, we can only do this if the points happen to fall on a ray emanating from the center.

We can travel on this one because it falls on a one of our rays.

We can also travel on circles centered at the origin.

Examples

Now here is the challenge:

We've got to get from one point to another in the shortest path; often this is a combination of traveling on circles and rays.

This, however, it could also be traveling on two rays.

Sometimes there exist two paths that travel the minimum distance.

Problem

Your challenge is to write a program that when given two points will give us the minimum distance between them if we follow these rules. The inputs can be given in either rectangular or polar forms and the output ought to be one number, the distance between.

Test Cases

(with rectangular input)

(1,1) (1,-1) -> ~ 2.22144
(0,0) (1, 1) -> ~ 1.41421
(1,0) (-0.4161 , 0.90929) -> ~ 2
(1,1) (1, 0) -> ~ 1.19961
(1,2) (3, 4) -> ~ 3.16609

Answer 1

Haskell, 49 48 bytes

(a!q)c r=min(q+r)$abs(q-r)+acos(cos$a-c)*min q r

Usage:

> let rect2polar (x,y)=(atan2 y x, sqrt(x^2+y^2))
> let test c1 c2=let [(a1,r1),(a2,r2)]=rect2polar<$>[c1,c2] in (a1!r1)a2 r2
> test (1,0) (-0.4161, 0.90929)
1.9999342590038496

Thanks to @Zgarb for saving a byte

Answer 2

JavaScript (ES6), 65 bytes

with(Math)(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s

Takes polar coordinates. Uses @Angs' trick for reducing an angle to between 0 and π. For rectangular coordinates, something like this works:

with(Math)g=(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s
with(Math)f=(x,y,v,w)=>g(hypot(y,x),atan2(y,x),hypot(w,v),atan2(y,v))

Answer 3

MATL, 22 bytes

|ttsGZ}/X/bX<*|bd|+hX<

Input is an array of two complex numbers.

Try it online! Or verify all test cases.

Explanation

|       % Implicitly input array and take absolute value of its entries
tt      % Duplicate twice
s       % Sum. This is the length of the path that follows the two radii
GZ}     % Push input again and split into the two numbers
/X/     % Divide and compute angle. This gives the difference of the angles
        % of the two points, between -pi and pi
bX<     % Bubble up a copy of the array of radii and compute minimum
*|      % Multiply and take absolute value. This is the arc part of the
        % path that follows one arc and the difference of radii
bd|     % Bubble up a copy of the array of radii and compute absolute
        % difference. This is the other part of the second path
+       % Add. This gives the length of second path
hX<     % Concatenate and take minimum to produce the smallest length.
        % Implicitly display

Answer 4

Ruby, 64 bytes

First, my submission. Lambda function with arguments distance 1, angle 1, distance 2, angle2.

->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

Now here's two different solutions of 66 bytes (excluding assignment f=) followed by my actual submission again at 64 bytes.

Solution 1:Using include Math, 66 bytes excluding f=
include Math;f=->r,a,s,b{[acos(cos(b-a)),2].min*[r,s].min+(s-r).abs}

Solution 2:Using complex number to define PI instead, 66 bytes excluding f=
f=->r,a,s,b{[d=(b-a).abs,?i.to_c.arg*4-d,2].min*[r,s].min+(s-r).abs}

SUBMISSION AGAIN, 64 bytes excluding f=
f=->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

The Submission is based on solution 2, but uses the identity (s-r).abs=s+r-[s,r].min*2 to shorten the code by 2 bytes, hence the -2 inside the brackets.

The other notable feature is the expression ?i.to_c.arg*4 = 2*PI without using include Math. If lower precision is acceptable this can be replaced by a literal.

Solution 2 commented in test program

f=->r,a,s,b{          #r,s are distances, a,b are angles for points 1 and 2 respectively.                       
    [d=(b-a).abs,       #From nearer point we can take arc of length d radians perhaps crossing zero angle to the ray of the further point
    ?i.to_c.arg*4-d,    #or go the other way round which may be shorter (?i.to_c.arg*4 == 2*PI, subtract d from this.)
    2].min*             #or go through the centre if the angle exceeds 2 radians.
  [r,s].min+          #Multiply the radians by the distance of the nearer point from the origin to get the distance travelled. 
  (s-r).abs           #Now add the distance to move along the ray out to the further point.
}

#test cases per question (given as complex numbers, converted to arrays of [distance,angle]+[distance,angle] (+ concatenates.)
#the "splat" operator * converts the array to 4 separate arguments for the function.
p f[*("1+i".to_c.polar + "1-i".to_c.polar)]
p f[*("0".to_c.polar + "1+i".to_c.polar)]
p f[*("1".to_c.polar + "-0.4161+0.90929i".to_c.polar)]
p f[*("1+i".to_c.polar + "1".to_c.polar)]
p f[*("1+2i".to_c.polar + "3+4i".to_c.polar)]

Output

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357

Answer 5

Mathematica 66 Bytes

This takes rectangular coordinates and can output an exact symbolic solution

Min[If[(m=Min[{p,q}=Norm/@#])>0,m*VectorAngle@@#,0]+Abs[p-q],p+q]&

Usage:

%/@{
{{1,1},{1,-1}},
{{0,0},{1,1}},
{{1,0},{-.4161,.90929}},
{{1,1},{1,0}},
{{1,2},{3,4}}
}

yields:

N@% yields:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Answer 6

Python 2, 164 126 125 132 bytes:

def A(a,b,c,d,p=3.1415926535):z=abs(a-c);M=lambda f:2*p*f*abs(b-d)/360.0;print min((a==c)*min(a+c,M(a))+(b==d)*z or'',M(a)+z,M(c)+z)

I am currently looking into golfing this more, though. Accepts polar coordinates. Should be called in the format A(r1,θ1,r2,θ2). Outputs a floating point value accurate up to 12 significant figures.

Try It Online! (Ideone)

A simple, straightforward implementation that calculates and outputs to STDOUT the minimum value out of an array of at most 3 values containing:

1. the minimum value out of either the sum of the two lengths (r1+r2) or the length of the arc connecting the two points iff r1==r2;
2. the difference between the two distances (abs(r1-r2)) iff θ1==θ2 (i.e. the two points are collinear);
3. if none of the previous 2 items are added, then an empty string ('') as apparently in Python a string is greater than any integer;
4. and 2 final values given from the distances traveled along a circle and a ray and vice-versa between the two points.

Answer 7

Wolfram Language (Mathematica), 47 bytes

MinMax@Abs@{##}.{Min[Abs[Arg@#-Arg@#2]-1,1],1}&

Try it online!

(beats the current 66-byte answer)

Take input as 2 complex numbers.

May have some issues if the input is symbolic. (e.g., Cos@2 + I Sin@2)