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)

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!

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!

Answer 6

Wolfram Language (Mathematica), 49 48 bytes

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

Try it online!

-1 thanks to attinat!

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.

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

Answer 10

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

Answer 11

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

Answer 12

Charcoal, 20 bytes

⬤θ¬ΣＥιΠＥ²⁻맧θ⁺κ⊖⊗νμ

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
    Ｅ                   Map over coordinates
       Ｅ²               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 13

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!