Medição da retidão de um segmento de curva (representado como uma polilinha)

11

Estou trabalhando em um algoritmo de rotulagem de contorno de elevação automática e um dos fatores que quero levar em consideração ao decidir as posições das etiquetas é quão "reto" é um segmento específico de um contorno. Quanto mais reta, maior a probabilidade de ser usada para colocar a etiqueta nesse segmento.

Cada contorno é representado por uma polilinha (mas com pontos próximos um do outro para parecer uma curva a olho nu). Em seguida, tenho um comprimento fixo (largura de um rótulo), digamos, 100 pixels. Se eu escolher aleatoriamente (ou não) um segmento de contorno com a largura de 100 pixels, desejo obter um valor quantitativo numérico de sua retidão (digamos zero para um segmento de contorno totalmente reto, algum valor maior que zero para um não segmento tão reto, e esse valor aumenta à medida que a curvatura aumenta).

Procurei por respostas, mas não encontrei nada realmente útil. Eu ficaria grato por qualquer indicação.

Igor Brejc
fonte

Respostas:

9

A resposta depende do contexto : se você estiver investigando apenas um pequeno número (limitado) de segmentos, poderá conseguir uma solução computacionalmente cara. No entanto, parece provável que você queira incorporar esse cálculo a algum tipo de pesquisa de bons pontos de etiqueta. Nesse caso, é de grande vantagem ter uma solução que seja computacionalmente rápida ou permita atualização rápida de uma solução quando o segmento de linha candidato varia ligeiramente.

Por exemplo, suponha que você pretenda realizar uma pesquisa sistemáticaatravés de todo um componente conectado de um contorno, representado como uma sequência dos pontos P (0), P (1), ..., P (n). Isso seria feito inicializando um ponteiro (índice na sequência) s = 0 ("s" para "start") e outro ponteiro f (para "finish") para ser o menor índice para o qual a distância (P (f), P (s))> = 100 e, em seguida, avançando s pela distância (P (f), P (s + 1))> = 100. Isso produz uma polilinha candidata (P (s), P (s + 1) ..., P (f-1), P (f)) para avaliação. Depois de avaliar sua "adequação" para suportar um rótulo, você aumentaria s em 1 (s = s + 1) e aumentaria f para (digamos) f 'es para s' até que uma polilinha candidata exceda o mínimo é produzido um intervalo de 100, representado como (P (s '), ... P (f), P (f + 1), ..., P (f')). Ao fazer isso, os vértices P (s) ... P (s ' É altamente desejável que a aptidão possa ser rapidamente atualizada a partir do conhecimento apenas dos vértices descartados e adicionados. (Esse procedimento de digitalização continuará até s = n; como sempre, f deve ter permissão para "contornar" de n de volta a 0 no processo.)

Essa consideração exclui muitas medidas possíveis de adequação ( sinuosidade , tortuosidade etc.) que, de outra forma, poderiam ser atraentes. Isso nos leva a favorecer medidas baseadas em L2 , porque elas geralmente podem ser atualizadas rapidamente quando os dados subjacentes mudam ligeiramente. Fazer uma analogia com a análise de componentes principais sugere que adotarmos a seguinte medida (onde menor é melhor, conforme solicitado): use o menor dos dois valores próprios da matriz de covariânciadas coordenadas do ponto. Geometricamente, essa é uma medida do desvio "típico" de um lado para o outro dos vértices na seção candidata da polilinha. (Uma interpretação é que sua raiz quadrada é o semi-eixo menor da elipse, representando os segundos momentos de inércia dos vértices da polilinha.) Será igual a zero apenas para conjuntos de vértices colineares; caso contrário, excederá zero. Ele mede um desvio médio de um lado para o outro em relação à linha de base de 100 pixels criada pelo início e pelo final de uma polilinha e, portanto, possui uma interpretação simples.

Como a matriz de covariância é de apenas 2 por 2, os valores próprios são rapidamente encontrados através da resolução de uma única equação quadrática. Além disso, a matriz de covariância é uma soma das contribuições de cada um dos vértices de uma polilinha. Assim, ele é atualizado rapidamente quando pontos são eliminados ou adicionados, levando a um algoritmo O (n) para um contorno de n pontos: ele será bem dimensionado para os contornos altamente detalhados previstos no aplicativo.

Aqui está um exemplo do resultado desse algoritmo. Os pontos pretos são vértices de um contorno. A linha vermelha sólida é o melhor segmento de polilinha candidato de comprimento de ponta a ponta maior que 100 nesse contorno. (O candidato visualmente óbvio no canto superior direito não é suficientemente longo.)

Figura

whuber
fonte
Uau, você me perdeu lá :). Você está certo sobre a pesquisa sistemática, eu já tenho que fazer isso para obter a tangente de cada vértice polilinha / polígono (os rótulos horizontais são preferidos aos verticais), então, em teoria, eu poderia estender essa pesquisa para abranger outras medidas. BTW: você produziu o gráfico de amostra usando um algoritmo real ou manualmente?
Igor Brejc
1
A ilustração é real, mas a implementação que eu usei não usa o procedimento de atualização de covariância e, portanto, não é ideal em termos computacionais.
whuber
2
O gráfico ao final faz com que esta resposta ainda mais incrível
Ragi Yaser Burhum
2
Igor, devo mencionar que a direção do rótulo é gratuita: é dada pela direção do eixo principal da elipse (o vetor próprio associado ao maior valor próprio). Portanto, é possível procurar simultaneamente de maneira eficiente a melhor combinação de orientação de etiqueta e linearidade da seção de contorno.
whuber
3

