Is it rectilinear?

Question

Today's challenge:

Given an ordered list of at least 3 unique integer 2D points forming a polygon, determine if the resulting polygon is Rectilinear.

A polygon is rectilinear if every interior angle is a right angle. The edges do not necessarily have to be purely vertical or horizontal (parallel to the x or y axis), as long as the angles are all right (This is slightly different than Wikipedia's definition, but it's the definition we'll be sticking with). For example, the following shape is a perfect square rotated 45°

(0, -1)
(1, 0)
(0, 1)
(-1, 0)

None of the lines are parallel to the x or y axis, but all of the angles are right so it is considered truthy for today's challenge. Note that the order of the points is important. The following reordering of these points gives a self-intersecting polygon, which is basically an hourglass shape rotated 45°. This is falsy:

(0, -1)
(0, 1)
(1, 0)
(-1, 0)

• You must take the input as an ordered set of points. Angles between the points or a "shape object" if your language has one, are not valid inputs.

• You must output one consistent value for truthy and a different consistent value for falsy.

• Note that truthy inputs will always have an even number of points.

• It is acceptable if your submission fails for very large inputs because of floating-point inaccuracies.

Note: If you want to visualize a polygon, I've found this tool and Desmos Graphing Calculator both very useful.

Truthy examples

(0, 0)
(0, 20)
(20, 20)
(20, 0)
(1, 1)
(0, 3)
(6, 6)
(7, 4)
# This example is self-intersecting
(2, 3)
(3, 1)
(-3, -2)
(-2, -4)
(2, -2)
(0, 2)
(4, 0)
(4, 2)
(0, 2)
(0, 4)
(2, 4)
(2, 5)
(4, 5)
(4, 3)
(6, 3)
(6, 0)

Falsy examples

(0, 0)
(0, 20)
(20, 20)
(20, 10)
(100, 100)
(100, 50)
(50, 100)
(2, 2)
(3, 3)
(6, 2)
(7, 3)
(100, 100)
(100, -100)
(-100, -100)
(-100, 99)

• tsh: Is (0,0) (0,1) (0,2) (2,2) (2,1) (2,0) expected falsy?
• tsh: What should output for (1,0) (2,0) (2,1) (3,1) (3,0) (0,0) (0,1) (1,1)?
• Esolanging Fruit: Isn't the answer always false if there are only three points?
• xnor: May we take points as complex numbers?
• flawr: Can we swap truthy and falsey?

Answer 1

Octave, (削除) 60 42 41 (削除ここまで) 40 bytes

I was just looking for an excuse to use nlfilter, too bad the solution was too long:) Now we compute the vectors of the sides of the polygon using d=x-x(:,[2:end,1])). Then d * d' computes all pairwise dot products. We are only interested if consecutive dot products are all zero, therefore we check whether the first superdiagonal diag(...,1) is all zeros using any(...).

