Un grupo de personas querían desarrollar una página que pusiera marcadores en secciones de un mapa(concretamente hablando, querían marcadores circulares lo más grande posibles en municipios de un mapa de michoacán). Imagino que fue idea de un empleado de oficina que tiene una fuerte afición a los tableros con tachuelas y a jugar en paint, porque de hecho para plantear la propuesta de este portal a los clientes mostraron una imagen de un mapa de Michoacán con puntos pintados en paint.
Alguien podría argumentar: "Pero poner puntos(o tachuelas) en un mapa es re-fácil, ¡sólo lo pones adentro del municipio y ya!". Estoy de acuerdo que para nosotros es fácil. También imagino que no le resultó difícil al que pintó el mapa en paint. Pero, ¿es fácil para una computadora?
Notemos que nosotros podemos hacer esto gracias a nuestra vista. ¿Cómo le podríamos enseñar a un ciego a dibujar puntos que caigan adentro del municipio deseado? Además, tenemos desarrollados conceptos como "adentro", o "afuera", lo entendemos sin siquiera pensar en lo que formalmente significa.
Parece que empezamos a entender por qué una computadora no sabe "poner puntitos en paint". Pero, para que quede más claro, primero tratemos de formalizar lo que significa "adentro" y "afuera".
Imaginemos que vamos en una camioneta destruyendo todo en nuestro camino, y que enfrente hay un terreno muy irregular. Supondremos que venimos de afuera del terreno. La primera vez que tiremos parte de la cerca, diremos que hemos entrado al terreno, pero cuando volvemos a tirar otra parte de la cerca, es porque salimos de él, y volvemos a empezar. Siguiendo este método podemos saber si estamos adentro o afuera del terreno con la paridad de la cantidad de veces que tiramos parte de la cerca.
¿Bonita idea no? Pues esa forma de saber si algo está adentro o afuera se le llama "Ray casting algorithm", y se puede implementar. Dejaré un link al final por si a alguien le interesa.
¡Bravo!. Ya podemos enseñarle a una computadora lo que significa "adentro" y "afuera". Pero veamos que esta idea sólo sirve para saber si algo que ya está se encuentra adentro o afuera. Alguien podría decir: "Bueno, pero pues fíjate cuándo entras y sales, mide la distancia entre esos dos puntos y listo". Y es una idea muy buena, que de hecho sí sirve, pero tiene una gran desventaja. El algoritmo es unidimensional, así que podría pasar que pases muy cerca de un borde y no te des cuenta, y si pones un marcador por ahí puede que se desborde de la orilla, o si evitas que se desborde puede que te quede muy chiquito, y nosotros buscamos poner marcadores que se puedan ver sin tanta dificultad.
Parece que ahora entendemos por qué es que las computadoras no saben usar paint. Ellas necesitan saber específicamente en dónde quieres el punto, y adentro de un municipio hay incontables puntos que puedes considerar que están adentro. Y tampoco podemos tomar puntos aleatorios, porque en primer lugar, es muy grande el conjunto de puntos posibles, y además, queremos lugares estratégicos en donde se pueda poner un marcador grandote. Además, existe otra dificultad. La computadora debería de ser capaz de poner VARIOS marcadores dentro de un mismo municipio.
¿Suena complicado no? Pensemos en el caso más simple...
Supongamos que nuestro polígono es un triángulo. Es claro que el punto ideal para poner un marcador es el incentro, con el inradio como radio. Y tenemos fórmulas que ubican exáctamente a este punto. Además, no importa qué tan irregular sea nuestro polígono(mientras sea también una curva cerrada simple), siempre podemos triangularlo. Entonces nuestro problema se reduce a buscar una "buena" triangulación.
¿Qué es una "buena" triangulación? Una que tenga triángulos con inradios grandotes. Si tenemos una triangulación con triángulos flaquitos, nuestros marcadores no se van a ver. Pues, precísamente existe una triangulación que maximiza la gordura de nuestros triángulos, llamada "Triangulación de Delaunay", ¡y es programable!(dejaré la referencia al final del artículo), sólo que hay un pequeño problema, la triangulación de Delaunay no ve aristas, sólo puntos. Es decir, puede ocurrir el siguiente caso:
Imaginemos que nuestro polígono está delimitado por la frontera roja, y la triangulación está indicada por las líneas azules. Esta no es una triangulación de nuestro polígono, ya que hay triángulos que estan tanto afuera como adentro del polígono. Pero se soluciona fácil.
Le puedes decir dónde está tu arista si pones muchos puntos muy cercanos entre sí que estén contenidos en la arista. Como es un algoritmo que evita triángulos flacos, ignorará las posibilidades que nos causan ruido de esta manera.
Por otra parte, por la misma razón de que Delaunay no ve aristas, se van a generar triángulos que están afuera de nuestro polígono irregular, pero basta con tomar los incentros de los triángulos para saber cuáles descartaremos, ya que ya tenemos un algoritmo que evalúa si un punto está adentro o está afuera.
Ahora, si los triángulos son muy poquitos, siempre podemos partir un triángulo grande en 4 triángulos chiquitos con las mismas proporciones, y podemos repetir el proceso cuantas veces se necesite para satisfacer la demanda de marcadores.
¡Bingo!, terminamos el problema. Y para cerrar con broche de oro, les dejo algunas imágenes del agoritmo corriendo en la práctica:
Aquí vemos al municipio de San Lucas con su triangulación de Delaunay. Son ignorados los puntos de los triángulos que caen fuera del municipio.
Y por último les dejo a Michoacán con todos los marcadores generados por cada municipio con la triangulación de Delaunay.
Referencias:
Ray Casting Algorithm: https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Triangulación de Delaunay: https://es.wikipedia.org/wiki/Triangulaci%C3%B3n_de_Delaunay
Live demos:
Ray Casting Algorithm: http://bl.ocks.org/bycoffe/5575904
Triangulación de Delaunay: http://bl.ocks.org/mbostock/4341156
