Avoid walking into a rectangle

Question

Given a rectangle, a start point, and an end point, find any path from start to finish that avoids the rectangle.

Example

Suppose you were at \$(1.5, -1.5)\$ and you needed to get to \$(2, 4)\$. However, there is a rectangle with upper left corner \$(1, 3)\$ and bottom right corner \$(4, 1)\$ in your way. It would look like this:

                             

There are lots of paths you could take to get from the (green) start to the (red) end:

• You could go via \$(-3, 3)\$.
• You could go to \$(-1.5, -0.5)\$ and then to \$(-1, 4)\$.
• Since you're infinitely thin (having perfected your workout routine), you could go via \$(4, 1)\$ and \$(4, 3)\$.
• Among many others.

Here's what those three options look like (click for full size):

Challenge

Given a starting point \$S\$, an end point \$E\$, and the coordinates for the upper left and bottom right corners of a rectangle (in any format reasonable for your language, including complex numbers if you wish), output a series of points \$A_1, A_2, \ldots, A_n\$ of any length such that the piecewise linear path \$S \rightarrow A_1 \rightarrow A_2 \rightarrow \ldots \rightarrow A_n \rightarrow E\$ does not intersect the interior of the rectangle. Note that:

• The start point and end point will not be inside the rectangle, nor on the edge or corner of the rectangle.
• Your path may touch the corners and edges of the rectangle, but must not intersect the rectangle's interior.
• You may output nothing, an empty list or similar if you wish to traverse \$S \rightarrow E\$ directly.
• You may assume that the rectangle has a strictly positive width and height.
• Your approach need not use the same number of points for all testcases.
• The path may have duplicate points, and may intersect itself, if you so wish.

Testcases

Here, (sx,sy) is the start point, (ex,ey) is the end point, (tlx,tly) is the top left corner of the rectangle and (brx,bry) is the bottom right corner. Note that from the spec we will always have tlx < brx and tly > bry.

Input                                  -> Sample output (one of infinite valid answers)
(sx,sy), (ex,ey), (tlx,tly), (brx,bry) -> ...

(1.5,-1.5), (2,4), (1,3), (4,1)        -> (-3,3)
                                       or (-1.5,0.5),(-1,4)
                                       or (4,1),(4,3)

(-5,0), (5,0), (-1,1), (2,-2)          -> (0,5)
                                       or (-5,1),(5,1)

(0.5,-2), (0.5,1), (2,2), (4,-3)       -> []
                                       or (0.5,-0.5)
                                       or (-1,-0.5)

Scoring

The shortest code in bytes wins.

Answer 1

JavaScript (ES6),  66  57 bytes

Expects (Sx,Sy,Ex,Ey,[Tx,Ty],[Bx,By]). Returns 3 points.

(S,s,E,e,T,B,[x,y]=T)=>[S>x&s<y?B:T,[B[0],y],E>x&e<y?B:T]

Try it online!

Method

The first point is \$(Bx,By)\$ if the start point is in the gray area or \$(Tx,Ty)\$ otherwise.

The second point is always \$(Bx,Ty)\$.

The third point is \$(Bx,By)\$ if the end point is in the gray area or \$(Tx,Ty)\$ otherwise.

Answer 2

Python 2, 49 bytes

lambda S,E,T,B:[(T*(L<B)+L+T)[::3]for L in S,T,E]

Try it online!

53 bytes

def f(S,E,T,B):
 for L in S,T,E:L[L>B]=T[L>B];print L

Try it online!

We make a path out of only horizontal or vertical segments, which means that each step changes one coordinate word-ladder-style.

Our path S->E always goes through the rectangle's top left vertex T.

S
?
T
?
E

We go from S to T via a pit stop that's a hybrid between them, changing either the first or second coordinate of S to that of T:

S0, S1      S0, S1
S0, T1  or  T0, S1
T0, T1      T0, T1

That is, we go from S to T by stepping vertical-then-horizontal or horizontal-then-vertical.

We pick one of them to avoid crossing the rectangle's interior, though in many cases either would work. Changing the first coordinate can only fail if we're directly right of the rectangle, and changing the second can only fail if we're directly above it. We can separate those two cases by checking whether we're left or right of B.

We similarly hybridize the end point E to connect it to T.

