Beste Übereinstimmung in einem zweigliedrigen Diagramm (z. B. Zuordnen von Beschriftungen zu Punkten auf einem Diagramm)

Question

Apr 14, 2012, 12:01 PM

Beste Übereinstimmung in einem zweigliedrigen Diagramm (z. B. Zuordnen von Beschriftungen zu Punkten auf einem Diagramm)

Ich versuche, Semantik aus grafischen xy-Diagrammen zu extrahieren, in denen die Punkte geplottet sind und einige oder alle eine Beschriftung haben. Das Etikett wird "in der Nähe des Punktes" gezeichnet, so dass ein Mensch normalerweise verstehen kann, welches Etikett zu welchem Punkt gehört. In diesem Diagramm ist zum Beispiel klar, welche Bezeichnung (Nummer) zu welchem Punkt (*) gehört, und ein Algorithmus, der auf der euklidischen Entfernung basiert, würde funktionieren. (Die Bezeichnungen und Punkte haben keine semantische Reihenfolge - beispielsweise ein Streudiagramm)

<code> *1
    *2

        *3

      *4
</code>

In überlasteten Plots kann die Autorensoftware / der Mensch das Etikett in verschiedene Richtungen platzieren, um Überlappungen zu vermeiden. Zum Beispiel in

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

Ein menschlicher Leser kann normalerweise herausfinden, welches Etikett welchem Etikett zugeordnet ist.

Eine Lösung, die ich akzeptieren würde, wäre, eine euklidische Abstandsmatrix zu erstellen und die Zeilen zu mischen, um das Minimum einer Funktion zu erhalten (z. B. die summierten Quadrate der Abstände auf der Diagonale oder eine andere Heuristik). Im zweiten Beispiel (mit den Punkten a, b, c, d im Uhrzeigersinn von der NW-Ecke) haben wir eine Distanzmatrix (bis 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>

und wir müssen beschriftena1 b2 c4 d3. Das Vertauschen der Reihen 3 und 4 ergibt die minimale Summe der Diagonalen. Hier ist ein komplexeres Beispiel, bei dem das einfache Auswählen des nächsten fehlschlagen kann

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

Wenn dies gelöst ist, muss ich zu den Fällen gehen, in denen die Anzahl der Etiketten kleiner oder größer als die Anzahl der Punkte sein kann.

Wenn der Algorithmus Standard ist, würde ich einen Zeiger auf Open Source Java schätzen (z. B. JAMA oder Apache Mathe)

HINWEIS: Diese SO AntwortIn der Nähe befindliche Punkte mit einem Pfad verknüpfen funktioniert nicht ganz als antwort, da der weg durch die punkte vorgegeben ist.