Package org.jungrapht.visualization.spatial

Class SpatialGrid<V>

  • All Implemented Interfaces:
    LayoutStateChange.Listener, LayoutVertexPositionChange.Listener<V>, TreeNode, Spatial<V,​V>
    public class SpatialGrid<V>
extends AbstractSpatial<V,​V>
implements Spatial<V,​V>, TreeNode, LayoutVertexPositionChange.Listener<V>
    A Spatial Data Structure to optimize rendering performance. The SpatialGrid is used to determine which graph vertices are actually visible for a given rendering situation. Only the visible vertices are passed to the rendering pipeline. When used with Edges, only Edges with at least one visible endpoint are passed to the rendering pipeline.

    See SimpleGraphSpatialTest (jung-samples) for a rendering that exposes the internals of the SpatialGrid.

    Author:
    Tom Nelson

    • Constructor Detail

      • SpatialGrid

        public SpatialGrid​(LayoutModel<V> layoutModel)
        Create an instance
        Parameters:
        layoutModel -

      • SpatialGrid

        public SpatialGrid​(LayoutModel<V> layoutModel,
                   Rectangle2D bounds,
                   int horizontalCount,
                   int verticalCount)
        Create an instance
        Parameters:
        bounds - the area of the grid
        horizontalCount - how many tiles in a row
        verticalCount - how many tiles in a column

    • Method Detail

      • setBounds

        public void setBounds​(Rectangle2D bounds)
        Set the layoutSize of the spatial grid and recompute the box widths and heights. null out the obsolete grid cache
        Specified by:
        setBounds in interface Spatial<V,​V>
        Parameters:
        bounds - recalculate the size of the spatial area

      • getContainingLeafs

        public Set<TreeNode> getContainingLeafs​(Point2D p)
        Specified by:
        getContainingLeafs in interface Spatial<V,​V>
        Parameters:
        p - a point to search in the spatial structure
        Returns:
        all leaf nodes that contain the passed point

      • getContainingLeafs

        public Set<TreeNode> getContainingLeafs​(double x,
                                        double y)
        Specified by:
        getContainingLeafs in interface Spatial<V,​V>
        Parameters:
        x - the x location to search for
        y - the y location to search for
        Returns:
        all leaf nodes that contain the passed coordinates

      • getContainingLeaf

        public TreeNode getContainingLeaf​(Object element)
        Specified by:
        getContainingLeaf in interface Spatial<V,​V>
        Parameters:
        element - element to search for
        Returns:
        the leaf node that currently contains the element (not a spatial search)

      • getGrid

        public List<Shape> getGrid()
        Lazily compute the gridCache if needed. The gridCache is a list of rectangles overlaying the layout area. They are numbered from 0 to horizontalCount*verticalCount-1
        Specified by:
        getGrid in interface Spatial<V,​V>
        Returns:
        the boxes in the grid

      • getMap

        public Map<Integer,​? extends Collection<V>> getMap()
        A Multimap of box number to Lists of vertices in that box
        Returns:
        the map of box numbers to contained vertices

      • getBoxNumber

        protected int getBoxNumber​(int boxX,
                           int boxY)
        given the box x,y coordinates (not the coordinate system) return the box number (0,0) has box 0 (horizontalCount,horizontalCount) has box horizontalCount*verticalCount - 1
        Parameters:
        boxX - the x value in the box grid
        boxY - the y value in the box grid
        Returns:
        the box number for boxX,boxY

      • getBoxNumber

        protected int getBoxNumber​(int[] boxXY)
        Parameters:
        boxXY - the (x,y) in the grid coordinate system
        Returns:
        the box number for that (x,y)

      • getBoxNumberFromLocation

        protected int getBoxNumberFromLocation​(Point p)
        give a Point in the coordinate system, return the box number that contains it
        Parameters:
        p - a location in the coordinate system
        Returns:
        the box number that contains the passed location

      • getBoxNumberFromLocation

        protected int getBoxNumberFromLocation​(double x,
                                       double y)
        give a Point in the coordinate system, return the box number that contains it
        Parameters:
        x - , y a location in the coordinate system
        Returns:
        the box number that contains the passed location

      • getBoxIndex

        protected int[] getBoxIndex​(double x,
                            double y)
        given (x,y) in the coordinate system, get the boxX,boxY for the box that it is in
        Parameters:
        x - a location in the coordinate system
        y - a location in the coordinate system
        Returns:
        a 2 dimensional array of int containing the box x and y coordinates

      • recalculate

        public void recalculate()
        Description copied from interface: Spatial
        rebuild the data structure
        Specified by:
        recalculate in interface Spatial<V,​V>

      • clear

        public void clear()
        Description copied from interface: Spatial
        destroy the current spatial structure
        Specified by:
        clear in interface Spatial<V,​V>

      • recalculate

        public void recalculate​(Collection<V> vertices)
        Recalculate the contents of the Map of box number to contained Vertices
        Parameters:
        vertices - the collection of vertices to update in the structure

      • update

        public void update​(V vertex,
                   Point location)
        update the location of a vertex in the map of box number to vertex lists
        Specified by:
        update in interface Spatial<V,​V>
        Parameters:
        vertex - the vertex to update in the structure
        location - the location of the element

      • getClosestElement

        public V getClosestElement​(Point2D p)
        Specified by:
        getClosestElement in interface Spatial<V,​V>
        Parameters:
        p - a point to search in the spatial structure
        Returns:
        the closest element to the passed point

      • getClosestElement

        public V getClosestElement​(double x,
                           double y)
        Specified by:
        getClosestElement in interface Spatial<V,​V>
        Parameters:
        x - coordinate of a point to search in the spatial structure
        y - coordinate of a point to search in the spatial structure
        Returns:
        the closest element to the passed coordinates

      • getVisibleTiles

        protected Collection<Integer> getVisibleTiles​(Shape visibleArea)
        given a rectangular area and an offset, return the tile numbers that are contained in it
        Parameters:
        visibleArea - the (possibly) non-rectangular area of interest
        Returns:
        the tile numbers that intersect with the visibleArea

      • getVisibleElements

        public Set<V> getVisibleElements​(Shape visibleArea)
        Given an area, return a collection of the vertices that are contained in it (the vertices that are contained in the boxes that intersect with the area)
        Specified by:
        getVisibleElements in interface Spatial<V,​V>
        Parameters:
        visibleArea - a shape projected on the grid
        Returns:
        the vertices that should be visible