Como posso verificar se uma linha desenhada pelo jogador segue um caminho?

8

Eu quero desenhar um caminho invisível que o usuário deve seguir. Eu armazenei esse caminho como pontos. Quando um jogador desenha uma linha, como posso testar se ela segue o caminho que eu armazenei?

Aqui está um exemplo para rastrear a letra A.

rastreio de exemplo

if((traitSprite.getX()<=Invisible.X  && traitSprite.getX()>=Invisible.X )){...}

( traitSpriteé um sprite.)

Android
fonte
Como você está armazenando o caminho que a linha traçada do jogador deve seguir? É isso que o sprite é?
Anko
não, são pontos que eu inseri manualmente. é uma péssima idéia, mas acho que o uso do "Vector2" será uma solução eficaz, mas eu realmente não sei como usá-lo.
Android

Respostas:

12

Aqui está uma solução baseada em vetor. Eu não tentei, mas parece bem conceitualmente.

Teoria

Acho que você armazenou a forma como segmentos de linha. Aqui está a letra A representada com três segmentos de linha.

segmentos de linha que representam uma letra

Eu assumi que os caminhos no desenho do usuário são armazenados como listas de pontos.

Podemos "inflar" esses segmentos de linha para permitir uma margem de erro ao verificar a proximidade : se o caminho desenhado pelo usuário está próximo da margem de erro correta das linhas.

segmentos de linha "inflados" caminho desenhado pelo usuário em cima da letra com margens de erro

No entanto, isso por si só não é suficiente. Também precisamos verificar a cobertura : se o desenho do usuário "cobre" uma grande fração da forma. Esses desenhos são ruins, porque, mesmo que se encaixem na margem de erro, estão faltando parte da carta:

desenhos ruins

Se verificarmos as duas coisas, podemos aproximar se o desenho do jogador é bom.

Implementação

Verificar a proximidade significa apenas para cada ponto do caminho do usuário, encontrar a distância entre essa e todas as linhas que compõem a letra, obter a menor e verificar se é menor que a margem de erro.

Verificar a cobertura é mais complicado, mas é possível obter uma aproximação muito boa com a matemática vetorial se, para cada segmento de linha, você encontrar o caminho mais próximo desenhado pelo usuário (verde) e projetar suas partes (verde escuro) nesse segmento de linha (preto), em seguida, verifique se os vetores projetados (em azul) a cobrem:

verificação de cobertura por projeção vetorial

Para projetar um vetor aem outro vetor b, faça

projection = dotProduct(a, b) / lengthSquared(b) * b

onde dotProductcalcula o produto escalar dos dois vetores e lengthSquaredé o que parece. Essencialmente, isso encontra o valor escalar de quanto avai na bdireção e multiplica- bo para obter um vetor na mesma direção. (O tutorial de detecção de colisão A da Metanet Software tem uma boa visualização disso na projeção do Apêndice A § ).

A direção do vetor projetado pode não ser realmente importante. Se você somar os comprimentos dos vetores projetados e compará-los com o comprimento total do segmento de linha, isso indicará qual fração é coberta. (Exceto em casos ímpares, consulte § Limitações abaixo).

Na imagem acima, o caminho abrangeria cerca da metade do segmento. Você pode escolher qualquer valor de tolerância que desejar.

Limitações

Letras curvas

Os segmentos de linha são sub-ideais: muitas letras são curvas! Como você representa um 'P' ou um 'O'?

Você pode usar muitos segmentos de linha (talvez com uma margem de erro maior).

letra P aproximada com segmentos de linha letra O aproximada com segmentos de linha

Você também pode começar a usar curvas de Bézier em vez de linhas para um ajuste mais próximo, mas observe que encontrar o ponto mais próximo em um Bézier é muito mais complexo - assim como muitas outras operações de medição.

Incompatibilidades

Margens de tolerância excessivamente relaxadas quanto à distância das linhas e cobertura da carta podem ter conseqüências não intencionais.

