La respuesta depende del contexto: si se va a investigar sólo una pequeña (bounded) número de segmentos, usted podría ser capaz de pagar un computacionalmente costosa solución. Sin embargo, parece probable que usted desee incorporar este cálculo dentro de algún tipo de búsqueda de la buena etiqueta de puntos. Si es así, es de gran ventaja para tener una solución que es computacionalmente rápido o permite una rápida actualización de una solución cuando el candidato segmento de línea es variado ligeramente.
Por ejemplo, supongamos que usted tiene la intención de llevar a cabo una búsqueda sistemática de todo un componente conectado de un contorno, representado como una secuencia de puntos P(0), P(1), ..., P(n). Esto se haría mediante la inicialización de un puntero (índice en la secuencia) s = 0 (la"s" de "inicio") y otro puntero f ("finalizar") a ser el más pequeño índice para que la distancia(P(f), P(s)) >= 100, y luego de avanzar s por tan largo como la distancia(P(f), P(s+1)) >= 100. Esto produce un candidato polilínea (P(s) P(s+1) ..., P(f-1), P(f)) para su evaluación. Después de evaluar su "idoneidad" para apoyar una etiqueta, entonces el incremento de s 1 (s = s+1) y proceder a aumentar la f a (digamos) f' y de s a s', hasta que, una vez más, un candidato de la polilínea que exceda el mínimo lapso de 100 se produce, representado como (P(s'), ..., P(f) P(f+1), ..., P(f')). Al hacerlo, los vértices P(s)...P(s'-1) son lanzadas desde el anterior candidato y vértices P(f+1), ..., P(f') se agregan a él. Es altamente deseable que el gimnasio puede ser rápida actualización de los conocimientos de sólo la quita y añade vértices. (Este procedimiento de análisis se continuó hasta que s = n; como de costumbre, f debe ser permitido "wrap around" de n a 0 en el proceso).
Esta consideración las normas muchas posibles medidas de fitness (sinuosidad, tortuosidad, etc.) que de otro modo podría ser atractivo. Nos conduce a favor L2-basado en las medidas, porque en general se puede actualizar de forma rápida cuando los datos subyacentes cambiar un poco. Tomando una analogía con el Análisis de Componentes Principales sugiere que entretener a la siguiente medida (donde los pequeños es mejor, como se solicita): utilizar el menor de los dos valores propios de la matriz de covarianza de las coordenadas del punto. Geométricamente, esto es una medida de la "típica" de lado a lado de la desviación de los vértices dentro del candidato de la sección de la polilínea. (Una interpretación es que su raíz cuadrada es la más pequeña semi-eje de la elipse que representa el segundo de los momentos de inercia de los vértices de la polilínea.) Que será igual a cero sólo para conjuntos de colineales vértices; de lo contrario, supera en cero. Mide un promedio de lado a lado de la desviación relativa a los 100 píxeles de referencia creado por el inicio y el final de una polilínea, y por lo tanto tiene una interpretación sencilla.
Debido a que la matriz de covarianza es sólo de 2 en 2, los valores propios son rápidamente encontró la solución de una sola ecuación cuadrática. Por otra parte, la matriz de covarianza es una suma de las contribuciones de cada uno de los vértices de una polilínea. Por lo tanto, es rápida actualización cuando los puntos se quitan o añaden, que conduce a un O(n) para el algoritmo de n-punto del contorno: esta escala bien a la muy detallada en los contornos de la concepción en la aplicación.
Aquí es un ejemplo del resultado de este algoritmo. Los puntos negros son los vértices de un contorno. La línea sólida roja es el mejor candidato polilínea segmento de extremo a extremo de la longitud es mayor de 100 dentro de ese contorno. (Visualmente el candidato obvio en la parte superior derecha no es suficiente.)
![Figure]()
