Kräftesimulation auf einer 2D-Oberfläche

[DerSammler]

Hi Java-Community!

Erstmal eine kurze Beschreibung der Situation: ich habe einen Baum, dessen Knoten alles Bilder sind. Die Bilder sind im Baum nach Ähnlichkeit angeordnet (Stichwort Content Based Image Retrieval) und haben voneinander einen bestimmten Ähnlichkeitsabstand. Momentan ist der Baum noch statisch, wird also einmal aufgebaut und das wars, wobei der Ähnlichkeitsabstand nicht berücksichtigt wird (alle Kanten sind gleich lang).
Nun das Problem: Wie mach ich das am geschicktesten, dass sich der Baum während der Laufzeit dynamisch verändert, also die einzelnen Bilder näher aufeinander zubewegen bzw. voneinander wegbewegen bis sich irgendwann ein Gleichgewicht eingestellt hat. Das Ganze möchte ich lösen ohne eine bereits bestehende API zu verwenden, also eine einfache Anziehungssimulation selber schreiben. Gezeichnet werden die Bilder übrigens alle auf ein JComponent, was wiederum auf einem JFrame liegt.
Gibts da irgendwelche fertigen theoretischen Grundlagen, auf was muss ich achten, wie wird das am effizientesten gehen, solche und ähnliche Fragen beschäftigen mich im Moment.
Über jede Hilfe wäre ich sehr erfreut,
Vielen Dank im Vorraus

MfG
-Der Sammler

 

[Marco13]

Hm - was genau jetzt die Frage ist, ist nicht ganz klar. Meinst du sowas
http://java.sun.com/applets/jdk/1.4/demo/applets/GraphLayout/example1.html
mit "Images" als Knoten? Geht es um das Layout an sich, oder die Bewegung....?

 

[kaie]

Ich habe sowas ähnliches mal vor ein paar Jahren geschrieben, allerdings mit Texten statt Bildern. Sollte aber leicht anzupassen sein. Hier der Quelltext:

Zunächst eine Klasse Knoten:

import java.awt.*;
import java.io.*;
import java.net.*;
import java.util.*;

public class Knoten
{
	//--------------------------------------------------------------------------
	//
	// Attribute
	//
	//--------------------------------------------------------------------------
	public boolean sichtbar     = false;                          // wird der Knoten momentan angezeigt?
	public double  sichtbarkeit = 0;                              // Hilfsvariable zum sanften ausblenden
	public String  text         = "";                             // Beschriftung
	public Knoten  vorgaenger   = null;                           // Eltern-Knoten
	public double  x            = 0;                              // Position x
	public double  y            = 0;                              // Position y
	public double  vx           = 0;                              // Geschwindigkeit x
	public double  vy           = 0;                              // Geschwindigkeit y
	public double  gummiband    = 100;                            // Länge der Verbindung zum Vorgänger
	public Color   hintergrund  = new Color(255,255,200);         // Hintergrund-Farbe
	public Color   vordergrund  = new Color(0,0,0);               // Schriftfarbe
	public Font    schrift      = new Font("Tahoma",Font.BOLD,16);// Schriftart
	public int     breite       = 0;                              // Breite in Pixeln
	public int     hoehe        = 0;                              // Höhe in Pixeln
	public Vector  nachfolger   = new Vector();                   // alle Kinderelemente
	public int     ebene        = 0;                              // Anzahl Vorgänger bis zum Urahn
	
	public static Vector sichtbareKnoten = new Vector();          // alle Momentan angezeigten Knoten
	
	//--------------------------------------------------------------------------
	//
	// Konstruktor
	//
	//--------------------------------------------------------------------------
	/**
	* erstellt einen neuen Knoten
	* @param k der Vorgänger-Knoten dieses Knotens. Für Wurzelknoten kann k auch null sein
	* @param s der Text dieses Knotens
	*/
	public Knoten( Knoten k, String s )
	{
		if( s==null ) s="";
		text = s;
		if( k!=null )
		{
			vorgaenger = k;
			x=k.x+Math.random()-.5;
			y=k.y+Math.random()-.5;
			k.nachfolger.addElement(this);
			ebene=k.ebene+1;
		}
		if( k==null )
		{
			x = 400;
			y = 400;
			hintergrund=Color.red;
			setzeSichtbar(true);
		}
	}
	
	/**
	* zeichnet die Verbindungslinien
	* @param g das Graphics-Objekt der Componente, auf die gezeichnet werden soll
	*/
	public void zeichneLinie( Graphics g )
	{
		// Ist überhaupt ein Vorgänger vorhanden?
		if( vorgaenger==null ) return;
		// Linie zeichnen
		g.setColor(new Color(0,0,0,(int)(255*sichtbarkeit)));
		g.drawLine((int)vorgaenger.x,(int)vorgaenger.y,(int)x,(int)y);
	}
	
