Shortest Path Around Obstacle

Question

The task here is simple: given a target location on an XY grid, and a rectangle on that grid, find the length of the shortest path from the origin to the target which does not intersect the rectangle.

All parameter values are integers. You can assume that neither the target point nor the origin is inside or on the border of the rectangle.

The rectangle can be specified in any reasonable format -- e.g. (<left x coordinate>, <top y coordinate>, <width>, <height>) or (<left x coordinate>, <right x coordinate>, <top y coordinate>, <bottom y coordinate>). For the purposes of these examples I will use the format (<left x coordinate>, <top y coordinate>, <width>, <height>).

Your answer must be within one percent of the true answer for any input (ignoring errors due to floating point).

Here is the example where the target coordinate is (5, 5) (shown in green) and the rectangle has top left corner of (2, 4) and width & height of (2, 3) (shown in maroon). The shortest path is shown in orange.

In this case, the shortest path has length \$\sqrt{2^2+4^2} + \sqrt{1^2+3^2}\ \approx 7.63\$.

Note that the rectangle does not need to be obstructing the path between the origin and the target location -- take the same rectangle as the previous example, but with the target point of (-3, 5):

In this case, the answer is \$\sqrt{3^2 + 5^2} \approx 5.83\$.

Test cases

target x	target y	rectangle x	rectangle y	width	height	answer
5	5	2	4	2	3	7.6344136152
5	5	4	2	3	2	7.0710678119
-3	5	2	4	2	3	5.83095189485
0	0	100	-50	50	30	0
0	100	-1	-2	3	4	100
8	0	1	2	3	4	9.7082039325
8	0	1	3	3	5	9.7082039325

Standard loopholes are forbidden. Since this is code-golf, the shortest program wins.

Answer 1

Vyxal ḋ, 54 bytes

ΠÞx¾pƛ00"p⁰J;'2lƛ¹ΠǔI¨VYƛǔ-:ǔk+v*R¨£Þ•±≈;a;a¬;ƛ¯v∆/∑;g

Try it Online!

Takes input in the form of [[left_x, right_x], [bottom_y, top_y]], [[target_x, target_y]].

How?

The first step is to generate all polygonal chains that begin with \$(0,0)\$ and end with the target and the rest of the vertices are some (or none) of the vertices of the rectangle.

ΠÞx¾pƛ00"p⁰J;
Π             # cartesian product of [left_x, right_x] and [bottom_y, top_y]
 Þx           # all combinations without replacement
   ¾p         # prepend an empty list
     ƛ      ; # map:
      00"p    #   prepend [0, 0]
          ⁰J  #   append the target

The second step is to filter out the chains that intersect the interior of the rectangle. This is done by checking if any of the segments intersects a diagonal of the rectangle at an interior point.

The key observation is that if segments \$AB\$ and \$CD\$ are not on the same line, they intersect at an interior point iff \$ACBD\$ is a non-degenerate convex quadrilateral. This is checked by looking at the vectors \$C-A\$, \$B-C\$, \$D-B\$ and \$A-D\$ and for each adjacent pair rotating the second one by 90° and computing the dot product. If all the dot products have the same sign than the quadrilateral must be non-degenerate and convex.

'2lƛ¹ΠǔI¨VYƛǔ-:ǔk+v*R¨£Þ•±≈;a;a¬;
'                               ; # filter by:
 2l                               #   all overlapping pairs
   ƛ                       ;      #   map:
    ¹Π                            #     cartesian product of the second to last input
      ǔ                           #     rotate right
       I                          #     split into two halves, this gives us the two diagonals
        ¨VY                       #     interleave vectorized over the right operand
           ƛ             ;        #     map:
            ǔ-                    #       rotate right and subtract from itself
              :                   #       duplicate
               ǔ                  #       rotate right
                k+v*              #       multiply each by [1, -1]
                    R             #       reverse each
                     ¨£Þ•         #       zip and reduce each pair by dot product
                         ±        #       sign
                          ≈       #       are all equal?
                            a     #     any
                              a   #   any
                               ¬  #   not

The last step is to calculate the lengths of all the remaining chains and get the minimum.

ƛ¯v∆/∑;g
ƛ     ;  # map:
 ¯       #   subtract adjacent pairs
  v∆/    #   get the length of each vector
     ∑   #   sum
       g # minimum

Answer 2

Haskell, 414 bytes

import Data.List
t[[[a,b],[c,d]],[[e,f],[g,h]]]=((a-e)*(f-h)-(b-f)*(e-g))/((a-c)*(f-h)-(b-d)*(e-g))
w x=t x>0&&t x<1
v s t=not(w[s,t]&&w[t,s])
s[[x,y],[l,t],[w,h]]=minimum[sum$map(\[[a,b],[c,d]]->((c-a)^2+(d-b)^2)**0.5)q|
 c<-subsequences[[l,t],[l+w,t],[l+w,t-h],[l,t-h]],length c<3,
 p<-permutations c,let r=[0,0]:p++[[x,y]],let q=zipWith(\a b->[a,b])r(tail r),
 all(v[[l,t],[l+w,t-h]])q,all(v[[l+w,t],[l,t-h]])q]

