Uma curva algébrica é um certo "subconjunto 1D" do "plano 2D" que pode ser descrito como um conjunto de zeros {(x,y) in R^2 : f(x,y)=0 }de um polinômio f. Aqui, consideramos o plano 2D como o plano real R^2, para que possamos imaginar facilmente como seria uma curva, basicamente algo que você pode desenhar com um lápis.

Exemplos:

• 0 = x^2 + y^2 -1 um círculo de raio 1
• 0 = x^2 + 2y^2 -1 uma elipse
• 0 = xy uma forma de cruz , basicamente a união do eixo xe do eixo y
• 0 = y^2 - x uma parábola
• 0 = y^2 - (x^3 - x + 1)uma curva elíptica
• 0 = x^3 + y^3 - 3xy o folium de Descartes
• 0 = x^4 - (x^2 - y^2) um lemniscato
• 0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) um trifólio
• 0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 um astroide

Tarefa

Dado um polinômio f(conforme definido abaixo) e os intervalos x / y, produz uma imagem em preto e branco de pelo menos 100x100 pixels que mostra a curva como linha preta em um fundo branco.

Detalhes

Cor : você pode usar quaisquer outras duas cores de sua escolha; deve ser fácil diferenciá-las.

Trama : em vez de uma imagem de pixel, você também pode exibir esta imagem como arte-ascii, onde o "pixel" do plano de fundo deve ser espaço / sublinhado ou outro caractere que "parece vazio" e a linha pode ser feita de um caractere que parece " cheio "como Mou Xou #.

Você não precisa se preocupar com o alias.

Você só precisa plotar linhas onde o sinal do polinômio muda de um lado da linha para o outro (o que significa que você pode, por exemplo, usar o algoritmo do quadrado de marcha), não é necessário plotar corretamente "casos patológicos como 0 = x^2onde o sinal ocorre" não muda ao passar de um lado da linha para o outro, mas a linha deve ser contínua e separar as regiões dos diferentes sinais de f(x,y).

Polinômio : O polinômio é dado como uma (m+1) x (n+1)matriz / lista de listas de coeficientes (reais), no exemplo abaixo, os termos dos coeficientes são dados em sua posição:

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

Se preferir, você pode assumir que a matriz é quadrada (o que sempre pode ser feito com o preenchimento de zero necessário) e, se desejar, também pode assumir que o tamanho da matriz é dado como entradas adicionais.

A seguir, os exemplos acima são representados como uma matriz definida assim:

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]

Casos de teste com intervalo x / intervalo y:

(Em um formato não tão legível, mas melhor disponível para copiar e colar, disponível aqui no 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]

Eu tenho a inspiração para algumas curvas deste pdf.

Haskell, 283 275 bytes

A função gdeve ser chamada com a matriz e os dois intervalos como argumentos. A matriz é apenas uma lista de listas, os intervalos cada uma lista de dois elementos.

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

Aqui estão as saídas para os casos mais interessantes: Observe que eu tive que diminuir o tamanho da resolução de 100x100 para cerca de 40x40 para que ela caiba no console (basta alterar o 102 codificado para um número menor). Observe também que o eixo y está apontando para baixo.

Matlab, 114 100 92 bytes

A ferramenta certa para o trabalho? Eu uso a maneira interessante que o Matlab faz printfpara gerar um polinômio como uma string. Esse polinômio pode ser fornecido para o ezplotqual plota a curva implícita no domínio especificado. Para facilitar a leitura, o código é apresentado com novas linhas depois; o que não é necessário e não é contado para o tamanho.

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

Progresso no golfe como snippet expansível.

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

Saída dos casos de teste (clique para visualização completa):

Python 2, 261 bytes

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))

Formato de entrada: matrix,xbounds,ybounds(por exemplo [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Formato de saída: PGM simples .

Isso estima a distância de cada centro de pixel à curva usando a aproximação de primeira ordem d ( x , y ) = | p ( x , y ) | / | ∇ p ( x , y ) |, onde ∇ p é o gradiente do polinômio p . (Esta é a distância de ( x , y ) à interseção do plano tangente em ( x , y , p ( x , y )) com o plano xy .) Em seguida, os pixels onde d (x , y ) tem menos de um pixel de largura da curva proporcionalmente a d ( x , y ), resultando em boas linhas antialias (mesmo que isso não seja um requisito).

Aqui estão os mesmos gráficos com a função de distância dividida por 16 para torná-la visível.

Python 3.5 + MatPlotLib + Numpy, 352 bytes:

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()

Uma função nomeada. Muito tempo, mas, ei, estou feliz por ter conseguido realizar a tarefa. Aceita 3 entradas, que são a m by nmatriz, as xséries -range e y-range, que devem estar todas em matrizes (por exemplo, [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Produz o gráfico concluído em uma nova janela gráfica e interativa. Vou jogar isso mais tempo quando puder, mas por enquanto estou feliz com isso.

Saídas finais para os casos de teste:

MATL , 67 61 bytes

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

Esse código é executado na versão 18.5.0 do idioma, que precede o desafio. Input usa o opcional m, nparâmetros. A matriz possui ponto e vírgula como separadores de linha. O formato exato de entrada (usando a parábola como exemplo) é

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

O código produz uma imagem com tamanho 255 × 255. Isso pode ser testado usando @Suever 's MATL online compilador, que, entre outras características muito interessantes, inclui saída gráfica. Veja por exemplo

• Curva elíptica ;
• Fólio de Descartes .

Este compilador ainda está em um estágio experimental. Relate quaisquer problemas para o @Suever na sala de chat do MATL . Se o botão "Executar" não funcionar, tente atualizar a página e clicar novamente.

Se você preferir a saída ASCII , o código precisará ser modificado um pouco (as alterações afetam apenas os dois primeiros e os quatro últimos caracteres do código acima):

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

Isso produz uma grade ASCII 100 × 100 que usa caracteres *para representar a curva. Você também pode testar isso com o @Dennis ' Experimente online! plataforma:

• Curva elíptica ;
• Fólio de Descartes .

Observe que a proporção da saída ASCII é alterada porque os caracteres são um pouco mais altos do que largos.

Explicação

O código primeiro calcula o polinômio de duas variáveis ​​em uma grade x - y . Isso faz uso intenso da transmissão , calculando um array 4D intermediário, em que cada dimensão representa valores x , valores y , x expoentes e expoentes respectivamente.

A partir dessa função, a linha de nível zero é calculada. Como o desafio especifica que apenas as alterações de sinal precisam ser detectadas, o código aplica a convolução 2D com um bloco 2 × 2 e marca um pixel como pertencente à linha, se não os quatro valores do bloco tiverem o mesmo sinal.

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)

Todos os casos de teste

Aqui estão todas as entradas no formato apropriado, caso você queira tentar:

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]