	/**
	* zeichnet den Knoten.
	* @param g das Graphics-Objekt der Componente, auf die gezeichnet werden soll
	*/
	public void zeichneText( Graphics g )
	{
		// Schrift setzen
		g.setFont(schrift);
		// Schriftausmaße ermitteln
		FontMetrics fm = g.getFontMetrics();
		int w = fm.stringWidth(text);
		int h = fm.getHeight();
		breite = w+4;
		hoehe  = h+4;
		// Hintergrundrechteck zeichnen
		g.setColor(new Color(hintergrund.getRed(),hintergrund.getGreen(),hintergrund.getBlue(),(int)(255*sichtbarkeit)));
		g.fillRect((int)x-w/2-2,(int)y-h/2-2,w+4,h+4);
		// Rahmen zeichnen
		g.setColor(new Color(0,0,0,(int)(255*sichtbarkeit)));
		g.drawRect((int)x-w/2-2,(int)y-h/2-2,w+4,h+4);
		// Text zeichnen
		g.setColor(new Color(vordergrund.getRed(),vordergrund.getGreen(),vordergrund.getBlue(),(int)(255*sichtbarkeit)));
		g.drawString(text,(int)x-w/2,(int)y-h/2+fm.getAscent());
	}
	
	/**
	* schaltet das Zeichnen eines Knotens ein oder aus.
	* @param b 
	*/
	public void setzeSichtbar( boolean b )
	{
		if( vorgaenger==null && !b )  return;
		sichtbar = b;
		if( b && !sichtbareKnoten.contains(this) ) sichtbareKnoten.addElement(this);
		if( b )
		{
			for( int i=0; i<nachfolger.size(); i++ )
			{
				Knoten k = (Knoten)nachfolger.elementAt(i);
				k.sichtbar=true;
				k.x = x+Math.random()-.5;
				k.y = y+Math.random()-.5;
				if( !sichtbareKnoten.contains(k) ) sichtbareKnoten.addElement(k);
			}
		} else
		{
			for( int i=0; i<nachfolger.size(); i++ )
			{
				Knoten k = (Knoten)nachfolger.elementAt(i);
				k.setzeSichtbar(b);
			}
		}
	}
	
	public void setzeAlleSichtbar()
	{		
		sichtbar=true;
		if( !sichtbareKnoten.contains(this) ) sichtbareKnoten.addElement(this);		
		for( int i=0; i<nachfolger.size(); i++ )
		{
			Knoten k = (Knoten)nachfolger.elementAt(i);
			k.setzeAlleSichtbar();
			k.x = x+Math.random()-.5;
			k.y = y+Math.random()-.5;
		}
	}
	
	/**
	* bewegt den Knoten um die aktuelle Geschwindigkeit. Außerdem wird der Knoten
	* durch Reibung abgebremst. Der Root-Knoten wird nicht bewegt, um zu verhindern,
	* dass das Netz aus dem Bild wandert.
	*/
	public void bewege()
	{
		if( sichtbar && sichtbarkeit<1 ) sichtbarkeit = Math.min(1,sichtbarkeit+.1);
		if( !sichtbar && sichtbarkeit>0 )
		{
			sichtbarkeit = Math.max(0,sichtbarkeit-.1);
			if( sichtbarkeit==0 )
				sichtbareKnoten.removeElement(this);		
		}
		if( vorgaenger==null ) return;
		x+=vx*.2;
		y+=vy*.2;
		vx*=0.7;
		vy*=0.7;
	}
	
	/**
	* sorgt dafür, dass das Gummiband den Knoten immer zu seinem Vorgängerknoten
	* zurückzieht. Je größer der Unterschied zwischen tatsächlichem Abstand und
	* Gummibandlänge (dem Soll-Abstand) ist, desto größer ist die ausgeübte Kraft.
	* (linear-elastisches Materialverhalten).
	*/
	public void anziehung()
	{
		if( vorgaenger==null ) return;
		
		double dx = vorgaenger.x-x;
		double dy = vorgaenger.y-y;
		double d = Math.sqrt(dx*dx+dy*dy)-gummiband;
		if( d==0 ) return;
		d=Math.min(d,100);
		vx+=d*dx*.01;
		vy+=d*dy*.01;
	}
	
