OTS2DSet.java

  1. package org.opentrafficsim.core.geometry;

  2. import java.awt.geom.Rectangle2D;
  3. import java.util.Collection;
  4. import java.util.HashSet;
  5. import java.util.Iterator;
  6. import java.util.Set;

  7. import com.vividsolutions.jts.geom.Envelope;

  8. import nl.tudelft.simulation.language.Throw;

  9. /**
  10.  * Set of OTSShape objects and provides methods for fast selection of those objects that intersect an OTSShape. <br>
  11.  * An OTS2DSet internally stores the OTSShapes in a quad tree. At time of construction the minimum cell size is defined. Node
  12.  * expansion is never performed on nodes that are smaller than this limit. <br>
  13.  * Each node (even the non-leaf nodes) store a set of OTSShape. Non-leaf nodes locally store those shapes that completely cover
  14.  * the rectangular area of the node. Such shapes are <b>not</b> also stored in leaf nodes below that node. OTSShapes that
  15.  * partially cover a non-leaf node are stored in each of the leaf nodes below that node that those OTSShapes (partially) cover.
  16.  * Leaf nodes that cannot be expanded (because they are too small) also store all OTSShapes that partially cover the area of the
  17.  * node. <br>
  18.  * If removal of an OTSShape objects results in a leaf becoming empty, that leaf is removed from its parent (which may then
  19.  * itself become empty and removed in turn).
  20.  * <p>
  21.  * Copyright (c) 2013-2016 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
  22.  * BSD-style license. See <a href="http://opentrafficsim.org/docs/current/license.html">OpenTrafficSim License</a>.
  23.  * <p>
  24.  * @version $Revision$, $LastChangedDate$, by $Author$, initial version Jun 20, 2016 <br>
  25.  * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
  26.  * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
  27.  * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
  28.  */
  29. public class OTS2DSet implements Set<OTSShape>
  30. {
  31.     /** Set of all shapes used for iterators, etc. */
  32.     private final Set<OTSShape> allShapes = new HashSet<OTSShape>();

  33.     /** How fine will this quad tree divide. This one is copied to each sub-node which is somewhat inefficient. */
  34.     private final double minimumCellSize;

  35.     /** Spatial storage for the OTSShapes. */
  36.     private QuadTreeNode quadTree;

  37.     /**
  38.      * Construct an empty OTS2DSet for a rectangular region. Objects that do not intersect this region will never be stored in
  39.      * this OTS2DSet. (Trying to add such an OTSShape is <b>not</b> an error; the <code>add</code> method will return false,
  40.      * indicating that the set has not been modified.)
  41.      * @param boundingBox Rectangle2D; the region
  42.      * @param minimumCellSize double; resolution of the underlying quad tree
  43.      * @throws OTSGeometryException when the bounding box covers no surface
  44.      */
  45.     public OTS2DSet(final Rectangle2D boundingBox, final double minimumCellSize) throws OTSGeometryException
  46.     {
  47.         Throw.when(null == boundingBox, NullPointerException.class, "The boundingBox may not be null");
  48.         Throw.when(boundingBox.getWidth() <= 0 || boundingBox.getHeight() <= 0, OTSGeometryException.class,
  49.                 "The boundingBox must have nonzero surface (got %s", boundingBox);
  50.         Throw.when(minimumCellSize <= 0, OTSGeometryException.class, "The minimumCellSize must be > 0 (got %f)",
  51.                 minimumCellSize);
  52.         this.quadTree = new QuadTreeNode(boundingBox);
  53.         this.minimumCellSize = minimumCellSize;
  54.     }

  55.     /** {@inheritDoc} */
  56.     @Override
  57.     public final int size()
  58.     {
  59.         return this.allShapes.size();
  60.     }

  61.     /** {@inheritDoc} */
  62.     @Override
  63.     public final boolean isEmpty()
  64.     {
  65.         return this.allShapes.isEmpty();
  66.     }

  67.     /** {@inheritDoc} */
  68.     @Override
  69.     public final boolean contains(final Object o)
  70.     {
  71.         return this.allShapes.contains(o);
  72.     }

  73.     /** {@inheritDoc} */
  74.     @Override
  75.     public final Iterator<OTSShape> iterator()
  76.     {
  77.         return new QuadTreeIterator();
  78.     }

  79.     /** {@inheritDoc} */
  80.     @Override
  81.     public final Object[] toArray()
  82.     {
  83.         return this.allShapes.toArray();
  84.     }

  85.     /** {@inheritDoc} */
  86.     @Override
  87.     public final <T> T[] toArray(final T[] a)
  88.     {
  89.         return this.allShapes.toArray(a);
  90.     }

  91.     /** {@inheritDoc} */
  92.     @Override
  93.     public final boolean add(final OTSShape e)
  94.     {
  95.         if (!this.quadTree.intersects(e))
  96.         {
  97.             return false;
  98.         }
  99.         if (this.allShapes.contains(e))
  100.         {
  101.             return false;
  102.         }
  103.         if (!this.quadTree.add(e))
  104.         {
  105.             System.err.println("add: ERROR object could not be added to the quad tree");
  106.         }
  107.         return this.allShapes.add(e);
  108.     }

  109.     /** {@inheritDoc} */
  110.     @Override
  111.     public final boolean remove(final Object o)
  112.     {
  113.         if (!this.allShapes.remove(o))
  114.         {
  115.             return false;
  116.         }
  117.         if (!this.quadTree.remove((OTSShape) o))
  118.         {
  119.             System.err.println("remove: ERROR object could not be removed from the quad tree");
  120.         }
  121.         return true;
  122.     }

  123.     /** {@inheritDoc} */
  124.     @Override
  125.     public final boolean containsAll(final Collection<?> c)
  126.     {
  127.         for (Object o : c)
  128.         {
  129.             if (!contains(o))
  130.             {
  131.                 return false;
  132.             }
  133.         }
  134.         return true;
  135.     }

  136.     /** {@inheritDoc} */
  137.     @Override
  138.     public final boolean addAll(final Collection<? extends OTSShape> c)
  139.     {
  140.         boolean result = false;
  141.         for (OTSShape s : c)
  142.         {
  143.             if (add(s))
  144.             {
  145.                 result = true;
  146.             }
  147.         }
  148.         return result;
  149.     }

  150.     /** {@inheritDoc} */
  151.     @Override
  152.     public final boolean retainAll(final Collection<?> c)
  153.     {
  154.         boolean result = false;
  155.         for (Iterator<OTSShape> it = iterator(); it.hasNext();)
  156.         {
  157.             OTSShape shape = it.next();
  158.             if (!c.contains(shape))
  159.             {
  160.                 it.remove();
  161.                 result = true;
  162.             }
  163.         }
  164.         return result;
  165.     }

  166.     /** {@inheritDoc} */
  167.     @Override
  168.     public final boolean removeAll(final Collection<?> c)
  169.     {
  170.         boolean result = false;
  171.         for (Iterator<OTSShape> it = iterator(); it.hasNext();)
  172.         {
  173.             OTSShape shape = it.next();
  174.             if (c.contains(shape))
  175.             {
  176.                 it.remove();
  177.                 result = true;
  178.             }
  179.         }
  180.         return result;
  181.     }

  182.     /** {@inheritDoc} */
  183.     @Override
  184.     public final void clear()
  185.     {
  186.         this.quadTree.clear();
  187.         this.allShapes.clear();
  188.     }

  189.     /**
  190.      * Return the set of all shapes in this OTS2DSet that intersect the given rectangle.
  191.      * @param rectangle Rectangle2D; the rectangle
  192.      * @return Set&lt;OTSShape&gt;; the shapes that intersect the rectangle
  193.      */
  194.     public final Set<OTSShape> intersectingShapes(final Rectangle2D rectangle)
  195.     {
  196.         return this.quadTree.intersectingShapes(rectangle);
  197.     }

  198.     /**
  199.      * Recursively print this OTS2DSet.
  200.      * @param recursionDepth int; maximum depth to recurse
  201.      * @return String
  202.      */
  203.     final String toString(final int recursionDepth)
  204.     {
  205.         return "OTS2DSet [contains " + size() + (1 == this.allShapes.size() ? "shape" : "shapes") + ", minimumCellSize="
  206.                 + this.minimumCellSize + ", quadTree=" + this.quadTree.toString(recursionDepth) + "]";
  207.     }

  208.     /** {@inheritDoc} */
  209.     @Override
  210.     public final String toString()
  211.     {
  212.         return toString(0);
  213.     }

  214.     /**
  215.      * Return all OTSShapes in this OTS2DSet that intersect a given OTSShape.
  216.      * @param shape OTSShape; the given OTSShape
  217.      * @return Set&lt;OTSShape&gt;; all OTSShapes in this OTS2DSet that intersect <code>shape</code>
  218.      */
  219.     public final Set<OTSShape> intersectingShapes(final OTSShape shape)
  220.     {
  221.         Envelope envelope = shape.getEnvelope();
  222.         Set<OTSShape> result =
  223.                 intersectingShapes(new Rectangle2D.Double(envelope.getMinX(), envelope.getMinY(), envelope.getWidth(),
  224.                         envelope.getHeight()));
  225.         for (Iterator<OTSShape> it = result.iterator(); it.hasNext();)
  226.         {
  227.             if (!it.next().intersects(shape))
  228.             {
  229.                 it.remove();
  230.             }
  231.         }
  232.         return result;
  233.     }

  234.     /**
  235.      * Return an ASCII art rendering of this OTS2DSet.
  236.      * @param recursionDepth int; maximum recursion depth
  237.      * @return String; a somewhat human readable rendering of this OTS2DSet
  238.      */
  239.     public final String toStringGraphic(final int recursionDepth)
  240.     {
  241.         return this.quadTree.toStringGraphic(recursionDepth);
  242.     }

  243.     /**
  244.      * Iterator for quad tree. Shall iterate over the local set of shapes and the (up to four) non-null leave nodes.
  245.      */
  246.     class QuadTreeIterator implements Iterator<OTSShape>
  247.     {
  248.         /** Underlying iterator that traverses the allShapes Set. */
  249.         @SuppressWarnings("synthetic-access")
  250.         private final Iterator<OTSShape> theIterator = OTS2DSet.this.allShapes.iterator();

  251.         /** Remember the last returned result so we can remove it when requested. */
  252.         private OTSShape lastResult = null;

  253.         /** {@inheritDoc} */
  254.         @Override
  255.         public final boolean hasNext()
  256.         {
  257.             return this.theIterator.hasNext();
  258.         }

  259.         /** {@inheritDoc} */
  260.         @Override
  261.         public final OTSShape next()
  262.         {
  263.             this.lastResult = this.theIterator.next();
  264.             return this.lastResult;
  265.         }

  266.         /** {@inheritDoc} */
  267.         @SuppressWarnings("synthetic-access")
  268.         @Override
  269.         public final void remove()
  270.         {
  271.             this.theIterator.remove();
  272.             if (!OTS2DSet.this.quadTree.remove(this.lastResult))
  273.             {
  274.                 System.err.println("iterator.remove: ERROR: could not remove " + this.lastResult + " from the quad tree");
  275.             }
  276.         }

  277.         /** {@inheritDoc} */
  278.         @Override
  279.         public String toString()
  280.         {
  281.             return "QuadTreeIterator [theIterator=" + this.theIterator + ", lastResult=" + this.lastResult + "]";
  282.         }

  283.     }

  284.     /**
  285.      * Spatial-aware storage for a set of OTSShape objects.
  286.      */
  287.     class QuadTreeNode
  288.     {
  289.         /** The OTSShapes stored at this node. */
  290.         private Set<OTSShape> shapes = new HashSet<OTSShape>();

  291.         /** The bounding box of this QuadTreeNode. */
  292.         private final Rectangle2D boundingBox;

  293.         /** The bounding box of this QuadTreeNode as an OTSShape. */
  294.         private final OTSShape boundingShape;

  295.         /**
  296.          * The four leaves of this node in the quad tree. An empty sub tree may be represented by null. If this field is
  297.          * initialized to null; this node may not expand by adding sub-nodes.
  298.          */
  299.         private final QuadTreeNode[] leaves;

  300.         /**
  301.          * Construct a new QuadTreeNode.
  302.          * @param boundingBox Rectangle2D; the bounding box of the area of the new QuadTreeNode
  303.          */
  304.         @SuppressWarnings("synthetic-access")
  305.         QuadTreeNode(final Rectangle2D boundingBox)
  306.         {
  307.             this.boundingBox = boundingBox;
  308.             this.boundingShape = rectangleShape(boundingBox);
  309.             this.leaves =
  310.                     boundingBox.getWidth() > OTS2DSet.this.minimumCellSize
  311.                             || boundingBox.getHeight() > OTS2DSet.this.minimumCellSize ? new QuadTreeNode[4] : null;
  312.         }

  313.         /**
  314.          * Return a Set containing all OTSShapes in this QuadTreeNode that intersect a rectangular area.
  315.          * @param rectangle Rectangle2D; the area
  316.          * @return Set&lt;OTSShape&gt;; the set
  317.          */
  318.         public Set<OTSShape> intersectingShapes(final Rectangle2D rectangle)
  319.         {
  320.             Set<OTSShape> result = new HashSet<OTSShape>();
  321.             if (!this.boundingBox.intersects(rectangle))
  322.             {
  323.                 return result;
  324.             }
  325.             if (null == this.leaves)
  326.             {
  327.                 return result;
  328.             }
  329.             for (QuadTreeNode leaf : this.leaves)
  330.             {
  331.                 if (null != leaf && leaf.intersects(rectangle))
  332.                 {
  333.                     result.addAll(leaf.intersectingShapes(rectangle));
  334.                 }
  335.             }
  336.             for (OTSShape shape : this.shapes)
  337.             {
  338.                 OTSShape rectangleShape = rectangleShape(rectangle);
  339.                 if (rectangleShape.intersects(shape))
  340.                 {
  341.                     result.add(shape);
  342.                 }
  343.             }
  344.             return result;
  345.         }

  346.         /**
  347.          * Test if this QuadTreeNode intersects a rectangular area.
  348.          * @param rectangle Rectangle2D; the rectangular area
  349.          * @return boolean; true if the rectangular area intersects this QuadTreeNode; false otherwise
  350.          */
  351.         private boolean intersects(final Rectangle2D rectangle)
  352.         {
  353.             return this.boundingBox.intersects(rectangle);
  354.         }

  355.         /**
  356.          * Remove all OTSShapes from this QuadTreeNode and cut off all leaves.
  357.          */
  358.         public void clear()
  359.         {
  360.             this.shapes.clear();
  361.             for (int index = 0; index < this.leaves.length; index++)
  362.             {
  363.                 this.leaves[index] = null;
  364.             }
  365.         }

  366.         /**
  367.          * Remove an OTSShape from this QuadTreeNode.
  368.          * @param shape OTSShape; the shape that must be removed.
  369.          * @return boolean; true if this node (or a sub-node) was altered; false otherwise
  370.          */
  371.         public boolean remove(final OTSShape shape)
  372.         {
  373.             if (!this.boundingShape.intersects(shape))
  374.             {
  375.                 return false;
  376.             }
  377.             for (OTSShape s : this.shapes)
  378.             {
  379.                 if (shape.equals(s))
  380.                 {
  381.                     this.shapes.remove(shape);
  382.                     return true;
  383.                 }
  384.             }
  385.             boolean result = false;
  386.             for (int index = 0; index < this.leaves.length; index++)
  387.             {
  388.                 QuadTreeNode qtn = this.leaves[index];
  389.                 if (null != qtn)
  390.                 {
  391.                     if (qtn.remove(shape))
  392.                     {
  393.                         result = true;
  394.                         if (qtn.isEmpty())
  395.                         {
  396.                             this.leaves[index] = null; // Cut off empty leaf node
  397.                         }
  398.                     }
  399.                 }
  400.             }
  401.             return result;
  402.         }

  403.         /**
  404.          * Check if this QuadTreeNode is empty.
  405.          * @return boolean; true if this QuadTreeNode is empty
  406.          */
  407.         private boolean isEmpty()
  408.         {
  409.             if (!this.shapes.isEmpty())
  410.             {
  411.                 return false;
  412.             }
  413.             if (null == this.leaves)
  414.             {
  415.                 return true;
  416.             }
  417.             for (QuadTreeNode qtn : this.leaves)
  418.             {
  419.                 if (null != qtn)
  420.                 {
  421.                     return false;
  422.                 }
  423.             }
  424.             return true;
  425.         }

  426.         /**
  427.          * Test if the area of this QuadTree intersects an OTSShape.
  428.          * @param shape OTSShape; the shape
  429.          * @return boolean; true if the area of this QuadTree intersects the shape; false otherwise
  430.          */
  431.         public boolean intersects(final OTSShape shape)
  432.         {
  433.             return this.boundingShape.intersects(shape);
  434.         }

  435.         /**
  436.          * Construct a OTSShape from a Rectangle2D.
  437.          * @param rectangle Rectangle3D; the rectangle
  438.          * @return OTSShape; a new OTSShape
  439.          */
  440.         private OTSShape rectangleShape(final Rectangle2D rectangle)
  441.         {
  442.             double left = rectangle.getMinX();
  443.             double bottom = rectangle.getMinY();
  444.             double right = rectangle.getMaxX();
  445.             double top = rectangle.getMaxY();
  446.             try
  447.             {
  448.                 return new OTSShape(new OTSPoint3D(left, bottom), new OTSPoint3D(right, bottom), new OTSPoint3D(right, top),
  449.                         new OTSPoint3D(left, top));
  450.             }
  451.             catch (OTSGeometryException exception)
  452.             {
  453.                 exception.printStackTrace();
  454.                 return null;
  455.             }
  456.         }

  457.         /**
  458.          * Add an OTSShape to this QuadTreeNode.
  459.          * @param shape OTSShape; the shape
  460.          * @return boolean; true if this QuadTreeNode changed as a result of this operation
  461.          */
  462.         public final boolean add(final OTSShape shape)
  463.         {
  464.             if (!this.boundingShape.intersects(shape))
  465.             {
  466.                 return false;
  467.             }
  468.             if ((null == this.leaves) || shape.contains(this.boundingBox))
  469.             {
  470.                 // shape belongs in the set of shapes of this node.
  471.                 return this.shapes.add(shape);
  472.             }
  473.             // This node may have leaves and shape does not entirely contain this node. Add shape to all applicable leaves.
  474.             boolean result = false;
  475.             for (int index = 0; index < this.leaves.length; index++)
  476.             {
  477.                 if (null == this.leaves[index])
  478.                 {
  479.                     double subWidth = this.boundingBox.getWidth() / 2;
  480.                     double subHeight = this.boundingBox.getHeight() / 2;
  481.                     if (0 == subWidth)
  482.                     {
  483.                         // loss of precision; degenerate into a binary tree
  484.                         subWidth = this.boundingBox.getWidth();
  485.                     }
  486.                     if (0 == subHeight)
  487.                     {
  488.                         // loss of precision; degenerate into a binary tree
  489.                         subHeight = this.boundingBox.getHeight();
  490.                     }
  491.                     double left = this.boundingBox.getMinX();
  492.                     if (0 != index / 2)
  493.                     {
  494.                         left += subWidth;
  495.                     }
  496.                     double bottom = this.boundingBox.getMinY();
  497.                     if (0 != index % 2)
  498.                     {
  499.                         bottom += subHeight;
  500.                     }
  501.                     Rectangle2D subBox = new Rectangle2D.Double(left, bottom, subWidth, subHeight);
  502.                     if (rectangleShape(subBox).intersects(shape))
  503.                     {
  504.                         // Expand this node by adding a sub node.
  505.                         this.leaves[index] = new QuadTreeNode(subBox);
  506.                         if (this.leaves[index].add(shape))
  507.                         {
  508.                             result = true;
  509.                         }
  510.                         else
  511.                         {
  512.                             throw new Error("Cannot happen: new QuadTreeNode refused to add shape that intersects it");
  513.                         }
  514.                     }
  515.                 }
  516.                 else
  517.                 {
  518.                     // Leaf node already exists. Let the leaf determine if shape should be stored (somewhere) in it.
  519.                     if (this.leaves[index].add(shape))
  520.                     {
  521.                         result = true;
  522.                     }
  523.                 }
  524.             }
  525.             return result;
  526.         }

  527.         /**
  528.          * Helper function for toString.
  529.          * @param recursionDepth int; maximum number of levels to print recursively
  530.          * @param index int; index in leaves
  531.          * @return String
  532.          */
  533.         private String printLeaf(final int recursionDepth, final int index)
  534.         {
  535.             QuadTreeNode leaf = this.leaves[index];
  536.             if (null == leaf)
  537.             {
  538.                 return "null";
  539.             }
  540.             if (recursionDepth > 0)
  541.             {
  542.                 return leaf.toString(recursionDepth - 1);
  543.             }
  544.             int leafSize = leaf.shapes.size();
  545.             return leafSize + " shape" + (1 == leafSize ? "" : "s");
  546.         }

  547.         /**
  548.          * Recursively print this QuadTreeNode.
  549.          * @param recursionDepth int; maximum depth to recurse
  550.          * @return String
  551.          */
  552.         final String toString(final int recursionDepth)
  553.         {
  554.             return "QuadTreeNode [" + this.shapes.size() + ", bounds=[LB: " + this.boundingBox.getMinX() + ","
  555.                     + this.boundingBox.getMinY() + ", RT: " + this.boundingBox.getMaxX() + "," + this.boundingBox.getMaxY()
  556.                     + "], " + subNodes(recursionDepth) + ", local " + this.shapes.size()
  557.                     + (1 == this.shapes.size() ? " shape" : " shapes") + "]";
  558.         }

  559.         /**
  560.          * Print the leaves of this QuadTreeNode.
  561.          * @param recursionDepth int; maximum depth to recurse
  562.          * @return String
  563.          */
  564.         private String subNodes(final int recursionDepth)
  565.         {
  566.             if (null == this.leaves)
  567.             {
  568.                 return "cannot have leaves";
  569.             }
  570.             return "leaves=[LB: " + printLeaf(recursionDepth, 0) + ", RB: " + printLeaf(recursionDepth, 1) + ", LT: "
  571.                     + printLeaf(recursionDepth, 2) + ", RT: " + printLeaf(recursionDepth, 3) + "]";
  572.         }

  573.         /** {@inheritDoc} */
  574.         @Override
  575.         public final String toString()
  576.         {
  577.             return toString(0);
  578.         }

  579.         /**
  580.          * Return concatenation of a number of copies of a string.
  581.          * @param count int; number of copies to concatenate
  582.          * @param string String; the string to repeat
  583.          * @return String
  584.          */
  585.         private String repeat(final int count, final String string)
  586.         {
  587.             StringBuilder result = new StringBuilder();
  588.             for (int i = 0; i < count; i++)
  589.             {
  590.                 result.append(string);
  591.             }
  592.             return result.toString();
  593.         }

  594.         /** Graphic to draw a vertical line. */
  595.         private static final String VLINE = "|";

  596.         /** Graphic to draw a horizontal line. */
  597.         private static final String HLINE = "-";

  598.         /** Graphic to draw a space. */
  599.         private static final String SPACE = " ";

  600.         /** Number of digits to print. */
  601.         private static final int NUMBERSIZE = 6;

  602.         /**
  603.          * Similar to toStringGraphic, but with QuadTreeNode argument which can be null. <br>
  604.          * This code is <b>not</b> optimized for performance; the repeated use of String.split is probably expensive.
  605.          * @param qtn QuadTreeNode; the QuadTreeNode to render. Can be null.
  606.          * @param recursionDepth int; levels to recurse
  607.          * @return String
  608.          */
  609.         private String subStringGraphic(final QuadTreeNode qtn, final int recursionDepth)
  610.         {
  611.             StringBuffer result = new StringBuffer();
  612.             if (0 == recursionDepth)
  613.             {
  614.                 if (null == qtn)
  615.                 {
  616.                     result.append(repeat(NUMBERSIZE, SPACE));
  617.                 }
  618.                 else
  619.                 {
  620.                     String numberBuf = String.format("%d", size());
  621.                     int spare = NUMBERSIZE - numberBuf.length();
  622.                     int filled = 0;
  623.                     while (filled < spare / 2)
  624.                     {
  625.                         result.append(SPACE);
  626.                         filled++;
  627.                     }
  628.                     result.append(numberBuf);
  629.                     while (filled < spare)
  630.                     {
  631.                         result.append(SPACE);
  632.                         filled++;
  633.                     }
  634.                     result.append("\n");
  635.                     return result.toString();
  636.                 }
  637.             }
  638.             else
  639.             {
  640.                 String[] left =
  641.                         subStringGraphic(null == qtn || null == qtn.leaves ? null : qtn.leaves[1], recursionDepth - 1).split(
  642.                                 "\\n");
  643.                 String[] right =
  644.                         subStringGraphic(null == qtn || null == qtn.leaves ? null : qtn.leaves[3], recursionDepth - 1).split(
  645.                                 "\\n");
  646.                 String horizontalLine = null;
  647.                 for (int i = 0; i < left.length; i++)
  648.                 {
  649.                     if (0 == i)
  650.                     {
  651.                         StringBuilder line = new StringBuilder();
  652.                         int width = left[0].length() + 1 + right[0].length();
  653.                         if (null == qtn)
  654.                         {
  655.                             line.append(repeat(width, SPACE));
  656.                         }
  657.                         else
  658.                         {
  659.                             String numberBuf = String.format("%d", qtn.shapes.size());
  660.                             int spare = width - numberBuf.length();
  661.                             line.append(repeat(spare / 2, HLINE));
  662.                             line.append(numberBuf);
  663.                             line.append(repeat(spare - spare / 2, HLINE));
  664.                         }
  665.                         horizontalLine = line.toString();
  666.                     }
  667.                     result.append(left[i]);
  668.                     result.append(null == qtn ? SPACE : VLINE);
  669.                     result.append(right[i]);
  670.                     result.append("\n");
  671.                 }
  672.                 result.append(horizontalLine);
  673.                 result.append("\n");
  674.                 left =
  675.                         subStringGraphic(null == qtn || null == qtn.leaves ? null : qtn.leaves[0], recursionDepth - 1).split(
  676.                                 "\\n");
  677.                 right =
  678.                         subStringGraphic(null == qtn || null == qtn.leaves ? null : qtn.leaves[2], recursionDepth - 1).split(
  679.                                 "\\n");
  680.                 for (int i = 0; i < left.length; i++)
  681.                 {
  682.                     result.append(left[i]);
  683.                     result.append(null == qtn ? SPACE : VLINE);
  684.                     result.append(right[i]);
  685.                     result.append("\n");
  686.                 }
  687.                 result.append("\n");
  688.             }
  689.             return result.toString();
  690.         }

  691.         /**
  692.          * Return a String depicting this QuadTreeNode.
  693.          * @param recursionDepth int; levels to recurse
  694.          * @return String
  695.          */
  696.         public final String toStringGraphic(final int recursionDepth)
  697.         {
  698.             return subStringGraphic(this, recursionDepth);
  699.         }

  700.     }

  701. }