20
\$\begingroup\$

Help! My math exam is coming up soon and I didn't study! 1 Part of the exam is to classify a quadrilateral given its vertex coordinates, which I, unfortunately, do not know how to do. 2

So, your challenge is to write a program to do this for me so I don't fail!

Challenge

Given four vertices such that no three of them are colinear, determine the most specific classification of the quadrilateral formed by those four vertices.

What I mean by "most specific classification" is that even though all squares are rectangles, if the shape is a square, you should indicate that it is a square and not indicate that it is a rectangle.

Input

Input will be given as four (x, y) coordinates. You may take these as a list of length 4 of lists/tuples of length 2. Alternatively, you can take input as a list of the x-coordinates and a list of the respective y-coordinates.

For example, if my shape has vertices at points (0, 0), (5, 0), (6, 1), and (1, 1), you may choose to take input in either of the following formats or something similar:

[(0, 0), (5, 0), (6, 1), (1, 1)]
([0, 5, 6, 1], [0, 0, 1, 1])

You may assume that the quadrilateral is not self-intersecting and that the points are given in the correct order (that is, two consecutive points in the input will be connected by a line segment in the quadrilateral).

Output

You will need a unique output for each of the following classes of quadrilaterals:

  • Square
  • Rectangle
  • Rhombus
  • Parallelogram
  • Trapezoid/Trapezium
  • Kite
  • Quadrilateral

This could be the exact name itself, a character, an integer, etc.

Rules

  • Standard Loopholes Apply
  • If your programming language has a built-in that will perform this exact task, that built-in is not allowed.
  • Built-ins for finding the distance between two points are allowed.
  • Built-ins for finding the angle between two lines are allowed.

At this point, if you know all of the terms, you are ready to start programming! (Test Cases are at the end)

Terminology

This section is for anyone who needs clarification on the definitions of the different shapes.

Square

A quadrilateral is a square if and only if all 4 of its sides are equal in length and every pair of adjacent sides is perpendicular (that is, it is both a rectangle and a rhombus).

Rectangle

A quadrilateral is a rectangle if and only if every pair of adjacent sides is perpendicular.

Rhombus

A quadrilateral is a rhombus if and only if all 4 of its sides are equal.

Parallelogram

A quadrilateral is a parallelogram if and only if each pair of opposite sides is parallel and each pair of opposite angles is equal. Both of these conditions imply each other so you only need to check for one of them.

Trapezoid/Trapezium

A quadrilateral is a trapezoid/trapezium if and only if it has at least one pair of parallel sides.

Kite

A quadrilateral is a kite if two opposite pairs of adjacent sides are equal in length; that is, two of its adjacent sides are equal and the other two are also equal.

Test Cases

input as (x, y) * 4 -> full name
[(0, 0), (1, 0), (1, 1), (0, 1)] -> square
[(0, 0), (1, 1), (-1, 3), (-2, 2)] -> rectangle
[(0, 0), (5, 0), (8, 4), (3, 4)] -> rhombus
[(0, 0), (5, 0), (6, 1), (1, 1)] -> parallelogram
[(0, 0), (4, 0), (3, 1), (1, 1)] -> trapezoid/trapezium
[(0, 0), (1, 1), (0, 3), (-1, 1)] -> kite  
[(0, 0), (2, 0), (4, 4), (0, 1)] -> quadrilateral

Links (Desmos Graphing Calculator)

Here are links to visualizations of each of the test cases.

Square
Rectangle
Rhombus
Parallelogram
Trapezoid/Trapezium
Kite
Quadrilateral

Winning Criteria

I can't bring a computer into the exam obviously, so I need you to write the shortest code possible so I can memorize it. I need to write it into the margins and run it using TryItOfflineTM so to fit it into the margins your program needs to be as small as possible!

1 Of course I actually did :P
2 Of course I actually do :P

