Nomeando este algoritmo: comparando e interpolando pontos?

Question

Minha pergunta pode ser um pouco estranha. Eu "desenvolvi" um algoritmo e não sei se já existe um algoritmo semelhante por aí.

A situação: eu tenho uma faixa definida por pontos de pista (2D). Os pontos de pista representam turnos, por exemplo. Entre os pontos de pista, existem apenas linhas retas. Agora recebo um conjunto de coordenadas neste espaço 2D. Calculei a distância do primeiro ponto de pista até as novas coordenadas e a distância para o intervalo para os dois primeiros pontos de pista. Se a distância das coordenadas medidas for menor que a distância do primeiro ao segundo ponto de pista, estou assumindo que esse ponto esteja entre esse intervalo. Eu então faço uma interpolação linear nisso. Se for maior, verificarei com o próximo intervalo.

Portanto, basicamente está levando distâncias de intervalo e tentando encaixá -las lá. Estou tentando rastrear um objeto se movendo aproximadamente ao longo desta faixa.

Isso soa familiar para alguém? Alguém pode ter uma sugestão para um algoritmo existente similar?

EDITAR: Pelo que afirmei até agora, quero esclarecer que uma posição não está se multiplicando para rastrear pontos. Considere o bom desenho ASCII Jonathan fez:

A posição X é encontrada no segmento 1 e 2 (S12). Agora, a próxima posição é Y, que não deve ser considerada próxima o suficiente para estar no S12. Vou passar para o S23 e verificar se está dentro.

Se estiver, não estarei verificando o S12 por nenhum outro valor, porque já encontrei um no próximo segmento. O algoritmo "não olha para trás".

Mas se não encontrar o segmento certo a partir daí, porque aconteceu para estar longe do primeiro segmento, mas ainda mais longe de qualquer outro segmento de qualquer maneira, eu abandonarei o valor e a próxima posição será procurada De volta ao S12, novamente.

O loop ainda continua sendo um problema. Considere que eu recebo Y para S23 e depois pule duas ou três posições (como elas estão muito longe), posso estar perdendo a pista. Eu poderia determinar uma posição no S34, onde já estaria no S56.

Talvez eu possa criar uma velocidade média para o Vage, informe em qual segmento deve ser.

Parece que, quanto maior os segmentos, maior a chance de tomar uma decisão certa.

Answer 1

O que me preocupa com o algoritmo que você descreveu é que ele é 'ganancioso' e pode escolher o segmento de faixa 'errado' (ou, pelo menos, um segmento de faixa que não é o mais próximo do ponto).

Hora de empurrar a arte ascii para os limites. Considere o caminho a seguir (os números representam a sequência na lista de pontos de pista) e a coordenada x (e, posteriormente, y).

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

Como devemos interpretar sua descrição?

C] alculam a distância do primeiro ponto de pista para as novas coordenadas e a distância para o intervalo para os dois primeiros pontos de pista. Se a distância das coordenadas medidas for menor que a distância do primeiro ao segundo ponto de pista, [suponha] que esse ponto esteja entre esse intervalo; [...] [eu] é maior, [...] verifique com o próximo intervalo.

Eu acho que a primeira frase significa:

• Calcule a distância de TP1 (ponto de trilha 1) para TP2 - chame de d12.
• Calcule a distância de TP1 a X (chame -a D1X) e de TP2 a X (chame de d2x).

A parte complicada é a interpretação da frase condicional.

Minha impressão é que, se D1X ou D2X for menor que D12, x será considerado (ou mais próximo) o segmento de faixa TP1 a TP2 (Chame It Segment S12).

Olhando para a posição de x no diagrama, fica moderadamente claro que D1X e D2X são menores que D12, então minha interpretação do seu algoritmo interpretaria x como associada a S12, mas X está claramente mais próximo de S23 ou S56 do que é para S12 (mas esses são descartados sem serem considerados).

Eu não entendi algo sobre o seu algoritmo?

Pensando um pouco: o que eu interpretei seu algoritmo significa é que, se o ponto X estiver dentro do círculo do raio D12 centrado no TP1 ou no círculo do raio D12 centrado no TP2, você associa X ao S12. No entanto, se também considerarmos o ponto Y, o algoritmo que eu sugiro que você esteja usando também o associaria ao S12.

Se o algoritmo for refinado para dizer MAX(D1Y, D2Y) < D12, então não considera y relacionado ao S12. No entanto, X provavelmente ainda é considerado relacionado ao S12 em vez de S23 ou S56.

Answer 2

A primeira parte desse algoritmo me lembra de um espaço discretizado. Um exemplo de representar esse espaço é o Ordem Z. curva de preenchimento de espaço. Eu usei esta técnica para representar um Quadtree, a estrutura de dados para um Refinamento de malha adaptável Código em que trabalhei e usei um algoritmo muito parecido com o que você descreve para atravessar a grade e determinar distâncias entre partículas.

A semelhança pode não ser imediatamente óbvia. Como você está preocupado apenas com os locais de intervalo, você está efetivamente tratando todos os pontos no intervalo como equivalente nesta etapa. É o mesmo que escolher um espaço que só possui pontos discretizados - você está efetivamente "estalando" seus pontos para uma grade.