# Construct n-gons with a ruler and compass

The task is to draw a regular polygon of n sides using only a compass and an unmarked ruler.

Input (n) is one of the following 10 numbers: 3, 4, 5, 6, 8, 10, 12, 15, 16, 17.

Method: Because you only have a ruler and compass you can only draw points, lines and circles.

A line can only be drawn:

• through two existing points.

A circle can only be drawn:

• with one point as its centre and with its perimeter passing through a second point.

A point can only be drawn:

• at the intersection of two lines,

• at the intersection(s) of a line and a circle,

• at the intersection(s) of two circles,

• at the outset, when you may draw 2 points to get started.

Through this process (and only through this process) you must draw the n lines of the requested n-gon, along with any working required to get to that stage.

EDIT: The position of intersections must be calculated, but lines and circles may be drawn by any means provided by the language.

Output is an image of an n-sided regular polygon, showing working.

Graphically there are no restrictions on image size, format, line thickness or anything else not mentioned here. However it must be possible to visually distinguish distinct lines, circles and their intersections. Additionally:

• The n lines that make up your n-gon's sides must be a different colour to your 'working' (i.e. any points, circles or other lines) and a different colour again to your background.
• Working can leave the borders of the drawing area, except points, which must all be within the visible bounds of the image.
• A circle can be a full circle or just an arc (as long as it shows required intersections).
• A line is infinite (i.e. leaves the drawing area) or cut off at the two points it goes through. EDIT: A line may be drawn at any length. Points can only be created where the drawn line visually intersects.
• A point can be drawn as you wish, including not marking it.

Scoring is twofold, a submission gets 1 point per input it supports, for a maximum of 10 points. In the event of a draw, shortest byte count wins.

Recognition will be given to submissions that can construct n-gons in the fewest steps or are able to construct n-gons outside of the given range, but it won't help your score.

Background info from Wikipedia

• If you allow lines to be cut off at the points they're defined by, that means relevant intersections could be outside the drawn line. – Martin Ender Oct 9 '14 at 21:17
• Can we use shortcuts like plotting two line segments AB and BC by plotting a single line strip ABC, if our language provides that? – Martin Ender Oct 9 '14 at 21:37
• Is it sufficient to draw the construction, or do does the program have to calculate it as well?. For example, if I want to draw a circle at the origin passing through the point (300,400) can i (knowing the radius is 500) do CIRCLE 0,0,500 or do I have to do R=SQRT(300^2+400^2): CIRCLE 0,0,R? (BTW working out postions of intersections is probably harder than lines and circles.) – Level River St Oct 10 '14 at 0:02
• From Wikipedia: Carl Friedrich Gauss in 1796 showed that a regular n-sided polygon can be constructed with straightedge and compass if the odd prime factors of n are distinct Fermat primes – Dr. belisarius Oct 10 '14 at 1:40
• Usually you call "unmarked ruler" as "straight edge" in mathematical terms, like the quote by belisarius. – justhalf Oct 10 '14 at 1:58

# BBC Basic, 8 polygons: 3,4,5,6,8,10,12,15 sides (also 60 sides)

I decided not to include 16 sides, simply because my pre-construction was getting rather cluttered. 2 more circles and a line would be needed. BTW 17 sides is very complicated indeed, and would perhaps go best as a separate program.

I got more return for adding 2 circles to my original construction to make the pentagon, as this also gave me access to 10,15 and 60 sides.

  GCOL 7                               :REM light grey
z=999                                :REM width of display (in positive and negative direction)
e=1                                  :REM enable automatic drawing of line through intersections of 2 circles
DIM m(99),c(99),p(99),q(99),r(99)    :REM array dimensioning for lines and points
REM lines have a gradient m and y-intercept c. Points have coordinates (p,q) and may be associated with a circle of radius r.

REM PRECONSTRUCTION