Na comunidade de computação gráfica, muitas vezes é necessário encontrar uma caixa delimitadora em torno de um objeto. Consequentemente, esse é um problema bem estudado, com algoritmos rápidos. Por exemplo, consulte o artigo Algoritmos da caixa delimitadora da Wikipedia . Você pode encontrar o retângulo de área mínima ao redor da polilinha e usar a proporção, altura / comprimento do retângulo. Para obter uma medida mais precisa, você pode observar o desvio da polilinha da linha central desse retângulo delimitador.

Joseph O'Rourke
fonte
1
Eu pensei em usar min. caixas delimitadoras, mas vejo dois problemas: a) complexidade computacional do cálculo de uma caixa que seria realmente mínima (e assim rotacionada), b) dois segmentos de curva com a mesma proporção podem ter uma curvatura muito diferente (pense em uma sinusoidal curva com a mesma amplitude, mas com diferentes períodos de onda).
Igor Brejc 29/10
1
É bom ver você aqui nas páginas de GIS, Joseph!
whuber
1
Sim, eu tenho o seu "Computational Geometry em C" livro em minhas mãos agora :)
Igor Brejc
1
Obrigado pela recepção, pessoal! :-) Sei que minha sugestão não é a medida ideal, mas a codificação está pronta para uso (se você tiver a estante certa). Esse tipo de problema foi estudado bastante em contextos de fabricação, onde eles precisam medir a qualidade de uma peça usinada.
Joseph O'Rourke
3

Não sei se isso ajuda, ou mesmo se conta como resposta, mas como eu estava sentado aqui pensando na pergunta que acabei de postar, pensei:

E se você colocar um círculo de um raio específico na sua linha de contorno. Esse círculo cruzará a linha de contorno em pelo menos dois lugares. Quanto mais reta a linha, menor a distância ao longo da linha de contorno entre os dois pontos de interseção. Quanto maior a distância ao longo da linha de contorno entre os pontos de interseção, mais curva é a linha. Se houver mais de dois pontos de interseção, a linha de contorno é muito curvilínea.

Você pode descobrir qual comprimento daria o melhor indicador de retidão e configurar uma rotina para percorrer cada linha de contorno e, onde ela era reta o suficiente, colocar o rótulo.

