Estou trabalhando em um jogo que exige que os jogadores desenhem uma linha de um ponto A (x1, y1) para o outro ponto B (x2, y2) na tela de um dispositivo Android.
Quero descobrir como esse desenho se encaixa em uma linha reta. Por exemplo, um resultado de 90% significaria que o desenho se encaixa quase perfeitamente na linha. Se os jogadores desenharem uma linha curva de A a B, deve obter uma pontuação baixa.
Os pontos finais não são conhecidos antecipadamente. Como posso fazer isso?
j=1
de modo que você pode comparartouchList[j]
comtouchList[j-1]
, mas quandotouch.phase == TouchPhase.Began
outouch.phase == TouchPhase.Ended
as posições não são adicionadostouchList
e, posteriormente, não incluídos nosumLength
. Esse bug estaria presente em todos os casos, mas seria mais aparente quando a linha tiver poucos segmentos.Respostas:
Uma linha perfeitamente reta também seria a linha mais curta possível com um comprimento total de
sqrt((x1-x2)² + (y1-y2)²)
. Uma linha mais rabiscada será uma conexão menos ideal e, portanto, inevitavelmente mais longa.Quando você pega todos os pontos individuais do caminho que o usuário desenhou e resume as distâncias entre eles, você pode comparar o comprimento total com o comprimento ideal. Quanto menor o comprimento total dividido pelo comprimento ideal, melhor a linha.
Aqui está uma visualização. Quando os pontos pretos são os pontos finais do gesto e os pontos azuis são os pontos que você mediu durante o gesto, você deve calcular e somar os comprimentos das linhas verdes e dividi-los pelo comprimento da linha vermelha:
Uma pontuação ou índice de sinuosidade igual a 1 seria perfeito, qualquer coisa maior seria menos perfeita, qualquer coisa abaixo de 1 seria um bug. Quando você preferir ter a pontuação em porcentagem, divida 100% por esse número.
fonte
Essa também pode não ser a melhor maneira de implementar isso, mas sugiro que um RMSD (desvio médio quadrático da raiz) seja melhor do que apenas o método da distância, nos casos mencionados por Dancrumb (veja as duas primeiras linhas abaixo).
RMSD = sqrt(mean(deviation^2))
Nota:
=sum(abs(deviation))
)(Por favor, desculpe a baixa qualidade do meu desenho)
Como você vê, você tem que
Se sua linha apontar para
(1, 3)
o desejado(3, -1)
(através da origem cada)h
da linha ideal até a do usuário, paralela a esse vetor.fonte
As respostas existentes não levam em consideração que os pontos finais são arbitrários (e não dados). Portanto, ao medir a retidão da curva, não faz sentido usar os pontos finais (por exemplo, para calcular o comprimento, ângulo, posição esperados). Um exemplo simples seria uma linha reta com as duas extremidades torcidas. Se medirmos usando a distância da curva e a linha reta entre os pontos finais, isso será bastante grande, pois a linha reta que desenhamos é deslocada da linha reta entre os pontos finais.
Como sabemos se a curva é reta? Supondo que a curva seja suave o suficiente, queremos saber quanto, em média, a tangente à curva está mudando. Para uma linha, isso seria zero (como a tangente é constante).
Se deixarmos a posição no tempo t ser (x (t), y (t)), a tangente é (Dx (t), Dy (t)), onde Dx (t) é a derivada de x no tempo t (este site parece estar com falta de suporte TeX). Se a curva não for parametrizada pelo comprimento do arco, normalizamos dividindo por || (Dx (t), Dy (t)) ||. Portanto, temos um vetor unitário (ou ângulo) da tangente à curva no tempo t. Então, o ângulo é a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||
Estamos interessados em || Da (t) || ^ 2 integrado ao longo da curva.
Dado que provavelmente temos pontos de dados discretos em vez de uma curva, devemos usar diferenças finitas para aproximar as derivadas. Então, Da (t) se torna
(a(t+h)-a(t))/h
. E, a (t) se torna((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||
. Em seguida, obtemos S somandoh||Da(t)||^2
todos os pontos de dados e possivelmente normalizando pelo comprimento da curva. Muito provavelmente, usamosh=1
, mas é realmente apenas um fator de escala arbitrário.Para reiterar, S será zero para uma linha e maior quanto mais se desvia de uma linha. Para converter para o formato necessário, use
1/(1+S)
. Dado que a escala é um tanto arbitrária, é possível multiplicar S por algum número positivo (ou transformá-lo de outra maneira, por exemplo, use bS ^ c em vez de S) para ajustar a retidão de certas curvas.fonte
Este é um sistema baseado em grade, certo? Encontre seus próprios pontos para a linha e calcule a inclinação da linha. Agora, usando esse cálculo, determine pontos válidos pelos quais a linha passaria, dada uma margem de erro do valor exato.
Através de uma pequena quantidade de testes de tentativa e erro, determine qual quantidade boa e ruim de pontos correspondentes existiria e configure seu jogo usando uma escala para os mesmos resultados dos testes.
ou seja, uma linha curta com inclinação quase horizontal pode ter 7 pontos pelos quais você pode desenhar. Se você puder corresponder consistentemente 6 ou mais dos 7 que foram determinados como parte da linha reta, essa seria a pontuação mais alta. A classificação do comprimento e da precisão deve fazer parte da pontuação.
fonte
Uma medida muito fácil e intuitiva é a área entre a melhor linha reta e a curva real. Determinar isso é bastante direto:
fonte
A idéia é manter todos os pontos que o usuário tocou, avaliar e somar a distância entre cada um desses pontos à linha formada quando o usuário libera a tela.
Aqui está algo para você começar no pseudo-código:
O que
cumulativeDistance
pode dar uma idéia sobre o acessório. Uma distância de 0 significaria que o usuário estava sempre na linha. Agora você teria que fazer alguns testes para ver como ele se comporta no seu contexto. E você pode querer ampliar o valor retornado pordistanceOfPointToLine
quadrá-lo para penalizar mais as grandes distâncias da linha.Não estou familiarizado com a unidade, mas o código
update
aqui pode entrar em umonDrag
funcionar.E você pode querer adicionar em algum lugar algum código para impedir o registro de um ponto, se for o mesmo que o último registrado. Você não deseja registrar itens quando o usuário não se move.
fonte
Um método que você pode usar é subdividir a linha em segmentos e criar um produto de ponto vetorial entre cada vetor que representa o segmento e um vetor representando uma linha reta entre o primeiro e o último ponto. Isso tem o benefício de permitir que você encontre segmentos extremamente "pontiagudos" facilmente.
Editar:
Além disso, eu consideraria o uso do comprimento do segmento além do produto escalar. Um vetor muito curto, mas ortogonal, deve contar menos que um longo, com menos desvios.
fonte
O mais fácil e rápido pode ser simplesmente descobrir a espessura da linha para cobrir todos os pontos da linha traçada pelo usuário.
Quanto mais espessa a linha, pior o usuário desenhou sua linha.
fonte
De alguma forma, consultando o MSalters Answer, aqui estão algumas informações mais específicas.
Use o método dos mínimos quadrados para ajustar uma linha aos seus pontos. Você está basicamente procurando por uma função y = f (x) que melhor se ajuste. Depois de o ter, pode utilizar os valores y reais para somar o quadrado das diferenças:
s = soma acima ((yf (x)) ^ 2)
Quanto menor a soma, mais reta a linha.
Como obter a melhor aproximação, é explicado aqui: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf
Basta ler em "Ajustando uma linha reta". Observe que t é usado em vez de xeb em vez de y. C e D devem ser determinados como aproximação, então você tem f (x) = C + Dx
Nota adicional: Obviamente, você também deve levar em consideração o comprimento da linha. Cada linha composta por 2 pontos será perfeita. Não sei o contexto exato, mas acho que usaria a soma dos quadrados divididos pelo número de pontos como classificação. Também acrescentaria a exigência de um comprimento mínimo, número mínimo de pontos. (Talvez cerca de 75% do comprimento máximo)
fonte