Convex Hull

Juan Mellado, 29 Noviembre, 2011 - 20:13

Para un proyecto me ha surgido la necesidad de calcular la envolvente convexa (convex hull) de un polígono. Después de rebuscar un buen rato por la red me he acabado decidiendo por implementar el algoritmo propuesto originalmente por Melkman. He hecho una pequeña aplicación en JavaScript, a modo de applet, para poder hacer pruebas de una manera visual y comprobar los resultados.

<br />

El programa permite añadir puntos pulsando sobre la pantalla, creando los segmentos de rectas entre ellos, y evitando que se crucen, ya que el algoritmo sólo funciona con polígonos simples. Por lo demás, he seguido al pie de la letra el pseudo-código propuesto en el paper para calcular la envolvente, ya que es un algoritmo muy sencillo.

Para los que sólo les interese el código, pongo a continuación la función que calcula la envolvente. La entrada es un array de puntos con los típicos atributos (x, y). Como mínimo debe haber tres puntos en el array para que la función devuelva un resultado.

function convexHull(points){
  var deque = [];
  if (points.length >= 3){
    if ( position(points[0], points[1], points[2]) > 0){
      deque.push(points[0]);
      deque.push(points[1]);
    }else{
      deque.push(points[1]);
      deque.push(points[0]);
    }
    deque.push(points[2]);
    deque.unshift(points[2]);
    for (var i = 3; i < points.length; ++ i){
      var point = points[i];
      if ( position(point, deque[0], deque[1]) < 0 ||
           position(deque[deque.length-2], deque[deque.length-1], point) < 0 ){
               
        while(position(deque[deque.length-2], deque[deque.length-1], point) <= 0 ){
          deque.pop();
        }
        deque.push(point);
            
        while( position(point, deque[0], deque[1]) <= 0 ){
          deque.shift();
        }
        deque.unshift(point);
      }
    }
  }

return deque; };

¿No encontró lo que buscaba?

Utilice el buscador para encontrar más páginas en esta web o en toda Internet.

Añadir nuevo comentario