Auto-intersección de eliminación en el desplazamiento de las curvas de

Question

Cuando se compute desplazamiento de las curvas (también llamado paralelo de las curvas), mediante la compensación de una distancia fija a lo largo de las normales a una curva, la curva resultante de la auto-cruza cuando la distancia de desplazamiento excede el radio de curvatura (ver más abajo).

Estoy buscando una manera práctica para detectar y eliminar el interior de los "bolsillos" que aparecen. La salida debe ser una curva continua con la auto-intersección reemplazado por un punto de esquina.

Mis curvas son en realidad cúbicos arcos, pero yo trabajo con aplanamiento y puntos discretos, por lo que uno puede ver la curva suave de la polilínea. En una variante de la pregunta, el desplazamiento es también varían a lo largo de la curva.

Actualización:

Hay una forma sencilla de detectar las cúspides: surgen en donde el radio de curvatura es igual a la distancia de desplazamiento. En el discreto configuración, el osculating círculo puede ser aproximada por la que circunscribe el círculo de los tres vértices consecutivos.

En la figura se vea compensado vértices, que son de color rojo cuando la estimación de la curvatura es menor que el desplazamiento. Este principio permite encontrar evidencia de auto-intersecciones.

Sospecho que la "escalera" que está formado por la inicial de la polilínea y el correspondiente equidistantes de los puntos puede ayudar a encontrar la intersección de manera eficiente.

Answer 1

Ya que sus curvas son curvas poligonales, el desplazamiento de las curvas también son curvas poligonales. Para cualquier desplazamiento de la curva, usted necesita para detectar la auto-intersección y, a continuación, cortar el bucle en la auto-punto de intersección. Usted necesitará código robusto para el segmento en segmentos de intersección. Entonces usted necesita para decidir sobre cuánto se preocupa por la eficiencia, y del grado de complejidad de un algoritmo que se está dispuesto a código.

Auto-intersección puede ser probado de manera eficiente por un barrido de la línea de algoritmo, pero que puede ser un exceso de aquí, porque los lazos tienden a ser pequeñas, de modo que las intersecciones son propensos a ser local. Usted podría encontrar ejemplos de los algoritmos de la búsqueda para "polígono de auto-intersección de detección." Por ejemplo: "Comprobar si el Polígono es Auto-Intersección."