Diferencia entre revisiones de «PrInf19: Juego: doble o nada versión masiva»

Revisión actual del 15:56 10 oct 2013

En esta práctica vamos a continuar con el juego anterior, pero vamos a realizar una implementación masiva. Es decir, en vez de probar con un solo punto, vamos a probar con miles de puntos generados aleatoriamente, y vamos a comprobar si cada uno de estos puntos acaba siendo repelido fuera del triángulo, o permanece dentro del triángulo. Una vez que hayamos realizado esta comprobación, dibujaremos las posiciones iniciales de los puntos que permanecen dentro del triángulo, para acabar generando una inquietante figura.

1 Requisitos previos

Antes de realizar esta práctica, es necesario haber realizado la práctica anterior, ya que vamos a reutilizar el código desarrollado en esa práctica:

• PrInf18: Juego: doble o nada

2 Simulación de Montecarlo

Dentro del triángulo que hemos usado en la práctica anterior, habrá puntos que si son usados para jugar, acabarán siempre dentro del triángulo. En cambio, habrá otros puntos, que acabarán siendo repelidos fuera del triángulo. La expresión matemática que relacione la posición de un punto con si se queda dentro o si sale repelido es compleja y muy difícil de deducir. Si queremos dibujar las posiciones de todos los puntos que no son repelidos, no podemos usar esa expresión matemática para encontrar el conjunto de puntos que no son repelidos.

En cambio, gracias a que estamos usando un ordenador, podemos probar varios miles de puntos, hacer que cada punto sirva como entrada para el juego, y luego quedarnos solo con los puntos que no han sido repelidos. Esta manera de proceder se conoce como Método de Montecarlo^[1]. En situaciones en los que obtener una expresión matemática no es factible, pero sabemos la propiedad que tiene que cumplir un resultado (en este caso, no ser repelido), los métodos de Montecarlo generan miles de posibles soluciones de manera aleatoria, y este conjunto se reduce quedándose solo con las soluciones que cumplan las propiedades buscadas.

3 Función doble o nada

El primer paso será crear una función que realice el juego de la práctica anterior. Esta función acepta como argumentos de entrada el punto a probar y los vértices del polígono. La función devuelve true si el punto continúa dentro del polígono tras llegar al límite de saltos, y devuelve false si el punto es repelido fuera del polígono. Esta función es muy similar al programa que hemos realizado en la práctica anterior, con la única excepción de que no dibuja nada y solo devuelve verdadero o falso.

Para facilitar el desarrollo de esta función, puedes utilizar la siguiente plantilla

function dentro = puntoSeQuedaDentro(p, x, y)
  nSaltos = 4;
  % Coordenadas del punto inicial
  xp = p(1);
  yp = p(2);
  xn = xp; % xn es cada una de las posiciones x por donde va pasando el iman
  yn = yp;
  % -------------------------------
  % TU CODIGO AQUI
  % En esta parte del codigo hay que hacer que el iman salte como maximo cuatro veces
  % Si sale del poligono, no hay que continuar saltando
  % Tiene que dibujar cada posicion en color magenta, con el siguiente comando
  % plot(xn,yn,'om','LineWidth',8, 'MarkerSize', 14); 
  %
  % Estos comentarios se pueden eliminar del código antes de enviar la solución
  % -------------------------------
  dentro = inpolygon(xn, yn, x, y);  
end

Tarea:

Termina la función usando la plantilla anterior, y guarda en un fichero de nombre puntoSeQuedaDentro.m.

Recuerda que el algoritmo consiste en los siguientes pasos:

1. Busca el vértice más cercano
2. El imán se repele hasta un punto situado al doble de distancia de ese vértice
3. Si ha salido, ya no se continúa probando
4. Si hemos alcanzado el límite de saltos, no seguimos probando
5. Si está todavía dentro y no hemos alcanzado el límite de saltos, volvemos al primer punto.

El código es exactamente el mismo que el usado en la práctica anterior.

4 Programa principal

Una vez que la función esté terminada, ya podemos probar puntos usando esta función. Ahora vamos a escribir un programa que pruebe 2000 puntos generados de manera aleatoria. Dibujaremos aquellos puntos que no salgan repelidos fuera del triángulo, para generar una figura como la de la derecha (en esa figura, se han usado 25000 puntos, en vez de 2000).

Triángulo generado por el juego, usando una simulación con 25,000 puntos aleatorios

% Vértices del polígono
x = [0 0.5 1];
y = [0 1 0];
xmin = min(x);
xmax = max(x);
ymin = min(y);
ymax = max(y);
% Total de puntos a probar
N = 2000;
% Coordenadas de los puntos a pintar
xp = [];
yp = [];
for k=1:N
  % Mensaje cada 50 puntos analizados
  if rem(k,50) == 0
    fprintf('%6d puntos analizados...\n', k);
  end
  % Punto aleatorio (con suerte, dentro del poligono)
  xr = xmin + rand*(xmax-xmin);
  yr = ymin + rand*(ymax-ymin);
  p = [xr yr];
  
  % ------------------
  % Tu codigo aqui
  % ------------------
end

% Pinta los puntos que se han quedado dentro
clf
fill(x,y, 'g')
hold on
plot(xp, yp, 'x')
hold off

Tarea:

Completa el código de la plantilla para dibujar solo los puntos que queden dentro del triángulo tras realizar el juego. Usa la función escrita en la sección anterior para comprobar cada punto.

No es necesario comprobar si el punto (xr, yr) generado de manera aleatoria es un punto interior al triángulo o no. De hecho, del orden de la mitad de los puntos generados caerán fuera del triángulo. El código que falta debe comprobar si el punto es repelido o no, y guardarlo si resulta que no se repele.

5 Resultado de la simulación

Los puntos interiores del triángulo que no salen repelidos tras cuatro saltos resultan ser los mismos que forman un famoso fractal, denominado triángulo de Sierpinski^[2]. En realidad, la simulación es una aproximación a la solución, porque los puntos del triángulo de Sierpinski no salen repelidos nunca, y serían necesarios infinitos saltos para comprobar si el punto sale o no. Sin embargo, con un límite de 4 saltos, el resultado obtenido es bastante fiel a la solución exacta del problema.

6 Ejercicio post-práctica

El programa dibuja las posiciones iniciales de los puntos que no son repelidos y que se quedan dentro del triángulo tras cuatro saltos. Modifica el programa para dibujar las posiciones iniciales de los puntos que sí son repelidos y caen fuera del polígono, en vez de los que se quedan dentro.

7 Referencias

1. ↑ Método de Montecarlo (Wikipedia ES)
2. ↑ Triángulo de Sierpinski (Wikipedia ES)