Tenho certeza de que isso não ajuda muito, e o que digo em inglês é muito mais difícil em qualquer linguagem de programação que você esteja usando, mas pode ser um começo?

Rex-H
fonte
Idéia interessante. Para simplificar, você pode calcular a proporção entre o comprimento do segmento de um lado e a distância entre os pontos inicial e final. Não é tão preciso, mas é rápido de calcular. E sua ideia de usar um círculo permitiria um cálculo mais preciso da retidão.
Igor Brejc 29/10
3

A abordagem mais fácil que consigo pensar é a relação entre o comprimento real do caminho entre o início e o fim e a distância mais curta (linha reta) do início ao ponto final. Linhas retas terão proporções próximas de uma, enquanto linhas muito curvas terão uma proporção muito alta.

Essa deve ser uma solução realmente fácil de implementar.


Atualização: Como Mike percebeu corretamente, isso seria igual ao Sinuosity .

insira a descrição da imagem aqui

underdark
fonte
Apenas o que me veio à mente depois de ler a resposta de Rex :)
Igor Brejc
4
basicamente o inverso da sinuosidade
Mike T
exatamente :) ....
underdark
2
Você está certo de que isso seria fácil de implementar, porque atualizar o comprimento conforme se procura por segmentos apropriados para rotular é tão simples quanto adicionar e subtrair comprimentos entre vértices sucessivos. No entanto, a sinuosidade não captura efetivamente o sentido em que uma curva pode se afastar da linearidade. Por exemplo, compare um semicírculo de diâmetro 100 com uma sequência linear de semicírculos de diâmetro 1 : ambas as curvas têm a mesma sinuosidade, mas o desvio de um lado para o outro da primeira é 100 vezes o do segundo (o que seria uma boa base para um rótulo).
whuber
Leve em consideração que, se sua polilinha desenhar um círculo, esse método fornecerá uma sinuosidade infinita que talvez não seja o resultado desejado.
obchardon
1

Ao pesquisar "curvatura" e "polilinha", obtive essas informações. Como posso encontrar a curvatura de uma polilinha? . Lá, ele sugeriu o uso de voltar à definição de curvatura - K= DF/Ds. Aqui, Fele quer dizer phi, ou Tna notação da wikipedia aqui ( http://en.wikipedia.org/wiki/Curvature ).

Digamos que você tenha uma sequência de três pontos, p0, p1 e p2. calcule a distância sentre p0 e p1, que é delta de s ( Ds), assumindo que os pontos estejam próximos o suficiente. Então você precisa delta de T ( DT), que é a mudança no vetor tangencial unitário entre p0 e p1. pode haver uma maneira sofisticada, mas o método bruto em que consigo pensar leva dois betores p0-> p1, p1-> p2, normaliza cada um para ter comprimento de um, depois pega a subtração vetorial desses dois e determina a magnitude. Essa é DT. Divisão produz uma curvatura K0_1. pegue p1, p2 e p3 para calcular K1_2e assim por diante.

Gostaria de saber se você se apossar do contorno como uma polilinha, não como pixels renderizados. Você disse 100px para que eu me preocupasse um pouco.

yosukesabai
fonte
Obrigado pelo link, vou ter que estudar a matemática por trás dele. Eu mencionei 100px simplesmente porque o texto do rótulo renderizado tem uma certa largura (em pixels), 100px era apenas um exemplo.
Igor Brejc 29/10
Pensar em curvatura é uma boa ideia. Curvatura em seções de contorno pesadamente suavizadas de comprimento suficiente pode ser apropriada, mas a curvatura em si não é: um único pequeno zigue-zague teria uma curvatura extremamente alta, por exemplo, mas seria inconseqüente em geral. Assim, com efeito, você usaria algum resumo estatístico do desvio da linearidade entre as seções da polilinha. Entre os possíveis candidatos, a curvatura seria um dos cálculos mais complexos a serem executados.
whuber