José FM

Aquí va el artículo y el código

...

...

En un viaje que hicimos en tren hace unos días, vimos un problema que tuvieron unas personas sentadas atrás de nosotros.

El tren va de Granada a Barcelona. Sale a las 9:45pm el viernes 13 (no es broma) y llega a las 5:05am el sábado 14 de Junio del 2008. El tren pasa por varias estaciones más en el trayecto, por lo que hay un flujo de
personas en todo el trayecto, ocupando y desocupando asientos.

El Sr. Pedro toma el tren en Granada, ocupando el asiento 44A con destino a Valencia. La Sr. Irma toma el tren en Albacete con destino a Tarragona y le venden el asiento 44A.

El problema que se presenta es el siguiente:

(Día, hora)  13, 21:45    14, 3:25      14, 5:15    14, 7:53
Pedro:       Granada              ------Valencia
Irma:                     Albacete------            Tarragona

En el tramo de Albacete a Valencia, el asiento 44A está signado a 2 personas. La razón para que suceda este problema es desconocida para nosotros, pero uno de los operarios del tren mencionó que este problema les pasa muy seguido (refiriéndose a mi parecer, a los trayectos nocturnos).

Parece que el problema redica en la verificación de horas cuando un trayecto empieza un día y termina en otro.

Dado que la cantidad de gente que viaja en el tren nocturno no es mucha, este problema pasa como una piedra en el camino, que aunque incomoda, se puede arreglar sentándose en otro lado.

Realmente comprobar que el asiento está ocupado en esas horas no debería de ser mucho problema. No se requieren más datos que los que ya están almacenados y tampoco se requieren usar estructuras de datos complejas. Lo que se requiese es parar un sistema entero que puede producir grandes pérdidas de dinero para la empresa y por lo visto, prefieren la piedra en el camino que pararse un momento y quitarla de ahí. Por cierto, esta piedra la pusieron ellos ahí y los que la sufren son los viajeros que toman el tren de noche.

Ayer 28 de abril del 2008, Lluvia y yo cumplimos 2 años de casados por el civil.

Estamos viviendo en España hasta terminar nuestro doctorado en unos 3 años.

Hemos pasado muchas cosas juntos. Muchas felicidades y muchos problemas, pero a esta fecha nos amamos más que aquel buen día en el que nos casamos.

Quiero agradecer a todos los que nos apoyaron directa o indirectamente en nuestro camino y desearles lo mejor en sus vidas.

No somos perfectos y nuestros actos tal vez no demuestren ese agradecimiento, pero va de corazón.

Gracias por todo.

Hace tiempo me entró el interés por los Diagramas de Voronoi.

Bases

Estos diagramas te permiten encontrar el vecino más cercano a un punto, para cada punto principal en el diagrama. Con punto principal me refiero a los puntos sobre los cuales se creó el diagrama, el cual también forma puntos propios.

Este diagrama es utilizado en varias áreas, incluyendo el modelado geográfico, las telecomunicaciones, la informática gráfica, entre otras muchas.

Sin contar todos los lugares en donde se usa este tipo de diagramas, estos diagramas son muy bonitos :-)

Acerca del algoritmo y las implementaciones

Para crear estos diagramas, hay varios algoritmos, pero el más eficiente (comprobado) es el algoritmo de Fortune, que se describe muy bien en el libro “Computational Geometry: Algorithms and Applications”. Este algoritmo es descrito en una sola hoja, pasando por muchas de explicación y de comprobación de propiedades, sin embargo, su implementación no es nada fácil ni rápida.

Hay varias implementaciones del algoritmo de Fortune para crear los diagramas de voroni. Estas implementaciones son en C, como la del autor, en C++, como las de algunas librerías para computación gráfica, en Java, etc.

Como nota adicional, hay un mundo de applets que muestran como crear los diagramas de voronoi, pero para ser sincero, no encontré una sola descripción decente de como implementar el algoritmo de Fortune.

Dificultades del algoritmo

