Determinando exatamente se/quando/onde uma linha em movimento cruzou um ponto em movimento

Novembro 3, 2021

Determinando exatamente se/quando/onde uma linha em movimento cruzou um ponto em movimento
Destino
Intuição
Modelo
Solução
Generalizar
Sumário
Discuss on Reddit
Arquivo

postado por Craig Gidney em 5 de fevereiro de 2013

Tento incluir exemplos de projetos quando publico bibliotecas. No caso de coleções perecíveis, o projeto de amostra era na verdade um jogo simples baseado em linhas de corte com o ponteiro do mouse:

Como parte da escrita da amostra, eu tive que resolver o problema de determinar se, quando, e onde o ponteiro do mouse foi varrido através de uma linha (ou vice versa). Minha referência usual para algoritmos de geometria não continha uma solução, então eu mesmo desenvolvi uma.

Neste post eu estarei explicando uma solução analítica para o problema. A solução é implementada numa pequena quantidade de código fonte (cerca de 150 linhas, contando comentários e métodos/tipos de suporte), também disponível no github.

Destino

Acontece que “o ponteiro do rato cortou a linha em movimento?” é um daqueles problemas matemáticos mágicos que começa com algumas restrições relativamente simples, depois parece tornar-se bastante complicado à medida que o resolve, mas depois quase tudo cancela ou combina nos últimos passos e você acaba com algo absurdamente simples. (Então, quando você volta a olhar para a solução, acontece que houve um caminho fácil o tempo todo.)

Para referência e motivação, eu vou apenas despejar a carne da implementação aqui mesmo, antes de explicá-la. As palavras sublinhadas são links para o código correspondente no github.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

Não sei sobre você, mas o fato de que o código acima resolve o problema me surpreende. Parece muito simples, e ainda assim não relacionado. Não deveria haver, tipo, casos de canto? Além disso, de onde vieram esses simples produtos cruzados? Como é que alimentá-los com um polinómio quadrático ajuda? Isto… vai precisar de ser explicado.

Intuição

Comecemos por considerar alguns dos casos que podemos encontrar, de forma a obter uma sensação intuitiva para o problema. A animação abaixo mostra vários movimentos de linha possíveis:

Simples: ambos os pontos finais movem-se à mesma velocidade, e apenas ao longo do vector normal da linha.
Sideways: um caso degenerado em que a linha se move ao longo do seu próprio comprimento.
Raise: um ponto final move-se horizontalmente enquanto o outro se move verticalmente (‘subir’ e descer a linha).
Mergulhar: um extremo move-se diagonalmente (‘mergulhar’ pelo meio) enquanto o outro se move verticalmente.

Várias varreduras

Notem que uma linha pode varrer um ponto 0, 1, ou 2 vezes à medida que os seus extremos se movem a uma velocidade constante de uma posição para outra. O caso ‘Raise’ contém, convenientemente, as três possibilidades. Isto, intuitivamente, é a razão pela qual a solução envolve uma equação quadrática (que pode ter 0, 1, ou 2 raízes reais distintas).

Outra realização útil é que alguns dos casos, como a linha movendo-se a uma taxa constante ou parada, corresponderá a equações quadráticas degeneradas onde o coeficiente de ordem mais alto é zero (ou seja, ou mesmo ). Precisamos incluir este tipo de casos nos testes.

Modelo

Para que um segmento de linha de a contenha um ponto , duas condições devem ser satisfeitas. Primeiro, o vector ‘offset’ de a tem de ser paralelo ao vector ‘delta’ de a . Podemos representar isto matematicamente exigindo que o seu produto cruzado seja zero: $(c-p) \ vezes (q-p) = 0$ . Isto garante que está na linha que você obtém ao estender o segmento de linha em ambas as direções (ou que você tem um segmento de linha de ponto único degenerado). Segundo, a projecção escalar do vector de desvio sobre o vector delta deve estar no intervalo correcto: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Isto garante que não passa de nenhum dos pontos finais do segmento.