Por exemplo, o jogador pode estar tentando desenhar um 'H' aqui.

uma letra H erroneamente reconhecida como A

Loops e sobreposições

loop e sobreposição em (possivelmente) letra reconhecida

Loops ou sobreposições no caminho desenhado pelo jogador podem resultar em algumas partes do desenho sendo contadas duas vezes ao projetá-las no segmento de linha mais próximo.

Isso poderia ser contornado através do processamento mais sofisticado dos vetores projetados, talvez armazenando exatamente onde o vetor projetado seria (armazene também a direção da projeção e o ponto mais próximo do segmento de linha ao ponto da linha desenhada pelo jogador) , rejeitando os novos que se sobrepõem.

Se o jogador desenhasse um único caminho e este fosse processado a partir do final marcado com o círculo azul, as partes verdes desse caminho seriam aceitas e as vermelhas rejeitadas, porque sua projeção se sobrepunha a algumas partes processadas anteriormente.

rejeitando loops e sobreposições

A implementação possui muitas sutilezas técnicas que provavelmente pertenceriam a uma pergunta diferente.

Jogadores imprevisivelmente aventureiros

Um jogador pode desenhar algo estranho que ainda passa .

trolololol

Embora você possa chamar isso de recurso! :)

Anko
fonte
obrigado, o que você propõe não desenhar fora da carta?
Android
@ Android As "margens de erro" laranja são para isso. Você pode rejeitar linhas que vão para fora deles: assim, por exemplo.
Anko
O que eu quero é fazer a letra como um SpriteBatch, então a única área em que posso desenhar é esse lote de sprites, que pode assumir a forma de A ou B, X .... isso é possível? se for como posso criar uma textura como um SpriteBatch? E agradeço antecipadamente.
Android
2

dr sugiro fazer o pincel dos jogadores pintar um plano 2D visível (ou invisível). Diferencie a imagem pintada dos usuários com a origem (a silhueta desejada ou o modelo 2D). Se você deseja aumentar a precisão, torne as linhas de orientação e as escovas mais estreitas, para permitir mais espaço para erros, torne a escova e o design mais espessos.

Caso contrário, você poderá medir a distância de cada (x, y) em que os usuários clicam / tocam no spline calculando o ponto para segmentar a distância. Em seguida, você pode calcular a média das distâncias para compor uma medida de precisão e eficiência. Isso exigirá mais trabalho para obter uma medida significativa da conclusão e perceber a eficácia com que o usuário executou.


Consideração: Sugiro que não o faça (verificando diretamente se uma linha segue um caminho). Esta é possivelmente uma má ideia. Parece que você deseja que o usuário preencha uma silhueta. O caminho em si é um spline (esquelético) representando a silhueta.

Se você simplesmente fizer com que o pincel dos jogadores aplique uma massa monocromática de pixels no plano 2D, poderá executar um processo em segundo plano que verifique quantos pixels estão dentro da silhueta e quantos estão fora. Isso pode resultar facilmente em% de sucesso, onde quanto% do padrão é preenchido é uma estatística de interesse e outra é quanto% está fora das bordas do modelo. Se você verificar as distâncias do sub-segmento, não será muito claro o trabalho dos usuários.

AturSams
fonte
1

A melhor solução para não usar gráficos é fazê-lo com matemática!

É fácil entender o quanto cada ponto (pintado pelo usuário) está longe do segmento /programming/849211/shortest-distance-between-a-point-and-a-line-segment

Como você pode calcular o erro médio, avalie quanto usuário está correto.

Alexsey Shestacov
fonte
obrigado, mas para letras como "C" "O"? ... não existe uma distância fixa entre os pontos ...
Android
Você pode fazer "C" e "O" de 6-8 segmentos de linha, assim como otheres, mas matemática vai ser um pouco diferente, em measurment erro termos
Alexsey Shestacov