Como quantificar a retidão de uma linha desenhada?

37

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?

user3637362
fonte
11
Você sabe com antecedência quais são seus dois pontos finais? Ou é determinado no momento em que o usuário para de tocar na tela?
Vaillancourt
Desculpe se minha descrição não está clara para você. Bem, o ponto inicial A (x, y) é o primeiro toque e o ponto final B (x, y) é quando liberamos da tela de toque como você disse.
user3637362
Temos uma pergunta relacionada sobre correspondência de cartas desenhadas por jogadores .
Anko
3
Não poste imagens para o código fonte no futuro.
Josh
11
@ user3637362 Eu entendo que você está começando j=1de modo que você pode comparar touchList[j]com touchList[j-1], mas quando touch.phase == TouchPhase.Beganou touch.phase == TouchPhase.Endedas posições não são adicionados touchListe, posteriormente, não incluídos no sumLength. Esse bug estaria presente em todos os casos, mas seria mais aparente quando a linha tiver poucos segmentos.
Kelly Thomas

Respostas:

52

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:

insira a descrição da imagem aqui

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.

Philipp
fonte
34
Há um pequeno problema com essa abordagem, em que polilinhas de comprimento igual não são igualmente "retas". Uma linha que oscila com baixo desvio (mas muitas vezes) sobre a linha reta é 'mais reta' do que uma linha de comprimento igual que se desvia para um único ponto e depois para trás.
Dancrumb
Não posso marcar com +1 os comentários da @Dancrumbs o suficiente - essa é uma limitação bastante importante desse método, como se o usuário estivesse desenhando uma linha reta, eles oscilarão um pouco, então isso parece um caso de uso comum.
T. Kiley
@Dancrumb basta fatorar a distância média da linha ou fator "distância máxima" em qualquer ponto da linha. Em seguida, você pode ponderar o algoritmo em direção a linhas mais bambas, com amplitudes de desvio menores, e longe das linhas que se afastam do caminho esperado.
Superdoggy
2
@Dancrumb me parece que isso pode acabar sendo um benefício para o caso de uso do OP. As linhas desenhadas à mão terão, naturalmente, pequenos desvios. Essa abordagem pode realmente funcionar para atenuar o efeito dessas diferenças esperadas.
2
@ user3637362 você tem um bug no seu código. Uma possível explicação é que você esqueceu de explicar a distância entre o ponto inicial e o primeiro ponto ou o ponto final e o último ponto, mas sem examinar seu código, é impossível dizer qual poderia ser seu erro.
Philipp
31

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:

  • A soma dos desvios absolutos (do tipo integral) pode ser melhor, pois não calcula a média de erros positivos com negativos. (=sum(abs(deviation)) )
  • Você provavelmente teria que procurar a menor distância até a linha linear se houver uma maneira que crie distâncias mais curtas do que soltar a perpendicular.

desenhando

(Por favor, desculpe a baixa qualidade do meu desenho)

Como você vê, você tem que

  1. encontre um vetor ortogonal para sua linha ( produto pontual é igual a 0 ).
    Se sua linha apontar para (1, 3) o desejado (3, -1)(através da origem cada)
  2. Meça as distâncias h da linha ideal até a do usuário, paralela a esse vetor.
  3. Calcule o RMSD ou a soma das diferenças absolutas.
gr4nt3d
fonte
A resposta de Joel Bosveld indica um caso interessante: uma linha quase perfeitamente reta com cantos no início e no final. Se a linha deve ser desenhada livremente pelo usuário, isso é realmente um problema. No entanto, acho que esse método poderia cobrir esse cenário. Pode-se realmente realizar um ajuste com RMSD ou Integral absoluto como um valor minimizado. Os valores iniciais podem ser os pontos inicial e final. Como o comprimento não importa, também é irrelevante se a otimização mover os pontos para que a linha ideal se estenda mais ou seja mais curta (a altura deve ser calculada para esse nível).
Gr4nt3d
11
Outro caso que isso não parece abranger: digamos que todos os pontos medidos estejam no eixo x, mas a linha inverte a direção várias vezes. Isso retornará um erro de 0.
dave mankoff
23

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 somando h||Da(t)||^2todos os pontos de dados e possivelmente normalizando pelo comprimento da curva. Muito provavelmente, usamos h=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.

Joel Bosveld
fonte
2
Esta é a definição mais sensata de retidão.
Marcks Thomas
11
Essa é de longe a resposta mais sensata e tenho certeza de que os outros parecerão muito frustrantes. Infelizmente, a forma em que a solução é apresentada é um pouco mais obscura que as outras, mas eu recomendo que o OP persista.
Dan Sheppard
Geralmente também acho que essa resposta é realmente a melhor. Embora um problema me incomode: o que acontece se a linha não for "suave o suficiente"? Por exemplo, se você tem dois segmentos de linha perfeitamente retos com um ângulo de, digamos, 90 °. Estou enganado ou isso resultaria em um resultado bastante baixo comparado a uma linha linear realmente suave? (Eu acho que o caso de usuário de Dancrumb com uma linha instável era um problema semelhante) ... Localmente, isso é certamente o melhor caminho.
precisa saber é o seguinte
3

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.

Arqueiro
fonte
3

Uma medida muito fácil e intuitiva é a área entre a melhor linha reta e a curva real. Determinar isso é bastante direto:

  1. Use um ajuste de mínimos quadrados em todos os pontos (isso evita o problema de torção final mencionado por Joel Bosveld).
  2. Para todos os pontos da curva, determine a distância da linha. Este também é um problema padrão. (álgebra linear, transformação de base.)
  3. Soma todas as distâncias.
MSalters
fonte
Você poderia se importar se eu pedir uma codificação de texto (JS, C #) ou pseudo-código, já que a maioria das respostas acima é descrita em teoria, não sei como começar?
user3637362
11
@ user3637362: StackOverflow tem respostas práticas: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

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:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

O que cumulativeDistancepode 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 updateaqui 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.

Vaillancourt
fonte
5
Quando você soma a distância entre a linha ideal e o ponto para cada ponto medido, precisa levar em consideração o número de medidas que tomou, caso contrário, quando o usuário desenha mais devagar ou usa um dispositivo com uma taxa de varredura mais rápida, eles registram mais pontos, o que significa que eles terão uma pontuação pior.
Philipp
@Philipp Sim, você faz! Devo admitir sua maneira de fazê-lo parece melhor que o meu: P
Vaillancourt
Penso que esta abordagem é melhorada tomando a distância média , em vez da distância cumulativa.
Dancrumb
@ Dancrumb Realmente, depende das necessidades, mas sim, isso seria uma maneira de fazê-lo.
Vaillancourt
2

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.

Kik
fonte
1

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.

Adam Davis
fonte
0

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)

philipp
fonte