rtreevisualizer.java

r_tree原代码

// RTree Visualizer
//
// Copyright (C) 2003  Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// Contact information:
//  Mailing address:
//    Marios Hadjieleftheriou
//    University of California, Riverside
//    Department of Computer Science
//    Surge Building, Room 310
//    Riverside, CA 92521
//
//  Email:
//    [e-mail]

import java.text.*;
import java.applet.Applet;
import java.awt.*;
import java.awt.GraphicsConfiguration;
import com.sun.j3d.utils.applet.MainFrame; 
import com.sun.j3d.utils.geometry.*;
import com.sun.j3d.utils.geometry.Primitive.*;
import com.sun.j3d.utils.universe.*;
import com.sun.j3d.utils.behaviors.mouse.*;
import javax.media.j3d.*;
import javax.vecmath.*;
import java.awt.AWTEvent;
import java.awt.event.*;
import java.util.*;
import java.io.*;
import com.sun.j3d.utils.behaviors.keyboard.*;
import spatialindex.spatialindex.*;
import spatialindex.storagemanager.*;
import spatialindex.rtree.*;
import com.sun.image.codec.jpeg.*;
import sun.awt.image.codec.*;
import java.awt.image.BufferedImage;

public class RTreeVisualizer extends Applet
{
	Matrix4d m_initialView = new Matrix4d(new double[]
	{
		1.0, 0.0, 0.0, -6.759999999999997,
		0.0, 0.3247962844387753, 0.9457839994495368, -5.339999999999969,
		0.0, -0.9457839994495368, 0.3247962844387753, -17.0,
		0.0, 0.0, 0.0, 1.0
	});

	protected Transform3D m_currentTransform = new Transform3D(m_initialView);
	protected float m_scaleFactor = 3.0f;
	protected BranchGroup m_scene = null;
	protected SimpleUniverse m_universe;
	protected Canvas3D m_canvas3D;
	protected RTree m_tree;

	protected Color3f[] m_levelColoring = new Color3f[]
	{
		new Color3f(1.0f, 1.0f, 1.0f), new Color3f(1.0f, 0.0f, 0.0f), new Color3f(0.0f, 1.0f, 0.0f), new Color3f(0.0f, 0.0f, 1.0f),
		new Color3f(0.6f, 0.6f, 0.6f), new Color3f(1.0f, 1.0f, 0.0f), new Color3f(0.0f, 1.0f, 1.0f), new Color3f(1.0f, 0.0f, 1.0f)
	};

	RTreeVisualizer(RTree tree)
	{
		m_tree = tree;

  	setLayout(new BorderLayout());
    GraphicsConfiguration config = SimpleUniverse.getPreferredConfiguration();

		m_canvas3D = new Canvas3D(config);
    add("Center", m_canvas3D);

    m_universe = new SimpleUniverse(m_canvas3D);
		m_canvas3D.getView().setBackClipDistance(999.0);
    createSceneGraph();
	}

	public void createSceneGraph()
	{
		if (m_scene != null)
		{
    	m_scene.detach();
      TransformGroup tg = (TransformGroup) m_scene.getChild(0);
      tg.getTransform(m_currentTransform);
		}

		// Create the root of the branch graph
		m_scene = new BranchGroup();
		m_scene.setCapability(BranchGroup.ALLOW_DETACH);
		m_scene.setCapability(BranchGroup.ALLOW_CHILDREN_READ);

    TransformGroup objTransform = new TransformGroup();
    objTransform.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);
    objTransform.setCapability(TransformGroup.ALLOW_TRANSFORM_READ);

		createTree(objTransform);

    m_scene.addChild(objTransform);
		objTransform.setTransform(m_currentTransform);

		KeyboardDriver kb = new KeyboardDriver(objTransform);
		kb.setSchedulingBounds(new BoundingSphere());
    m_scene.addChild(kb);

