O conteúdo deste artigo é muito básico, principalmente para iniciantes como eu, então, por favor, pergunte a todos os imperadores do algoritmo para dar uma olhada rápida
Citar
Sabe -se que o segmento 1 da linha (A, B) e o segmento de linha 2 (C, D), onde o ABCD é o endpoint, encontre o ponto de interseção P do segmento de linha. (paralelo ou colinear são considerados disjuntos)
Algoritmo 1: Encontre o ponto de interseção da linha reta, onde os dois segmentos de linha estão localizados e determine se o ponto de interseção está nos segmentos de duas linhas.
Ao encontrar o ponto de interseção de uma linha reta, podemos encontrá -la através da equação geral de Ax+por+C = 0 da linha reta (ABC na equação é um coeficiente, não o ponto final mencionado acima. Além disso, as equações oblíquas de apontar e as equações de interceptação oblíqua também podem ser usadas, não aqui por agora).
Então, com base na relação posicional entre o ponto de interseção e o ponto final do segmento de linha, podemos determinar se o ponto de interseção está no segmento de linha.
A fórmula é a seguinte:
<Code> segmentos de função (a, b, c, d) { /** 1 Resolva o sistema de equações lineares e encontre a interseção dos segmentos de linha. **/ // Se o denominador for 0, é paralelo ou colinear e não cruzar o denominador var = (por - ay)*(dx - cx) - (ax - bx)*(cy - dy); if (denominador == 0) {return false; } // A coordenada de interseção da linha reta, onde o segmento de linha está localizado (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) / denominador; /** 2 Determine se a interseção está em dois segmentos **/se (// a interseção está na linha 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - por) <= 0 // e a interseção também está on -line 2 && (x - cx) (x - dx) <= 0) e a interseção também é Retorne à interseção P Return {x: x, y: y}} // Caso contrário, o retorno disjunto false} </code>O algoritmo primeiro tem uma idéia clara e fácil de entender, mas seu desempenho não é alto. Porque calcula a interseção antes que não se saiba se a interseção é válida (no segmento on -line), o que leva muito tempo.
Se o ponto de interseção for finalmente inválido, o cálculo anterior será em vão. Além disso, todo o processo de cálculo também é muito complicado.
Então, existe uma maneira de saber se existe um ponto de interseção eficaz primeiro e depois calculá -lo?
Obviamente, a resposta é sim. Portanto, alguns algoritmos são encontrados.
Algoritmo 2: determine se os dois pontos finais de cada segmento de linha estão em ambos os lados do outro segmento de linha. Em seguida, encontre a interseção da linha reta, onde os dois segmentos de linha estão localizados, caso contrário eles não se cruzam.
O primeiro passo é determinar se dois pontos estão em ambos os lados de um determinado segmento de linha. O método de projeção geralmente pode ser usado:
Encontre o vetor normal do segmento de linha, depois projete o ponto na linha normal e, finalmente, julgue a relação entre o ponto e o segmento de linha com base na posição projetada.
Veja a foto abaixo
A projeção no segmento de linha normal CD do ponto A e do ponto B é mostrado na figura. Neste momento, também precisamos projetar o CD do segmento de linha em nossa linha normal (basta selecionar um do ponto C ou o ponto D).
Usado principalmente para referência.
Na figura, a projeção do ponto A e do ponto B são projetados em ambos os lados da projeção do ponto C, indicando os dois lados do segmento de linha CD do segmento de linha AB.
Da mesma forma, apenas julgue se o CD está em ambos os lados do segmento de linha AB novamente.
Encontrar normais, projeção e outras coisas parecem muito complicadas, mas na verdade é realmente bastante complicado para mim. Eu não sabia muito sobre o conhecimento da geometria há alguns meses (esqueci todo o conhecimento da geometria quando estava estudando: '()' '
Felizmente, o aprendizado e a implementação não são complicados e há fórmulas a seguir.
Encontre o normal do segmento de linha AB:
var nx = por - ay, ny = ax - bx; var normalline = {x: nx, y: ny}; NOTA: Onde os significados geométricos de normalLine.x e normalLine.y representam a direção da linha normal, não as coordenadas.
Encontre a posição de projeção do ponto C na linha normal:
var dist = normalline.x*cx + normalino.y*cy;
Nota: A "posição de projeção" aqui está um escalar, que representa a distância da origem do normal, não as coordenadas do ponto de projeção.
Geralmente é o suficiente para saber essa distância.
Depois de calcularmos a projeção dos pontos A (DERA), o ponto B (distb) e o ponto C (distc) na figura, podemos julgar facilmente a posição relativa com base em seus respectivos tamanhos.
Quando Data == distb == distc, os dois segmentos são colineares
Quando Data == distb! = Distc, os dois segmentos de linha são paralelos
Quando o DISTA e o DISTB estão do mesmo lado do DISTC, os dois segmentos de linha não se cruzam.
Quando o DISTA e o distb estão no lado oposto do DISTC, se os dois segmentos de linha se cruzam precisam ser julgados novamente se a relação entre o ponto C e o segmento de linha AB.
As etapas anteriores implementam apenas "julgando se os segmentos de linha se cruzam". Quando o resultado é verdadeiro, precisamos encontrar ainda mais o ponto de interseção.
Vamos falar sobre o processo de encontrar o ponto de interseção mais tarde. Vamos primeiro olhar para a implementação completa deste algoritmo:
segmentos de funçãoIntr (a, b, c, d) {// n1 n1 var nx1 = (por - ay), ny1 = (ax - bx); // normal n2 var nx2 = (dy - cy), ny2 = (cx - dx); // Dois normais são multiplicados, se o resultado for 0, significa que o CD do segmento de linha AB e o segmento são paralelos ou colineares e não cruzam o denominador var = nx1*ny2 - ny1*nx2; if (denominador == 0) {return false; } // projeção no normal 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; // A projeção do ponto A e do ponto B estão no mesmo lado da projeção do ponto C (para o caso no segmento de linha, este exemplo é tratado como disjunta); if (dista_n2*distb_n2> = 0) {return false; } // // julga a relação entre o ponto C do ponto D e o segmento de linha AB, o princípio é o mesmo que acima // // projeção no n1 n1 var 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 as coordenadas de interseção var fração = dista_n2 / denominador; var dx = fração * ny1, dy = -fração * nx1; retornar {x: ax + dx, y: ay + dy}; }O método usado para encontrar as coordenadas do ponto de interseção no final parece um pouco estranho, e parece que é discreto.
De fato, é semelhante ao algoritmo no algoritmo 1, exceto que muitos dos termos de cálculo nele foram calculados com antecedência.
Em outras palavras, a parte do algoritmo para encontrar as coordenadas do ponto de interseção em duas milhas é realmente feita de equações lineares de uma linha reta.
Agora, vamos comparar o algoritmo um e o algoritmo dois de uma maneira simples, áspera e não científica:
1. Na melhor das hipóteses, a complexidade dos dois algoritmos é a mesma
2. No pior caso, a quantidade de cálculo do algoritmo 1 e o algoritmo 2 é quase a mesma
3. No entanto, o algoritmo 2 fornece mais "condições finais iniciais"; portanto, em média, o algoritmo 2 deve ser melhor.
Após o teste real, a situação real é realmente o caso.
Os dois algoritmos anteriores são basicamente comuns e podem lidar com a maioria das situações. Mas, de fato, há um algoritmo melhor.
Isso é o que acabei de aprender recentemente (aprendi agora e o vendi agora, não se importe ...)
Algoritmo 3: determine se os dois pontos finais de cada segmento de linha estão em ambos os lados do outro segmento de linha. Se você encontrar a interseção da linha reta, onde os dois segmentos de linha estão localizados, caso contrário, eles não se cruzarão.
(Hein? Por que parece o mesmo que o algoritmo 2? Não duvido que seja realmente o mesmo ...)
O chamado algoritmo 3 é na verdade apenas uma melhoria do algoritmo 2. As principais melhorias são:
A relação posicional entre pontos e segmentos de linha não é julgada pela projeção normal, mas pela área de triângulos compostos por pontos e segmentos de linha.
Vamos primeiro revisar a fórmula da área do triângulo: sabe -se que os três pontos a (x, y) b (x, y) c (x, y) da área do triângulo são:
<code> var triarea = ((ax - cx) * (por - cy) - (ay - cy) * (bx - cx)) /2; </code>
Como a área de um paralelogramo (dois vetores são lados adjacentes) compostos por dois vetores forking == Os dois vetores, a fórmula acima não é difícil de entender.
Além disso, como os vetores têm instruções, a área também tem instruções. Geralmente, usamos no sentido anti -horário positivo e no sentido horário como negativo.
Os pontos -chave do algoritmo melhorado são:
Se os sinais positivos e negativos da área do triângulo formados por "segmento de linha AB e Point C" forem diferentes da área do triângulo formada por "segmento de linha AB e Point D",
Em seguida, o ponto C e o ponto D estão localizados em ambos os lados do segmento de linha AB.
Como mostrado na figura abaixo:
O triângulo mostrado pela linha pontilhada na figura tem diferentes direções de enrolamento (a ordem da definição dos três lados), de modo que os símbolos positivos e negativos da área são diferentes.
Vejamos o código primeiro:
Como precisamos apenas julgar o símbolo, não precisamos dividir o seguinte por 2 na fórmula da área do triângulo anterior.
segmentos de função (a, b, c, d) {// 2 vezes a área do triângulo ABC var Area_ABC = (ax - cx) * (por - cy) - (ay - cy) * (bx - cx); // 2 vezes a área do triângulo Abd var Area_abd = (AX - DX) * (por - dy) - (ay - dy) * (Bx - dx); // Se os símbolos de área forem os mesmos, os dois pontos não se cruzam do mesmo lado (no caso do ponto no segmento de linha, este exemplo é tratado como discoint); if (are_abc*área_abd> = 0) {return false; } // 2 vezes a área do triângulo CDA var Area_cda = (CX - AX) * (dy - ay) - (cy - ay) * (dx - ax); // 2 vezes a área do triângulo CDB // Nota: Há uma pequena otimização aqui. Não há necessidade de calcular a área com a fórmula, mas é derivada adicionando e subtraindo as três áreas conhecidas. var área_cdb = área_cda + área_abc - are_abd; if (are_cda * área_cdb> = 0) {return false; } // Calcule as coordenadas de interseção var T = área_cda / (Area_abd- Area_ABC); var dx = t*(bx - ax), dy = t*(por - ay); retornar {x: ax + dx, y: ay + dy}; }Finalmente, a parte que calcula as coordenadas de interseção é a mesma que o algoritmo.
Com base no algoritmo 2, o algoritmo 3 simplifica bastante as etapas de cálculo e o código é mais simplificado. Pode -se dizer que é o melhor entre os três algoritmos. O mesmo vale para os resultados reais dos testes.
Obviamente, devemos ser honestos, em JavaScript, a complexidade do tempo dos três algoritmos é realmente semelhante para cálculos comuns (especialmente no mecanismo V8).
No meu caso de teste, também conduzi testes de interseção anormais de um milhão de níveis para ampliar a lacuna entre os três algoritmos.
Resumir
No entanto, com a atitude de lutar pela excelência e aprendizado, a busca de um algoritmo melhor sempre tem seu significado positivo. Os acima são vários algoritmos que usam JS para alcançar pontos de interseção do segmento de linha. O conteúdo não é muito profundo. Espero que seja útil para todos aprenderem JS.