14
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Is (0,0) (0,1) (0,2) (2,2) (2,1) (2,0) expected falsy? \$\endgroup\$ – tsh Nov 8 at 2:26
  • \$\begingroup\$ What should output for (1,0) (2,0) (2,1) (3,1) (3,0) (0,0) (0,1) (1,1)? \$\endgroup\$ – tsh Nov 8 at 2:30
  • \$\begingroup\$ Isn't the answer always false if there are only three points? \$\endgroup\$ – Esolanging Fruit Nov 8 at 2:37
  • \$\begingroup\$ May we take points as complex numbers? \$\endgroup\$ – xnor Nov 8 at 8:52
  • \$\begingroup\$ Can we swap truthy and falsey? \$\endgroup\$ – flawr Nov 8 at 15:56

13 Answers 13

6
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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

Jelly, 7 bytes

;`_ƝḋƝẸ

Try it online!

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

-2 bytes thanks to Jonathan Allan!

\$\endgroup\$
  • 1
    \$\begingroup\$ Save two: ;_ƝḋƝẸ \$\endgroup\$ – Jonathan Allan Nov 8 at 15:00
  • 1
    \$\begingroup\$ @JonathanAllan I'm not sure what you mean? \$\endgroup\$ – caird coinheringaahing Nov 8 at 16:08
  • \$\begingroup\$ Looks like Jonathan Allan proposed a 7 bytes solution? \$\endgroup\$ – stephanmg Nov 8 at 16:13
  • \$\begingroup\$ @stephanmg That's 6 bytes and doesn't work \$\endgroup\$ – caird coinheringaahing Nov 8 at 16:14
  • 1
    \$\begingroup\$ @JonathanAllan Yep, that works, thanks! \$\endgroup\$ – caird coinheringaahing Nov 8 at 17:36
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!
\$\endgroup\$
  • 1
    \$\begingroup\$ 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=) \$\endgroup\$ – DJMcMayhem Nov 8 at 21:26
  • \$\begingroup\$ Thanks, happy to be here! I've update the submission! \$\endgroup\$ – sstannus Nov 8 at 21:32
  • \$\begingroup\$ Since the challenge allows any 2 consistent values, you could swap true/false and use any instead of not sum 94 bytes \$\endgroup\$ – DJMcMayhem Nov 8 at 21:35
  • \$\begingroup\$ if you want to keep truthy/falsey you can do 1-condition \$\endgroup\$ – qwr Nov 9 at 17:52
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ very nice trick for computing the dot product. \$\endgroup\$ – qwr Nov 14 at 21:29
1
\$\begingroup\$

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.

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

Wolfram Language (Mathematica), 49 48 bytes

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

Try it online!

-1 thanks to attinat!

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

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

\$\endgroup\$
  • \$\begingroup\$ 37 bytes: 0==##&@@Sin[2PolygonAngle@Polygon@#]& \$\endgroup\$ – Roman Nov 9 at 16:46
  • \$\begingroup\$ @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) \$\endgroup\$ – Lukas Lang Nov 9 at 17:34
  • \$\begingroup\$ Excellent, you read the instructions more closely than me. \$\endgroup\$ – Roman Nov 9 at 18:59
  • \$\begingroup\$ Alternatives for 35 bytes: #.#==0&@*Cos@*PolygonAngle@*Polygon and #.#==0&@Cos@PolygonAngle@Polygon@#& \$\endgroup\$ – Roman Nov 9 at 21:18
0
\$\begingroup\$

Charcoal, 20 bytes

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

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
       E²               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
\$\endgroup\$
0
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ You can drop the 1- in the return value, since any two distinct return values are fine \$\endgroup\$ – Lukas Lang Nov 9 at 19:14
0
\$\begingroup\$

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ idk any ruby but creating a function instead of reading from stdin will likely be shorter. \$\endgroup\$ – qwr Nov 14 at 21:18
  • 1
    \$\begingroup\$ I don't know ruby at all, but wouldn't saving ARGV to a shorter variable name be shorter? \$\endgroup\$ – EdgyNerd Nov 23 at 20:49
  • \$\begingroup\$ @EdgyNerd: Yeah you right. I also don't know too much Ruby, just for fun. \$\endgroup\$ – stephanmg Nov 25 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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