ORIGIN 500,500
p(60)=0:q(60)=0                      :REM P60=centre of main circle
p(15)=240:q(15)=70                   :REM P15=intersection main circle & horiz line
t=FNr(60,15)                         :REM draw main circle, set radius, SQR(240^2+70^2)=250 units (125 pixels)
t=FNl(1,60,15)                       :REM L1=horizontal through main circle
t=FNc(15,45,1,60,-1)                 :REM define P45 as other intersection of main cir and horiz line. overwrite P15 with itself.

t=FNr(15,45):t=FNr(45,15)            :REM draw 2 large circles to prepare to bisect L1
t=FNc(61,62,2,45,15)                 :REM bisect L1, forming line L2 and two new points
t=FNc(30,0,2,60,-1)                  :REM define points P0 and P30 on the crossings of L2 and main circle
t=FNr(30,60):t=FNc(40,20,3,60,30)    :REM draw circles at P30, and line L3 through intersections with main circle, to define 2 more points
t=FNr(15,60):t=FNc(25,5,4,60,15)     :REM draw circles at P15, and line L4 through intersections with main circle, to define 2 more points
t=FNx(63,3,4):t=FNl(5,63,60)         :REM draw L5 at 45 degrees
t=FNc(64,53,5,60,-1)                 :REM define where L5 cuts the main circle

e=0                                  :REM disable automatic line drawing through intersections of 2 circles
GCOL 11                              :REM change to light yellow for the 5 sided preconstruction
t=FNx(65,1,4):t=FNr(65,0)            :REM draw a circle of radius sqrt(5) at intersection of L1 and L4
t=FNc(66,67,1,65,-1)                 :REM find point of intersection of this circle with L1
t=FNr(0,67)                          :REM draw a circle centred at point 0 through that intersection
t=FNc(36,24,6,60,0)                  :REM find the intersections of this circle with the main circle

REM USER INPUT AND POLYGON DRAWING

INPUT d
g=ASC(MID\$("  @@XT u X @  T",d))-64  :REM sides,first point: 3,0; 4,0; 5,24; 6,20; 8,53; 10,24; 12,0; 15,20
IF d=60 THEN g=24                    :REM bonus polygon 60, first point 24
FORf=0TOd
GCOL12                             :REM blue
h=(g+60DIVd)MOD60                  :REM from array index for first point, calculate array index for second point
t=FNr(h,g)                         :REM draw circle centred on second point through first point
t=FNc((h+60DIVd)MOD60,99,99,60,h)  :REM calculate the position of the other intersection of circle with main circle. Assign to new point.
GCOL9                              :REM red
LINEp(g),q(g),p(h),q(h)            :REM draw the side
g=h                                :REM advance through the array
NEXT

END

REM FUNCTIONS

REM line through a and b
DEFFNl(n,a,b)
m(n)=(q(a)-q(b))/(p(a)-p(b))
c(n)=q(a)-m(n)*p(a)
LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z
=n

REM radius of circle at point a passing through point b
DEFFNr(a,b)
r(a)=SQR((p(a)-p(b))^2+(q(a)-q(b))^2)
CIRCLEp(a),q(a),r(a)
=a

REM intersection of 2 lines: ma*x+ca=mb*x+cb so (ma-mb)x=cb-ca
DEFFNx(n,a,b)
p(n)=(c(b)-c(a))/(m(a)-m(b))
q(n)=m(a)*p(n)+c(a)
=n

REM intersection of 2 circles a&b (if b>-1.) The first step is calculating the line through the intersections
REM if b < 0 the first part of the function is ignored, and the function moves directly to calculating intersection of circle and line.
REM inspiration from http://math.stackexchange.com/a/256123/137034

DEFFNc(i,j,n,a,b)
IF b>-1 c(n)=((r(a)^2-r(b)^2)-(p(a)^2-p(b)^2)-(q(a)^2-q(b)^2))/2/(q(b)-q(a)):m(n)=(p(a)-p(b))/(q(b)-q(a)):IF e LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z

REM intersection of circle and line
REM (mx+ c-q)^2+(x-p)^2=r^2
REM (m^2+1)x^2 + 2*(m*(c-q)-p)x + (c-q)^2+p^2-r^2=0
REM quadratic formula for ux^2+vx+w=0 is x=-v/2u +/- SQR(v^2-4*u*w)/2u or x= v/2u +/- SQR((v/2u)^2 - w/u)

