Melhor correspondência em um gráfico bipartido (por exemplo, associando rótulos a pontos em um gráfico)
Eu estou tentando extrair semântica de gráficos xy gráficos onde os pontos são plotados e alguns ou todos têm um rótulo. O rótulo é plotado "perto do ponto", de modo que um humano pode normalmente entender qual rótulo vai com qual ponto. Por exemplo, neste gráfico, está claro qual rótulo (número) pertence a qual ponto (*) e um algoritmo baseado na distância euclidiana funcionaria. (Os rótulos e pontos não têm ordenação semântica - por exemplo, um gráfico de dispersão)
*1
*2
*3
*4
Em parcelas congestionadas, o software / usuário de criação pode colocar o rótulo em direções diferentes para evitar a sobreposição. Por exemplo em
1**2
**4
3
Um leitor humano pode normalmente descobrir qual rótulo está associado a qual rótulo.
Uma solução que eu aceitaria seria criar uma matriz de distância euclidiana e embaralhar as linhas para obter o mínimo de uma função (por exemplo, os quadrados somados das distâncias na diagonal ou outra heurística). No segundo exemplo (com os pontos marcados a, b, c, d no sentido horário a partir do canto NW), temos uma matriz de distância (para 1 d.p.)
a b c d
1ab2 1 1.0 2.0 2.2 1.4
dc4 2 2.0 1.0 1.4 2.2
3 3 2.0 2.2 1.4 1.0
4 2.2 1.4 1.0 2.0
e precisamos rotulara1 b2 c4 d3
. Trocar as linhas 3 e 4 fornece a soma mínima da diagonal. Aqui está um exemplo mais complexo, onde simplesmente escolher o mais próximo pode falhar
*1*2*5
**4
3 *6
Se isso for resolvido, precisarei ir a casos em que o número de rótulos pode ser menor ou maior que o número de pontos.
Se o algoritmo é padrão, eu apreciaria um ponteiro para Open Source Java (por exemplo, JAMA ou Apache)
NOTA: Esta resposta SOAssociando pontos próximos a um caminho não funciona como resposta, porque o caminho através dos pontos é dado.