Como você calcula o ponto mais próximo em 2 curvas?
15
Dados os pontos de uma linha e uma curva quadrática de bezier, como você calcula o ponto mais próximo? .... Da mesma forma, dados os pontos de 2 curvas, como você consegue o ponto mais próximo?
Aqui está a minha tentativa. Os algoritmos a seguir estão longe de serem perfeitos , mas são simples e acredito que você deve começar com isso, verificar se eles funcionam na sua situação e mudar para algo mais rápido e / ou mais preciso posteriormente.
A ideia é a seguinte:
Faça a amostra da curva de Bézier, encontre o ponto mais próximo nessa amostra
Experimente uma vizinhança em torno do ponto encontrado, encontre um novo ponto mais próximo
Continue até que o ponto não mude muito
Algoritmo para distância da curva de Bézier à linha
A curva de Bézier é parametrizada por uma função F(t)usando um conjunto de pontos de controle e um parâmetro variável t. O número de pontos de geração não é importante.
A linha é parametrizada por dois pontos Ae B.
Deixe SAMPLES = 10por exemplo
Comece com t0 = 0et1 = 1
Deixei dt = (t1 - t0) / SAMPLES
Se dt < 1e-10(ou qualquer outra condição de precisão que você achar conveniente), o algoritmo será concluído e a resposta seráF(t0) .
Calcule uma lista de SAMPLES + 1pontos na curva de Bézier:
L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
...
L[SAMPLES] = F(t0 + SAMPLES * dt)
Descubra qual ponto do Líndice ié o mais próximo da linha. Use qualquer método de distância de ponto / linha que você conhece, por exemplo, a distância quadrada ||AB^L[i]A||² / ||AB||²onde ^denota produto cruzado e ||…||é a distância.
Se i == 0, defina i = 1; se i == SAMPLES, definai = SAMPLES - 1
Deixe t1 = t0 + (i + 1) * dtet0 = t0 + (i - 1) * dt
Volte para a etapa 3.
Algoritmo para distância da curva de Bézier à curva de Bézier
Desta vez, temos duas curvas de Bézier, parametrizadas por F(t)e G(t).
Deixe SAMPLES = 10por exemplo
Comece com t0 = 0, t1 = 1, s0 = 0es1 = 1
Deixei dt = (t1 - t0) / SAMPLES
Deixei ds = (s1 - s0) / SAMPLES
Se dt < 1e-10(ou qualquer outra condição de precisão que você achar conveniente), o algoritmo será concluído e a resposta seráF(t0) .
SE esta é a primeira execução do loop:
6.1 Calcule uma lista de SAMPLES + 1pontos F( veja acima ).
6.2 Calcule uma lista de SAMPLES + 1pontos G.
6.3 Descubra qual par de pontos está mais próximo um do outro.
6.4 Atualização t0, t1, s0, s1como visto acima.
ELSE : alternativamente, calcule uma lista de pontos em FOU uma lista de pontos G, depois encontre qual ponto Festá mais próximo G(s0)e atualiza t0e t1, OU qual ponto Gestá mais próximo F(t0)e atualiza s0e s1.
Volte para a etapa 3.
Problemas
Por design, esses algoritmos sempre convergem para um mínimo local. No entanto, não há garantia de que eles convergirão para a melhor solução. Em particular, o algoritmo de curva de Bézier não é muito bom e, no caso de duas curvas estarem próximas umas das outras em muitos lugares, você pode, infelizmente, perder a solução a longo prazo.
Mas como eu disse, antes de começar a pensar em soluções mais robustas, você deve primeiro experimentar essas simples.
1) Traduza tudo para um eixo, portanto, em vez de precisar calcular o comprimento de um ponto para, a 'linha', a 'linha' é, por exemplo, o eixo Y.
Então, dada uma curva mais bezier, eu diria que depende do número de pontos de controle.
Se houver três (início, 'controle' e fim), eu faria algum tipo de verificação (digamos cada um por cento e depois refino entre os mais próximos (digamos, uma abordagem 'binária').
Mais pontos que eu experimentaria o casal mais próximo do (eixo Y traduzido).
Tenho certeza de que um cara de matemática pode lhe dar a solução exata (em matemática), mas se você quiser encontrar a solução / em um videogame, poderá estar melhor com uma solução ligeiramente boa, pois a solução real pode conter várias respostas ( Nem estou falando de poder de processamento).
Para a curva de Bezier - caixa reta, a maneira mais precisa de encontrar a resposta é fazer o seguinte:
Transforme o problema para que a linha reta seja sempre horizontal em Y = 0. Isso é feito multiplicando todos os pontos de controle por uma matriz afim apropriada. (Presumo que você esteja familiarizado com a representação de transformações afins do plano com matrizes 3x3 com 3 entradas fixas.)
Inspecione as coordenadas Y dos pontos de controle. Se eles não tiverem o mesmo sinal, pode haver uma interseção com a linha. Calcule as raízes da parte Y da curva de Bezier. Você pode usar qualquer método de localização de raiz para polinômios, existem muitos na literatura. Por exemplo, google "marcha convexa do casco" - esse é um método razoavelmente bom para os polinômios usados nas curvas de Bezier. Cada raiz encontrada é o valor temporal de uma interseção com a linha, onde a distância é zero - seu trabalho é feito.
Se todas as cordas Y tiverem o mesmo sinal, calcule a derivada da parte Y da curva de Bezier. Você pode ignorar as coordenadas X dos pontos, pois elas não fazem diferença - a linha de destino é horizontal. Encontre as raízes desse derivado. Esses são os valores de tempo nos quais a curva está localmente mais próxima da linha.
Avalie explicitamente a curva de Bezier para todas as raízes encontradas na etapa anterior e relate a raiz que fornece a menor distância da linha. Você também precisa verificar os pontos de extremidade - eles podem dar uma distância menor do que qualquer raiz.
Respostas:
Aqui está a minha tentativa. Os algoritmos a seguir estão longe de serem perfeitos , mas são simples e acredito que você deve começar com isso, verificar se eles funcionam na sua situação e mudar para algo mais rápido e / ou mais preciso posteriormente.
A ideia é a seguinte:
Algoritmo para distância da curva de Bézier à linha
A curva de Bézier é parametrizada por uma função
F(t)
usando um conjunto de pontos de controle e um parâmetro variávelt
. O número de pontos de geração não é importante.A linha é parametrizada por dois pontos
A
eB
.Deixe
SAMPLES = 10
por exemploComece com
t0 = 0
et1 = 1
Deixei
dt = (t1 - t0) / SAMPLES
Se
dt < 1e-10
(ou qualquer outra condição de precisão que você achar conveniente), o algoritmo será concluído e a resposta seráF(t0)
.Calcule uma lista de
SAMPLES + 1
pontos na curva de Bézier:L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
L[SAMPLES] = F(t0 + SAMPLES * dt)
Descubra qual ponto do
L
índicei
é o mais próximo da linha. Use qualquer método de distância de ponto / linha que você conhece, por exemplo, a distância quadrada||AB^L[i]A||² / ||AB||²
onde^
denota produto cruzado e||…||
é a distância.Se
i == 0
, definai = 1
; sei == SAMPLES
, definai = SAMPLES - 1
Deixe
t1 = t0 + (i + 1) * dt
et0 = t0 + (i - 1) * dt
Volte para a etapa 3.
Algoritmo para distância da curva de Bézier à curva de Bézier
Desta vez, temos duas curvas de Bézier, parametrizadas por
F(t)
eG(t)
.Deixe
SAMPLES = 10
por exemploComece com
t0 = 0
,t1 = 1
,s0 = 0
es1 = 1
Deixei
dt = (t1 - t0) / SAMPLES
Deixei
ds = (s1 - s0) / SAMPLES
Se
dt < 1e-10
(ou qualquer outra condição de precisão que você achar conveniente), o algoritmo será concluído e a resposta seráF(t0)
.SE esta é a primeira execução do loop:
6.1 Calcule uma lista de
SAMPLES + 1
pontosF
( veja acima ).6.2 Calcule uma lista de
SAMPLES + 1
pontosG
.6.3 Descubra qual par de pontos está mais próximo um do outro.
6.4 Atualização
t0
,t1
,s0
,s1
como visto acima.ELSE : alternativamente, calcule uma lista de pontos em
F
OU uma lista de pontosG
, depois encontre qual pontoF
está mais próximoG(s0)
e atualizat0
et1
, OU qual pontoG
está mais próximoF(t0)
e atualizas0
es1
.Volte para a etapa 3.
Problemas
Por design, esses algoritmos sempre convergem para um mínimo local. No entanto, não há garantia de que eles convergirão para a melhor solução. Em particular, o algoritmo de curva de Bézier não é muito bom e, no caso de duas curvas estarem próximas umas das outras em muitos lugares, você pode, infelizmente, perder a solução a longo prazo.
Mas como eu disse, antes de começar a pensar em soluções mais robustas, você deve primeiro experimentar essas simples.
fonte
1) Traduza tudo para um eixo, portanto, em vez de precisar calcular o comprimento de um ponto para, a 'linha', a 'linha' é, por exemplo, o eixo Y.
Então, dada uma curva mais bezier, eu diria que depende do número de pontos de controle.
Se houver três (início, 'controle' e fim), eu faria algum tipo de verificação (digamos cada um por cento e depois refino entre os mais próximos (digamos, uma abordagem 'binária').
Mais pontos que eu experimentaria o casal mais próximo do (eixo Y traduzido).
Tenho certeza de que um cara de matemática pode lhe dar a solução exata (em matemática), mas se você quiser encontrar a solução / em um videogame, poderá estar melhor com uma solução ligeiramente boa, pois a solução real pode conter várias respostas ( Nem estou falando de poder de processamento).
fonte
Algumas respostas da página do blog Algorithmist , que encontra corretamente o ponto mais próximo na curva quadrática de bezier.
Demo .
fonte
Para a curva de Bezier - caixa reta, a maneira mais precisa de encontrar a resposta é fazer o seguinte:
fonte