    MouseRotate myMouseRotate = new MouseRotate();
		myMouseRotate.setTransformGroup(objTransform);
    myMouseRotate.setSchedulingBounds(new BoundingSphere());
    m_scene.addChild(myMouseRotate);

    MouseTranslate myMouseTranslate = new MouseTranslate();
    myMouseTranslate.setTransformGroup(objTransform);
    myMouseTranslate.setSchedulingBounds(new BoundingSphere());
    m_scene.addChild(myMouseTranslate);

    MouseZoom myMouseZoom = new MouseZoom();
    myMouseZoom.setTransformGroup(objTransform);
    myMouseZoom.setSchedulingBounds(new BoundingSphere());
    m_scene.addChild(myMouseZoom);

		// Let Java 3D perform optimizations on this scene graph.
    m_scene.compile();
    m_universe.addBranchGraph(m_scene);
	}

	void createTree(Group g)
	{
		System.out.println("\nTree properties:");
		System.out.println(m_tree);

		MyQueryStrategy qs = new MyQueryStrategy();

		try
		{
			m_tree.queryStrategy(qs);
			if (qs.m_entries.isEmpty()) return;
		}
		catch (Exception e)
		{
			e.printStackTrace();
			System.exit(-1);
		}

		float offsetX = 0.0f;
		float offsetY = 0.0f;
		int startLevel = qs.m_root.m_level;

		if (qs.m_root.m_region.m_pLow.length > 3)
		{
			System.err.println("2 and 3-dimsnional R-trees are only supported.");
			System.exit(-1);
		}

		do
		{
			createData(g, qs.m_root, offsetX, offsetY, 0.03f);
			Data r = (Data) qs.m_entries.get(0);
			if (r != qs.m_root) createData(g, r, offsetX, offsetY, 0.02f);

			for (int cIndex = 1; cIndex < qs.m_entries.size(); cIndex++)
			{
				r = (Data) qs.m_entries.get(cIndex);
				createData(g, r, offsetX, offsetY, 0.0f);
			}

			if (qs.m_entries.size() - 1 > 0)
			{
				String txt = "";
				if (qs.m_entries.size() - 1 == 1) txt = "1 child";
				else if (qs.m_entries.size() - 1 > 1) txt = (qs.m_entries.size() - 1) + " children";

		    Text2D t = new Text2D(txt,  m_levelColoring[0], "Helvetica", 50, Font.BOLD);
				BoundingBox b = (BoundingBox) t.getBounds();
				Point3d u = new Point3d();
				b.getUpper(u);
				Point3d l = new Point3d();
				b.getLower(l);
				Vector3f v = new Vector3f(offsetX, (float) (offsetY - 0.03f - u.y - l.y), (qs.m_root.m_region.m_pLow.length == 3) ? (float) (m_scaleFactor * qs.m_root.m_region.m_pHigh[2]) : 0.0f);
				Transform3D t1 = new Transform3D();
				t1.setTranslation(v);
				TransformGroup tg = new TransformGroup();
				tg.setTransform(t1);
				tg.addChild(t);
				g.addChild(tg);
			}

			try
			{
				m_tree.queryStrategy(qs);
				if (qs.m_entries.isEmpty())
				{
					veryImportantFunction(g, offsetX, offsetY);
					return;
				}
			}
			catch (Exception e)
			{
				e.printStackTrace();
				System.exit(-1);
			}

			Data rnew = (Data) qs.m_entries.get(0);

			if (rnew.m_level < startLevel)
			{
				startLevel = rnew.m_level;
				offsetX += m_scaleFactor * (float) qs.m_root.m_region.m_pHigh[0] + 0.5f;
				offsetY = 0.0f;
			}
			else
			{
				offsetY += m_scaleFactor * (float) qs.m_root.m_region.m_pHigh[1] + 0.8f;
			}
		}
		while (! qs.m_entries.isEmpty());
	}

	void createData(Group g, Data d, float offsetX, float offsetY, float pad)
	{
		Appearance a = new Appearance();
		ColoringAttributes ca = new ColoringAttributes();
		ca.setColor(m_levelColoring[(d.m_level < 0 || d.m_level >= m_levelColoring.length) ? 0 : d.m_level]);
		a.setColoringAttributes(ca);

		Transform3D t = new Transform3D();
		t.setTranslation(new Vector3d(offsetX, offsetY, 0.0f));
		TransformGroup tg = new TransformGroup();
		tg.setTransform(t);

		if (d.m_region.m_pLow.length == 2)
		{
			LineArray qa = new LineArray(8, LineArray.COORDINATES);
			qa.setCoordinate(0, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), 0.0));
			qa.setCoordinate(1, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), 0.0));
			qa.setCoordinate(2, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), 0.0));
			qa.setCoordinate(3, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), 0.0));
			qa.setCoordinate(4, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), 0.0));
			qa.setCoordinate(5, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), 0.0));
			qa.setCoordinate(6, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), 0.0));
			qa.setCoordinate(7, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), 0.0));
			tg.addChild(new Shape3D(qa, a));

			a = new Appearance();
			a.setColoringAttributes(ca);
			LineAttributes la = new LineAttributes();
			la.setLinePattern(LineAttributes.PATTERN_DASH_DOT);
			a.setLineAttributes(la);

			qa = new LineArray(2, LineArray.COORDINATES);
			qa.setCoordinate(0, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), 0.0));
			qa.setCoordinate(1, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), 0.0));
			tg.addChild(new Shape3D(qa, a));

			g.addChild(tg);
		}
		else
		{
			LineArray qa = new LineArray(24, LineArray.COORDINATES);
			qa.setCoordinate(0, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(1, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(2, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(3, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(4, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(5, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(6, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(7, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(8, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(9, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(10, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(11, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(12, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(13, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(14, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			qa.setCoordinate(15, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(16, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(17, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(18, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(19, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(20, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(21, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(22, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(23, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));

			tg.addChild(new Shape3D(qa, a));

			a = new Appearance();
			a.setColoringAttributes(ca);
			LineAttributes la = new LineAttributes();
			la.setLinePattern(LineAttributes.PATTERN_DASH_DOT);
			a.setLineAttributes(la);

			qa = new LineArray(4, LineArray.COORDINATES);
			qa.setCoordinate(0, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(1, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pHigh[1] + pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(2, new Point3d(m_scaleFactor * (d.m_region.m_pHigh[0] + pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pHigh[2] + pad)));
			qa.setCoordinate(3, new Point3d(m_scaleFactor * (d.m_region.m_pLow[0] - pad), m_scaleFactor * (d.m_region.m_pLow[1] - pad), m_scaleFactor * (d.m_region.m_pLow[2] - pad)));
			tg.addChild(new Shape3D(qa, a));

			g.addChild(tg);
		}
	}

	public void veryImportantFunction(Group g, float offsetX, float offsetY)
	{
		// easter egg.
    Appearance textAppear = new Appearance();
    ColoringAttributes textColor = new ColoringAttributes();
    textColor.setColor(0.65f, 0.1f, 0.66f);
    textAppear.setColoringAttributes(textColor);
    PolygonAttributes pa = new PolygonAttributes();
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    textAppear.setPolygonAttributes(pa);
		Font3D font3D = new Font3D(new Font("Helvetica", Font.PLAIN, 1), new FontExtrusion());
		Text3D textGeom = new Text3D(font3D, new String("marioh"));
    textGeom.setAlignment(Text3D.ALIGN_CENTER);
    Shape3D textShape = new Shape3D(textGeom, textAppear);
		Transform3D t3d = new Transform3D();
		t3d.setTranslation(new Vector3f(offsetX, offsetY, -10.0f));
		TransformGroup textGroup = new TransformGroup();