Algoritmo: pasar una polilínea de fuente a una polilínea de referencia (tal vez parcial o totalmente)

Question

En nuestro sistema, no son los requisitos que queremos mover algunas líneas de código fuente (con poca precisión) para las líneas de referencia (con alta precisión). Siguientes imágenes se le da el uso normal de los casos. El rojo es una línea de código fuente y el azul es una línea de referencia.

Para este caso, la línea de código fuente sería trasladado parcialmente, y el resultado sería como el de la línea verde muestra:

Hay situaciones en las que el origen de la línea de la necesidad de ser trasladado por completo.

Resultado:

Actualmente nuestra solución es jefe de proyecto/punto final de la línea de la fuente a la línea de referencia y viceversa, a continuación, encontrar proyecta puntos en el origen y de la línea de referencia. Con estos proyecta puntos, podemos extraer la pieza necesaria de la fuente y la línea de referencia y luego combinarlos en una nueva.

Esto funciona para la mayoría de los casos, pero hay casos en que este método no funciona. Específicamente, cuando cualquiera de la línea "C" como la forma o la cabeza punto está muy cerca del punto final. Las dos fotos siguientes da el escenario.

Aplicando mi algoritmo, obtenemos el resultado:

En una manera que es comprensible debido a que el algoritmo actual sólo busca proyecta puntos y extractos de líneas.

Lo que nos espera es algo como esto:

Entonces, ¿qué necesito más robusto algoritmo para hacer esto, por lo que también pueden manejar casos especiales como el anterior. He tratado de proyecto de todos los puntos de una línea a otra y encontrar los dos proyecta puntos que más cerca de la cabeza y el punto final de la proyección de la línea, pero no hubo suerte. Todavía puedo encontrar casos en los que dar resultados inesperados.

Alguien ha llegado a través de problemas similares antes? También sería genial si hay un software o de la biblioteca puede hacer trabajo similar. Cualquier respuesta será bienvenida.

Answer 1

Usted tendrá una tolerancia de ajuste y gire a la tolerancia de este algoritmo (supongo que usted ya tiene una tolerancia de ajuste).

Proyecto de la cabeza punto de la línea de origen de la línea de referencia. Romper la línea de referencia en este punto proyectado.

Atravesar la línea de código fuente desde la cabeza, a punto para el primer vértice para obtener la dirección de viajar a lo largo de la línea de origen. Recorrer cada una de sus dos líneas de referencia de las proyecciones del punto de origen al siguiente vértice. Si la dirección de la marcha es en el turno de la tolerancia de la dirección de desplazamiento de la cabeza en la línea de la fuente, a continuación, aplicar el algoritmo normalmente, pero sólo con que la sección de la línea de referencia. Si el algoritmo alcanza el final de la línea de origen, está hecho. Si no, romper la línea de código fuente entre la transformada de la pieza y las no transformadas pieza (que incluirá el punto final).

Ahora tome las no transformadas pedazo de proyecto y el punto final en la referencia original de la línea. Hacer el mismo procedimiento que antes... atravesar el código fuente desde el punto de finalización para el primer vértice a encontrar la dirección de desplazamiento. Romper la línea de referencia en el punto final del proyecto y recorrer cada uno para saber si la dirección de desplazamiento de la proyección de punto final es en el turno de la tolerancia. Si es así, utilice la pieza de la línea de referencia para aplicar el algoritmo normalmente.

Recuerda, en este punto solo la utiliza sin transformar la pieza, por lo que no se superponen con la cabeza en el punto de transformación.

Por último, la combinación de los dos resultante de la línea de piezas si es necesario: la cabeza de punto transformado la pieza a partir de la proyección de la cabeza a punto de las no transformadas breakpoint y, a continuación, en el punto final transformado la pieza a partir de las no transformadas punto de quiebre para la proyección de punto final.

Answer 2

Mi estimación es que final casos voluntad a menudo como excepciones que no son máquina programable. He trabajado con problemas similares y siempre requieren una cierta cantidad de edición manual. Lo que hay que afinar para son las excepciones que se producen por el caso y servir en un sistema de gestión de trabajo a un usuario final.