In the code, each of the three points S,T,E is hybridized with T and printed. For T, the hybridization leaves it unchanged. The 53-byte version of the code uses list mutation, which necessitates a non-lambda function. The 49-byte version above does it with list-slicing trickery (T*(L<B)+L+T)[::3], equivalent to [L+T,T+L][L<B][::3].

49 bytes

def f(B,*R):
 for L in R:L[L>B]=R[1][L>B];print L

Try it online!

Takes inputs in order B,S,T,E as two-element lists.

Answer 3

R, 86 82 94 81 79 bytes

Edits: -4 bytes by not outputting the start & end points, and then +12 -1 byte to fix bug (see below)

function(p,q,r,s=.5:-1)list(r[1+all(p*s>(z=r[1,]*s)),],r[2:3],r[1+all(q*s>z),])

Try it online!

Goes directly from starting point to one of the reachable specified rectangle corners*. Then goes to any of the non-specified corners (along the edge of the rectangle), and from there to a specified corner (this might or might not be a backtrack), from which it can go directly to the end point.

A slightly-modified version of the program can avoid any detours if the rectangle isn't actually in the way, for 90 bytes.

(* The bug fix: I initially assumed that the closest specified corner was always reachable, but this isn't necessarily the case if the rectangle is very wide & flat, and the starting-point is below it but close to the left-hand end, for instance).

Answer 4

C 125 bytes

z(a,b){printf("%d:%d|",a,b);}d(m,n,p,q,r,s,u,v){(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}

try it online

code explanation

z(a,b){printf("%d:%d|",a,b);}   // print routine
d(m,n,p,q,r,s,u,v)              // function take x0 y0 xa ya x1 y1 xb yb
                                // x0 y0  - top left corner of rectangle
                                // xa ya  - start point a
                                // x1 y1  - bottom right corner of rectangle
                                // xa ya  - end point b
{(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);
                                // 1st cross product to decide P1 (see below)
(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}
                                // 2nd cross product to decide P2 (see below)

method

if we go from a to b below then we can first choose one point on the rectangle that will definitely connect with a without crossing by looking to see which side of the diagonal a is on - below we choose P1. Similarly, by comparing the position of b with the other diagonal we can choose a second point P2 that will connect with b without crossing the rectangle - as indicated in the diagram. Now P1 and P2 will always connect without crossing the rectangle and we are done. The list is

P1

P2

(note to find which side of the diagonal we are we can use the cross product - if positive one side - if negative the other.)

Answer 5

Charcoal, 19 bytes

ＩＥ⟦θζη⟧Ｅι⎇⁼μ›ιε§ζμλ

Try it online! Link is to verbose version of code. I wanted to do this using at most two points but I couldn't come up with an easy way of deciding which direction to jump. I then tried adding a third point, but this quickly simplified into a port of @xnor's algorithm. Takes input as 4 tuples. Explanation:

  ⟦θζη⟧             List of points S, T, E
 Ｅ                  Map over list
        ι           Current point
       Ｅ           Map over coordinates 
            ›ιε     Is the current point to the right of B
          ⁼μ        If this is the appropriate coordinate
               §ζμ  Take the relevant coordinate from T
                  λ Otherwise keep the coordinate
Ｉ                   Cast to string
                    Implicitly print

Answer 6

Scala, 126 bytes

Modified from @Arnauld's answer.

---

Golfed version. Try it online!

type D=Double
type Q=(D,D)
def f(S:D,s:D,E:D,e:D,T:Q,B:Q)={val(x,y)=T;Seq(if(S>x&&s<y)B else T,(B._1,y),if(E>x&&e<y)B else T)}

Ungolfed version. Try it online!

object Main {
  type D=Double
  
  def f(S: D, s: D, E: D, e: D, T: (D, D), B: (D, D)): List[(D, D)] = {
    val (x, y) = T

    val first = if (S > x && s < y) B else T
    val second = (B._1, y)
    val third = if (E > x && e < y) B else T

    List(first, second, third)
  }

  def main(args: Array[String]): Unit = {
    println(f(1.5, -1.5, 2, 4, (1, 3), (4, 1)))
    println(f(-5, 0, 5, 0, (-1, 1), (2, -2)))
    println(f(0.5, -2, 0.5, 1, (2, 2), (4, -3)))
  }
}