	/**
	* erzeugt eine Abstossungskraft zwischen diesem Knoten und einem anderen
	* Knoten. Die Abstoßungskraft nimmt mit dem Quadrat des Abstandes ab. Die
	* Abstossung findet nur einseitig statt, d.h. nur der betrachtete Knoten,
	* nicht der abstossende Knoten k werden beschleunigt. Um eine gegenseitige
	* Abstossung zu erreichen, muss diese Methode für alle Knotenpaare
	* aufgerufen werden.
	* @param k der Knoten, von dem der betrachtete Knoten abgestossen wird
	*/
	public void abstossung( Knoten k )
	{
		if( k==this || k.vorgaenger==this || k.ebene>ebene ) return;
		double dx = k.x-x;
		double dy = k.y-y;
		double d = 50/Math.pow(dx*dx+dy*dy,1);;
		d=Math.min(d,50);
		if( dx==0 && dy==0 ) return;
		vx-=d*dx;
		vy-=d*dy;
	}
	
	
	//--------------------------------------------------------------------------
	//
	// statische Methoden
	//
	//--------------------------------------------------------------------------
	public static void bewegeAlle()
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			((Knoten)sichtbareKnoten.elementAt(i)).bewege();
		}
	}
	
	public static void anziehungAlle()
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			((Knoten)sichtbareKnoten.elementAt(i)).anziehung();
		}
	}
	
	public static void abstossungAlle()
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			Knoten k1 = (Knoten)sichtbareKnoten.elementAt(i);
			for( int j=0; j<sichtbareKnoten.size(); j++ )
			{
				Knoten k2 = (Knoten)sichtbareKnoten.elementAt(j);
				k1.abstossung(k2);
			}
		}
	}
	
	public static void zeichneAlleLinien( Graphics g )
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			Knoten k = (Knoten)sichtbareKnoten.elementAt(i);
			k.zeichneLinie(g);
		}
	}

	public static void zeichneAlleKnoten( Graphics g )
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			Knoten k = (Knoten)sichtbareKnoten.elementAt(i);
			k.zeichneText(g);
		}
	}
	
	public static Knoten sucheKnoten( double x, double y )
	{
		for( int i=0; i<sichtbareKnoten.size(); i++ )
		{
			 Knoten k = (Knoten)sichtbareKnoten.elementAt(i);
			 if( k.x-k.breite/2<=x && k.x+k.breite/2>=x && k.y-k.hoehe/2<=y && k.y+k.hoehe/2>=y )
			 	return k;
		}
		return null;
	}
	
	//--------------------------------------------------------------------------
	//
	// Lade-Methode für XML-Dateien
	//
	//--------------------------------------------------------------------------
	public static void ausXML( String datei )
	{
		try
		{
			// Text einlesen
			BufferedReader in = new BufferedReader( new FileReader(datei));
			String s = "";
			String line = in.readLine();
			while( line!=null )
			{
				s+=line;
				line=in.readLine();
			}
			
			// Text zerlegen
			Knoten aktuell = null;
			StringTokenizer token = new StringTokenizer(s,"<>",true);
			boolean tag = false;
			while( token.hasMoreTokens() )
			{
				String t=token.nextToken();
				if( t.equals("<") )
					tag=true;
				else if( t.equals(">") )
					tag=false;
				else
				{
					if( tag )
					{
						if( t.startsWith("!") )
						{
						}
						else if( t.startsWith("/") )
						{
							aktuell=aktuell.vorgaenger;
						}
						else if( t.endsWith("/") )
						{
							new Knoten( aktuell,new StringTokenizer(t,"/",false).nextToken() );
						} else
						{
							aktuell = new Knoten( aktuell,new StringTokenizer(t,"/",false).nextToken() );
						}
					} else
					{
						if( t.trim().length()>0 )
						{
							Knoten k = new Knoten(aktuell,t);
							k.hintergrund=Color.green;
						}
					}
				}
			}
		} catch( Exception e ) {}
	}
}

Die Darstellung erfolgt auf einem Canvas:

import java.awt.*;
import java.awt.event.*;

public class TreeView extends Canvas implements Runnable, MouseListener, MouseMotionListener
{
	//-------------------------------------------------------------------------
	//
	// Attribute
	//
	//-------------------------------------------------------------------------
	/**
	 * Image zum DoubleBuffering der Grafikdarstellung
	 */
	private Image buffer = null;
	/**
	 * der Knoten, der momentan vom Benutzer mit der Maus verschoben wird.
	 */
	private Knoten dragKnoten = null;
		
	//-------------------------------------------------------------------------
	//
	// Konstruktor
	//
	//-------------------------------------------------------------------------
	/**
	 * erzeugt einen neuen TreeView. Im Hintergrund wird der Bewegungs-Thread
	 * gestartet, der die Knoten animiert und das Bild neu zeichnet.
	 */
	public TreeView()
	{
		addMouseListener(this);
		addMouseMotionListener(this);
		new Thread(this).start();
	}
	