Como o tempo vai de a , o nosso segmento de linha terá varrido um ponto se e só se houver um tempo onde o segmento de linha actual contém . Como os pontos finais do nosso segmento de linha estão se movendo a uma velocidade constante, o caminho que eles seguem é também um segmento de linha. Um ponto final movendo-se de para estará no ponto interpolado linearmente $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ no momento . Note que eu vou abreviar como para economizar espaço. Ligar os nossos pontos em movimento às nossas fórmulas ‘segmento de linha contém pontos’ diz-nos que temos de encontrar satisfazendo $0 \leq t \leq 1$ e $(c - (p_0 + p_d \cdot t)) \{(q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ e $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} \leq 1$ .

Note que “algum produto cruzado deve ser igual a 0″ não é a única maneira de enquadrar o problema. Também faz sentido pensar nisso como encontrando um e , ambos na faixa , de tal forma que é o resultado de ler ambos os pontos finais através do seu caminho por e depois ler entre os pontos finais por . Matematicamente, isso significa . As variáveis e correspondem aproximadamente a “quando” e “onde” uma intersecção ocorre. No entanto, é mais difícil resolver o problema nesta forma, porque não está inicialmente isolado, por isso vou usar o enquadramento do produto cruzado (ao contrário do que fiz da primeira vez…).

Solução

O produto cruzado e o produto ponto têm algumas propriedades muito boas que vão facilitar o isolamento de . Segundo, o escalonamento pode ser feito antes ou depois de qualquer produto, significando $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ e $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , onde é um número real. Finalmente, o produto ponto é comutativo, significando $u \cdot v = v \cdot u$ , enquanto o produto cruzado é anti-comutativo, significando $u \cdot v = -v \cdot v = -v \cdot u$ .

Aplicando este conhecimento do produto, e usando alguma retrospectiva para saber tratar subexpressões particulares como variáveis individuais, podemos transformar a nossa equação cross-product-is-zero em uma equação quadrática:

$\begin{align*} 0 =(c - (p_0 + p_d \cdot t)) \{ q_0 + q_d {cdot t)-(p_0 + p_d {cdot t)) \\= ((c - p_0) - p_d |cdot t) |times ((q_0 - p_0) - (q_d - p_d) |cdot t) | (a + b |cdot t) |times (c + d |cdot t) |;;|;|;|;\a = c - p_0; a = c - p_0; c = q_0 - p_0; b = -p_d; b = -p_d; a = c - p_0; c = q_0 - p_0; c = q_0 d = -(q_d - p_d) a ^2 ^cdot (b ^time d) + t ^cdot t + b ^cdot t + b ^time d ^cdot t ^2 ^cdot (b ^time d) + t ^cdot (a \vezes d + b vezes c) + (a {alinhamento*}$

(Isto é hilariantemente mais simples do que a rota que eu tomei da primeira vez.)

Ah, agora está claro de onde veio a forma da solução de código. Começamos com um produto cruzado igual a zero (afirmando que o vetor da linha até o ponto era paralelo à linha) e tivemos que dividir o produto para isolar somas de termos envolvendo diferentes potências de . Isto produz naturalmente uma equação quadrática com coeficientes que envolvem produtos cruzados. Neat!

Note que esta é uma equação muito “robusta”, porque nunca assumimos nada sobre os vetores ou escalares ao longo do caminho. Por exemplo, nunca dividimos (ou cancelamos implicitamente) por uma variável, por isso não introduzimos nenhuma condição de não-zero à espreita.

Com a equação simplificada, determinar os valores possíveis de é apenas o material padrão “resolver polinomial quadrático”. Temos de lidar com casos de canto com zeros, o que torna o código um pouco mais complicado, mas é apenas uma coisa chata caso a caso, por isso vou apenas ligar a ele.

Após sabermos um possível valor de , podemos descobrir exactamente onde a colisão ocorreu usando a fórmula de contenção plug-t-in-line-segment-ponto-contenção mencionada um caminho de volta: $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . Eu chamo esta fórmula de “projeção de lerp” de para a linha no momento , porque ela retorna a proporção para lerp by, do ponto inicial ao ponto final da linha, a fim de obter de volta. É um método prático para extrair:

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

Finalmente, uma vez que temos e , precisamos verificar se eles estão no intervalo . Se estiver fora do intervalo, então a colisão não ocorrerá durante a etapa de tempo atual. Se estiver fora do alcance, então a colisão ocorrerá na linha estendida, mas não no segmento de linha. Como e descrevem quanto lerp a fim de encontrar quando/onde a colisão ocorreu, também é útil voltar ao chamador.

Generalizar

Um detalhe importante que ainda não mencionei é que um ponteiro do mouse em movimento obviamente não corresponde a um ponto. Felizmente, podemos simplesmente cancelar o movimento do ponteiro do rato no último passo (assumindo que é linear), deduzindo-o do movimento do segmento de linha. Isto não só reduz o sistema a um solvível, mas os valores resultantes e são válidos sem qualquer tipo de transformação inversa. O uso se parece com isto:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

Uma complicação potencial é segmentos de linha degenerados que não têm comprimento (onde ambos os pontos finais são iguais). O código não lida explicitamente com este caso, mas agirá como se fosse impossível cortar uma linha que é realmente um ponto. O cálculo de , se for alcançado, será dividido por zero. O resultado (ou -infinidade, +infinidade, ou NaN) falhará a verificação do intervalo.

Outro aspecto que não cobri é o ‘ângulo de corte’. Na animação que mostra os vários casos, os cortes vermelhos são orientados pela leitura entre as velocidades dos dois pontos finais por (quando a velocidade resultante é 0, um ângulo aleatório é escolhido). Mas também usei abordagens alternativas como “o ângulo de corte é a velocidade do ponto”. Basicamente, é um caso de usar o que parece bom e parece natural em vez de tentar descobrir o verdadeiro significado de “ângulo de corte”.

Sumário

Este problema torna-se trivial assim que se aplica algum conhecimento da álgebra linear. Acho que isso não é muito surpreendente, já que a álgebra linear (e os polinômios) aparecem em toda parte, especialmente na geometria.

Uma generalização natural deste problema é incluir espessuras. Afinal, as linhas desenhadas nas telas não são infinitamente finas. Ter uma espessura também é uma boa maneira de reduzir o efeito de arredondamento de erros de ponto flutuante em diferentes direções durante diferentes passos de tempo. Outra mudança útil seria a capacidade de lidar com caminhos parabólicos, uma vez que os objectos do jogo estão muitas vezes em queda livre. Por outro lado, acho que provavelmente é mais fácil tratar ‘linhas grossas’ como polígonos com passos de tempo de velocidade constante.

–

Discuss on Reddit

–

Twisted Oak Studios oferece consultoria e desenvolvimento em projetos interativos de alta tecnologia. Confira nosso portfólio, ou nos dê um grito se você tem algo que você acha que alguns engenheiros radicais realmente deveriam ajudá-lo.

Arquivo

strilanc
O que os computadores Quantum fazem mais rápido, com Caveats
Naming Things: Fail-Useful
Detecting Simple Cycles Forming, Faster
Third Party Bit Commitment
Angular Velocity is Simple
Collection Equality is Hard
Deadlocks in Practice: Não Segurar Bloqueios Enquanto Notifica
Paralisação de Força Bruta
Um Ano de Opiniões sobre Objetivo-C
Referenciando Substratos Mais Rápido, sem Vazamento de Memória
Não Chorar Sobre Código Antigo
Explorar Portões Ternários Universais
Experimentos Impraticáveis #2: Protegendo a Névoa de Guerra entre Pares contra Piratas do Mapa

Aquecendo o Abrandamento Exponencial Enumerando Duas Vezes
Utilizando a Imortalidade para Matar Ciclos de Callback Acidental

Fichas de Cancelamento (e Futuros Colapsantes) para Objetivo-C
Visualizando os Eigenvectores de uma Rotação
Colapsing Futures in Objective-C
Bug Hunting #1: Garbled Audio from End to End
Experimentos Práticos #1: Representando Números como Polinómios
Implementando Pseudo-Telepatia Quântica
Volta Sobre Seus Malditos Avisos
Big-O Trivial Feito Trivial
Insectos Insondáveis #7: The Broken Oven
Solomonoff’s Mad Scientist
Yearly Blogging Roundup #1
What is not a Monad
Searching a Sorted Matrix Faster
How to Read Nested Ternary Operators
Making Sublime Text 2 Jump to the Correct Line with Unity on OS X

My Bug, O meu mau número 4: Leitura simultânea
Teste API completo com reflexos
Optimização de um combinador de analisadores em uma memória
Não tratar caminhos como cordas
Quebrar a função de um caixilho de brinquedo
Contar Iteradores preguiçosamente
Instrumentos insondáveis #6: Pretend Precision
Meu Bug, My Bad #3: Acidentalmente Attacking WarCraft 3
Collapsing Types vs Monads (followup)
Collapsing Futures: Fácil de Usar, Difícil de Representar
Explicar Exceções Atuais vs Programação em um Estilo Funcional Mínimo
O Mistério do Flunf
Explicar como se eu fosse Cinco: The Socialist Millionaire Problem and Secure Multi-Party Computation
Computer Science Blows My Mind
Visita aos Execution Labs em Montreal
Dados de Transmutação, Conservando a Entropia
Regra de Polegar: Peça o Relógio
Regra de Polegar: Use Métodos Purposefully Weakened Methods
Regra de Polegar: Pré-condições a serem verificadas Explicitamente
Listas Ligadas de Interseção Mais Rápido
Mouse Path Smoothing for Jack Lumber
My Bug, My Bad #2: Afundado por flutuação
Reprima-se Diferentemente
Algoritmo de busca quântica do cultivador
Seguir para tipos não-nuláveis vs C#
Optimizar o Just in Time com árvores de expressão
Quando um…Latência do Caminho Não Importa
Determinando exactamente se/quando/onde uma linha em movimento intersectou um ponto em movimento
Emulando Actores em C# com Async/Await
Fazendo uma fila imutável com operações de tempo constante garantido
Melhorando as Excepções Verificadas
Relecções Perecíveis: Os Benefícios de Remoção por Tempo de Vida
Desacoplamento controle compartilhado
Desacoplamento código UI inlined
Linq para Cobranças: Beyond IEnumerable<T>
Publicar o seu .Net como um pacote NuGet
Quando nulo não é suficiente: um tipo de opção para C#
Insectos insondáveis #5: Somente leitura ou não
Minkowski somas: exemplos
Meu Bug, My Bad #1: Esferas fractais
Trabalho em torno da frágil Virtualização da IU no Windows 8
Ancapsular ângulos
Insectos insondáveis #4: Chaves que não são
Como eu usaria uma mônada (em C#)?
Métodos úteis/interessantes #1: Observável. WhenEach
Insectos insondáveis #3: String you along
Aulas de Implementação Anónimas – Um Padrão de Design para C#
Tarefas para ActionScript 3 – Melhorar a Programação Orientada por Eventos
Soma e diferenças de Mindowski
Tipos Não-Nuláveis vs C#: Corrigindo o erro de bilhões de dólares
Instrumentos insondáveis #2: Slashing Out
Esquemas deScript e classes base
Retirada de fontes da unidade
Busando “Tipos Fantasmas” para codificar comprimentos de listas no seu tipo
Crítica construtiva das Extensões Reativas API
Quaterniões parte 3
Quaterniões parte 2
Quaterniões parte 1
Instrumentos insondáveis #1: Você pode ter coisas! Você pode ter coisas EM coisas! Você pode ter …
Coroutinas – Mais do que você quer saber
Ajuda de pacote de assetes
O Visual Studio vai embora
.Net’s time traveling StopWatch
Introducing Catalyst

Savage Rose

Determinando exatamente se/quando/onde uma linha em movimento cruzou um ponto em movimento | Twisted Oak Studios Blog