Is this quadrilateral cyclic?
up vote
17
down vote
favorite
In mathematics, a cyclic quadrilateral is one whose vertices all lie on the same circle. In other words, every vertex is on the circumcircle of the other three. For more information, see the MathWorld article.
Examples
These quadrilaterals are cyclic:
This trapezoid is not cyclic.
(Images from Wikipedia)
Objective
Given the coordinates of four vertices in counterclockwise order which form a convex quadrilateral, determine if the quadrilateral is cyclic.
Coordinates will be integers (note, however, that the circumcenter coordinates and circumradius are not necessarily integers.) As implied by the previous paragraph, no three points will be co-linear and no two coincident.
I/O
You may take input using any reasonable format. In particular, [[x1,x2,x3,x4],[y1,y2,y3,y4]]
, [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]
and complex numbers are all fine.
Output using any different consistent values for true and false.
Test cases
True:
[0,0], [314,0], [314,1], [0,1]
[-5,5], [5,-5], [1337,42], [42,1337]
[104, -233], [109, -232], [112, -231], [123, -224]
False:
[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]
code-golf math decision-problem geometry
add a comment |
up vote
17
down vote
favorite
In mathematics, a cyclic quadrilateral is one whose vertices all lie on the same circle. In other words, every vertex is on the circumcircle of the other three. For more information, see the MathWorld article.
Examples
These quadrilaterals are cyclic:
This trapezoid is not cyclic.
(Images from Wikipedia)
Objective
Given the coordinates of four vertices in counterclockwise order which form a convex quadrilateral, determine if the quadrilateral is cyclic.
Coordinates will be integers (note, however, that the circumcenter coordinates and circumradius are not necessarily integers.) As implied by the previous paragraph, no three points will be co-linear and no two coincident.
I/O
You may take input using any reasonable format. In particular, [[x1,x2,x3,x4],[y1,y2,y3,y4]]
, [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]
and complex numbers are all fine.
Output using any different consistent values for true and false.
Test cases
True:
[0,0], [314,0], [314,1], [0,1]
[-5,5], [5,-5], [1337,42], [42,1337]
[104, -233], [109, -232], [112, -231], [123, -224]
False:
[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]
code-golf math decision-problem geometry
add a comment |
up vote
17
down vote
favorite
up vote
17
down vote
favorite
In mathematics, a cyclic quadrilateral is one whose vertices all lie on the same circle. In other words, every vertex is on the circumcircle of the other three. For more information, see the MathWorld article.
Examples
These quadrilaterals are cyclic:
This trapezoid is not cyclic.
(Images from Wikipedia)
Objective
Given the coordinates of four vertices in counterclockwise order which form a convex quadrilateral, determine if the quadrilateral is cyclic.
Coordinates will be integers (note, however, that the circumcenter coordinates and circumradius are not necessarily integers.) As implied by the previous paragraph, no three points will be co-linear and no two coincident.
I/O
You may take input using any reasonable format. In particular, [[x1,x2,x3,x4],[y1,y2,y3,y4]]
, [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]
and complex numbers are all fine.
Output using any different consistent values for true and false.
Test cases
True:
[0,0], [314,0], [314,1], [0,1]
[-5,5], [5,-5], [1337,42], [42,1337]
[104, -233], [109, -232], [112, -231], [123, -224]
False:
[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]
code-golf math decision-problem geometry
In mathematics, a cyclic quadrilateral is one whose vertices all lie on the same circle. In other words, every vertex is on the circumcircle of the other three. For more information, see the MathWorld article.
Examples
These quadrilaterals are cyclic:
This trapezoid is not cyclic.
(Images from Wikipedia)
Objective
Given the coordinates of four vertices in counterclockwise order which form a convex quadrilateral, determine if the quadrilateral is cyclic.
Coordinates will be integers (note, however, that the circumcenter coordinates and circumradius are not necessarily integers.) As implied by the previous paragraph, no three points will be co-linear and no two coincident.
I/O
You may take input using any reasonable format. In particular, [[x1,x2,x3,x4],[y1,y2,y3,y4]]
, [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]
and complex numbers are all fine.
Output using any different consistent values for true and false.
Test cases
True:
[0,0], [314,0], [314,1], [0,1]
[-5,5], [5,-5], [1337,42], [42,1337]
[104, -233], [109, -232], [112, -231], [123, -224]
False:
[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]
code-golf math decision-problem geometry
code-golf math decision-problem geometry
edited Nov 17 at 23:18
FryAmTheEggman
14.6k32482
14.6k32482
asked Nov 17 at 19:52
lirtosiast
15.6k436105
15.6k436105
add a comment |
add a comment |
8 Answers
8
active
oldest
votes
up vote
11
down vote
Wolfram Language (Mathematica), 23 bytes
#∈Circumsphere@{##2}&
Try it online!
Takes four inputs: the lists {x1,y1}
, {x2,y2}
, {x3,y3}
, and {x4,y4}
. Checks if the first point lies on the circumcircle of the other three. Also works for checking if $n+1$ points in $mathbb R^n$ are concyclic, provided the last $n$ of them are affinely independent (because Circumsphere
is sad if you give it a degenerate input).
Alternatively, here is a mathematical approach:
Wolfram Language (Mathematica), 29 28 25 24 bytes
Det@{#^2+#2^2,##,1^#}^0&
Try it online!
Takes two lists as input: {x1,x2,x3,x4}
and {y1,y2,y3,y4}
. Returns Indeterminate
when the four points are on a common circle, and 1
otherwise.
From the four points $(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$, this solution constructs the matrix below:
$begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \ x_1 & x_2 & x_3 & x_4 \ y_1 & y_2 & y_3 & y_4 \ 1 & 1 & 1 & 1 end{bmatrix}$
The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.
The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0
is Indeterminate
while anything else gives 1
.
add a comment |
up vote
9
down vote
Python 3, 70 bytes
lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8
Try it online!
I use the Ptolemy's theorem.
In a quadrilateral, if the sum of the products of its two pairs of
opposite sides is equal to the product of its diagonals, then the
quadrilateral can be inscribed in a circle.
b
, c
, d
, e
are complex numbers.
add a comment |
up vote
8
down vote
Perl 6, 44 bytes
{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}
Try it online!
Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
add a comment |
up vote
6
down vote
JavaScript (ES6)
Testing the angles, 114 bytes
Takes input as the array $[x1,y1,x2,y2,x3,y3,x4,y4]$. Returns a Boolean value.
a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI
Try it online!
Computing a determinant, 130 bytes
Takes input as $[x1,x2,x3,x4]$ and $[y1,y2,y3,y4]$ in currying syntax. Returns a Boolean value.
This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.
x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))
Try it online!
add a comment |
up vote
4
down vote
TI-Basic (83 series), 21 bytes
e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3
Takes input as a list of four complex numbers in Ans
. Returns 1
if the quadrilateral is cyclic and 0
otherwise.
This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values $z_1, z_2, z_3, z_4$, then:
ΔList(augment(Ans,Ans
computes the differences $z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$ (and a few more redundant terms),
e^(ΔList(ln(
of that computes the ratios $frac{z_3-z_2}{z_2-z_1}, frac{z_4-z_3}{z_3-z_2}, frac{z_1-z_4}{z_4-z_3}, dots$.- We check if the product of the first and third terms, which is $frac{z_3-z_2}{z_2-z_1} cdot frac{z_1-z_4}{z_4-z_3}$, has no imaginary part. Note that this is the same as the cross-ratio $(z_3,z_1;z_2,z_4) = frac{z_2-z_3}{z_2-z_1} : frac{z_4-z_3}{z_4-z_1}$.
I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.
add a comment |
up vote
3
down vote
JavaScript (ES6) (101 bytes)
p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)
Takes input as [x1,y1,x2,y2,x3,y3,x4,y4]
, outputs a Boolean.
Checked based on $$ef=ac+bd$$ where $e,f$ are the diagonals and $a,b,c,d$ are the sides in order.
Try it online!
add a comment |
up vote
2
down vote
Jelly, 11 bytes
²Sṭ;L€€ṖÆḊ¬
Try it online!
Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.
How it works
²Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
ṭ Append to the input
;L€€ Add two rows of [1,1,1,1]'s
Ṗ Remove an extra row
ÆḊ¬ Is the determinant zero?
Jelly, 12 bytes
Iµ÷×ƭ/÷SµḞ=A
Try it online!
Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.
How it works
Iµ÷×ƭ/÷SµḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
µ Refocus on above for sum function
÷×ƭ/÷S (z2-z1)÷(z3-z2)×(z4-z3)÷(z4-z1)
µ Refocus again
Ḟ=A (real part) == (norm) within error margin
i.e. imag part is negligible?
I believe both are golfable...
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 25 bytes
{0=-/|⍵}(-⌿2 3⍴2/⌽)×⊃-1↓⊢
Try it online!
Ptolemy's theorem, credit: Кирилл Малышев's answer
add a comment |
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
11
down vote
Wolfram Language (Mathematica), 23 bytes
#∈Circumsphere@{##2}&
Try it online!
Takes four inputs: the lists {x1,y1}
, {x2,y2}
, {x3,y3}
, and {x4,y4}
. Checks if the first point lies on the circumcircle of the other three. Also works for checking if $n+1$ points in $mathbb R^n$ are concyclic, provided the last $n$ of them are affinely independent (because Circumsphere
is sad if you give it a degenerate input).
Alternatively, here is a mathematical approach:
Wolfram Language (Mathematica), 29 28 25 24 bytes
Det@{#^2+#2^2,##,1^#}^0&
Try it online!
Takes two lists as input: {x1,x2,x3,x4}
and {y1,y2,y3,y4}
. Returns Indeterminate
when the four points are on a common circle, and 1
otherwise.
From the four points $(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$, this solution constructs the matrix below:
$begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \ x_1 & x_2 & x_3 & x_4 \ y_1 & y_2 & y_3 & y_4 \ 1 & 1 & 1 & 1 end{bmatrix}$
The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.
The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0
is Indeterminate
while anything else gives 1
.
add a comment |
up vote
11
down vote
Wolfram Language (Mathematica), 23 bytes
#∈Circumsphere@{##2}&
Try it online!
Takes four inputs: the lists {x1,y1}
, {x2,y2}
, {x3,y3}
, and {x4,y4}
. Checks if the first point lies on the circumcircle of the other three. Also works for checking if $n+1$ points in $mathbb R^n$ are concyclic, provided the last $n$ of them are affinely independent (because Circumsphere
is sad if you give it a degenerate input).
Alternatively, here is a mathematical approach:
Wolfram Language (Mathematica), 29 28 25 24 bytes
Det@{#^2+#2^2,##,1^#}^0&
Try it online!
Takes two lists as input: {x1,x2,x3,x4}
and {y1,y2,y3,y4}
. Returns Indeterminate
when the four points are on a common circle, and 1
otherwise.
From the four points $(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$, this solution constructs the matrix below:
$begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \ x_1 & x_2 & x_3 & x_4 \ y_1 & y_2 & y_3 & y_4 \ 1 & 1 & 1 & 1 end{bmatrix}$
The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.
The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0
is Indeterminate
while anything else gives 1
.
add a comment |
up vote
11
down vote
up vote
11
down vote
Wolfram Language (Mathematica), 23 bytes
#∈Circumsphere@{##2}&
Try it online!
Takes four inputs: the lists {x1,y1}
, {x2,y2}
, {x3,y3}
, and {x4,y4}
. Checks if the first point lies on the circumcircle of the other three. Also works for checking if $n+1$ points in $mathbb R^n$ are concyclic, provided the last $n$ of them are affinely independent (because Circumsphere
is sad if you give it a degenerate input).
Alternatively, here is a mathematical approach:
Wolfram Language (Mathematica), 29 28 25 24 bytes
Det@{#^2+#2^2,##,1^#}^0&
Try it online!
Takes two lists as input: {x1,x2,x3,x4}
and {y1,y2,y3,y4}
. Returns Indeterminate
when the four points are on a common circle, and 1
otherwise.
From the four points $(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$, this solution constructs the matrix below:
$begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \ x_1 & x_2 & x_3 & x_4 \ y_1 & y_2 & y_3 & y_4 \ 1 & 1 & 1 & 1 end{bmatrix}$
The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.
The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0
is Indeterminate
while anything else gives 1
.
Wolfram Language (Mathematica), 23 bytes
#∈Circumsphere@{##2}&
Try it online!
Takes four inputs: the lists {x1,y1}
, {x2,y2}
, {x3,y3}
, and {x4,y4}
. Checks if the first point lies on the circumcircle of the other three. Also works for checking if $n+1$ points in $mathbb R^n$ are concyclic, provided the last $n$ of them are affinely independent (because Circumsphere
is sad if you give it a degenerate input).
Alternatively, here is a mathematical approach:
Wolfram Language (Mathematica), 29 28 25 24 bytes
Det@{#^2+#2^2,##,1^#}^0&
Try it online!
Takes two lists as input: {x1,x2,x3,x4}
and {y1,y2,y3,y4}
. Returns Indeterminate
when the four points are on a common circle, and 1
otherwise.
From the four points $(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$, this solution constructs the matrix below:
$begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \ x_1 & x_2 & x_3 & x_4 \ y_1 & y_2 & y_3 & y_4 \ 1 & 1 & 1 & 1 end{bmatrix}$
The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.
The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0
is Indeterminate
while anything else gives 1
.
edited Nov 18 at 5:35
answered Nov 18 at 3:16
Misha Lavrov
4,091424
4,091424
add a comment |
add a comment |
up vote
9
down vote
Python 3, 70 bytes
lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8
Try it online!
I use the Ptolemy's theorem.
In a quadrilateral, if the sum of the products of its two pairs of
opposite sides is equal to the product of its diagonals, then the
quadrilateral can be inscribed in a circle.
b
, c
, d
, e
are complex numbers.
add a comment |
up vote
9
down vote
Python 3, 70 bytes
lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8
Try it online!
I use the Ptolemy's theorem.
In a quadrilateral, if the sum of the products of its two pairs of
opposite sides is equal to the product of its diagonals, then the
quadrilateral can be inscribed in a circle.
b
, c
, d
, e
are complex numbers.
add a comment |
up vote
9
down vote
up vote
9
down vote
Python 3, 70 bytes
lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8
Try it online!
I use the Ptolemy's theorem.
In a quadrilateral, if the sum of the products of its two pairs of
opposite sides is equal to the product of its diagonals, then the
quadrilateral can be inscribed in a circle.
b
, c
, d
, e
are complex numbers.
Python 3, 70 bytes
lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8
Try it online!
I use the Ptolemy's theorem.
In a quadrilateral, if the sum of the products of its two pairs of
opposite sides is equal to the product of its diagonals, then the
quadrilateral can be inscribed in a circle.
b
, c
, d
, e
are complex numbers.
edited Nov 17 at 23:06
answered Nov 17 at 22:59
Кирилл Малышев
40115
40115
add a comment |
add a comment |
up vote
8
down vote
Perl 6, 44 bytes
{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}
Try it online!
Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
add a comment |
up vote
8
down vote
Perl 6, 44 bytes
{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}
Try it online!
Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
add a comment |
up vote
8
down vote
up vote
8
down vote
Perl 6, 44 bytes
{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}
Try it online!
Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.
Perl 6, 44 bytes
{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}
Try it online!
Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.
edited Nov 18 at 0:05
answered Nov 17 at 23:43
nwellnhof
6,3131125
6,3131125
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
add a comment |
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
42? Is it still accurate?
– Jo King
Nov 18 at 4:24
1
1
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
@JoKing No, it's not.
– nwellnhof
Nov 18 at 9:44
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
What does the colon do in this case? It's definitely not a label, and also not a method call.
– user202729
Nov 18 at 14:55
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
@user202729 It is a method call with indirect invocant syntax.
– nwellnhof
Nov 18 at 15:44
add a comment |
up vote
6
down vote
JavaScript (ES6)
Testing the angles, 114 bytes
Takes input as the array $[x1,y1,x2,y2,x3,y3,x4,y4]$. Returns a Boolean value.
a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI
Try it online!
Computing a determinant, 130 bytes
Takes input as $[x1,x2,x3,x4]$ and $[y1,y2,y3,y4]$ in currying syntax. Returns a Boolean value.
This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.
x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))
Try it online!
add a comment |
up vote
6
down vote
JavaScript (ES6)
Testing the angles, 114 bytes
Takes input as the array $[x1,y1,x2,y2,x3,y3,x4,y4]$. Returns a Boolean value.
a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI
Try it online!
Computing a determinant, 130 bytes
Takes input as $[x1,x2,x3,x4]$ and $[y1,y2,y3,y4]$ in currying syntax. Returns a Boolean value.
This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.
x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))
Try it online!
add a comment |
up vote
6
down vote
up vote
6
down vote
JavaScript (ES6)
Testing the angles, 114 bytes
Takes input as the array $[x1,y1,x2,y2,x3,y3,x4,y4]$. Returns a Boolean value.
a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI
Try it online!
Computing a determinant, 130 bytes
Takes input as $[x1,x2,x3,x4]$ and $[y1,y2,y3,y4]$ in currying syntax. Returns a Boolean value.
This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.
x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))
Try it online!
JavaScript (ES6)
Testing the angles, 114 bytes
Takes input as the array $[x1,y1,x2,y2,x3,y3,x4,y4]$. Returns a Boolean value.
a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI
Try it online!
Computing a determinant, 130 bytes
Takes input as $[x1,x2,x3,x4]$ and $[y1,y2,y3,y4]$ in currying syntax. Returns a Boolean value.
This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.
x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))
Try it online!
edited Nov 18 at 8:46
answered Nov 17 at 23:29
Arnauld
70.3k686295
70.3k686295
add a comment |
add a comment |
up vote
4
down vote
TI-Basic (83 series), 21 bytes
e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3
Takes input as a list of four complex numbers in Ans
. Returns 1
if the quadrilateral is cyclic and 0
otherwise.
This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values $z_1, z_2, z_3, z_4$, then:
ΔList(augment(Ans,Ans
computes the differences $z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$ (and a few more redundant terms),
e^(ΔList(ln(
of that computes the ratios $frac{z_3-z_2}{z_2-z_1}, frac{z_4-z_3}{z_3-z_2}, frac{z_1-z_4}{z_4-z_3}, dots$.- We check if the product of the first and third terms, which is $frac{z_3-z_2}{z_2-z_1} cdot frac{z_1-z_4}{z_4-z_3}$, has no imaginary part. Note that this is the same as the cross-ratio $(z_3,z_1;z_2,z_4) = frac{z_2-z_3}{z_2-z_1} : frac{z_4-z_3}{z_4-z_1}$.
I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.
add a comment |
up vote
4
down vote
TI-Basic (83 series), 21 bytes
e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3
Takes input as a list of four complex numbers in Ans
. Returns 1
if the quadrilateral is cyclic and 0
otherwise.
This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values $z_1, z_2, z_3, z_4$, then:
ΔList(augment(Ans,Ans
computes the differences $z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$ (and a few more redundant terms),
e^(ΔList(ln(
of that computes the ratios $frac{z_3-z_2}{z_2-z_1}, frac{z_4-z_3}{z_3-z_2}, frac{z_1-z_4}{z_4-z_3}, dots$.- We check if the product of the first and third terms, which is $frac{z_3-z_2}{z_2-z_1} cdot frac{z_1-z_4}{z_4-z_3}$, has no imaginary part. Note that this is the same as the cross-ratio $(z_3,z_1;z_2,z_4) = frac{z_2-z_3}{z_2-z_1} : frac{z_4-z_3}{z_4-z_1}$.
I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.
add a comment |
up vote
4
down vote
up vote
4
down vote
TI-Basic (83 series), 21 bytes
e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3
Takes input as a list of four complex numbers in Ans
. Returns 1
if the quadrilateral is cyclic and 0
otherwise.
This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values $z_1, z_2, z_3, z_4$, then:
ΔList(augment(Ans,Ans
computes the differences $z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$ (and a few more redundant terms),
e^(ΔList(ln(
of that computes the ratios $frac{z_3-z_2}{z_2-z_1}, frac{z_4-z_3}{z_3-z_2}, frac{z_1-z_4}{z_4-z_3}, dots$.- We check if the product of the first and third terms, which is $frac{z_3-z_2}{z_2-z_1} cdot frac{z_1-z_4}{z_4-z_3}$, has no imaginary part. Note that this is the same as the cross-ratio $(z_3,z_1;z_2,z_4) = frac{z_2-z_3}{z_2-z_1} : frac{z_4-z_3}{z_4-z_1}$.
I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.
TI-Basic (83 series), 21 bytes
e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3
Takes input as a list of four complex numbers in Ans
. Returns 1
if the quadrilateral is cyclic and 0
otherwise.
This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values $z_1, z_2, z_3, z_4$, then:
ΔList(augment(Ans,Ans
computes the differences $z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$ (and a few more redundant terms),
e^(ΔList(ln(
of that computes the ratios $frac{z_3-z_2}{z_2-z_1}, frac{z_4-z_3}{z_3-z_2}, frac{z_1-z_4}{z_4-z_3}, dots$.- We check if the product of the first and third terms, which is $frac{z_3-z_2}{z_2-z_1} cdot frac{z_1-z_4}{z_4-z_3}$, has no imaginary part. Note that this is the same as the cross-ratio $(z_3,z_1;z_2,z_4) = frac{z_2-z_3}{z_2-z_1} : frac{z_4-z_3}{z_4-z_1}$.
I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.
answered Nov 18 at 17:31
Misha Lavrov
4,091424
4,091424
add a comment |
add a comment |
up vote
3
down vote
JavaScript (ES6) (101 bytes)
p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)
Takes input as [x1,y1,x2,y2,x3,y3,x4,y4]
, outputs a Boolean.
Checked based on $$ef=ac+bd$$ where $e,f$ are the diagonals and $a,b,c,d$ are the sides in order.
Try it online!
add a comment |
up vote
3
down vote
JavaScript (ES6) (101 bytes)
p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)
Takes input as [x1,y1,x2,y2,x3,y3,x4,y4]
, outputs a Boolean.
Checked based on $$ef=ac+bd$$ where $e,f$ are the diagonals and $a,b,c,d$ are the sides in order.
Try it online!
add a comment |
up vote
3
down vote
up vote
3
down vote
JavaScript (ES6) (101 bytes)
p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)
Takes input as [x1,y1,x2,y2,x3,y3,x4,y4]
, outputs a Boolean.
Checked based on $$ef=ac+bd$$ where $e,f$ are the diagonals and $a,b,c,d$ are the sides in order.
Try it online!
JavaScript (ES6) (101 bytes)
p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)
Takes input as [x1,y1,x2,y2,x3,y3,x4,y4]
, outputs a Boolean.
Checked based on $$ef=ac+bd$$ where $e,f$ are the diagonals and $a,b,c,d$ are the sides in order.
Try it online!
edited Nov 21 at 4:49
answered Nov 21 at 4:42
Alvin Li
415
415
add a comment |
add a comment |
up vote
2
down vote
Jelly, 11 bytes
²Sṭ;L€€ṖÆḊ¬
Try it online!
Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.
How it works
²Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
ṭ Append to the input
;L€€ Add two rows of [1,1,1,1]'s
Ṗ Remove an extra row
ÆḊ¬ Is the determinant zero?
Jelly, 12 bytes
Iµ÷×ƭ/÷SµḞ=A
Try it online!
Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.
How it works
Iµ÷×ƭ/÷SµḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
µ Refocus on above for sum function
÷×ƭ/÷S (z2-z1)÷(z3-z2)×(z4-z3)÷(z4-z1)
µ Refocus again
Ḟ=A (real part) == (norm) within error margin
i.e. imag part is negligible?
I believe both are golfable...
add a comment |
up vote
2
down vote
Jelly, 11 bytes
²Sṭ;L€€ṖÆḊ¬
Try it online!
Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.
How it works
²Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
ṭ Append to the input
;L€€ Add two rows of [1,1,1,1]'s
Ṗ Remove an extra row
ÆḊ¬ Is the determinant zero?
Jelly, 12 bytes
Iµ÷×ƭ/÷SµḞ=A
Try it online!
Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.
How it works
Iµ÷×ƭ/÷SµḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
µ Refocus on above for sum function
÷×ƭ/÷S (z2-z1)÷(z3-z2)×(z4-z3)÷(z4-z1)
µ Refocus again
Ḟ=A (real part) == (norm) within error margin
i.e. imag part is negligible?
I believe both are golfable...
add a comment |
up vote
2
down vote
up vote
2
down vote
Jelly, 11 bytes
²Sṭ;L€€ṖÆḊ¬
Try it online!
Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.
How it works
²Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
ṭ Append to the input
;L€€ Add two rows of [1,1,1,1]'s
Ṗ Remove an extra row
ÆḊ¬ Is the determinant zero?
Jelly, 12 bytes
Iµ÷×ƭ/÷SµḞ=A
Try it online!
Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.
How it works
Iµ÷×ƭ/÷SµḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
µ Refocus on above for sum function
÷×ƭ/÷S (z2-z1)÷(z3-z2)×(z4-z3)÷(z4-z1)
µ Refocus again
Ḟ=A (real part) == (norm) within error margin
i.e. imag part is negligible?
I believe both are golfable...
Jelly, 11 bytes
²Sṭ;L€€ṖÆḊ¬
Try it online!
Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.
How it works
²Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
ṭ Append to the input
;L€€ Add two rows of [1,1,1,1]'s
Ṗ Remove an extra row
ÆḊ¬ Is the determinant zero?
Jelly, 12 bytes
Iµ÷×ƭ/÷SµḞ=A
Try it online!
Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.
How it works
Iµ÷×ƭ/÷SµḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
µ Refocus on above for sum function
÷×ƭ/÷S (z2-z1)÷(z3-z2)×(z4-z3)÷(z4-z1)
µ Refocus again
Ḟ=A (real part) == (norm) within error margin
i.e. imag part is negligible?
I believe both are golfable...
answered Nov 21 at 7:01
Bubbler
6,154759
6,154759
add a comment |
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 25 bytes
{0=-/|⍵}(-⌿2 3⍴2/⌽)×⊃-1↓⊢
Try it online!
Ptolemy's theorem, credit: Кирилл Малышев's answer
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 25 bytes
{0=-/|⍵}(-⌿2 3⍴2/⌽)×⊃-1↓⊢
Try it online!
Ptolemy's theorem, credit: Кирилл Малышев's answer
add a comment |
up vote
1
down vote
up vote
1
down vote
APL (Dyalog Classic), 25 bytes
{0=-/|⍵}(-⌿2 3⍴2/⌽)×⊃-1↓⊢
Try it online!
Ptolemy's theorem, credit: Кирилл Малышев's answer
APL (Dyalog Classic), 25 bytes
{0=-/|⍵}(-⌿2 3⍴2/⌽)×⊃-1↓⊢
Try it online!
Ptolemy's theorem, credit: Кирилл Малышев's answer
answered Nov 22 at 17:41
ngn
6,53312459
6,53312459
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176162%2fis-this-quadrilateral-cyclic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown