Konstruuj n-gony za pomocą linijki i kompasu

16

Zadanie polega na narysowaniu regularnego wielokąta n boków za pomocą tylko kompasu i nieoznakowanej linijki.

Dane wejściowe (n) to jedna z następujących 10 liczb: 3, 4, 5, 6, 8, 10, 12, 15, 16, 17.

Metoda : Ponieważ masz tylko linijkę i kompas, możesz rysować tylko punkty, linie i okręgi.

Linię można narysować tylko:

  • przez dwa istniejące punkty.

Koło można narysować tylko:

  • z jednym punktem jako środkiem, a jego obwód przechodzi przez drugi punkt.

Punkt można narysować tylko:

  • na przecięciu dwóch linii

  • na przecięciu linii i koła

  • na przecięciu dwóch kręgów

  • na początku, kiedy możesz narysować 2 punkty, aby rozpocząć.

Poprzez ten proces (i tylko przez ten proces) musisz narysować n linii żądanego n-gona wraz z wszelkimi pracami wymaganymi do przejścia do tego etapu.

EDYCJA: Pozycja skrzyżowań musi zostać obliczona, ale linie i okręgi można narysować dowolnymi środkami przewidzianymi przez język.

Wyjście to obraz wielokąta n-stronnego, przedstawiający działanie.

Graficznie nie ma żadnych ograniczeń dotyczących rozmiaru obrazu, formatu, grubości linii lub czegokolwiek innego nie wymienionego tutaj. Musi być jednak możliwe wizualne rozróżnienie wyraźnych linii, okręgów i ich przecięć. Do tego:

  • N linii, które składają się na boki twojego n-gona, muszą mieć inny kolor niż twój „działający” (tj. Dowolne punkty, koła lub inne linie) oraz inny kolor tła.
  • Praca może opuścić granice obszaru rysunku, z wyjątkiem punktów, które muszą znajdować się w widocznych granicach obrazu.
  • Okrąg może być pełnym kołem lub tylko łukiem (o ile pokazuje wymagane przecięcia).
  • Linia jest nieskończona (tzn. Opuszcza obszar rysowania) lub odcięta w dwóch punktach, przez które przechodzi. EDYCJA: Linia może być narysowana na dowolnej długości. Punkty można tworzyć tylko tam, gdzie narysowana linia przecina się wizualnie.
  • Punkt można narysować według własnego uznania, w tym nie oznaczać go.

Punktacja jest dwojaka, zgłoszenie otrzymuje 1 punkt za każdy obsługiwany wkład, co daje maksymalnie 10 punktów. W przypadku remisu wygrywa najkrótsza liczba bajtów.

Uznanie zostanie przyznane tym, które mogą skonstruować n-gony w jak najmniejszej liczbie kroków lub są w stanie skonstruować n-gony poza podanym zakresem, ale to nie poprawi twojego wyniku.

Informacje podstawowe z Wikipedii

jsh
źródło
Jeśli zezwolisz na odcinanie linii w punktach, w których są zdefiniowane, oznacza to, że odpowiednie skrzyżowania mogą znajdować się poza narysowaną linią.
Martin Ender
Czy możemy używać skrótów, takich jak wykreślanie dwóch segmentów linii AB i BC, wykreślając pasek ABC z jedną linią, jeśli nasz język to zapewnia?
Martin Ender
1
Czy wystarczy narysować konstrukcję, czy też program musi ją również obliczyć ?. Na przykład, jeśli chcę narysować okrąg w punkcie początkowym przechodzącym przez punkt (300,400), czy mogę (wiedząc, że promień wynosi 500) zrobić, CIRCLE 0,0,500czy muszę R=SQRT(300^2+400^2): CIRCLE 0,0,R? (BTW wypracowanie pozycji skrzyżowań jest prawdopodobnie trudniejsze niż linie i okręgi.)
Level River St
Z Wikipedii: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,
Zwykle nazywacie „nieoznakowaną linijkę” matematycznie „prostą krawędzią”, jak cytat Belizariusza.
justhalf 10.10.14

Odpowiedzi:

10

BBC Basic, 8 wielokątów: 3,4,5,6,8,10,12,15 strony (także 60 stron)

Pobierz emulator ze strony http://www.bbcbasic.co.uk/bbcwin/download.html

Postanowiłem nie uwzględniać 16 stron, po prostu dlatego, że moja przedkonstrukcja była dość zagracona. Potrzebne byłyby jeszcze 2 kółka i linia. BTW 17 stron jest naprawdę bardzo skomplikowane i być może najlepiej byłoby, gdyby był to osobny program.

Dostałem więcej zwrotu za dodanie 2 kółek do mojej oryginalnej konstrukcji, aby stworzyć pięciokąt, ponieważ to również dało mi dostęp do 10,15 i 60 stron.

  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

