11
\$\begingroup\$

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.

shortest path between the origin and (5,5) with blocking rectangle with top left corner of (2, 4) and width & height of (2, 3)

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):

shortest path between the origin and (-3,5) with blocking rectangle with top left corner of (2, 4) and width & height of (2, 3)

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 , the shortest program wins.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ Apr 16, 2023 at 18:48
  • \$\begingroup\$ I assume you're allowed to run a line alone the edge of the rectangle? \$\endgroup\$
    – Neil
    Apr 16, 2023 at 18:52
  • \$\begingroup\$ @Neil Yes, you are. \$\endgroup\$ Apr 16, 2023 at 19:15
  • 2
    \$\begingroup\$ The second test case is incorrect. The rectangle doesn't intersect the segment (0, 0), (5, 5) so the answer should be sqrt(5^2+5^2) = 7.07106781186548. \$\endgroup\$
    – AndrovT
    Apr 18, 2023 at 18:26
  • 1
    \$\begingroup\$ @97.100.97.109 Could you please add a picture where path include 3 segments? For more generality. It is very easy to do with Geogebra \$\endgroup\$
    – lesobrod
    Apr 19, 2023 at 9:26

4 Answers 4

4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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):

enter image description here enter image description here enter image description here

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):

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 196 bytes

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

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:

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

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.

I₂ΣXθ²

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.

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

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

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

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

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

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

»I⌊Eυ⌊EζΣ⁺↔Eλ⁻ν§ιξE⟦ιEλ⁻§θξν⟧₂ΣXν²

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.