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)

<code> *1
    *2

        *3

      *4
</code>

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

<code>1**2
 **4
 3
</code>

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.)

<code>             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
</code>

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

<code> *1*2*5
  **4
  3 *6
</code>

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.