/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.geometry.examples.tutorials.bsp;
  
  import java.io.File;
  import java.util.Deque;
  import java.util.HashMap;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  
  import javax.xml.parsers.DocumentBuilder;
  import javax.xml.parsers.DocumentBuilderFactory;
  import javax.xml.parsers.ParserConfigurationException;
  import javax.xml.transform.OutputKeys;
  import javax.xml.transform.Transformer;
  import javax.xml.transform.TransformerException;
  import javax.xml.transform.TransformerFactory;
  import javax.xml.transform.dom.DOMSource;
  import javax.xml.transform.stream.StreamResult;
  
  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
  import org.apache.commons.geometry.euclidean.twod.AffineTransformMatrix2D;
  import org.apache.commons.geometry.euclidean.twod.Bounds2D;
  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
  import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.RegionNode2D;
  import org.apache.commons.geometry.euclidean.twod.Vector2D;
  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
  import org.apache.commons.numbers.core.Precision;
  import org.w3c.dom.Document;
  import org.w3c.dom.Element;
  
  /** Class for writing SVG visualizations of 2D BSP trees.
   */
  public class BSPTreeSVGWriter {
  
      /** SVG XML namespace. */
      private static final String SVG_NAMESPACE = "http://www.w3.org/2000/svg";
  
      /** SVG version. */
      private static final String SVG_VERSION = "1.1";
  
      /** Property key used to set the indent level of the output xml. */
      private static final String INDENT_AMOUNT_KEY = "{http://xml.apache.org/xslt}indent-amount";
  
      /** Indent amount for the output xml. */
      private static final int INDENT_AMOUNT = 4;
  
      /** String containing default node name characters. */
      private static final String DEFAULT_NODE_NAMES = "abcdefghijklmnopqrstuvwxyz";
  
      /** Id used for the geometry area clip path. */
      private static final String GEOMETRY_AREA_CLIP_PATH_ID = "geometry-area";
  
      /** Path string command to move to a point. */
      private static final char PATH_MOVE_TO = 'M';
  
      /** Path string command to draw a line to a point. */
      private static final char PATH_LINE_TO = 'L';
  
      /** Space character. */
      private static final char SPACE = ' ';
  
      /** Name of the SVG "rect" element. */
      private static final String RECT_ELEMENT = "rect";
  
      /** Name of the SVG "path" element. */
      private static final String PATH_ELEMENT = "path";
  
      /** Name of the "class" attribute. */
      private static final String CLASS_ATTR = "class";
  
      /** Name of the "width" attribute. */
      private static final String WIDTH_ATTR = "width";
  
      /** Name of the "height" attribute. */
      private static final String HEIGHT_ATTR = "height";
  
      /** Name of the "x" attribute. */
      private static final String X_ATTR = "x";
 
     /** Name of the "y" attribute. */
     private static final String Y_ATTR = "y";
 
     /** CSS style string for the generated SVG. */
     private static final String STYLE =
         "text { font-size: 14px; } " +
         ".node-name { text-anchor: middle; font-family: \"Courier New\", Courier, monospace; } " +
         ".geometry-border { fill: none; stroke: gray; stroke-width: 1; } " +
         ".arrow { fill: none; stroke: blue; stroke-width: 1; } " +
         ".cut { fill: none; stroke: blue; stroke-width: 1; stroke-dasharray: 5,3; } " +
         ".region-boundary { stroke: orange; stroke-width: 2; } " +
         ".inside { fill: #aaa; opacity: 0.2; } " +
         ".tree-path { fill: none; stroke: gray; stroke-width: 1; } " +
         ".inside-node { font-weight: bold; }";
 
     /** The width of the SVG. */
     private static final int WIDTH = 750;
 
     /** The height of the SVG. */
     private static final int HEIGHT = 375;
 
     /** The margin used in the SVG. */
     private static final int MARGIN = 5;
 
     /** Amount of the overall width of the SVG to use for the geometry area. */
     private static final double GEOMETRY_AREA_WIDTH_FACTOR = 0.5;
 
     /** Amount of the overall width of the SVG to use for the tree structure area. */
     private static final double TREE_AREA_WIDTH_FACTOR = 1.0 - GEOMETRY_AREA_WIDTH_FACTOR;
 
     /** Angle that arrow heads on lines make with the direction of the line. */
     private static final double ARROW_ANGLE = 0.8 * Math.PI;
 
     /** Length of arrow head lines. */
     private static final double ARROW_LENGTH = 8;
 
     /** Distance between levels of the tree in the tree structure display. */
     private static final double TREE_VERTICAL_SPACING = 45;
 
     /** Line end margin used in the lines between nodes in the tree structure display. */
     private static final double TREE_LINE_MARGIN = 10;
 
     /** Precision context used for floating point comparisons. */
     private static final Precision.DoubleEquivalence PRECISION = Precision.doubleEquivalenceOfEpsilon(1e-6);
 
     /** Geometry bounds; only geometry within these bounds is rendered. */
     private final Bounds2D bounds;
 
     /** Factor determining how much of the available horizontal width for a node should be used to
      * offset it from its parent.
      */
     private double treeParentOffsetFactor = 0.25;
 
     /** Minimum horizontal offset for tree nodes from their parents. */
     private double treeParentXOffsetMin = 0;
 
     /** Construct a new instance that will render regions within the given bounds.
      * @param bounds bounds used to determine what output
      */
     public BSPTreeSVGWriter(final Bounds2D bounds) {
         this.bounds = bounds;
     }
 
     /** Set the offset factor determining how much of the available horizontal width for
      * a node should be used to offset it from its parent.
      * @param treeParentOffsetFactor offset factor
      */
     public void setTreeParentOffsetFactor(final double treeParentOffsetFactor) {
         this.treeParentOffsetFactor = treeParentOffsetFactor;
     }
 
     /** Set the minimum horizontal offset for tree nodes from their parents.
      * @param treeParentXOffsetMin minimum offset
      */
     public void setTreeParentXOffsetMin(final double treeParentXOffsetMin) {
         this.treeParentXOffsetMin = treeParentXOffsetMin;
     }
 
     /** Write an SVG visualization of the given BSP tree. Default names are assigned to the tree nodes.
      * @param tree tree to output
      * @param file path of the svg file to write
      */
     public void write(final RegionBSPTree2D tree, final File file) {
         final Deque<RegionNode2D> nodeQueue = new LinkedList<>();
         nodeQueue.add(tree.getRoot());
 
         final Map<RegionNode2D, String> nodeNames = new HashMap<>();
 
         final String names = DEFAULT_NODE_NAMES;
         RegionNode2D node;
         for (int i = 0; i < names.length() && !nodeQueue.isEmpty(); ++i) {
             node = nodeQueue.removeFirst();
 
             nodeNames.put(node, names.substring(i, i + 1));
 
             if (node.isInternal()) {
                 nodeQueue.add(node.getMinus());
                 nodeQueue.add(node.getPlus());
             }
         }
 
         write(tree, nodeNames, file);
     }
 
     /** Write an SVG visualization of the given BSP tree.
      * @param tree tree to output
      * @param nodeNames map of node instances to the names that should be used for them in the svg
      * @param file path of the svg file to write
      */
     public void write(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames, final File file) {
         try {
             final DocumentBuilderFactory docBuilderFactory = DocumentBuilderFactory.newInstance();
             final DocumentBuilder docBuilder = docBuilderFactory.newDocumentBuilder();
 
             final Document doc = docBuilder.newDocument();
 
             // create the svg element
             final Element root = svgElement("svg", doc);
             doc.appendChild(root);
 
             root.setAttribute("version", SVG_VERSION);
             root.setAttribute(WIDTH_ATTR, String.valueOf(WIDTH));
             root.setAttribute(HEIGHT_ATTR, String.valueOf(HEIGHT));
 
             // add a defs element for later use
             final Element defs = svgElement("defs", doc);
             root.appendChild(defs);
 
             // add a style element
             final Element style = svgElement("style", doc);
             root.appendChild(style);
             style.setTextContent(STYLE);
 
             // write the tree
             writeTreeGeometryArea(tree, nodeNames, root, defs, doc);
             writeTreeStructureArea(tree, nodeNames, root, doc);
 
             // output to the target file
             final TransformerFactory transformerFactory = TransformerFactory.newInstance();
             final Transformer transformer = transformerFactory.newTransformer();
             transformer.setOutputProperty(OutputKeys.INDENT, "yes");
             transformer.setOutputProperty(INDENT_AMOUNT_KEY, String.valueOf(INDENT_AMOUNT));
 
             final DOMSource source = new DOMSource(doc);
             final StreamResult target = new StreamResult(file);
 
             transformer.transform(source, target);
 
         } catch (final ParserConfigurationException | TransformerException e) {
             // throw as a runtime exception for convenience
             throw new RuntimeException("Failed to create SVG", e);
         }
     }
 
     /** Write the svg area containing the visual representation of the tree geometry.
      * @param tree tree to write
      * @param nodeNames map of nodes to the names that should be used to identify them
      * @param root root svg element
      * @param defs svg defs element
      * @param doc xml document
      */
     private void writeTreeGeometryArea(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames,
             final Element root, final Element defs, final Document doc) {
         final double geometrySvgX = MARGIN;
         final double geometrySvgY = MARGIN;
         final double geometrySvgWidth = (GEOMETRY_AREA_WIDTH_FACTOR * WIDTH) - (2 * MARGIN);
         final double geometrySvgHeight = HEIGHT - (2 * MARGIN);
 
         defineClipRect(GEOMETRY_AREA_CLIP_PATH_ID,
                 geometrySvgX, geometrySvgY,
                 geometrySvgWidth, geometrySvgHeight,
                 defs, doc);
 
         // create the box containing the 2D content
         final Element geometryGroup = svgElement("g", doc);
         root.appendChild(geometryGroup);
         geometryGroup.setAttribute(CLASS_ATTR, "geometry");
         geometryGroup.setAttribute("clip-path", "url(#" + GEOMETRY_AREA_CLIP_PATH_ID + ")");
 
         // set up the transform so we can write geometry elements with their natural coordinates
         final AffineTransformMatrix2D transform = computeGeometryTransform(bounds, geometrySvgX, geometrySvgY,
                 geometrySvgWidth, geometrySvgHeight);
 
         // add the tree geometry
         tree.accept(new TreeGeometryVisitor(transform, nodeNames, geometryGroup, doc));
 
         // create a box outlining the geometry area
         final Element border = svgElement(RECT_ELEMENT, doc);
         border.setAttribute(CLASS_ATTR, "geometry-border");
         floatAttr(border, X_ATTR, geometrySvgX);
         floatAttr(border, Y_ATTR, geometrySvgY);
         floatAttr(border, WIDTH_ATTR, geometrySvgWidth);
         floatAttr(border, HEIGHT_ATTR, geometrySvgHeight);
 
         root.appendChild(border);
 
     }
 
     /** Write the svg area containing the visual representation of the tree structure.
      * @param tree tree to write
      * @param nodeNames map of nodes to the names that should be used to identify them
      * @param root svg root element
      * @param doc xml document
      */
     private void writeTreeStructureArea(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames,
             final Element root, final Document doc) {
         final Element treeGroup = svgElement("g", doc);
         root.appendChild(treeGroup);
         treeGroup.setAttribute(CLASS_ATTR, "tree");
 
         final double offsetX = ((1 - TREE_AREA_WIDTH_FACTOR) * WIDTH) + MARGIN;
         final double offsetY = MARGIN;
 
         final double svgWidth = (TREE_AREA_WIDTH_FACTOR * WIDTH) - (2 * MARGIN);
         final double svgHeight = HEIGHT - (2 * MARGIN);
 
         treeGroup.setAttribute("transform", "translate(" + offsetX + " " + offsetY + ")");
 
         tree.accept(new TreeStructureVisitor(tree.height(), svgWidth, svgHeight, nodeNames, treeGroup, doc));
     }
 
     /** Compute the transform required to convert from the geometry coordinate system given in {@code bounds}
      * to the one defined by the given svg coordinates. The y-axis from the geometry is oriented to point
      * upwards in the svg.
      * @param bounds the bounds of the geometry
      * @param svgX x coordinate in the upper-left corner of the svg target box
      * @param svgY y coordinate in the upper-left corner of the svg target box
      * @param svgWidth width of the svg target box
      * @param svgHeight height of the svg target box
      * @return a transform converting from geometry space to svg space
      */
     private static AffineTransformMatrix2D computeGeometryTransform(final Bounds2D bounds,
             final double svgX, final double svgY, final double svgWidth, final double svgHeight) {
 
         final Vector2D boundsDiagonal = bounds.getDiagonal();
 
         return AffineTransformMatrix2D
             .createTranslation(bounds.getMin().negate())
             .scale(svgWidth / boundsDiagonal.getX(), -svgHeight / boundsDiagonal.getY())
             .translate(svgX, svgY + svgHeight);
     }
 
     /** Define an SVG clipping rectangle.
      * @param id id of the clipping rectangle to add
      * @param x x coordinate of the clipping rectangle
      * @param y y coordinate of the clipping rectangle
      * @param svgWidth width of the clipping rectangle
      * @param svgHeight height of the clipping rectangle
      * @param defs svg "defs" element
      * @param doc xml document
      */
     private void defineClipRect(final String id, final double x, final double y,
             final double svgWidth, final double svgHeight, final Element defs, final Document doc) {
 
         final Element clipPath = svgElement("clipPath", doc);
         clipPath.setAttribute("id", id);
 
         defs.appendChild(clipPath);
 
         final Element rect = svgElement(RECT_ELEMENT, doc);
         floatAttr(rect, X_ATTR, x);
         floatAttr(rect, Y_ATTR, y);
         floatAttr(rect, WIDTH_ATTR, svgWidth);
         floatAttr(rect, HEIGHT_ATTR, svgHeight);
 
         clipPath.appendChild(rect);
     }
 
     /** Convenience method for setting a floating-point attribute on an element.
      * @param element element to set the attribute on
      * @param name name of the attribute to set
      * @param value value of the attribute to set
      */
     private static void floatAttr(final Element element, final String name, final double value) {
         element.setAttribute(name, String.valueOf(value));
     }
 
     /** Convenience method for creating an element from the svg namespace.
      * @param name the name of the element
      * @param doc document to create the element in
      * @return the element from the svg namespace
      */
     private static Element svgElement(final String name, final Document doc) {
         return doc.createElementNS(SVG_NAMESPACE, name);
     }
 
     /** Base class for BSP tree visitors that output SVG content.
      */
     private abstract class AbstractSVGTreeVisitor implements BSPTreeVisitor<Vector2D, RegionNode2D> {
 
         /** Map of nodes to the names that should be used to identify them. */
         private final Map<RegionNode2D, String> nodeNames;
 
         /** Parent SVG element to append new elements to. */
         private final Element parent;
 
         /** Xml document. */
         private final Document doc;
 
         /** Number of nodes visited so far. */
         private int count = 0;
 
         /** Construct a new instance.
          * @param nodeNames map of nodes ot the names that should be used to identify them
          * @param parent parent SVG element
          * @param doc xml document
          */
         AbstractSVGTreeVisitor(final Map<RegionNode2D, String> nodeNames, final Element parent, final Document doc) {
             this.nodeNames = nodeNames;
             this.parent = parent;
             this.doc = doc;
         }
 
         /** {@inheritDoc} */
         @Override
         public Order visitOrder(final RegionNode2D internalNode) {
             return Order.NODE_MINUS_PLUS;
         }
 
         /** {@inheritDoc} */
         @Override
         public Result visit(final RegionNode2D node) {
             ++count;
 
             final String name = (nodeNames != null && nodeNames.containsKey(node)) ?
                     nodeNames.get(node) :
                     String.valueOf(count);
 
             visitNode(name, node);
 
             return Result.CONTINUE;
         }
 
         /** Create a new svg element with the given name and append it to the parent node.
          * @param name name of the element
          * @return the created element, already appended to the parent
          */
         protected Element createChild(final String name) {
             final Element child = createElement(name);
             parent.appendChild(child);
 
             return child;
         }
 
         /** Create an svg element with the given name. The element is <em>not</em> appended to the
          * parent node.
          * @param name name of the element
          * @return the created element
          */
         protected Element createElement(final String name) {
             return svgElement(name, doc);
         }
 
         /** Create an SVG text element containing the name of a tree node. The returned element is
          * <em>not</em> appended to the parent.
          * @param name name of the tree node
          * @param svgPt location to place the text
          * @return text element containing the given node name
          */
         protected Element createNodeNameElement(final String name, final Vector2D svgPt) {
             final Element text = createElement("text");
             text.setAttribute(CLASS_ATTR, "node-name");
             text.setAttribute("dominant-baseline", "middle");
             floatAttr(text, X_ATTR, svgPt.getX());
             floatAttr(text, Y_ATTR, svgPt.getY());
             text.setTextContent(name);
 
             return text;
         }
 
         /** Create a path element representing a line from {@code svgStart} to {@code svgEnd}.
          * @param className class name to place on the element
          * @param svgStart start point
          * @param svgEnd end point
          * @return path element
          */
         protected Element createPathElement(final String className, final Vector2D svgStart, final Vector2D svgEnd) {
             final Element path = createElement(PATH_ELEMENT);
             path.setAttribute(CLASS_ATTR, className);
 
             final StringBuilder pathStr = new StringBuilder();
             pathStr.append(PATH_MOVE_TO)
                 .append(pointString(svgStart))
                 .append(SPACE)
                 .append(PATH_LINE_TO)
                 .append(pointString(svgEnd));
 
             path.setAttribute("d", pathStr.toString());
 
             return path;
         }
 
         /** Create a string containing the coordinates of the given point in the format used by the SVG
          * {@code path} element.
          * @param pt point to represent as an SVG string
          * @return SVG string representation of the point
          */
         protected String pointString(final Vector2D pt) {
             return pt.getX() + " " + pt.getY();
         }
 
         /** Visit a node in the tree.
          * @param name the name for the node in the visualization
          * @param node the node being visited
          */
         protected abstract void visitNode(String name, RegionNode2D node);
     }
 
     /** BSP tree visitor that outputs SVG representing the tree geometry.
      */
     private final class TreeGeometryVisitor extends AbstractSVGTreeVisitor {
 
         /** The geometry bounds as a region instance. */
         private final Parallelogram boundsRegion;
 
         /** Transform converting from geometry space to SVG space. */
         private final AffineTransformMatrix2D transform;
 
         /** Group element containing the tree geometry paths. */
         private final Element pathGroup;
 
         /** Group element containing the tree node labels. */
         private final Element labelGroup;
 
         /** Construct a new instance for generating SVG geometry content.
          * @param transform transform converting from geometry space to SVG space
          * @param nodeNames map of nodes to the names that should be used to identify them
          * @param parent parent SVG element
          * @param doc xml document
          */
         TreeGeometryVisitor(final AffineTransformMatrix2D transform, final Map<RegionNode2D, String> nodeNames,
                 final Element parent, final Document doc) {
             super(nodeNames, parent, doc);
 
             this.boundsRegion = bounds.toRegion(PRECISION);
 
             this.transform = transform;
 
             // place the label group after the geometry group so the labels appear on top
             this.pathGroup = svgElement("g", doc);
             pathGroup.setAttribute(CLASS_ATTR, "paths");
             parent.appendChild(pathGroup);
 
             this.labelGroup = svgElement("g", doc);
             labelGroup.setAttribute(CLASS_ATTR, "labels");
             parent.appendChild(labelGroup);
         }
 
         /** {@inheritDoc} */
         @Override
         protected void visitNode(final String name, final RegionNode2D node) {
             if (node.isLeaf()) {
                 visitLeafNode(name, node);
             } else {
                 visitInternalNode(name, node);
             }
         }
 
         /** Visit a leaf node.
          * @param name name of the node
          * @param node the leaf node
          */
         private void visitLeafNode(final String name, final RegionNode2D node) {
             final RegionBSPTree2D tree = node.getNodeRegion().toTree();
             tree.intersection(boundsRegion.toTree());
 
             final Vector2D svgCentroid = toSvgSpace(tree.getCentroid());
 
             labelGroup.appendChild(createNodeNameElement(name, svgCentroid));
 
             if (node.isInside()) {
                 for (final LinePath linePath : tree.getBoundaryPaths()) {
                     final Element path = createElement(PATH_ELEMENT);
                     pathGroup.appendChild(path);
                     path.setAttribute(CLASS_ATTR, "inside");
 
                     final StringBuilder sb = new StringBuilder();
 
                     for (final Vector2D pt : linePath.getVertexSequence()) {
                         if (sb.length() < 1) {
                             sb.append(PATH_MOVE_TO);
                         } else {
                             sb.append(SPACE)
                                 .append(PATH_LINE_TO);
                         }
 
                         sb.append(pointString(toSvgSpace(pt)));
                     }
 
                     path.setAttribute("d", sb.toString());
                 }
             }
         }
 
         /** Visit an internal node.
          * @param name name of the node
          * @param node the internal node
          */
         private void visitInternalNode(final String name, final RegionNode2D node) {
             final LineConvexSubset trimmedCut = boundsRegion.trim(node.getCut());
 
             final Vector2D svgStart = toSvgSpace(trimmedCut.getStartPoint());
             final Vector2D svgEnd = toSvgSpace(trimmedCut.getEndPoint());
 
             final Vector2D svgMid = svgStart.lerp(svgEnd, 0.5);
 
             labelGroup.appendChild(createNodeNameElement(name, svgMid));
 
             pathGroup.appendChild(createPathElement("cut", svgStart, svgEnd));
 
             final String arrowPathString = createCutArrowPathString(svgStart, svgEnd);
             if (arrowPathString != null) {
                 final Element arrowPath = createElement(PATH_ELEMENT);
                 pathGroup.appendChild(arrowPath);
                 arrowPath.setAttribute(CLASS_ATTR, "arrow");
                 arrowPath.setAttribute("d", arrowPathString);
             }
 
             final RegionCutBoundary<Vector2D> boundary = node.getCutBoundary();
             if (boundary != null) {
                 addRegionBoundaries(boundary.getInsideFacing());
                 addRegionBoundaries(boundary.getOutsideFacing());
             }
         }
 
         /** Add path elements for the given list of region boundaries.
          * @param boundaries boundaries to add path elements for
          */
         private void addRegionBoundaries(final List<HyperplaneConvexSubset<Vector2D>> boundaries) {
             LineConvexSubset trimmed;
             for (final HyperplaneConvexSubset<Vector2D> boundary : boundaries) {
                 trimmed = boundsRegion.trim(boundary);
 
                 if (trimmed != null) {
                     pathGroup.appendChild(createPathElement(
                             "region-boundary",
                             toSvgSpace(trimmed.getStartPoint()),
                             toSvgSpace(trimmed.getEndPoint())));
                 }
             }
         }
 
         /** Create an SVG path string defining an arrow head for the line segment that extends from
          * {@code svgStart} to {@code svgEnd}.
          * @param svgStart line segment start point
          * @param svgEnd line segment end point
          * @return an SVG path string defining an arrow head for the line segment
          */
         private String createCutArrowPathString(final Vector2D svgStart, final Vector2D svgEnd) {
             final Vector2D dir = svgStart.vectorTo(svgEnd);
             if (!dir.eq(Vector2D.ZERO, PRECISION)) {
 
                 final double az = Math.atan2(dir.getY(), dir.getX());
                 final Vector2D upperArrowPt = PolarCoordinates
                         .toCartesian(ARROW_LENGTH, az + ARROW_ANGLE)
                         .add(svgEnd);
 
                 final Vector2D lowerArrowPt = PolarCoordinates
                         .toCartesian(ARROW_LENGTH, az - ARROW_ANGLE)
                         .add(svgEnd);
 
                 final StringBuilder sb = new StringBuilder();
                 sb.append(PATH_MOVE_TO)
                     .append(pointString(upperArrowPt))
                     .append(SPACE)
                     .append(PATH_LINE_TO)
                     .append(pointString(svgEnd))
                     .append(SPACE)
                     .append(PATH_LINE_TO)
                     .append(pointString(lowerArrowPt));
 
                 return sb.toString();
             }
 
             return null;
         }
 
         /** Convert the given point in geometry space to SVG space.
          * @param pt point in geometry space to convert
          * @return point in SVG space
          */
         private Vector2D toSvgSpace(final Vector2D pt) {
             return transform.apply(pt);
         }
     }
 
     /** BSP tree visitor that outputs SVG representing the tree structure.
      */
     private final class TreeStructureVisitor extends AbstractSVGTreeVisitor {
 
         /** Top of the content area. */
         private final double svgTop;
 
         /** Width of the content area. */
         private final double svgWidth;
 
         /** Map of nodes to their rendered locations in the content area. */
         private final Map<RegionNode2D, Vector2D> nodeLocations = new HashMap<>();
 
         /** Construct a new instance for rendering a representation of the structure of a BSP tree.
          * @param treeNodeHeight the height of the BSP tree
          * @param svgWidth available SVG width for the content
          * @param svgHeight available SVG height for the content
          * @param nodeNames map of nodes to the names that should be used to identify them
          * @param parent parent SVG element
          * @param doc xml document
          */
         TreeStructureVisitor(final int treeNodeHeight, final double svgWidth, final double svgHeight,
                 final Map<RegionNode2D, String> nodeNames, final Element parent, final Document doc) {
             super(nodeNames, parent, doc);
 
             final double requiredSvgHeight = treeNodeHeight * TREE_VERTICAL_SPACING;
             final double svgMid = 0.5 * svgHeight;
 
             this.svgTop = svgMid - (0.5 * requiredSvgHeight);
             this.svgWidth = svgWidth;
         }
 
         /** {@inheritDoc} */
         @Override
         protected void visitNode(final String name, final RegionNode2D node) {
             final Vector2D loc = getNodeLocation(node);
             nodeLocations.put(node, loc);
 
             final Element nodeGroup = createChild("g");
             nodeGroup.setAttribute(CLASS_ATTR, getNodeClassNames(name, node));
 
             nodeGroup.appendChild(createNodeNameElement(name, loc));
 
             final Vector2D parentLoc = nodeLocations.get(node.getParent());
             if (parentLoc != null) {
                 final Vector2D offset = loc.vectorTo(parentLoc).withNorm(TREE_LINE_MARGIN);
                 nodeGroup.appendChild(createPathElement("tree-path", loc.add(offset), parentLoc.subtract(offset)));
             }
         }
 
         /** Get a string containing the class names that should be used for the given node.
          * @param name name of the node
          * @param node the node
          * @return a string containing the class names that should be used for the given node
          */
         private String getNodeClassNames(final String name, final RegionNode2D node) {
             final StringBuilder sb = new StringBuilder();
             sb.append("node-").append(name);
 
             if (node.isLeaf()) {
                 sb.append(SPACE)
                     .append(node.isInside() ? "inside-node" : "outside-node");
             }
 
             return sb.toString();
         }
 
         /** Get the SVG location where the visual representation of the given node should be rendered.
          * @param node the node to determine the location for
          * @return the SVG location where the node should be rendered
          */
         private Vector2D getNodeLocation(final RegionNode2D node) {
             // find the node parent
             final RegionNode2D parent = node.getParent();
             final Vector2D parentLoc = nodeLocations.get(parent);
             if (parentLoc == null) {
                 // this is the root node
                 return Vector2D.of(
                         0.5 * svgWidth,
                         svgTop);
             } else {
                 // align with the parent
                 double parentXOffset = Math.max(
                         treeParentOffsetFactor * (svgWidth / (1 << parent.depth())),
                         treeParentXOffsetMin);
                 if (node.isMinus()) {
                     parentXOffset = -parentXOffset;
                 }
 
                 return Vector2D.of(
                             parentLoc.getX() + parentXOffset,
                             parentLoc.getY() + TREE_VERTICAL_SPACING
                         );
             }
         }
     }
 }