El contenido de este artículo es muy básico, principalmente para principiantes como yo, así que por favor solicite a todos los emperadores de algoritmo que echen un vistazo rápido.
Cita
Se sabe que el segmento de línea 1 (A, B) y el segmento de línea 2 (C, D), donde ABCD es el punto final, encuentre el punto de intersección P del segmento de línea. (Paralelo o colineal se consideran disjuntos)
Algoritmo 1: Encuentre el punto de intersección de la línea recta donde se encuentran los dos segmentos de la línea y luego determine si el punto de intersección está en los dos segmentos de la línea.
Al encontrar el punto de intersección de una línea recta, podemos encontrarlo a través de la ecuación general de Ax+por+C = 0 de la línea recta (ABC en la ecuación es un coeficiente, no el punto final mencionado anteriormente. Además, las ecuaciones oblicuas puntuales y las ecuaciones de intercepción oblicua también se pueden usar, no aquí por ahora).
Luego, según la relación posicional entre el punto de intersección y el punto final del segmento de línea, podemos juzgar si el punto de intersección está en el segmento de línea.
La fórmula es la siguiente:
<código> Los segmentos de funciones (A, B, C, D) { /** 1 Resuelve el sistema de ecuaciones lineales y encuentre la intersección de segmentos de línea. **/ // Si el denominador es 0, es paralelo o colineal, y no intersecta var denominador = (por - ay)*(dx - cx) - (ax - bx)*(cy - dy); if (denominator == 0) {return false; } // La coordenada de intersección de la línea recta donde se encuentra el segmento de línea (x, y) var x = ((bx - ax) * (dx - cx) * (cy - ay) + (por - ay) * (dx - cx) * ax - (dy - cy) * (bx - ax) * cx) / denominator; var y = - ((por - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (por - ay) * cy) / denominator; / ** 2 Determine si la intersección está en dos segmentos **/ if (// La intersección está en línea segmento 1 (x - ax) * (x - bx) <= 0 &&& (y - ay) * (y - por) <= 0 // y la intersección también está en el segmento 2 && (x - cx) * (x - dx) <= 0 && (y - * (y - y - 0) // Vuelve a la intersección p return {x: x, y: y}} // de lo contrario, el disjunto return false} </code>El algoritmo primero tiene una idea clara y fácil de entender, pero su rendimiento no es alto. Debido a que calcula la intersección antes de que no esté claro si la intersección es válida (en el segmento en línea), lo que lleva mucho tiempo.
Si finalmente se encuentra que el punto de intersección no es válido, entonces el cálculo anterior será en vano. Además, todo el proceso de cálculo también es muy complicado.
Entonces, ¿hay alguna forma de saber si hay un punto de intersección efectivo primero y luego calcularlo?
Obviamente, la respuesta es sí. Entonces se encuentran algunos algoritmos.
Algoritmo 2: Determine si los dos puntos finales de cada segmento de línea están en ambos lados del otro segmento de línea. Luego encuentre la intersección de la línea recta donde se encuentran los dos segmentos de la línea, de lo contrario no se cruzan.
El primer paso es determinar si dos puntos están en ambos lados de un determinado segmento de línea. El método de proyección generalmente se puede utilizar:
Encuentre el vector normal del segmento de línea, luego proyecte el punto en la línea normal y finalmente juzgue la relación entre el punto y el segmento de línea en función de la posición proyectada.
Vea la imagen a continuación
La proyección en el segmento de línea normal del punto A y el punto B se muestra en la figura. En este momento, también necesitamos proyectar el CD del segmento de línea en nuestra línea normal (solo seleccione uno de los puntos C o del punto D).
Principalmente utilizado para referencia.
En la figura, la proyección del punto A y el punto B se proyecta en ambos lados de la proyección del punto C, lo que indica ambos lados del segmento de línea CD del segmento de línea AB.
Del mismo modo, solo juzga si el CD está en ambos lados del segmento de línea AB nuevamente.
Encontrar normales, proyección y otras cosas suenan muy complicadas, pero de hecho es bastante complicado para mí. No sabía mucho sobre el conocimiento de la geometría hace unos meses (olvidé todo el conocimiento de la geometría cuando estaba estudiando: '()'
Afortunadamente, el aprendizaje y la implementación no son complicados, y hay fórmulas a seguir.
Encuentre el segmento de línea normal AB:
var nx = por - ay, ny = ax - bx; var normalline = {x: nx, y: ny}; NOTA: Donde los significados geométricos de normalLine.x y normalLine.y Y representan la dirección de la línea normal, no las coordenadas.
Encuentre la posición de proyección del punto C en la línea normal:
var dist = normalline.x*cx + normalline.y*cy;
Nota: La "posición de proyección" aquí es un escalar, que representa la distancia al origen de lo normal, no a las coordenadas del punto de proyección.
Por lo general, es suficiente para conocer esta distancia.
Después de calcular la proyección de los puntos A (DISTA), el punto B (DISTB) y el punto C (DISTC) en la figura, podemos juzgar fácilmente la posición relativa en función de sus respectivos tamaños.
Cuando DISTA == DISTB == DISTC, los dos segmentos son colineales
Cuando DISTA == DISTB! = DISTC, los dos segmentos de línea son paralelos
Cuando DISTA y DISTB están en el mismo lado de DISTC, los dos segmentos de línea no se cruzan.
Cuando DISTA y DISTB están en el lado opuesto de DISTC, si los dos segmentos de línea se cruzan deben juzgarse nuevamente si la relación entre el punto C y el segmento de línea AB.
Los pasos anteriores solo implementan "juzgar si los segmentos de línea se cruzan". Cuando el resultado es verdadero, necesitamos encontrar aún más el punto de intersección.
Hablemos sobre el proceso de encontrar el punto de intersección más tarde. Primero veamos la implementación completa de este algoritmo:
segmments de funciónintr (a, b, c, d) {// N1 normal var nx1 = (por - ay), ny1 = (ax - bx); // N2 N2 Var NX2 = (DY - CY), NY2 = (CX - DX); // Dos normales se multiplican, si el resultado es 0, significa que el segmento de línea AB y el CD del segmento son paralelos o colineales, y no se cruzan con denominador var = nx1*ny2 - ny1*nx2; if (denominator == 0) {return false; } // proyección en N2 var Distc_n2 = nx2 * cx + ny2 * cy; var dista_n2 = nx2 * ax + ny2 * ay-distc_n2; var distb_n2 = nx2 * bx + ny2 * by-distc_n2; // La proyección del punto A y el punto B está en el mismo lado de la proyección del punto C (para el caso en el segmento de línea, este ejemplo se trata como disjunto); if (dista_n2*distb_n2> = 0) {return false; } // // juzga la relación entre el punto C del punto D y el segmento de línea AB, el principio es el mismo que arriba // // proyección en N1 VAR normal DISTA_N1 = NX1 * AX + NY1 * AY; var distc_n1 = nx1 * cx + ny1 * cy-dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if (distc_n1*distd_n1> = 0) {return false; } // Calcule las coordenadas de intersección var fracción = dista_n2 / denominator; var dx = fracción * ny1, dy = -Fraction * nx1; return {x: ax + dx, y: ay + dy}; }El método utilizado para encontrar las coordenadas del punto de intersección al final parece un poco extraño, y parece que es discreto.
De hecho, es similar al algoritmo en el algoritmo 1, excepto que muchos de los términos de cálculo en él se han calculado por adelantado.
En otras palabras, la parte del algoritmo para encontrar las coordenadas del punto de intersección en dos millas está hecha de ecuaciones lineales de línea recta.
Ahora comparemos el algoritmo uno y el algoritmo dos de una manera simple, áspera y no científica:
1. En el mejor de los casos, la complejidad de los dos algoritmos es la misma
2. En el peor de los casos, la cantidad de cálculo del algoritmo 1 y el algoritmo 2 es casi el mismo
3. Sin embargo, el algoritmo 2 proporciona más "condiciones finales tempranas", por lo que, en promedio, el algoritmo 2 debería ser mejor.
Después de las pruebas reales, la situación real es de hecho el caso.
Los dos algoritmos anteriores son básicamente comunes y pueden hacer frente a la mayoría de las situaciones. Pero de hecho, hay un mejor algoritmo.
Esto es lo que acabo de aprender recientemente (lo aprendí ahora y lo vendí ahora, no te importe ...)
Algoritmo 3: Determine si los dos puntos finales de cada segmento de línea están en ambos lados del otro segmento de línea. Si encuentra la intersección de la línea recta donde se encuentran los dos segmentos de la línea, de lo contrario no se cruzarán.
(¿Eh? ¿Por qué se siente lo mismo que el algoritmo 2? No dudes de que es lo mismo ...)
El llamado Algoritmo 3 es en realidad solo una mejora para el Algoritmo 2. Las principales mejoras son:
La relación posicional entre los puntos y los segmentos de línea no se juzga por la proyección normal, sino por el área de triángulos compuestos de puntos y segmentos de línea.
Primero revisemos la fórmula del área del triángulo: se sabe que los tres puntos A (x, y) b (x, y) c (x, y) del área del triángulo son:
<code> var triarea = ((ax - cx) * (por - cy) - (ay - cy) * (bx - cx)) /2; </código>
Debido a que el área de un paralelogramo (dos vectores son lados adyacentes) compuesto por dos vectores bifurcado == Los dos vectores, la fórmula anterior no es difícil de entender.
Además, dado que los vectores tienen instrucciones, el área también tiene instrucciones. Por lo general, usamos en sentido antihorario como positivo y en sentido horario como negativo.
Los puntos clave del algoritmo mejorado son:
Si los signos positivos y negativos del área del triángulo formado por "segmento de línea AB y punto C" son diferentes del área del triángulo formado por "Segmento de línea AB y Punto D",
Luego, el punto C y el punto D se encuentran en ambos lados del segmento de línea AB.
Como se muestra en la figura a continuación:
El triángulo que se muestra por la línea punteada en la figura tiene diferentes direcciones de devanado (el orden de definición de los tres lados), por lo que los símbolos positivos y negativos del área son diferentes.
Veamos primero el código:
Dado que solo necesitamos juzgar el símbolo, no necesitamos dividir lo siguiente por 2 en la fórmula anterior del área del triángulo.
Segmentos de funciónintr (a, b, c, d) {// 2 veces el área del triángulo ABC var a área_abc = (ax - cx) * (por - cy) - (ay - cy) * (bx - cx); // 2 veces el área del triángulo ABD Var Area_abd = (Ax - Dx) * (por - Dy) - (Ay - Dy) * (Bx - Dx); // Si los símbolos de área son los mismos, los dos puntos no se cruzan en el mismo lado (en el caso del punto en el segmento de línea, este ejemplo se trata como disjunto); if (área_abc*área_abd> = 0) {return false; } // 2 veces el área del triángulo CDA var área_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax); // 2 veces el área del triángulo CDB // NOTA: Hay una pequeña optimización aquí. No es necesario calcular el área con la fórmula, pero se deriva agregando y restando las tres áreas conocidas. var área_cdb = área_cda + área_abc - área_abd; if (área_cda * área_cdb> = 0) {return false; } // Calcule las coordenadas de intersección var t = área_cda / (área_abd- ause_abc); var dx = t*(bx - ax), dy = t*(por - ay); return {x: ax + dx, y: ay + dy}; }Finalmente, la parte que calcula las coordenadas de intersección es la misma que el algoritmo.
Basado en el algoritmo 2, el algoritmo 3 simplifica enormemente los pasos de cálculo y el código está más simplificado. Se puede decir que es el mejor entre los tres algoritmos. Lo mismo es cierto para los resultados de la prueba reales.
Por supuesto, debemos ser honestos, en JavaScript, la complejidad del tiempo de los tres algoritmos es en realidad similar para los cálculos ordinarios (especialmente bajo el motor V8).
En mi caso de prueba, también realicé pruebas anormales de intersección de segmento de línea de millones de niveles para ampliar la brecha entre los tres algoritmos.
Resumir
Sin embargo, con la actitud de luchar por la excelencia y el aprendizaje, seguir un algoritmo mejor siempre tiene su significado positivo. Los anteriores son varios algoritmos que usan JS para lograr puntos de intersección del segmento de línea. El contenido no es muy profundo. Espero que sea útil para todos aprender JS.