Kurva aljabar adalah "subset 1D" tertentu dari "bidang-2D" yang dapat digambarkan sebagai seperangkat nol {(x,y) in R^2 : f(x,y)=0 }dari polinomial f. Di sini kita menganggap bidang 2D sebagai bidang nyata R^2sehingga kita dapat dengan mudah membayangkan seperti apa bentuk kurva itu, pada dasarnya benda yang bisa Anda gambar dengan pensil.

Contoh:

• 0 = x^2 + y^2 -1 lingkaran jari-jari 1
• 0 = x^2 + 2y^2 -1 sebuah elips
• 0 = xy sebuah salib bentuk, pada dasarnya persatuan sumbu x dan sumbu y
• 0 = y^2 - x sebuah parabola
• 0 = y^2 - (x^3 - x + 1)sebuah kurva eliptik
• 0 = x^3 + y^3 - 3xy folium dari Descartes
• 0 = x^4 - (x^2 - y^2) sebuah lemniscate
• 0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) sebuah trifolium
• 0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 astroid

Tugas

Diberikan polinomial f(seperti yang didefinisikan di bawah), dan rentang x / y, menghasilkan gambar hitam dan putih minimal 100x100 piksel yang menunjukkan kurva sebagai garis hitam pada latar belakang putih.

Detail

Warna : Anda dapat menggunakan dua warna lain pilihan Anda, seharusnya mudah membedakannya.

Plot : Alih-alih gambar piksel Anda juga dapat menampilkan gambar ini sebagai ascii-art, di mana latar belakang "piksel" harus spasi / garis bawah atau karakter lain yang "terlihat kosong" dan garis dapat dibuat dari karakter yang terlihat " penuh "suka Matau Xatau #.

Anda tidak perlu khawatir tentang aliasing.

Anda hanya perlu memplot garis di mana tanda perubahan polinomial dari satu sisi garis ke yang lain (itu berarti Anda bisa misalnya menggunakan algoritma marching square), Anda tidak perlu memplot dengan benar "kasus patologis seperti di 0 = x^2mana tanda tidak tidak berubah ketika pergi dari satu sisi garis ke yang lain. Tapi garis harus kontinu dan memisahkan wilayah dari tanda - tanda yang berbeda f(x,y).

Polinomial : Polinomial diberikan sebagai (m+1) x (n+1)matriks / daftar daftar koefisien (nyata), dalam contoh di bawah ini syarat-syarat koefisien diberikan dalam posisi mereka:

[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

Jika Anda suka, Anda dapat mengasumsikan matriks menjadi kuadrat (yang selalu dapat dilakukan dengan zero-padding yang diperlukan), dan jika Anda mau, Anda juga dapat mengasumsikan bahwa ukuran matriks diberikan sebagai input tambahan.

Berikut ini, contoh-contoh dari atas direpresentasikan sebagai matriks yang didefinisikan seperti ini:

Circle:       Ellipse:      Parabola:  Cross:    Elliptic Curve: e.t.c
[-1, 0, 1]    [-1, 0, 1]    [ 0,-1]    [ 0, 0]   [-1, 1, 0,-1]
[ 0, 0, 0]    [ 0, 0, 0]    [ 0, 0]    [ 0, 1]   [ 0, 0, 0, 0]
[ 1, 0, 0]    [ 2, 0, 0]    [ 1, 0]              [ 1, 0, 0, 0]

Uji kasus dengan kisaran x / rentang y:

(Dalam format yang tidak begitu mudah dibaca tetapi lebih baik salin-tempel tersedia di sini di pastebin .)

Circle:     
[-1, 0, 1]   [-2,2]   [-2,2]
[ 0, 0, 0]
[ 1, 0, 0]

Ellipse:
[-1, 0, 1]   [-2,2]   [-1,1]
[ 0, 0, 0]
[ 2, 0, 0]

Cross:
[ 0, 0]      [-1,2]   [-2,1]
[ 0, 1]

Parabola:
[ 0,-1]      [-1,3]   [-2,2]
[ 0, 0]
[ 1, 0]

Elliptic Curve:
[-1, 1, 0,-1]    [-2,2]   [-3,3]
[ 0, 0, 0, 0]  
[ 1, 0, 0, 0]  

Folium of Descartes:
[  0,  0,  0,  1]    [-3,3]   [-3,3]
[  0, -3,  0,  0]
[  0,  0,  0,  0]
[  1,  0,  0,  0]

Lemniscate:
[  0,  0, -1,  0,  1]    [-2,2]   [-1,1]
[  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0]

Trifolium:
[ 0, 0, 0,-1, 1]    [-1,1]   [-1,1]
[ 0, 0, 0, 0, 0]
[ 0, 3, 2, 0, 0]
[ 0, 0, 0, 0, 0]
[ 1, 0, 0, 0, 0]

Astroid:
[ -1,  0,  3,  0, -3,  0,  1]    [-1,1]   [-1,1]
[  0,  0,  0,  0,  0,  0,  0]
[  3,  0, 21,  0,  3,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[ -3,  0,  3,  0,  0,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0,  0,  0]

Saya mendapatkan inspirasi untuk beberapa kurva dari pdf ini.

Haskell, 283 275 byte

Fungsi gharus dipanggil dengan matriks dan dua rentang sebagai argumen. Matriks hanya daftar daftar, rentang masing-masing daftar elemen dua.

import Data.List
t=transpose
u=tail
z=zipWith
l%x=sum$z(*)l$iterate(*x)1                                   --generate powers and multiply with coefficients
e m y x=[l%x|l<-m]%y                                         --evaluate the encoded polynomial
a#b=[a,a+(b-a)/102..b]                                       --create a range
g m[u,w][i,j]=unlines$v[map((0<).e m y)$u#w|y<-i#j]          --evaluate the function on the grid, get the sign
f g=u[u$u$map fst$scanl(\(r,l)c->(c==l,c))(1<0,1<0) l|l<-g]  --find +- or -+ transitions within lines
a&b|a&&b=' '|0<1='#'                                         --helper function for creating the string
v g=z(z(&))(f g)(t$f$t g)                                    --create the string

Di sini keluaran untuk kasus-kasus yang lebih menarik: Perhatikan bahwa saya harus mengurangi ukuran dari 100x100 menjadi sekitar 40x40 sehingga masih pas di konsol (cukup ganti hardcoded 102 ke angka yang lebih kecil). Perhatikan juga bahwa sumbu y mengarah ke bawah.

Matlab, 114 100 92 byte

Alat yang tepat untuk pekerjaan itu? Saya menggunakan cara menarik Matlab printfuntuk menghasilkan polinomial sebagai string. Polinomial ini dapat disediakan untuk ezplotmemplot kurva implisit pada domain yang ditentukan. Agar mudah dibaca, kode disajikan dengan baris baru setelah; yang tidak diperlukan dan tidak dihitung terhadap ukuran.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Perkembangan golf sebagai cuplikan yang dapat diperluas.

Iteration 1, clean arguments, 114 bytes
---------------------------------------
function P(A,W,H)
h=size(A,1);
t=0:numel(A)-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 1.5, historical revisionism (thanks @flawr), 111 bytes
--------------------------------------------------------------
function P(A,W,H)
[h,w]=size(A);
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])


Iteration 2, playing dirty, 100 bytes
-------------------------------------
The code can be golfed further if I use that taking matrix sizes as inputs are
fair game, but it feels sad to ruin such neat input arguments. However,
this is code golf and I'll abuse anything I can and I end up at a nice 100 bytes:

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H]);

Iteration 2.5, fix your code (thanks @LuisMendo), 98 bytes
----------------------------------------------------------
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';fix(t/h);rem(t,h)]),[W,H]);

Iteration 3, more power to printf, 92 bytes [current best]
----------------------------------------------------------
Use `%.0f` instead of `fix`/`floor`.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Output dari kasus uji (klik untuk tampilan penuh):

Python 2, 261 byte

E=enumerate
M,[a,c],[b,d]=input()
e=(c-a)/199.
I=200
J=-int((b-d)/e-1)
print'P2',I,J,255
i=I*J
while i:i-=1;x,y=c-i%I*e,b+i/I*e;u,v,w=map(sum,zip(*((z*p/x,z*q/y,z)for q,R in E(M)for p,t in E(R)for z in[t*x**p*y**q])));print int(255*min(1,(w*w/(u*u+v*v))**.5/e))

