PrInf19: Juego: doble o nada versión masiva

Práctica de Informática
Juego: doble o nada
Práctica anterior	Siguiente práctica
Este artículo es un guión de prácticas de Informática

Este artículo está en versión beta. El autor de este artículo no lo ha terminado todavía, por favor no lo edites hasta que elimine este mensaje.

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