u=m(n)^2+1
v=-(m(n)*(c(n)-q(a))-p(a))/u               :REM here v corresponds to v/2u in the formula above
w=SQR(v^2-((c(n)-q(a))^2+p(a)^2-r(a)^2)/u)

s=SGN(c(n)+m(n)*v-q(a)):IF s=0 THEN s=1    :REM sign of s depends whether midpoint between 2 points to be found is above centre of circle a
p(i)=v+s*w:q(i)=m(n)*p(i)+c(n)             :REM find point that is clockwise respect to a
p(j)=v-s*w:q(j)=m(n)*p(j)+c(n)             :REM find point that is anticlockwise respect to a
=n


The program does a pre-construction before asking for any user input. This is sufficient to define at least 2 points on the main circle which correspond to adjacent vertices of a 3,4,5,6,8,10,12,15 or 60 sided figure. The points are stored in a set of 99-element arrays, in which elements 0-59 are set aside for equally spaced points around the circumference. This is mainly for clarity, the octagon does not fit perfectly into 60 points so some flexibility is needed there (and also for the 16-gon if it were included.) The image looks like the image below, in white and grey, with only the two circles in yellow being exclusively dedicated to shapes with multiples of 5 sides. See http://en.wikipedia.org/wiki/Pentagon#mediaviewer/File:Regular_Pentagon_Inscribed_in_a_Circle_240px.gif for my preferred pentagon drawing method. The jaunty angle is to avoid vertical lines, as the program cannot handle infinite gradients. The user inputs a number d for the number of sides required. The program looks up in the array the index of the first of the two points (the next one is 60/d away in a clockwise direction.)

The program then loops through the process of drawing a circle centred on the second point that passes throug the first, and calculating the new intersection in order to walk its way round the main circle. The construction circles are drawn in blue, and the required polygon is drawn in red. The final images look like this.

I'm quite pleased with them. BBC Basic performs the calculations accurately enough. However its apparent (particularly with 15 and 60 sides) that BBC Basic tends to draw circles with a slightly smaller radius than it should. • One trick I missed with this is that the 45-degree line cuts the main circle just beside two circles that can be used to construct the 24-gon and 40-gon, both factors of 120. There are two factors of 60 (20 and 30) missing, which would require one more circle in the preconstruction, to define the two missing corners of the pentagon and give the differences 1/5-1/6=1/30 and 1/5-1/4=1/20. However I don't think I'll be updating my answer at the moment. BTW, Thanks for the bonus @Martin! – Level River St Oct 22 '14 at 23:19

## Mathematica, 23 4 polygons, 759 bytes

