Ray's intersecting lines

Question

Ray has created some ASCII lines which he is using to draw with on a canvas.

His canvas can be any width and height between 1 to 100 characters (the borders do not count towards these dimensions). He has created the below artwork as an example.

+==============+
[\ / ]
[ \ / ]
[ \ / ]
[ \ ]
[| \ ]
[| \ ]
[ -------------]
+==============+

Ray wants to work out if there are any lines on his canvas which, if extended to the canvas bounds, would intersect another line.

Rules

Only these characters will be used for the lines:

-\|/

Only these characters will be used for the borders:

+=[]

An intersection counts if any two lines would occupy the same cell, or alternatively if they would pass through each other, if they were extended to the canvas bounds. See the last two non-intersecting test-cases for an important edge case in this regard.

Test Cases

################
 Intersecting
################
1.
+==============+
[ / ]
[ \ / ]
[ \/ ]
[ \ ]
[ ]
[ ]
[ ]
[ ]
+==============+
2.
+==============+
[/ ]
[ | ]
[ | ]
[ | ]
[ ]
[ --- ]
[ ]
[ ]
+==============+
3.
+==============+
[ ]
[ \ ]
[ ]
[ / ]
[ ]
[ ]
[ /]
[ ]
+==============+
4.
+==============+
[ ]
[ / ]
[ / ]
[ ]
[ ]
[ ]
[ ]
[ - ]
+==============+
5.
+==============+
[ - ]
[ - ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ \ - ]
+==============+
################
Non-intersecting
################
1.
+==============+
[ / ]
[ //// ]
[ ]
[ ]
[ / ]
[ ]
[ / ]
[ ]
+==============+
2.
+==============+
[ ----- ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ \ / ]
[ ]
+==============+
3.
+==============+
[ ]
[ ]
[ ]
[ ]
[ ]
[ |||||||||]
[\ ]
[ \ ]
+==============+
4.
+==============+
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
+==============+
5.
+==============+
[ / \/ \\ ]
+==============+
6.
+==============+
[ \ /| ]
[ \ / | ]
[ \/ | ]
+==============+
7.
+=========+
[/ /\ \]
[\ \/ /]
+=========+
8.
+=========+
[ /\ ]
[ ]
+=========+
9.
+=========+
[ /\ ]
+=========+
10.
+=+
[/]
[\]
[ ]
[-]
+=+
11.
+=+
[ ]
+=+
12.
+=+
[/]
+=+
13.
+====+
[\ /]
+====+
14.
+====+
[/ \]
+====+
15.
+=+
[/]
[ ]
[ ]
[\]
+=+
16.
+=+
[\]
[ ]
[ ]
[/]
+=+
17.
+=========+
[/ \]
[\ /]
+=========+

Write a program or function to determine if the canvas has lines which, when extended to the canvas bounds, are intersecting or not

Input

The canvas, including borders and all the lines. This can be formatted however you want (as a list of strings, a list of characters, a string, etc) and can be provided how you deem fit (stdin, a function input, etc)

Output

Indicate if any two (or more) lines do or do not intersect with any of the following methods:

• Return or print true or false as booleans or strings (any capitalisation)
• Return or print 1 or 0 as numbers or strings
• Return or print yes or no (any capitalisation)

Scoring

Standard code golf rules.

Edge Cases / FAQ

• Test cases with lines formed from the same character intersecting will never be provided. E.g.:

+==============+
[ ]
[ --- --- ]
[ ]
[ ]
[ ]
+==============+

Worked Examples

1. Intersects at X
+==============+ +==============+
[ ] [ \ / ]
[ \ ] [ \ / ] 
[ ] [ \ / ] 
[ / ] [ \ / ] 
[ ]-->[ \ / ] 
[ ] [ X ]
[ /] [ / \ /] 
[ ] [ / \ / ] 
+==============+ +==============+
2. Pass through each other
(counts as intersection)
+==============+ +==============+
[ / ] [ \ / ]
[ \ / ] [ \ / ]
[ \/ ] [ \/ ]
[ \ ] [ /\ ]
[ ]-->[ / \ ]
[ ] [ / \ ]
[ ] [/ \ ] 
[ ] [ \ ] 
+==============+ +==============+
3. Intersects at X
+==============+ +==============+
[/ ] [/ | ]
[ | ] [ | ]
[ | ] [ | ]
[ | ] [ | ]
[ ]-->[ | ]
[ --- ] [--X-----------]
[ ] [ | ]
[ ] [ | ]
+==============+ +==============+
4. No intersection
+==============+ +==============+
[ ] [ |||||||||]
[ ] [ |||||||||]
[ ] [ |||||||||]
[ ] [ |||||||||]
[ ]-->[ |||||||||]
[ |||||||||] [ |||||||||]
[\ ] [\ |||||||||]
[ \ ] [ \ |||||||||]
+==============+ +==============+

• Arnauld: Suggested non-intersecting test case.
• Jonathan Allan: ...and the same, but just its corners.
• tata: What outputs are expected for these testcases? Current answers disagree with each other. \$ {\begin{array}{cccccc} \text{+}&\text{=}&\text{=}&\text{=}&\text{=}&\text{+} \\ \text{[}&\text{\\}&\text{ }&\text{ }&\text{/}&\text{]} \\ \text{+}&\text{=}&\text{=}&\text{=}&\text{=}&\text{+} \end{array}} \$ and \$ {\begin{array}{cccccc} \text{+}&\text{=}&\text{=}&\text{=}&\text{=}&\text{+} \\ \text{[}&\text{/}&\text{ }&\text{ }&\text{\\}&\text{]} \\ \text{+}&\text{=}&\text{=}&\text{=}&\text{=}&\text{+} \end{array}} \$
• Ted: @tata those are non intersecting.
• tata: I would suggest to adding these 2 testcases, plus with another 2 by rotating them 90 degree.

Answer 1

JavaScript (ES7), 167 bytes

Expects a matrix of ASCII codes. Returns a Boolean value.

m=>m.some((r,y)=>r.some((c,x)=>c**3&72&&L.some(([a,b,c])=>(g=(v,q)=>(v/=a*B-A*b)>.5&v<q.length-1.5)(a*C-A*c,m)&g(c*B-C*b,r),L.push([A=c%7-3,B=c/3&2,C=A*x+B*y]))),L=[])

Try it online!

Method

Summary

We scan the input matrix from top-left to bottom-right, storing the equation parameters of the detected lines along the way and testing if any new line intersects a previous one within the canvas.

Detecting line intersections

For each line character \$c\$ at position \$(X,Y)\$ in the input matrix, we push in the array \$L\$ the parameters \$(A,B,C)\$ of the equation of the corresponding line:

$$Ax+By=C$$

where \$C=AX+BY\$ in all cases, and \$A\$, \$B\$ are defined as follows:

Character	A	B	Equation
\	\$-1\$	\1ドル\$	\$-x+y=C\$
/	\1ドル\$	\1ドル\$	\$x+y=C\$
-	\0ドル\$	\1ドル\$	\$y=C\$
|	\1ドル\$	\0ドル\$	\$x=C\$

For each line already stored in \$L\$ with parameters \$(a,b,c)\$, we compute its intersection point \$(x,y)\$ with the new line:

$$x=\frac{cB-Cb}{aB-Ab}$$ $$y=\frac{aC-Ac}{aB-Ab}$$

and test whether we have \$x\in(1/2,W-3/2)\$ and \$y\in(1/2,H-3/2)\$, where \$H\$,\$W\$ are the dimensions of the matrix.

NB: Although the above definitions of \$x\$ and \$y\$ are valid only if \$aB-Ab\neq0\$, this will also work as-is in the JS implementation for \$aB-Ab=0\$ (we'll get either NaN or +/-Infinity, which will make the tests fail as expected).

Character processing

The table below shows the formulas that are used to determine if an ASCII code matches a line character and, if it does, which values of \$A\$ and \$B\$ must be used (note that both values are doubled, which doesn't change the definition of the line).

Character	Type	c = ASCII code	c**3&72	A = c%7-3	B = c/3&2
+	border	43	0	n/a	n/a
=	border	61	0	n/a	n/a
[	border	91	0	n/a	n/a
]	border	93	0	n/a	n/a
	background	32	0	n/a	n/a
\	line	92	64	-2	2
/	line	47	8	2	2
-	line	45	64	0	2
|	line	124	64	2	0

Answer 2

Jelly, (削除) 59 (削除ここまで) 44 bytes

-13 bytes thanks to Unrelated String (explode the grid first so \ always overlaps / at some character).

K€Z$+=Ɱ"-|/\"1ZŒdŒD4ƭoẸ$1ドルZŒḍŒḌ4ƭƊ€SZṖḊƊ4¡ỊȦ

A monadic Link that accepts a list of lines and yields 0 if the rays intersect or 1 if not (i.e. inverted).

Try it online! Or see the test-suite .

How?

Explode the canvas with space characters:

K€Z$+
 $ - last two links as a monad - f(Canvas):
K€ - join each with space characters
 Z - transpose
 + - repeat that -> A Canvas with space filling between rows AND columns

Create ray component masks:

=Ɱ"-|/\" - vectorised equals? mapped across "-|/\"

Extend rays within each of these four masks:

1ZŒdŒD4ƭoẸ$1ドルZŒḍŒḌ4ƭƊ€
 Ɗ€ - for each {Mask}:
 4ƭ - apply each of these four in turn:
1 - no-op ('-' uses rows)
 Z - transpose ('|' uses columns)
 Œd - anti-diagonals (for '/')
 ŒD - diagonals (for '\')
 € - for each "Strip":
 $ - last two links as a monad:
 Ẹ - any? -> Strip contains ray segment(s)
 o - {Strip} vectorised logical OR {that}
 -> Strip of all ones if any 1s existed, else zeros
 4ƭ - apply each of these four in turn:
 1 - no-op
 Z - transpose
 Œḍ - convert back from anti-diagonals
 ŒḌ - convert back from diagonals

Check for crossing rays

SZṖḊƊ4¡ỊȦ
S - sum respective mask values together
 4¡ - do this four times:
 Ɗ - last three links as a monad:
 Z - transpose
 Ṗ - pop
 Ḋ - dequeue
 Ị - insignificant (vectorises) --> 1 at 0 or 1, else 0
 Ȧ - any and all?

• Unrelated String: I think this works for 46? Tried rolling the ṖḊ into the start but it hits some weird vectorization snag on the third-to-last case.
• Jonathan Allan: Yes! That'll work - making all characters at odd coordinates in a bigger grid. I thought about something like this early on and never came back to try to integrate it.
• Jonathan Allan: The ṖḊ needs to happen later because the un-diagonal atoms are not inverses of each other when given a 2d array of width or height one (for example). This is still an edge case when we explode the canvas, since we add no spaces in such a case.
• Unrelated String: And of course, if we did add spaces, they would need to be stripped afterwards regardless!

Answer 3

Python 3.8 (pre-release), (削除) 536 (削除ここまで) 374 bytes

def f(b):
 s,h,w,z="-\|/",len(b),len(b[0]),0
 for r in range(h):
 for c in range(w):
 if(v:=b[r][c])in s:y,x,k,l,z=r,c,*[[0,1],[1,1],[1,0],[1,-1]][s.find(v)],5
 while z:
 if" "!=b[y][x]!=v or v=="\\"and"//"==b[y-1][x]+b[y][x-1]or v=="/"and"\\\\"==b[y-1][x]+b[y][x+1]:return 1
 while(0in[y-h+1+k,x-w+1+l,y+k,x+l])*z:k,l=-k,-l;z-=1
 b[y][x]=v;y+=k;x+=l
 return 0

Try it online!

Explanation

s is all line characters, h and w are the height and width of the board. z is used to run the main loop, so set it to 0 to avoid triggering it until we find a line.

 s,h,w,z="-\|/",len(b),len(b[0]),0

Iterate through the board

 for r in range(h):
 for c in range(w):

Store the value of the cell we're looking at in v. If v is a line character, set z to begin the loop to check for intersections. Start looking at y,x which is initially set to the current cell r,c. k,l are set to the direction associated with the current line character. z keeps track of when we've finished analysing this cell.

 if(v:=b[r][c])in s:y,x,k,l,z=r,c,*[[0,1],[1,1],[1,0],[1,-1]][s.find(v)],5

An intersection has occurred in any of the following conditions:

• If the currently extended point (b[x][y]) is anything except for an empty space, or the character we're currently extending
• If the character being investigated is \, and the cell directly above, and directly to the left are both /
• If the character being investigated is /, and the cell directly above, and directly to the right are both \

 while z:
 if" "!=b[y][x]!=v or v=="\\"and"//"==b[y-1][x]+b[y][x-1]or v=="/"and"\\\\"==b[y-1][x]+b[y][x+1]:return 1

This is slightly complicated. Essentially, this serves to reverse the direction we're moving along the line when we hit an edge. This is what the checks for [y-h+1+k,x-w+1+l,y+k,x+l] do. If any of them are 0, our next move would put us on an edge. In that case, we reverse the direction of k and l. However, we also can end up in a situation where a move in either direction will put us on the edge. E.g.: if the board is 1x1. Therefore, we need to prevent the loop from continuing if this is the case. So instead of an if statement, this is a while loop, which also decrements z, which is the condition controlling the outer loop.

 while(0in[y-h+1+k,x-w+1+l,y+k,x+l])*z:k,l=-k,-l;z-=1

Set the current cell to the character being investigated, move the cursor.

 b[y][x]=v;y+=k;x+=l;

Answer 4

Charcoal, (削除) 95 (削除ここまで) 70 bytes

WS⊞υιυUE1¦1F⊗LυF⊗LθF8«Jκι≔§-/|\λη¿=η⊟KD2✳λ«W‹!KK✳+4λ1¿No−-/|\ηKK≔-ω»»⎚ω

Try it online! Link is to verbose version of code. Takes a rectangular array of newline-terminated strings as input and outputs a Charcoal boolean, i.e. - if any rays intersect, nothing if not. Explanation:

WS⊞υιυUE1¦1

Input the canvas, write it to Charcoal's canvas, then double-space it, using @UnrelatedString's tip to @JonathanAllan.

F⊗LυF⊗LθF8«

Loop over all possible cells and directions.

Jκι≔§-/|\λη

Jump to the cell and work out the ray character for the current direction.

¿=η⊟KD2✳λ«

If there is an appropriate ray entering this cell, then...

W‹!KK✳+4λ1

... extend the ray though any empty spaces, and...

¿No−-/|\ηKK≔-ω

... check whether the ray directly intersected a ray in a different direction.

»»⎚ω

Clear the canvas and output the final result.

• Ted: It seems to fail intersecting test case 2, which I've also added as worked example 3 for further clarity.
• Neil: @Ted Thanks, the code was extending the ray backwards by mistake, and this happened to work for rays extending downwards because it found the ray again on a later iteration.
• Ted: Nice, it passes all the test cases now. Thanks for the answer :D