Program wykonuje wstępną konstrukcję, zanim poprosi o dane wejściowe użytkownika. To wystarczy, aby zdefiniować co najmniej 2 punkty na głównym okręgu, które odpowiadają sąsiednim wierzchołkom figury 3,4,5,6,8,10,10,15 lub 60-stronnej. Punkty są przechowywane w zestawie 99-elementowych tablic, w których elementy 0-59 są odłożone na równomiernie rozmieszczone punkty na obwodzie. Ma to głównie na celu zapewnienie przejrzystości, ośmiokąt nie mieści się idealnie w 60 punktach, więc potrzebna jest tam pewna elastyczność (a także 16-gon, jeśli byłby uwzględniony). Zdjęcie wygląda jak zdjęcie poniżej, w kolorze białym i szarym, z tylko dwa żółte kółka poświęcone są wyłącznie kształtom z wielokrotnością 5 boków. Zobacz http://en.wikipedia.org/wiki/Pentagon#mediaviewer/File:Regular_Pentagon_Inscribe_in_a_Circle_240px.gifdla mojej preferowanej metody rysowania pięciokątem. Jawny kąt ma na celu uniknięcie linii pionowych, ponieważ program nie obsługuje nieskończonych gradientów.

wprowadź opis zdjęcia tutaj

Użytkownik wprowadza liczbę dwymaganej liczby stron. Program wyszukuje w tablicy indeks pierwszego z dwóch punktów (następny znajduje się 60 / d dalej w kierunku zgodnym z ruchem wskazówek zegara).

Następnie program przechodzi przez proces rysowania koła wyśrodkowanego na drugim punkcie przechodzącym przez pierwszy i obliczania nowego skrzyżowania w celu obejścia głównego koła. Koła konstrukcyjne są narysowane na niebiesko, a wymagany wielokąt jest narysowany na czerwono. Ostateczne obrazy wyglądają tak.

Jestem z nich bardzo zadowolony. BBC Basic wykonuje obliczenia wystarczająco dokładnie. Jednak jest oczywiste (szczególnie z 15 i 60 bokami), że BBC Basic ma tendencję do rysowania kół o nieco mniejszym promieniu niż powinien.

wprowadź opis zdjęcia tutaj

Level River St
źródło
1
Jedną sztuczką, której mi brakowało, jest to, że linia 45 stopni przecina główny okrąg tuż obok dwóch kół, których można użyć do zbudowania 24-gon i 40-gon, oba to czynniki 120. Istnieją dwa czynniki 60 (20 i 30) brakujące, co wymagałoby jeszcze jednego koła w prekonstrukcji, aby zdefiniować dwa brakujące narożniki pięciokąta i podać różnice 1 / 5-1 / 6 = 1/30 i 1 / 5-1 / 4 = 1/20 . Jednak nie sądzę, żebym w tej chwili aktualizował swoją odpowiedź. BTW, dzięki za bonus @Martin!
Level River St
16

Mathematica, 2 3 4 wielokąty, 759 bajtów

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}}]

Losowe punkty wypunktowania:

  • Dane wejściowe są dostarczane za pośrednictwem monitu.
  • Obecnie obsługuję dane wejściowe 3 , 4 , 6 , 8 .
  • Z twoich opcji wybrałem następujące style wydruku:
    • Pełne kręgi.
    • Linie od punktu końcowego do punktu końcowego, chyba że odpowiednie skrzyżowanie leży na zewnątrz, w takim przypadku zakoduję zakres na stałe.
    • Brak punktów.
    • Obróbki są czarne, wielokąty są czerwone - nie ze względów estetycznych, ale z powodów golfowych.
  • Między wielokątami występuje poważne powielanie kodu. Myślę, że w pewnym momencie zrobię po prostu jedną konstrukcję dla wszystkich z nich, wyliczając wszystkie linie, punkty i okręgi po drodze, a następnie po prostu zmniejszę, Switchaby wybrać odpowiednie koła i linie dla każdej konstrukcji. W ten sposób mogłem ponownie wykorzystać wiele prymitywów między nimi.
  • Kod zawiera wiele funkcji typu plansza, które określają wszystkie odpowiednie skrzyżowania i tworzą koła z dwóch punktów.
  • Mając to na miejscu, będę dodawać więcej wielokątów w przyszłości.

Oto nielepszy kod:

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}
   }
  ]

A oto wyniki:

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Martin Ender
źródło
Zastanawiam się tylko, czy krótsze byłoby na stałe zakodować czerwone i czarne linie i okręgi dla każdego typu danych wejściowych i narysować je.
Optymalizator
@Optimizer Podejrzewam, że dla większych n dokładnych wyrażeń dla punktów prawdopodobnie również będą one dość długie. Myślę, że kiedy dodam więcej wielokątów, w pewnym momencie sensowne będzie utworzenie jednej konstrukcji dla wszystkich z nich, a następnie wybranie odpowiednich okręgów i linii w Switch. To prawdopodobnie pozwoliłoby mi ponownie użyć znacznie więcej linii i punktów w kręgach.
Martin Ender
Ja to mam krótszy sposób na zbudowanie ośmiokąta, ale nie jestem pewien, jak ci to pokazać ...
dumny haskeller
@proudhaskeller Czy jest jeszcze krótszy, jeśli weźmie się pod uwagę, że pierwszych 5 wierszy konstrukcji można porzucić, ponownie wykorzystując kod z kwadratu, i że ten sposób konstruowania można potencjalnie uogólnić, aby skonstruować dowolny 2n-gon z n-gonu ? (Obie rzeczy mam na myśli, aby to poprawić.) Jeśli tak ... ummm ... Przypuszczam, że rygorystyczny opis z nazwanymi punktami, taki jak ten , zadziałałby.
Martin Ender
@proudhaskeller Możesz zamiast tego opublikować go samodzielnie, zanim wygasa nagroda. ;)
Martin Ender