S=Solve;n=Norm;A=Circle;L=Line;c={#,Norm[#-#2]}&{a_,b_List}~p~{c_,d_List}:=a+l*b/.#&@@S[a+l*b==c+m*d,{l,m}]{a_,b_List}~p~{c_,r_}:=a+l*b/.S[n[c-a-l*b]==r,l]{c_,r_}~p~{d_,q_}:={l,m}/.S[n[c-{l,m}]==r&&n[d-{l,m}]==q,{l,m}]q={0,0};r={1,0};a=q~c~r;b=r~c~q;Graphics@Switch[Input[],3,{s=#&@@p[a,b];A@@@{a,b},Red,L@{q,r,s,q}},4,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;A@@@{a,b,d},L/@Accumulate/@{k,j},Red,L@{q,e,r,f,q}},6,{d={q,r};e=#&@@d~p~a;f=e~c~q;{g,h}=a~p~f;{i,j}=a~p~b;A@@@{a,b,f},L@{#-2#2,#+2#2}&@@d,Red,L@{r,i,g,e,h,j,r}},8,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;g=e~c~q;h=q~c~e;i=r~c~e;{o,s}=g~p~h;{t,u}=g~p~i;o={o,2s-2o};s={t,2u-2t};{t,u}=o~p~d;{v,w}=s~p~d;A@@@{a,b,d,g,h,i},L/@Accumulate/@{k,j,o,s},Red,L@{q,t,e,v,r,u,f,w,q}}]


Random bullet points:

• Input is provided via prompt.
• I'm currently supporting inputs 3, 4, 6, 8.
• From your options, I chose the following plotting styles:
• Full circles.
• Lines from endpoint to endpoint, unless a relevant intersection lies outside, in which case I'll hardcode the extent.
• No points.
• Workings are black, polygons are red - not for aesthetic but for golfing reasons.
• There's some serious code duplication between the polygons. I think at some point I'll just do a single construction for all of them, enumerating all lines and points and circles along the way, and then just reduce the Switch to select the relevant circles and lines for each construction. That way I could reuse a lot of primitives between them.
• The code contains a lot of boilerplate functions which determine all the relevant intersections, and create circles from two points.
• With that in place, I will be adding more polygons in the future.

Here is the ungolfed code:

S = Solve;
n = Norm;
A = Circle;
L = Line;
c = {#, Norm[# - #2]} &
{a_, b_List}~p~{c_, d_List} :=
a + l*b /. # & @@ S[a + l*b == c + m*d, {l, m}]
{a_, b_List}~p~{c_, r_} := a + l*b /. S[n[c - a - l*b] == r, l]
{c_, r_}~p~{d_, q_} := {l, m} /.
S[n[c - {l, m}] == r && n[d - {l, m}] == q, {l, m}]
q = {0, 0};
r = {1, 0};
a = q~c~r;
b = r~c~q;
Graphics@Switch[Input[],
3,
{
s = # & @@ p[a, b];
A @@@ {a, b},
Red,
L@{q, r, s, q}
},
4,
{
k = {q, r};
{d, e} = a~p~b;
j = {d, e - d};
d = k~p~j~c~q;
{e, f} = j~p~d;
A @@@ {a, b, d},
L /@ Accumulate /@ {k, j},
Red,
L@{q, e, r, f, q}
},
6,
{
d = {q, r};
e = # & @@ d~p~a;
f = e~c~q;
{g, h} = a~p~f;
{i, j} = a~p~b;
A @@@ {a, b, f},
L@{# - 2 #2, # + 2 #2} & @@ d,
Red,
L@{r, i, g, e, h, j, r}
},
8,
{
k = {q, r};
{d, e} = a~p~b;
j = {d, e - d};
d = k~p~j~c~q;
{e, f} = j~p~d;
g = e~c~q;
h = q~c~e;
i = r~c~e;
{o, s} = g~p~h;
{t, u} = g~p~i;
o = {o, 2 s - 2 o};
s = {t, 2 u - 2 t};
{t, u} = o~p~d;
{v, w} = s~p~d;
A @@@ {a, b, d, g, h, i},
L /@ Accumulate /@ {k, j, o, s},
Red,
L@{q, t, e, v, r, u, f, w, q}
}
]


And here are the outputs:    • Just wondering if it would be shorter to hard code the red and black lines and circles for each input type and draw them. – Optimizer Oct 10 '14 at 9:37
• @Optimizer I suppose for larger n exact expressions for the points will probably become quite long, too. I think when I add more polygons, at some point it will make sense to make one single construction for all of them, and then just select the relevant circles and lines in the Switch. That would probably allow me to reuse a lot more circles lines and points. – Martin Ender Oct 10 '14 at 9:43
• I this I have a shorter way to construct the octagon, but I'm not sure how to show it to you... – proud haskeller Oct 12 '14 at 12:39
• @proudhaskeller Is it still shorter if you consider that the first 5 lines of the construction could actually be ditched be reusing code from the square, and that this way of constructing it could potentially be generalised to construct any 2n-gon from an n-gon? (Both things, I have in mind for improving this.) If so... ummm... I suppose a rigorous description with named points like this one would work. – Martin Ender Oct 12 '14 at 12:42
• @proudhaskeller You could instead post it yourself before the bounty expires. ;) – Martin Ender Oct 13 '14 at 10:01