Lo que hace difícil la implementación de este algoritmo es que utiliza algunas estructuras de datos especializadas, impidiendo el uso de algunas estructuras genéricas que ya traen varios lenguajes. También utiliza muchos cálculos geométricos que uno tiene que averiguar por su cuenta, por ejemplo, la intersección entre 2 parábolas.

La verdad, la principal batalla para mí fue entender el algoritmo y los requerimientos que este tenía. Aunque no lo he implementado por falta de tiempo, me gustaría terminar la implementación que estaba en curso pero usando otras herramientas para hacerlo más accesible y rápido.

Requerimientos del algoritmo de Fortune

El algoritmo utiliza una técnica llamada sweep line, que requiere un árbol de búsqueda balanceado ( AvlTree ) y especializado para este algoritmo.

En general, el libro mencionado describe muy bien el algoritmo y sus bases, pero para entender mejor su funcionamiento tuve que bajar varias diapositivas, las cuales incluyo abajo en los links.

Otra estructura que se usa es la cola priorizada( Heap ), que debe permitir eliminar un elemento en cualquier parte de la cola. Esta heap se usa para manejar los eventos producidos por el algoritmo.

Algunas operaciones geométricas que se requieren son:

• Punto medio de un segmento
• Intersección entre 2 segmentos
  • Intersección entre 2 segmentos 1
  • Intersección entre 2 segmentos 2
  • Intersección entre 2 segmentos 3
• Circuncentro de 3 puntos
• Manejo de parábolas
  • Parábola
  • Intersección entre 2 parábolas

Varios algoritmos geométricos estan descritos en el libro Computational Geometry in C, 2ed , de Joseph O’Rourke.

Partes desarrolladas

Actualmente llevo pocas partes desarrolladas de este algoritmo. Mi intención era hacer una implementación del algoritmo de Fortune en Javascript, usando el HtmlCanvas(solo Firefox, Safari y Opera) para mostrar el diagrama.

La verdad es que quiero hacer muchas cosas pero no creo que tenga tiempo para todas así que lo que salga es bueno :-)

A este momento tengo hechas algunas partes aisladas del algoritmo, ya que como dije anteriormente, me pricipal problema fue entender el algoritmo y saber que hacer para implementarlo. Si después actualizo la implementación, pues haré otro Post o actualizaré este.

Dividí las partes en 3 archivos(por el momento):

• Estructuras geométricas . Aquí se manejan los clases para manejar puntos y segmentos, en las cuales se implementan varios algoritmos geométricos como la intersección entre 2 segmentos y el punto medio de un segmento. También está implementada la mediatriz de un segmento, como la que se implementó el cálculo del circuncentro, el cual todavía no ha sido metído en la clase VSegment.
• Manejo de pintado . Aquí se maneja lo relativo al pintado en el Html Canvas. Se maneja el pintado de líneas, círculos y puntos. Esta archivo depende del core geométrico.
• Estructuras de datos . Aquí estarían implementados el árbol de búsqueda para la sweep line y la heap pero por ahora solo está la heap. Esta heap está implementada usando un arreglo como base, como viene descrito en el artículo enlazado.

En los siguientes links muestro los archivos de prueba de esas partes:

• Prueba de intersección de 2 segmentos
• Prueba de circuncentro
• Prueba de la cola priorizada

Links de interés:

Wiki dedicada a los Diagramas de Voronoi
Libro Computational Geometry: Algorithms and Applications
Capítulo del libro anterior dedicado a los Diagramas de Voronoiwww

Título: Designing and evaluating online communities: research speaks to emerging practice

Autor: Jenny Preece, Chadia Abras, Diane Maloney-Krichmar
Int. J. Web Based Communities, Vol. 1, No. 1, pp.2-18

Pequeño resumen

El artículo habla de 3 cosas principalmente: el desarrollo centrado en la comunidad, los métodos tradicionales de evaluación de comunidades online y los métodos de evaluación centrados en la sociabilidad aplicados a las comunidades online.

Primero muestra el entorno en el que se desarrollan las comunidades online, pasando entonces a dar una explicación más detallada de lo que es el desarrollo centrado en la comunidad.