\$\endgroup\$
  • 1
    \$\begingroup\$ I might be able to help you with your margin problem xkcd.com/1381 \$\endgroup\$ – Rohan Jhunjhunwala Jun 22 '17 at 15:24
  • \$\begingroup\$ @RohanJhunjhunwala I am the new Fermat (I think that's the right person?). But nice XKCD ref :P \$\endgroup\$ – HyperNeutrino Jun 22 '17 at 15:26
  • \$\begingroup\$ is CSV allowed input? \$\endgroup\$ – tuskiomi Jun 22 '17 at 15:39
  • \$\begingroup\$ What is the partial order of specificity? \$\endgroup\$ – Peter Taylor Jun 22 '17 at 16:12
  • \$\begingroup\$ Related \$\endgroup\$ – Digital Trauma Jun 22 '17 at 16:19
6
\$\begingroup\$

APL (Dyalog), 104 89 80 82 81 79 78 bytes

⍙←{⍵⍺⍺1⌽⍵}
⎕←(|x){⍵≡2⌽⍵:≡⍙¨0⍺⍵⋄2 4=+/1=2|+⍙↑⍵(=⍙⍺)}2|1+-⍙(12○x←-⍙⎕+.×1 0J1)÷○1

Try it online!


Input/Output

Takes a 4×2 matrix of coordinates as input

Outputs

  • 1 1 1 for Square
  • 1 1 0 for Rhombus
  • 1 0 1 for Rectangle
  • 1 0 0 for Parallelogram
  • 1 0 for Kite
  • 0 1 for Trapezium
  • 0 0 for Quadrilateral

Algorithm

First, find all 4 side lengths and angles of the quadrilateral

If both pairs of opposite angles are equal (OA), then the shape is some kind of parallelogram. Determine if all side lengths are equal (AS, Adjacent Sides) and if all angles are equal (AA).

+--------+----------------+----------------+
|        |       AA       |      ~AA       |
+--------+----------------+----------------+
|   AS   |     Square     |    Rhombus     |
|--------+----------------+----------------+
|  ~AS   |    Rectangle   |  Parallelogram |
+--------+----------------+----------------+

If not OA, then:

  • Determine if there are exactly 2 pairs of equal adjacent sides and if they are separated (aabb instead of aaab). If so, the shape is a kite.

  • Determine if there are exactly 1 pair of parallel opposite sides. If so, the shape is a trapezium.

  • Otherwise, the shape is a quadrilateral.


Code

⍙←{⍵⍺⍺1⌽⍵} defines a new operator. In APL, an operator means a higher-order function. This operator takes 1 functional argument (⍺⍺) and returns a monadic function that:

  1. Rotates (1⌽) the argument ()
  2. Apply ⍺⍺ between it and

This is especially useful for scalar functions since most of them implicitly map across array arguments, allowing to apply those between each adjacent pair of elements with wrap around. For example +⍙1 2 3 4 is 1 2 3 4 + 2 3 4 1 which evaluates to 3 5 7 5.


x←-⍙⎕+.×1 0J1 converts the input coordinate matrix into an array of complex numbers representing the vectors of the 4 sides of the shape.

  • , when referenced, takes and returns input

  • 1 0J1 represents the vector [1,i] ("vector" in the mathematical sense, and "i" as the square root of -1). In APL, a complex number a+bi is written aJb

  • +.× matrix multiplication. Mathematically, the result would be a 4×1 matrix. However, +.× is called "inner product" in APL which generalizes matrix multiplication and vector inner product and allows you to do even stuff like "multiply" a 3-dimensional array with a 2-dimensional one. In this case, we are multiplying a 4×2 matrix and a 2-element vector, resulting in a 4-element vector (of the complex number representations of the 4 given vertices).

  • -⍙ is pairwise subtraction with wrap around as noted above. This gives the vectors of the 4 sides of the shape (as complex numbers). These vectors point in the "reverse" direction but that doesn't matter.

  • x← stores that into the variable x


2|1+-⍙(12○x)÷○1 finds (a representation of) the exterior angles at the 4 vertices of the shape.

  • 12○x finds the principal argument, in radians, of each of the 4 side vectors.

  • ÷○1 divides by π so that the angles are easier to work with. Thus, all angles are expressed as a multiple of a straight angle.

  • -⍙ Pairwise subtraction with wrap around as noted above. This gives the 4 exterior angles.

  • 2|1+ The principal argument is capped (-1,1] and pairwise subtraction makes the range (-2,2]. This is bad since the same angle has 2 different representations. By doing "add 1 mod 2", the angle is re-capped at (0,2]. Although all angles are 1 more than what it should be, it's fine if we keep that in mind.


|x finds the magnitude of each of the 4 side vectors


{⍵≡2⌽⍵:≡⍙¨0⍺⍵⋄2 4=+/1=2|+⍙↑⍵(=⍙⍺)} defines and applies a function with the array of 4 exterior angles as right argument and the array of 4 side lengths as right argument .

  • The function has a guarded expression. In this case, ⍵≡2⌽⍵ is the guard.
  • If the guard evaluates to 1 then the next expression ≡⍙¨0⍺⍵ is executed and its value returned.
  • If the guard evaluates to 0, that expression is skipped and the one after that 2 4=...=⍙⍺) gets executed instead.