Format input: matrix,xbounds,ybounds(misalnya [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Format output: PGM polos .

Ini memperkirakan jarak dari setiap pusat piksel ke kurva menggunakan pendekatan orde pertama d ( x , y ) = | p ( x , y ) | / | ∇ p ( x , y ) |, di mana ∇ p adalah gradien dari polinomial p . (Ini adalah jarak dari ( x , y ) ke persimpangan bidang tangen pada ( x , y , p ( x , y )) dengan xy .) Kemudian piksel tempat d (x , y) kurang dari satu piksel lebar kurva secara proporsional ke d ( x , y ), menghasilkan garis antialias yang bagus (meskipun itu bukan keharusan).

Berikut adalah grafik yang sama dengan fungsi jarak dibagi 16 untuk membuatnya terlihat.

Python 3.5 + MatPlotLib + Numpy, 352 byte:

from matplotlib.pyplot import*;from numpy import*
def R(M,S,U,r=range):N=linspace;E='+'.join([str(y)+'*'+m for y,m in[q for i,g in zip(M,[[i+'*'+p for p in['1']+['x^%d'%p for p in r(1,len(M[0]))]]for i in['1']+['y^%d'%i for i in r(1,len(M))]])for q in zip(i,g)if q[0]]]);x,y=meshgrid(N(*S,200),N(*U,200));contour(x,y,eval(E.replace('^','**')),0);show()

Fungsi bernama. Cukup lama, tapi hei, saya senang saya bisa menyelesaikan tugas. Mengambil 3 input, yaitu m by nmatriks, x-range, dan y-range, yang semuanya harus dalam array (misalnya, [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Menghasilkan grafik yang selesai di jendela baru, grafis, interaktif. Akankah golf ini turun lebih banyak waktu ketika saya bisa, tetapi untuk sekarang, saya senang dengan itu.

Hasil Akhir untuk Kasus Uji:

MATL , 67 61 byte

8Wt:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4=0YG

Kode ini berjalan pada rilis 18.5.0 bahasa, yang mendahului tantangan. Input menggunakan opsionalm , nparameter. Matriks memiliki titik koma sebagai pemisah baris. Format input yang tepat (menggunakan parabola sebagai contoh) adalah

[-1,3]
3  
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Kode menghasilkan gambar dengan ukuran 255 × 255. Hal ini dapat diuji dengan menggunakan @Suever 's MATL online compiler, yang antara fitur yang sangat menarik lainnya, termasuk output grafis. Lihat misalnya

• Kurva berbentuk bulat panjang ;
• Folium dari Descartes .

Kompiler ini masih dalam tahap percobaan. Silakan laporkan masalah apa pun ke @Suever di obrolan MATL . Jika tombol "Jalankan" tidak berfungsi, coba segarkan halaman dan klik lagi.

Jika Anda lebih suka keluaran ASCII , kode perlu dimodifikasi sedikit (perubahan hanya mempengaruhi dua karakter pertama dan terakhir dari kode di atas):

101t:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4<42*c

Ini menghasilkan kisi ASCII 100 × 100 yang menggunakan karakter *untuk mewakili kurva. Anda juga dapat menguji ini dengan @Dennis ' Coba online! peron:

• Kurva berbentuk bulat panjang ;
• Folium dari Descartes .

Perhatikan bahwa rasio aspek keluaran ASCII diubah karena karakternya sedikit lebih tinggi daripada lebar.

Penjelasan

Kode pertama menghitung polinomial dua variabel pada kisi x - y . Ini membuat penggunaan penyiaran , komputasi array 4D menengah di mana masing-masing dimensi mewakili nilai x , nilai y , eksponen x , eksponen y masing-masing.

Dari fungsi itu, garis level nol dihitung. Karena tantangan menentukan bahwa hanya perubahan tanda yang perlu dideteksi, kode tersebut menerapkan konvolusi 2D dengan blok 2 × 2, dan menandai piksel sebagai bagian dari garis jika tidak keempat nilai blok memiliki tanda yang sama.

8W      % Push 2^8, that is, 256. (The ASCII-output version pushes 101 instead)
t:q     % Duplicate. Push range [0 1 ... 255]
wq      % Swap. Subtract 1 to obtain 255
/       % Divide. Gives normalized range [0 1/255 2/255... 1]
t       % Duplicate
2:"     % For loop: do this twice
  w     %   Swap top two elements in the stack
  i     %   Input two-number array defining x range (resp. y in second iteration)
  d     %   Difference of the two entries
  *     %   Multiply by normalized range
  2M1)  %   Push the array again and get its first entry
  +     %   Add. This gives the range for x values (resp. y)
  i     %   Input m (n in second iteration)
  :q    %   Range [0 1 ...m-1] (resp. [0 1 ...n-1])
  !     %   Convert to column array
  ^     %   Power, element-wise with broadcast. This gives a matrix of size m×256
        %   (resp. n×256) of powers of x (resp. y) for the range of values computed
        %   previously
]       % End for loop
!       % Transpose. This transforms the n×256 matrix of powers of y into 256×n
2       % Push 2
&!      % Permute dimensions 1 and 3: transforms the 256×n matrix into a 4D array
        % of size 1×n×256×1
w       % Swap top two elements in the stack: bring 256×m matrix to top
[1IK2]  % Push vector [1 3 4 2]
&!      % Permute dimensions as indicated by the vector: transforms the m×256 matrix
        % into a 4D array of size m×1×1×256
*       % Multiply element-wise with broadcast: gives 4D array of size m×n×256×256
        % with mixed powers of x and y for at the grid of x, y values
*       % Implicitly input m×n matrix. Multiply element-wise with broadcast: gives
        % 4D array of size m×n×256×256
ss      % Sum along first two dimensions: gives 4D array of size 1×1×256×256
&e      % Squeeze singleton dimensions: gives matrix of size 256×256. This is the
        % two-variable polynomial evaluated at the x, y grid.
        % Now we need to find the zero level curve of this function. We do this by 
        % detecting when the sign of the function changes along any of the two axes
ZS      % Matrix of sign values (1, 0 or -1)
5Y6     % Predefined literal: matrix [1 1; 1 1]
2&Y+    % Compute 2D convolution, keeping only the valid (central) part
|4=     % True if absolute value of result is 4, which indicates no sign changes.
        % (The ASCII version computes a negated version of this, for better display)
0YG     % Display as image. (The ASCII-output version does the following instead:
        % multiply by 42 and convert to char. 42 is ASCII for '*', and character 0 
        % is shown as space. The 2D char array is then implicitly displayed)

Semua uji kasus

Berikut adalah semua input dalam format yang sesuai, jika Anda ingin mencoba:

Circle:
[-2,2]
3
[-2,2]
3
[-1, 0, 1; 0, 0, 0; 1, 0, 0]

Ellipse:
[-2,2]
3
[-1,1]
3
[-1, 0, 1; 0, 0, 0; 2, 0, 0]

Cross:
[-1,2]
2
[-2,1]
2
[0, 0; 0, 1]

Parabola:
[-1,3]
3  
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Elliptic Curve:
[-2,2]
3
[-3,3]
4
[-1, 1, 0,-1; 0, 0, 0, 0; 1, 0, 0, 0]

Folium of Descartes:
[-3,3]
4
[-3,3]
4
[0,  0,  0,  1; 0, -3,  0,  0; 0,  0,  0,  0; 1,  0,  0,  0]


Lemniscate:
[-2,2]
3
[-1,1]
5
[0,  0, -1,  0,  1; 0,  0,  0,  0,  0; 1,  0,  0,  0,  0]

Trifolium:
[-1,1]
5
[-1,1]
5
[0, 0, 0,-1, 1; 0, 0, 0, 0, 0; 0, 3, 2, 0, 0; 0, 0, 0, 0, 0; 1, 0, 0, 0, 0]

Astroid
[-1,1]
7
[-1,1]
7
[-1,  0,  3,  0, -3,  0,  1; 0,  0,  0,  0,  0,  0,  0; 3,  0, 21,  0,  3,  0,  0; 0,  0,  0,  0,  0,  0,  0; -3,  0,  3,  0,  0,  0,  0; 0,  0,  0,  0,  0,  0,  0; 1,  0,  0,  0,  0,  0,  0]