Plotter de curva algebraica

14

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.

falla
fuente
¿" No tiene que preocuparse por el alias " significa que podemos colorear cada píxel de acuerdo a si su centro se encuentra en la línea?
Peter Taylor
No veo la conexión con el alias. Pero no, debe haber una línea continua que separe las regiones de diferentes signos.
flawr
La matriz no es mx n, sino (m+1)x (n+1). ¿Qué tomamos como entrada: m, no m+1,n+1? ¿O podemos elegir?
Luis Mendo
¿Podemos mostrar la función graficada en una nueva ventana?
R. Kap
1
@LuisMendo Sí, el eje puede estar en la dirección que desee. (Mientras sean ortogonales =)
error

Respuestas:

10

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.

falla
fuente
Hay un par de pequeños campos de golf que puedes hacer aquí. La última línea usa parens cuando podría usar $para guardar un byte. Los dos lugares donde usa mappodrían estar (<$>), y dado que solo usa euna vez, puede extraer el (0<)interior de su definición. También epodría nombrarse (!)para guardar 3 bytes.
Post Rock Garf Hunter
Y el infijo zen la definición de le vpermite deshacerse de 4 paréntesis (alrededor z(&)y f g).
Post Rock Garf Hunter
También podría cambiar el nombre #de un solo carácter (por ejemplo s) y hacer que el ajuste de patrones en las listas en lugar de g. (por ejemplo s[a,b]=[a,a+(b-a)/102..b];g m u i=unlines$v[m!y<$>s u|y<-s i])
Post Rock Garf Hunter
6

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.


Salida de los casos de prueba (haga clic para una vista completa): Casos de prueba

algmyr
fuente
2
Muy buena solución usando sprintf/ezplot!
flawr
Usar en fixlugar de floorpodría ayudarlo a alcanzar el recuento de bytes de dos dígitos :-)
Luis Mendo
¡También podría usar [h,w]=size(A);t=0:h*w-1;para guardar otros tres bytes!
flawr
@LuisMendo En realidad, puedo hacerlo mejor. Me entristeció que el printf de Matlab no tenga un marcador de posición entero, pero aún admite cosas como %.0f. ¡Eso significa que puedo dejar caer el piso por completo y dejar que lo printfarregle!
algmyr
@flawr Utilizo la segunda parte de eso en iteraciones posteriores. Me doy cuenta de que mi formato con la mejor versión anterior no era perfectamente obvio. Formato editado para aclarar esto.
algmyr
6

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

salida

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

Anders Kaseorg
fuente
Espera, entonces, ¿en qué parte del código ocurre el trazado gráfico real?
R. Kap
@ R.Kap El código escribe una imagen en formato PGM simple en stdout. Hay una printdeclaración para el encabezado de la imagen y una printdeclaración en el whilebucle para el valor de cada píxel.
Anders Kaseorg
Wow, eso es realmente genial! ¿Te importaría profundizar un poco más sobre tu algoritmo de trazado?
flawr
@flawr He ampliado un poco la explicación; ¿Eso responde a tus preguntas?
Anders Kaseorg
@AndersKaseorg Sí, muchas gracias!
flawr
5

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:

Salida final

R. Kap
fuente
5

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

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 @DennisPruébalo en línea! plataforma:

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]
Luis Mendo
fuente
2
Aún más legible que Perl. ¡Buen trabajo, también un buen compilador en línea!
flawr
@flawr es más legible que Perl LOL. En cuanto al compilador en línea, ¡todo es trabajo de Suever!
Luis Mendo
1
@flawr ¡Ahora con convolución!
Luis Mendo
1
<3 convolución!
flawr