⍵≡2⌽⍵ checks if both pairs of opposite angles are equal.

  • 2⌽⍵ rotates the angles array by 2 places.
  • ⍵≡ checks if that is the same as itself

≡⍙¨0⍺⍵ returns a unique value for each parallelogram-type shape.

  • 0⍺⍵ is the 3-element array of the scalar 0, the side lengths array , and the angles array .
  • ≡⍙¨ executes ≡⍙ for each of those elements.
  • ≡⍙ checks if all values of an array are equal by checking if rotating it by 1 gives the same array. Scalars do not rotate so ≡⍙0 returns 1. As noted above, ≡⍙⍺ checks for a rhombus and ≡⍙⍵ checks for a rectangle.

2 4=+/1=2|+⍙↑⍵(=⍙⍺) returns a unique value for each non-parallelogram-type shape. This is achieved by intertwining the checks for kite and trapezium.


2=+/1=2|+⍙⍵ checks for a trapezium.

  • +⍙⍵ gives the adjacent angle sums. The interior angles of parallel lines sum to a straight angle, thus so does the exterior angles of parallel sides of a quadrilateral. So, each pair of parallel sides should lead to two 1 or -1 in the adjacent angle sums.

  • 1=2| However, the angles in are 1 more than what they should be, so the angles actually sum to 1 or 3. This can be checked by "mod 2 equals 1".

  • +/ sums the array. This gives a count of adjacent angle sums which is 1 or 3.

  • 2= check if that equals 2. (I.e. if there is exactly one pair of parallel sides)


4=+/1=2|+⍙(=⍙⍺) checks for a kite.

  • (=⍙⍺) gives an array indicating which adjacent sides are equal. Unlike , = work element-wise. Thus, this is a 4-element array with 1s where the length of that side is equal to that of the "next" side.

  • +⍙ Pairwise sum with wrap around.

  • 1=2| Since (=⍙⍺) gives a boolean array (one with only 0s and 1s), the only possible values of pairwise sum are 0, 1 and 2. So 1=2| is same as just 1=.

  • +/ sums the array. This gives a count of pairwise sums which is 1.

  • 4= check if that equals 4. The only way that happens is if (=⍙⍺) is 1 0 1 0 or 0 1 0 1. As noted above, this means the shape is a kite.


2 4=+/1=2|+⍙↑⍵(=⍙⍺) intertwines the above checks.

  • ⍵(=⍙⍺) is the 2-element nested array of the array and the array (=⍙⍺)

  • promotes the nested array to a proper matrix. Since ⍵(=⍙⍺) is a 2-element array of 4-element arrays, the result is a 2×4 matrix.

  • +⍙ Since (and, by extension, ) rotates the last (horizontal) axis, +⍙ to a matrix is same as applying +⍙ to each row individually.

  • 1=2| both residue/mod (|) and equals (=) works on a per-element basis, even to matrices.

  • +/ By default, reduce (/) works along the last (horizontal) axis. So +/ sums along rows and turn a 2×4 matrix into a 2-element simple array.

  • 2 4= Since = works per-element, this checks the kite and trapezium conditions simultaneously.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 195 bytes