	//-------------------------------------------------------------------------
	//
	// Zeichenmethode
	//
	//-------------------------------------------------------------------------
	public void paint( Graphics g2 )
	{
		// Buffer-Image erzeugen oder aktualisieren
		int w = getSize().width;
		int h = getSize().height;
		if( buffer==null || buffer.getWidth(null)!=w || buffer.getHeight(null)!=h )
		{
			buffer = createImage(w,h);
		}
		// Offscreen-Graphics-Objekt holen
		Graphics g = buffer.getGraphics();
		
		// Hintergrund zeichnen
		g.setColor(getBackground());
		g.fillRect(0,0,w,h);
		// Alle Knoten und Verbindungslinien zeichnen
		Knoten.zeichneAlleLinien(g);
		Knoten.zeichneAlleKnoten(g);
		// Buffer-Bild darstellen
		g2.drawImage(buffer,0,0,null);
	}
	
	/**
	 * Flackern des Bildes beim DoubleBuffering unterbinden.
	 */
	public void update( Graphics g )
	{
		paint(g);
	}
	
	/**
	 * run-Methode des Aktualisier-Threads. Hier werden jede
	 * Sekunde alle Knoten bewegt und das Bild neu gezeichnet.
	 */
	public void run()
	{
		while( true )
		{
			try{ Thread.sleep(50); } catch( Exception e ){}
			repaint();
			Knoten.abstossungAlle();
			Knoten.anziehungAlle();
			Knoten.bewegeAlle();
		}
	}
	
	//-------------------------------------------------------------------------
	//
	// MouseListener-Methoden
	//
	//-------------------------------------------------------------------------
	public void mouseReleased( MouseEvent me ) {}
	public void mouseEntered ( MouseEvent me ) {}
	public void mouseExited  ( MouseEvent me ) {}
	public void mouseMoved   ( MouseEvent me ) {}
	public void mousePressed ( MouseEvent me )
	{
		// nächsten Knoten heraussuchen
		dragKnoten=Knoten.sucheKnoten(me.getX(),me.getY());
	}
	public void mouseClicked ( MouseEvent me )
	{
		// einzelne oder alle Knoten darstellen oder verstecken
		if( dragKnoten!=null && me.getClickCount()==2 ) dragKnoten.setzeAlleSichtbar();
		else if( dragKnoten!=null ) dragKnoten.setzeSichtbar(!me.isMetaDown());
	}
	public void mouseDragged ( MouseEvent me )
	{
		// ausgewählten Knoten verschieben
		if( dragKnoten!=null )
		{
			dragKnoten.x=me.getX();
			dragKnoten.y=me.getY();
		}
	}
}

Und zum Testen kannst Du einfach die folgende Klasse verwenden:

import java.awt.*;
public class Test
{
	public static void main( String[] args )
	{
		Knoten[] k = new Knoten[17];
		
		k[0] = new Knoten(null,"java");
		k[1] = new Knoten(k[0],"java.lang");
		k[2] = new Knoten(k[0],"java.util");
		k[3] = new Knoten(k[0],"java.io");
		k[4] = new Knoten(k[0],"java.net");
		
		k[5] = new Knoten(k[1],"String");
		k[6] = new Knoten(k[1],"Math");

		k[7] = new Knoten(k[2],"Vector");
		k[8] = new Knoten(k[2],"ArrayList");
		k[9] = new Knoten(k[3],"PrintWriter");
		k[10] = new Knoten(k[3],"File");
		k[11] = new Knoten(k[3],"OutputStream");
		k[12] = new Knoten(k[4],"Socket");
		k[13] = new Knoten(k[4],"URL");
		
		k[14] = new Knoten(k[11],"PrintStream");
		k[15] = new Knoten(k[11],"ObjectOutputStream");
		k[16] = new Knoten(k[11],"DataOutputStream");

		k[0].x = 300;
		k[0].y = 300;
		
		// alles in einem Frame anzeigen
		Frame f = new Frame("TreeGraph");
		f.setSize(600,600);
		f.add(new TreeView());
		f.setVisible(true);
	}
}

Kannst den Quelltext gerne weiterverwenden und umschreiben. War eh nur als Spielerei gedacht. Übrigens kann man sich mit der Methode "ausXML" in "Knoten" eine komplette XML-Datei als dynamischen Baum anzeigen lassen.

Viel Spaß beim Ausprobieren!

P.S.: Bitte vergebt mir die vielen statischen Methoden. Wie gesagt: es war nur als Spielzeug gedacht!

 

[pyr0t0n]

zwar mal nix zum thema wollt da oben gepostete bsp programm mal testen, aber er zeigt mir nur knoten 0 an. Habs 1:1 kopiert

 

[kaie]

Am Anfang sind alle Knoten ausser dem Hauptknoten versteckt. Mach einfach mal einen Doppelklick auf den Knoten, dann sollten die anderen auftauchen...

 

[DerSammler]

Vielen Dank erstmal, das werd ich mal anpassen und mal sehen, ob das bei mir auch so geht ;-)