Try it online!

Answer 3

Wolfram Language (Mathematica), 213 bytes

(p=Join[{c={0.,0.}},#1,{#2}];Min[ArcLength/@If[RegionDisjoint[Polygon@#1,l=Line@{c,#2}],{l},m=MeshCoordinates@ConvexHullMesh@p;s=m[[FindShortestTour[m][[2]]]];g=Position[s,#2][[1, 1]];Line/@{s[[;;g]],s[[g;;]]}]])&

Try it online!
Input must be float: array of all vertices and goal point.

There are three main cases (orange is convex hull of all points):

All of them catch by the next (ungolfed, self-explained) algorithm:

shortestPath[vertices_, goal_] :=
  Module[{polygon = Polygon@vertices,
    allPoints = Join[{{0., 0.}}, vertices, {goal}],
    directPath = Line[{{0., 0.}, goal}]},
   paths = If[RegionDisjoint[polygon, directPath],
     {directPath},
     convPoints = MeshCoordinates@ConvexHullMesh@allPoints;
     orderPoints = FindShortestTour[convPoints][[2]];
     goalPosition = Position[orderPoints, 6][[1, 1]];
     Line /@ {convPoints[[;; goalPosition]], 
       convPoints[[goalPosition ;;]]}
     ];
   Min[ArcLength /@ paths]
   ];

Fortunately it is also works for any convex polygon (last test):

Answer 4

Charcoal, 196 bytes

¿∨⊙θ¬∨ι∧›⁰§ηκ‹⁰⁺§ηκ§η⁺²κ¬‹⌈Ｅθ∧ι∕⁺§ηκ∧‹ι⁰§η⁺²κ↔ι⌊Ｅθ∨¬ι∕⁺§ηκ∧›ι⁰§η⁺²κ↔ιＩ₂ΣＸ貫≔⟦⟧ζＦ²Ｆ⟦⁰§η⁻³ι⟧Ｆ²«Ｆ¬›∧λ§θι§ηι⊞⎇λζυＥ…η²⎇⁼ξιν⁺νκＦ¬‹∧λ§θι⁺§ηι§η⁺²ι⊞⎇λζυＥ…η²⎇⁼ξι⁺ν§η⁺²ι⁺νκ»Ｉ⌊Ｅυ⌊ＥζΣ⁺↔Ｅλ⁻ν§ιξＥ⟦ιＥλ⁻§θξν⟧₂ΣＸν²

Try it online! Link is to verbose version of code. Takes as input the target and the rectangle using the bottom left corner and size (note that this differs slightly from the test cases in the question). Explanation:

¿∨⊙θ¬∨ι∧›⁰§ηκ‹⁰⁺§ηκ§η⁺²κ¬‹⌈Ｅθ∧ι∕⁺§ηκ∧‹ι⁰§η⁺²κ↔ι⌊Ｅθ∨¬ι∕⁺§ηκ∧›ι⁰§η⁺²κ↔ι

Use the Liang-Barksy algorithm to test whether the line intersects the rectangle; the first part of the expression covers the first two steps where the line is parallel to but not between two edges, while the rest calculates the intersections in terms of the parametric equation to see whether the line lies outside the rectangle.

Ｉ₂ΣＸθ²

If it does not intersect the rectangle then just output the Euclidean distance to the target.

«≔⟦⟧ζ

Otherwise, separately prepare to collect the corners of the rectangle visible from the origin and the target.

Ｆ²Ｆ⟦⁰§η⁻³ι⟧Ｆ²«

Loop over the two axes, the length along that axis, and the origin and the target point.

Ｆ¬›∧λ§θι§ηι⊞⎇λζυＥ…η²⎇⁼ξιν⁺νκ

If the point is to the left or below the rectangle respectively, then collect the corners on that "near" side of the rectangle.

Ｆ¬‹∧λ§θι⁺§ηι§η⁺²ι⊞⎇λζυＥ…η²⎇⁼ξι⁺ν§η⁺²ι⁺νκ

If the point is to the right or above the rectangle respectively, then collect the corners on that "far" side of the rectangle.

»Ｉ⌊Ｅυ⌊ＥζΣ⁺↔Ｅλ⁻ν§ιξＥ⟦ιＥλ⁻§θξν⟧₂ΣＸν²

For each pair of points, calculate the Euclidean distance from the origin to the first point, the taxicab distance to the second point, and the Euclidean distance to the target, and output the minimum sum.