Este tipo de desarrollo se apoya fuertemente en la evaluación continua de la comunidad y de su soporte en software, cubriendo el desarrollo y a vida de la comunidad.
A través de esta aplicación se hace notar la necesidad de buenos métodos de evaluación de las comunidades online, ya que estos nos van a permitir crear comunidades exitosas.

Después pasa a describir el uso de los métodos tradicionales de evaluación en estas comunidades, puntualizando como estos métodos no cubren los aspectos de sociabilidad y usabilidad de las comunidades online.

El autor muestra el caso de estudio de una comunidad online exitosa, midiendo su éxito en base a la cantidad de posts que se crean cada determinado tiempo.

En este estudio, se ve que a pesar de que la comunidad no muestra muchos aspectos considerados muy importantes para su éxito, la comunidad goza de tal éxito. Por ejemplo, una de las referencias consultadas dice que es muy importante mostrar el propósito de la comunidad, las políticas de la misma y los procedimientos en ésta; sin embargo, la comunidad evaluada no presentaba ninguno de estos aspectos y aún así gozaba de bastante salud.

También se notó que la comunidad funcionaba bien con aspectos tecnológicos sencillos, buscando la facilidad de uso sencillo y la velocidad, que al parecer sí les importaba mucho.

Al final de este caso de estudio, el autor puntualiza que obtener los aspectos sociales que hacen exitosa una comunidad no son sencillos de obtener y pueden variar entre comunidades.

Este estudio también utilizó técnicas de observación etnográficas para evaluar a la comunidad, puntualizando las dificultades que puede tener el aplicarlas, pero también mostrando las ventajas de este tipo de técnicas.

En el segundo caso de estudio, el autor muestra el uso de técnicas de evaluación herística sobre varias comunidades.

Estas evalaciones se basan es saber que es lo que el usuario quiere de su comunidad, ayudando así a los desarrolladores de la misma para que estos puedan proveer esas funcionalidades a los usuarios de tal comunidad.

Este tipo de técnicas tienen sus desventajas debido a la reacción positiva o negativa de la comunidad ante tales estudios, pero también tiene muchas ventajas en cuestión de resultados para la comunidad y en el costo de las mismas, que generalmente es poco a comparación de otras técnicas de evaluación.

El autor saca varias conclusiones de estos estudios, siendo las principales la necesidad de definir técnicas que evaluen eficientemente la sociabilidad y usabilidad, dependiendo de las comunidades a las que van dirigidos estos estudios.

Se puntualiza el hecho de que los métodos tradicionales de evaluación de comunidades online son insuficientes para esta tarea y que se requieren crear nuevos métodos orientados a la sociabilidad y usabilidad.

También se muestra como el uso de evaluaciones heurísticas puede traer grandes beneficios a la comunidad, siendo de apoyo a los otros métodos de evaluación.

También se muestran los beneficios de las técnicas etnográficas y se sugiere desarrollar técnicas de observación orientadas a la etnografía para el uso de los moderadores de las comunidades online.

Para terminar, se muestra la intención de desarrollar herramientas de apoyo a los moderadores, desarrolladores, evaluadores y usuarios de las comunidades online.

Comentarios personales

Creo que las principales aportaciones del artículo son que muestra que se necesitan técnicas específicas para evaluar comunidades online, mostrando que otras técnicas usadas son insuficientes para este trabajo.

Creo una comunidad puede tener las mejores tecnologías para compartir videos, pero si lo que buscan es compartir imágenes, pues la comunidad no va a tener mucho éxito, ya que el entorno tecnológico no provee lo necesario para el objetivo de esa comunidad en específico.

Yo veo los foros como un entorno para comunidades online muy flexible, ya que son sencillos de usar y permiten comunicación semifluida.

Creo que el éxito de una comunidad implica más que los usuarios de las mismas tengan objetivos en común y que se lleven de forma aceptable para ellos. Una vez que este tipo de usuarios se encuentran, pueden usar casi cualquier tecnología para comunicarse. Por lo tanto, creo también que los estudios heurísticos y etnográficos tienen más sentido en las comunidades online, ya que se trata de evaluar sociabilidad entre personas y no necesariamente entornos tecnológicos.