Tengo un objeto System.Windows.Shapes.Polygon, cuyo diseño está determinado completamente por una serie de puntos. Necesito determinar si este polígono se intersecta a sí mismo; es decir, si alguno de los lados del polígono se cruza con cualquiera de los otros lados en un punto que no es un vértice. ¿Hay una forma fácil/rápida de calcular esto?Compruebe si el polígono se autointercala
fácil, lento, bajo consumo de memoria: compara cada segmento contra todos los demás y comprobar si hay intersecciones. Complejidad O (n).
ligeramente más rápido, huella de memoria medio (modificado versión de arriba): almacenar bordes en "cubos" espaciales, a continuación, realizar por encima de algoritmo en función de cada cubo. Complejidad O (n/m) para m cucharones (suponiendo una distribución uniforme).
rápido & huella de memoria alta: usar una función hash espacial para dividir bordes en cubos. Verificar colisiones. Complejidad O (n).
Fast & baja huella de memoria: utilizar un algoritmo de barrido de línea, tal como el descrito here (o here). complejidad O (n log n)
El último es mi favorito, ya que tiene buena velocidad - balance de la memoria, especialmente la Bentley-Ottmann algorithm. La implementación tampoco es muy complicada.
Compruebe si se cruza un par de segmentos de línea no contiguos.
Todos deben cruzarse en los vértices; la pregunta entonces se convierte en lo que es la manera más rápida de verificar una intersección sin vértice entre un conjunto arbitrario de segmentos de línea. – GWLlosa
Buen punto, editado para comprobar si los segmentos no contiguos se cruzan. No creo que haya un método incorporado, tendrás que escribir un método. Comience por obtener Polygon.Points –
¿No quiere decir ** abrir ** segmentos de línea? Nunca he oído hablar de segmentos de línea no contiguos. –
En aras de la exhaustividad agrego otro algoritmo a esta discusión.
Asumiendo que el lector conoce los cuadros delimitadores alineados con el eje (Google sí no) Puede ser muy eficiente encontrar rápidamente pares de bordes que tienen el conflicto entre ellos de AABB usando el "Algoritmo de barrido y poda". (buscalo en Google). Las rutinas de intersección son llamadas en estos pares.
La ventaja aquí es que incluso puede cruzarse con un borde no recto (círculos y splines) y el enfoque es más general aunque casi igual de eficiente.
Estoy tratando de entender el último algoritmo mientras hablamos; particularmente, tengo problemas para rastrear el significado/propósito de la estructura T. – GWLlosa
* T * es una estructura que contiene los segmentos de línea que cruzan la línea de barrido * L *. La estructura más eficiente sería un árbol de búsqueda binario (ver también el [algoritmo de Bentley-Ottmann] (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm)). –
Agregué otro [vínculo donde el algoritmo Bentley-Ottmann] (http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm) se describe con ilustraciones. –