Una curva algebraica es un cierto "subconjunto 1D" del "plano 2D" que puede describirse como un conjunto de ceros {(x,y) in R^2 : f(x,y)=0 }de un polinomio f. Aquí consideramos el plano 2D como el plano real, de R^2modo que podemos imaginar fácilmente cómo podría ser esa curva, básicamente algo que se puede dibujar con un lápiz.

Ejemplos:

• 0 = x^2 + y^2 -1 un círculo de radio 1
• 0 = x^2 + 2y^2 -1 una elipse
• 0 = xy una forma de cruz , básicamente la unión del eje x y el eje y
• 0 = y^2 - x una parábola
• 0 = y^2 - (x^3 - x + 1)una curva elíptica
• 0 = x^3 + y^3 - 3xy el folio de Descartes
• 0 = x^4 - (x^2 - y^2) un lemniscate
• 0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) un trifolium
• 0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 un astroide

Tarea

Dado un polinomio f (como se define a continuación) y los rangos x / y, genera una imagen en blanco y negro de al menos 100x100 píxeles que muestra la curva como una línea negra sobre un fondo blanco.

Detalles

Color : puede usar cualquiera de los otros dos colores de su elección, debería ser fácil distinguirlos.

Trama : en lugar de una imagen de píxeles, también puede mostrar esta imagen como un arte gráfico, donde los "píxeles" de fondo deben ser espacios / subrayados u otro carácter que "se vea vacío" y la línea puede estar hecha de un carácter que se vea " completo "como Mo Xo #.

No tiene que preocuparse por los alias.

Solo necesita trazar líneas donde el signo del polinomio cambia de un lado a otro de la línea (eso significa que podría, por ejemplo, usar el algoritmo de cuadrado de marcha), no tiene que trazar correctamente "casos patológicos como 0 = x^2donde lo hace el signo no cambia cuando va de un lado de la línea al otro, pero la línea debe ser continua y separar las regiones de los diferentes signos de f(x,y).

Polinomio : el polinomio se proporciona como una (m+1) x (n+1)matriz / lista de listas de coeficientes (reales), en el siguiente ejemplo, los términos de los coeficientes se dan en su posición:

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

Si lo prefiere, puede suponer que la matriz es cuadrada (lo que siempre se puede hacer con el relleno de cero necesario), y si lo desea, también puede suponer que el tamaño de la matriz se da como entradas adicionales.

A continuación, los ejemplos de arriba se representan como una matriz definida así:

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 prueba con rango x / rango y:

(En un formato no tan legible pero mejor para copiar y pegar disponible aquí en 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]

Tengo la inspiración para algunas curvas de este pdf.

Haskell, 283 275 bytes

La función gdebe llamarse con la matriz y los dos rangos como argumentos. La matriz es solo una lista de listas, los rangos son una lista de dos 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

Aquí las salidas para los casos más interesantes: Tenga en cuenta que tuve que reducir el resultado de 100x100 a aproximadamente 40x40 para que quepa en la consola (simplemente cambie el 102 codificado a un número más pequeño). También tenga en cuenta que el eje y está apuntando hacia abajo.

Matlab, 114 100 92 bytes

¿La herramienta adecuada para el trabajo? Utilizo la forma interesante que hace Matlab printfpara generar un polinomio como una cadena. Este polinomio puede proporcionarse para ezplottrazar la curva implícita en el dominio especificado. Para facilitar la lectura, el código se presenta con nuevas líneas después; que no es necesario y no se cuenta para el tamaño.

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

El progreso del golf como fragmento expandible.

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

Salida de los casos de prueba (haga clic para una vista 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(p [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]. Ej .). Formato de salida: PGM simple .

Esto estima la distancia desde cada centro de píxeles a la curva usando la aproximación de primer orden d ( x , y ) = | p ( x , y ) | / | ∇ p ( x , y ) |, donde ∇ p es el gradiente del polinomio p . (Esta es la distancia desde ( x , y ) a la intersección del plano tangente en ( x , y , p ( x , y )) con el plano xy .) Luego, los píxeles donde d (x , y) tiene menos de un ancho de píxel de la curva proporcionalmente a d ( x , y ), lo que da como resultado bonitas líneas antialias (aunque eso no es un requisito).

Aquí están los mismos gráficos con la función de distancia dividida por 16 para hacerla visible.

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

Una función con nombre. Bastante largo, pero bueno, estoy feliz de haber podido realizar la tarea. Toma 3 entradas, que son la m by nmatriz, el xrango y el yrango, que deberían estar en matrices (por ejemplo,[[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2] ). Emite el gráfico completado en una nueva ventana gráfica e interactiva. Jugaré golf más tiempo cuando pueda, pero por ahora, estoy contento con eso.

Salidas finales para los casos de prueba:

MATL , 67 61 bytes

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

Este código se ejecuta en la versión 18.5.0 del lenguaje, que precede al desafío. De entrada utiliza el programa opcional m, nparámetros. La matriz tiene punto y coma como separadores de fila. El formato de entrada exacto (usando la parábola como ejemplo) es

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

El código produce una imagen con un tamaño de 255 × 255. Esto se puede probar usando @Suever 's MAT línea compilador, que, entre otras características muy interesantes, incluye la salida gráfica. Ver por ejemplo

• Curva elíptica ;
• Folium de Descartes .

Este compilador todavía está en una etapa experimental. Informe cualquier problema a @Suever en la sala de chat de MATL . Si el botón "Ejecutar" no funciona, intente actualizar la página y haga clic nuevamente.

Si prefiere la salida ASCII , el código debe modificarse un poco (los cambios solo afectan los primeros dos y los últimos cuatro caracteres del código anterior):

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

Esto produce una cuadrícula ASCII de 100 × 100 que usa caracteres *para representar la curva. También puedes probar esto con @Dennis '¡ Pruébalo en línea! plataforma:

• Curva elíptica ;
• Folium de Descartes .

Tenga en cuenta que la relación de aspecto de la salida ASCII se modifica porque los caracteres son ligeramente más altos que anchos.

Explicación

El código primero calcula el polinomio de dos variables en una cuadrícula x - y . Esto hace un uso intensivo de la transmisión , computando una matriz 4D intermedia donde cada dimensión representa valores de x , valores y , exponentes x , y exponentes respectivamente.

A partir de esa función, se calcula la línea de nivel cero. Dado que el desafío especifica que solo se deben detectar cambios en los signos, se aplica el código convolución 2D con un bloque de 2 × 2 y marca un píxel como perteneciente a la línea si no los cuatro valores del bloque tienen el mismo signo.

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 los casos de prueba

Aquí están todas las entradas en el formato apropiado, en caso de que desee probar:

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]