Introducción
Este verano estoy trabajando en una sección de tecnología en Västerås. He trabajado en la misma empresa y en aproximadamente el mismo cargo durante tres veranos consecutivos. El trabajo es muy técnico, divertido y desafiante. A diferencia de muchos puestos de trabajo de verano otra en una oficina, he encontrado uno en el que tengo la responsabilidad y la oportunidad de trabajar con las tareas comunes. En concreto, yo trabajo en el desarrollo de herramientas para simplificar los cálculos, mayormente en MatLab, la programación de interfaz gráfica de usuario y Java. El nuevo estilo orientado a objetos de MatLab hace que el código mucho más clara que hace unos años.
El problema
El otro día me enfrenté a un pequeño reto. Simplificado que se centró en la búsqueda de un polígono que encierra un conjunto de puntos complejos que se encuentran dispersos en el plano. En un primer momento no he encontrado la función que hace esto en Matlab, que por supuesto era muy extraño. Por lo tanto, decidió buscar un algoritmo personalizado. En este post voy a describir mi algoritmo.
Figura 1. Ejemplos de concha convexa.
Mi Alogritm
Yo describiría mi algoritmo de estar utilizando la figura 2. Para empezar, voy a explicar la dificultad de encontrar vivienda. Lo que pasa es que todos los puntos no están ordenados en una estructura. Si los puntos están ordenados en torno a un punto central, se puede utilizar el orden y la distancia desde el centro de resolver el problema. Sin embargo, se necesitan al menos O (n log (n)) para hacer una clasificación lineal. Mi algoritmo funciona en la lista de seleccionados y probablemente aún más tiempo, porque no han obtenido ninguna prueba.
La idea es ciertamente para comenzar con mi punto en la dirección x, y luego encontrar el punto en que el valor de k se convierte en el máximo. es decir, averiguar:
max (K_i) = (y_min - y_i) / (x_min - x_i) para i = [todos los artículos] Esto le da el punto de p_2..
Todos los puntos de menor que y valor X_min puede omitirse. Todos los puntos con valor de x menor que p_2 También se puede descartar para su posterior lectura.
k_2 continuación, se encontró por encontrar el punto que minimiza:
k_1 - (y_1 - y_i) / (x_1 - x_i) para i = [todos los puntos no están excluidos]
Del mismo modo encontramos K_A en general por:
min (K_A-1 - (y_a-1 - y_i) / (x_a-1 - x_i)) para i = [todos los puntos no están excluidos]
El cálculo se hace por la mitad superior del polígono hasta llegar al punto en que es máxima en la dirección x. Posteriormente, el mismo algoritmo para la mitad inferior del polígono.
Figura 2. Algoritmo para el caso convexo.
Rendimiento
El rendimiento del algoritmo depende de la cantidad de puntos que terminan en el polígono. Hago linjärsök hasta la lista que apunta en el polígono. Esto significa que la complejidad es O (N * número de búsqueda). El número de puntos en el polígono óptima es entre 10 y 25 puntos dependiendo de su oportunidad. El algoritmo es por lo tanto relativamente rápido.
Código
El código no es público.
Matlab solución - el casco convexo
Mi algoritmo hace lo mismo en función de Matlab convhull . Convexo es, pues, la palabra en Inglés de un polígono cerrado o un cuerpo convexo. Otro buen recurso es http://en.wikipedia.org/wiki/Convex_hull_algorithms explican que el tiempo mínimo teórico para encontrar una concha convexa es del orden O (n log (n)).