@(x)any(diag((d=x-x(:,[2:end,1]))*d',1))

Try it online!

Answer 2

APL (Dyalog Unicode), 16 bytes

×ばつ/0=4○しろまる×ばつ2÷/2-/,⍨

Try it online!

Accepts the input as a list of complex numbers, e.g. 1j2 means \$ 1 + 2i \$ which represents the point \$ (1,2) \$.

The result is 1 if the given polygon is rectilinear, 0 otherwise.

How it works

×ばつ/0=4○しろまる×ばつ2÷/2-/,⍨
 ,⍨ Concatenate self, so that all angles can be tested
 2-/ Difference of two adjacent values, i.e. vectors
 2÷/ Ratio of two adjacent values, i.e. angle difference
 ×ばつ Normalize to unit vectors
 4○しろまる∘ Compute sqrt(1+x^2)
 Zero if and only if the angle is a right angle
 i.e. the normalized angle difference vector is i or -i×ばつ/0= Test if all results are zero, i.e. all angles are right angles

Answer 3

Jelly, 7 bytes

;`_ƝḋƝẸ

Try it online!

Outputs \0ドル\$ if rectilinear, \1ドル\$ otherwise

-2 bytes thanks to Jonathan Allan!

• Jonathan Allan: Save two: ;_ƝḋƝẸ
• caird coinheringaahing: @JonathanAllan I'm not sure what you mean?
• stephanmg: Looks like Jonathan Allan proposed a 7 bytes solution?
• caird coinheringaahing: @stephanmg That's 6 bytes and doesn't work
• caird coinheringaahing: @JonathanAllan Yep, that works, thanks!

Answer 4

Zsh, 94 bytes

for v w;:
for x y;a+=($[v-x]\ $[w-y])&&v=$x&&w=$y
for v w x y ($=a[-1] ${=a:^a})((r|=v*x+w*y))

Try it online!

Input as flattened list of coordinates, outputs via exit code (1 if rectilinear, 0 if not rectilinear). There are three loops here:

for v w;: # this does nothing other than set $v and $w to the last coordinate pair

for x y # ($v,$w) is previous vertex, ($x,$y) is current vertex
 a+=($[v-x]\ $[w-y]) && # vector ($v,$w)->($x,$y) as space-delimited string
 v=$x && w=$y # save previous point

for v w x y ($=a[-1] ${=a:^a}) # This iterates through all subsequent vectors (see below)
 ((r|=v*x+w*y)) # calculate the dot product, bitwise-or with previous dot-products
 # if non-zero, r will be non-zero and the exit code will be zero

The last loop uses ${= }, which splits parameters on spaces, and ${ :^ }, which zips two arrays together (in this case, an array with itself). So, we have the last element in the array, followed by every element twice. That isn't an even number of coordinate pairs, so on the last iteration, x and y are empty. This is fine for the dot product, though, it will compute the dot product with the zero vector, which will always be rectilinear.

Using debug traps, you can walk through the function here.

Answer 5

Python3, 98 bytes

lambda p:not sum((a-c)*(e-c)+(b-d)*(f-d)for(a,b),(c,d),(e,f)in zip(*[p[i:]+p[:i]for i in[0,1,2]]))

Try it online!

Takes in a list of tuple points and outputs True if the points are rectilinear, False otherwise.

How it works

p # contains a list of points
[p[i:]+p[:i]for i in[0,1,2]] # makes 3 lists of p rotated 0, 1, and, 2 places respectively
zip(*[p[i:]+p[:i]for i in[0,1,2]]) # zips the shifted lists together
(a,b),(c,d),(e,f) in zip(*[p[i:]+p[:i]for i in[0,1,2]]) # extracts (x0,y0), (x1,y1), and (x2,y2) from the zipped lists
(a-c)*(e-c)+(b-d)*(f-d) # translates the 0th and 2nd point by the 1st and computes the dot product, which should be 0 if the points are orthogonal
sum((a-c)*(e-c)+(b-d)*(f-d)for(a,b),(c,d),(e,f)in zip(*[p[i:]+p[:i]for i in[0,1,2]])) # sums all of the consecutive dot products together
not sum((a-c)*(e-c)+(b-d)*(f-d)for(a,b),(c,d),(e,f)in zip(*[p[i:]+p[:i]for i in[0,1,2]])) # finally negate the result since if the sum is 0 than all of the points are orthogonal and hence the points form a rectilinear shape!

• DJMcMayhem: Welcome to code-golf! I think this is actually 98 bytes since you'll need to include lambda p: in your answer. (Though you can leave out the f=)
• sstannus: Thanks, happy to be here! I've update the submission!
• DJMcMayhem: Since the challenge allows any 2 consistent values, you could swap true/false and use any instead of not sum 94 bytes
• qwr: if you want to keep truthy/falsey you can do 1-condition

Answer 6

Charcoal, 20 bytes

⬤θ¬ΣEιΠE2−맧θ+κ⊖⊗νμ

Try it online! Link is to verbose version of code. Outputs using Charcoal's default boolean format, which is - for true and nothing for false. Works by separately subtracting each point's x- and y-coordinates from its two adjacent points, then taking the products of the subtractions, then summing, which results in zero when the point is at a right angle. Explanation:

 θ Input array
⬤ Each point satisfies
 ι Current point
 E Map over coordinates
 E2 Map over implicit range `0`..`1`
 λ Current coordinate
 − Subtract
 ν Inner value `0` or `1`
 ⊗ Doubled to `0` or `2`
 ⊖ Decremented to `-1` or `1`
 κ Outer index
 + Added
 θ Input array
 § Get the adjacent point
 § μ Take the relevant coordinate
 Π Take the product
 Σ Take the sum
 ¬ Is zero
 Implicitly print

Answer 7

Python 2, 68 bytes

lambda l:any(((a-b)/(b-c)).real for a,b,c in zip(l,l[1:]+l,l[2:]+l))

Try it online!

Input is a list of complex numbers. Output is True or False, swapped.

• qwr: very nice trick for computing the dot product.

Answer 8

Haskell, 54 bytes

all((==0).sum).r(*).r(-)
r=(=<<tail<>id).z.z
z=zipWith

Try it online!

Uses (<>), which is available in base in the latest release.

Answer 9

Wolfram Language (Mathematica), (削除) 49 (削除ここまで) 48 bytes

0==##&@@Dot@@@({#,r@#})&[(r=RotateLeft)@#-#]&

Try it online!

-1 thanks to attinat!

• att: 48 bytes

Answer 10

Wolfram Language (Mathematica), (削除) 41 (削除ここまで) (削除) 35 (削除ここまで) 34 bytes

Norm@Cos@PolygonAngle@Polygon@#>0&

Returns False for rectilinear polygons and True otherwise.

Only works in 12.0+, so no TIO link

-6 bytes thanks to @Roman

-1 bytes thanks to deleted comment

• Roman: 37 bytes: 0==##&@@Sin[2PolygonAngle@Polygon@#]&
• Lukas Lang: @Roman Thanks! I even managed to shave off another two bytes using Cos@ instead of Sin[2...] (since vertices will never lie in a straight line, this is enough)
• Roman: Excellent, you read the instructions more closely than me.
• Roman: Alternatives for 35 bytes: #.#==0&@*Cos@*PolygonAngle@*Polygon and #.#==0&@Cos@PolygonAngle@Polygon@#&

Answer 11

Excuse my rusty Ruby. Maybe someone can hint how to shorten. :)

Ruby, 158 bytes

s=0;a=ARGV;a[0].split(",").zip(a[2].split(",")).map{|a,b|b.to_i-a.to_i}.zip(
a[1].split(",").zip(a[3].split(",")).map{|a,b|b.to_i-a.to_i}){|a,b|s+=a*b};p s==0

Try it online!

• qwr: idk any ruby but creating a function instead of reading from stdin will likely be shorter.
• Edgex42: I don't know ruby at all, but wouldn't saving ARGV to a shorter variable name be shorter?
• stephanmg: @EdgyNerd: Yeah you right. I also don't know too much Ruby, just for fun.

Answer 12

Python and numpy, (削除) 94 (削除ここまで) 92 bytes

Uses roll a silly number of times and has two input lists of x and y coordinates. It is easier to rotate an array with python lists (x[1:]+x[:1]) but naturally numpy arrays aren't concatenated with +.

from numpy import roll as r
def f(x,y):a,b=r(x,1)-x,r(y,1)-y;return 1-any(a*r(a,1)+b*r(b,1))

• Lukas Lang: You can drop the 1- in the return value, since any two distinct return values are fine

Answer 13

R, (削除) 60 (削除ここまで) 53 bytes

Takes in a vector of complex coordinates and returns swapped truthy and falsey. Uses xnor's dot product trick.

function(x,a=c(x[-1],x[1])-x)any(Re(a/c(a[-1],a[1])))

-7 bytes by using inline rotation instead of creating a function.

R, (削除) 82 (削除ここまで) (削除) 79 (削除ここまで) 75 bytes

Improved version taking advantage of doing computation in default parameters to save on curly braces.

r=pryr::f(c(z[-1],z[1]))
function(x,y,a=r(x)-x,b=r(y)-y)any(a*r(a)+b*r(b))

-3 bytes by using pryr::f anonymous function and returning 0 for truthy, 1 for falsey.

-4 bytes with better roll function

R, 87 bytes, original answer

My first R answer! Uses same array rotation logic as my numpy answer.

r=function(x)c(tail(x,-1),x[1])
x=scan()
y=scan()
a=r(x)-x
b=r(y)-y
!any(a*r(a)+b*r(b))