Which[s=Differences@{##,#};l=Norm/@s;r=#.#2==#2.#3==0&@@s;Equal@@l,If[r,1,2],#==#3&&#2==#4&@@l,If[r,3,4],MatchQ[l,{a_,b_,b_,a_}|{a_,a_,b_,b_}],5,#+#3=={0,0}||#2+#4=={0,0}&@@Normalize/@s,6,1>0,7]&

With whitespace:

Which[
    s = Differences @ {##,#};
    l = Norm /@ s;
    r = #.#2 == #2.#3 == 0& @@ s;

    Equal @@ l, If[r, 1, 2],
    # == #3 && #2 == #4& @@ l, If[r, 3, 4],
    MatchQ[l, {a_,b_,b_,a_}|{a_,a_,b_,b_}], 5,
    #+#3 == {0,0} || #2+#4 == {0,0}& @@ Normalize /@ s, 6,
    1 > 0, 7
]&

Outputs 1 for squares, 2 for rhombi, 3 for rectangles, 4 for parallelograms, 5 for kites, 6 for trapezoids, and 7 for anything else. I'd post a TIO link, but this apparently doesn't work in Mathics.

If the four points are P, Q, R, and S, then {##,#} is {P,Q,R,S,P}, so s is the list of side vectors {Q-P,R-Q,S-R,P-S}, l is the lengths of those vectors, and r is the condition that the angle between Q-P and R-Q as well as the angle between R-Q and S-R are both 90 degrees.

Thus, if all the sides lengths are equal, then the quadrilateral is a rhombus. If r holds, it is in fact a square, otherwise it's just a plain rhombus.

Ruling out rhombi, if both pairs of opposite side lengths are equal, then the quadrilateral is still parallelogram. If r holds, it is in fact a rectangle, otherwise, it's just a plain parallelogram.

Ruling out parallelograms, the list of side lengths l is of the form {a,b,b,a} or {a,a,b,b} for some a and b, then the quadrilateral is a kite. Note that it can't additionally be a trapezoid or it would in fact be a rhombus.

Ruling out parallelograms and kites, if the quadrilateral has a pair of parallel sides, then it is a trapezoid. We check this by Normalizeing the side vectors and checking whether a pair of opposite vectors adds to {0,0}.

Ruling out all of the above, if 1 > 0 (it better be), then the quadrilateral is just a plain old quadrilateral.

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

Python 2, 463 410 408 397 bytes

Saved 53 bytes by using a tuple in the sixth line instead of indexing into a list.

Saved 11 bytes by shifting to output integers 1 through 7 instead of the first letter of each shape. The integers correspond as follows:

  1. Square
  2. Rectangle
  3. Rhombus
  4. Parallelogram
  5. Trapezoid
  6. Kite
  7. Quadrilateral
from numpy import *;D=dot
from numpy.linalg import *;N=norm
def P(a,b):x=D(a,b);y=N(a)*N(b);return x==y or x==-y
def Q(a,b):return int(N(a)==N(b))
L=input()
a,b,c,d=tuple([(L[i][0]-L[(i+1)%4][0],L[i][1]-L[(i+1)%4][1]) for i in range(4)])
g=7
e=Q(a,c)+Q(b,d)
if e==2:
 g=(1if D(a,b)==0 else 3) if Q(a,b) else 2 if D(a,b)==0 else 4
elif P(a,c) or P(b,d):
 g = 5
elif Q(a,b) or Q(b,c):
 g = 6
print g

Try it online!

Ungolfed to show the logic

Shown as a function, to show output for the different test input. note I changed the "Rectangle" test example from the one originally provided in the question, which was not a rectangle.

The logic rests on dot products and the norm (length) of the vectors formed by the sides of the quadrilateral to assess whether sides are equal in length, parallel on opposite sides, or perpendicular to adjacent sides.

def S(va, vb):
    return (va[0]-vb[0], va[1]-vb[1])
def dot(sa,sb):      # Eventually replaced with numpy.dot
    return(sa[0]*sb[0]+sa[1]*sb[1])
def norm(s):         # Eventually replaced by numpy.linalg.norm
    return (s[0]**2+s[1]**2)**.5
def isperp(a,b):     # Test if lines/vectors are perpendicular
    return dot(a,b)==0
def ispar(a,b):      # Test if lines/vectors are parallel
    x = dot(a,b)
    y = norm(a)*norm(b)
    return x == y or x == -y
def iseq(a,b):       # Test if lines/vectors are equal in length
    return norm(a)==norm(b)
   
def f(L):
    #Define the four sides
    s = []
    for i in range(4):
        s.append(S(L[i],L[(i+1)%4]))  # I refer often so shorter names may eventually

    guess = 'Q'
    eqsides = 0           # These 6 lines eventually golfed using integer arithmetic by returning an int from iseq()
    if iseq(s[0], s[2]):
        eqsides += 1
    if iseq(s[1],s[3]):
        eqsides += 1
    if eqsides == 2:
    # Opposite sides are equal, so square, rhombus, rectangle or parallelogram
        if iseq(s[0],s[1]):       #Equal adjacent sides, so square or rhombus
            guess='S' if isperp(s[0], s[1]) else 'H'
        else:                     # rectangle or Parallelogram
            guess='R' if isperp(s[0], s[1]) else 'P'
    elif ispar(s[0],s[2]) or ispar(s[1],s[3]):
        guess = 'T'
    elif iseq(s[0],s[1]) or iseq(s[1],s[2]):
        guess = 'K'
    return guess
    

#test suite:
print f([(0, 0), (1, 0), (1, 1), (0, 1)]) # -> square
print f([(0, 0), (1, 1), (-1, 3), (-2, 2)]) # -> rectangle
print f([(0, 0), (5, 0), (8, 4), (3, 4)]) #  -> rhombus
print f([(0, 0), (5, 0), (6, 1), (1, 1)]) #  -> parallelogram
print f([(0, 0), (4, 0), (3, 1), (1, 1)]) # -> trapezoid/trapezium
print f([(0, 0), (1, 1), (0, 3), (-1, 1)]) #-> kite  
print f([(0, 0), (2, 0), (4, 4), (0, 1)]) #-> quadrilateral

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Misclassified [(0, 0), (2, 2), (4, 0), (0,-2)] as kite \$\endgroup\$ – TwiNight Jun 27 '17 at 0:39
  • \$\begingroup\$ Would this work? repl.it/JRzE \$\endgroup\$ – Zacharý Jul 7 '17 at 13:34
  • \$\begingroup\$ @TwiNight Thanks. Did not see this possibility. Problem is that my initial algorithm only checks to see if there's ONE pair of sides of matched length. As you example shows, that's not sufficient. I'd need to check for one pair of matched sides, and then check if the opposite pair are also similar in length. Been too busy to implement that. \$\endgroup\$ – CCB60 Jul 18 '17 at 1:19
0
\$\begingroup\$

Batch, 287 bytes

@set/aa=%3-%1,b=%4-%2,c=%5-%1,d=%6-%2,e=%7-%1,f=%8-%2,g=a*a+b*b,h=(h=c-a)*h+(h=d-b)*h,i=(i=c-e)*i+(i=d-f)*i,j=e*e+f*f,p=!(i-g)+!(j-h),q=!(h-g),r=!(a*e+b*f),k=q+!(j-i)^|!(j-g)+!(h-i),t=!(a*(f-d)-b*(e-c))+!((c-a)*f-(d-b)*e)
@if %p%==2 (echo 1%r%%q%)else if %k%==2 (echo 1)else (echo 1%t%)

Outputs in binary: 1 = Kite, 10 = Quadrilateral, 11 = Trapezium, 100 = Parallelogram, 101 = Rhombus, 110 = Rectangle, 111 = Square. Explanation: g, h, i, j are the squares of the lengths of the sides. p is the number of pairs of opposite sides with the same length, q distinguishes between parallelograms/rectangles and rhobmi/squares by checking whether the opposite pairs are in fact equal, r distinguishes between parallelograms/rhombi and rectangles/squares via a perpendicularity check, k checks for a kite by looking for pairs of equal adjacent sides and t checks for a trapezium via a couple of parallel side checks.

\$\endgroup\$
  • \$\begingroup\$ See this comment \$\endgroup\$ – TwiNight Jun 27 '17 at 0:40
  • \$\begingroup\$ @TwiNight Bah, checking for a kite is really awkward. \$\endgroup\$ – Neil Jun 27 '17 at 10:09
  • \$\begingroup\$ Yeah, I was lucky to find a compact way to do it \$\endgroup\$ – TwiNight Jun 27 '17 at 10:15
  • \$\begingroup\$ @TwiNight I'll take your word for it; APL is completely unreadable to me. \$\endgroup\$ – Neil Jun 27 '17 at 10:43
  • \$\begingroup\$ The part where I check for kite is 2=|-.=⍙⍺. Certainly looks compact if you ignore the work put into calculating (the 4 side lengths) and a whole line to define \$\endgroup\$ – TwiNight Jun 27 '17 at 10:59

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.