View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.examples.tutorials.bsp;
    18
    19  import java.io.File;
    20  import java.util.Deque;
    21  import java.util.HashMap;
    22  import java.util.LinkedList;
    23  import java.util.List;
    24  import java.util.Map;
    25
    26  import javax.xml.parsers.DocumentBuilder;
    27  import javax.xml.parsers.DocumentBuilderFactory;
    28  import javax.xml.parsers.ParserConfigurationException;
    29  import javax.xml.transform.OutputKeys;
    30  import javax.xml.transform.Transformer;
    31  import javax.xml.transform.TransformerException;
    32  import javax.xml.transform.TransformerFactory;
    33  import javax.xml.transform.dom.DOMSource;
    34  import javax.xml.transform.stream.StreamResult;
    35
    36  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    37  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
    38  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
    39  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    40  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    41  import org.apache.commons.geometry.euclidean.twod.AffineTransformMatrix2D;
    42  import org.apache.commons.geometry.euclidean.twod.Bounds2D;
    43  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    44  import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
    45  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    46  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.RegionNode2D;
    47  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    48  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    49  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
    50  import org.w3c.dom.Document;
    51  import org.w3c.dom.Element;
    52
    53  /** Class for writing SVG visualizations of 2D BSP trees.
    54   */
    55  public class BSPTreeSVGWriter {
    56
    57      /** SVG XML namespace. */
    58      private static final String SVG_NAMESPACE = "http://www.w3.org/2000/svg";
    59
    60      /** SVG version. */
    61      private static final String SVG_VERSION = "1.1";
    62
    63      /** Property key used to set the indent level of the output xml. */
    64      private static final String INDENT_AMOUNT_KEY = "{http://xml.apache.org/xslt}indent-amount";
    65
    66      /** Indent amount for the output xml. */
    67      private static final int INDENT_AMOUNT = 4;
    68
    69      /** String containing default node name characters. */
    70      private static final String DEFAULT_NODE_NAMES = "abcdefghijklmnopqrstuvwxyz";
    71
    72      /** Id used for the geometry area clip path. */
    73      private static final String GEOMETRY_AREA_CLIP_PATH_ID = "geometry-area";
    74
    75      /** Path string command to move to a point. */
    76      private static final char PATH_MOVE_TO = 'M';
    77
    78      /** Path string command to draw a line to a point. */
    79      private static final char PATH_LINE_TO = 'L';
    80
    81      /** Space character. */
    82      private static final char SPACE = ' ';
    83
    84      /** Name of the SVG "rect" element. */
    85      private static final String RECT_ELEMENT = "rect";
    86
    87      /** Name of the SVG "path" element. */
    88      private static final String PATH_ELEMENT = "path";
    89
    90      /** Name of the "class" attribute. */
    91      private static final String CLASS_ATTR = "class";
    92
    93      /** Name of the "width" attribute. */
    94      private static final String WIDTH_ATTR = "width";
    95
    96      /** Name of the "height" attribute. */
    97      private static final String HEIGHT_ATTR = "height";
    98
    99      /** Name of the "x" attribute. */
    100     private static final String X_ATTR = "x";
    101
    102     /** Name of the "y" attribute. */
    103     private static final String Y_ATTR = "y";
    104
    105     /** CSS style string for the generated SVG. */
    106     private static final String STYLE =
    107         "text { font-size: 14px; } " +
    108         ".node-name { text-anchor: middle; font-family: \"Courier New\", Courier, monospace; } " +
    109         ".geometry-border { fill: none; stroke: gray; stroke-width: 1; } " +
    110         ".arrow { fill: none; stroke: blue; stroke-width: 1; } " +
    111         ".cut { fill: none; stroke: blue; stroke-width: 1; stroke-dasharray: 5,3; } " +
    112         ".region-boundary { stroke: orange; stroke-width: 2; } " +
    113         ".inside { fill: #aaa; opacity: 0.2; } " +
    114         ".tree-path { fill: none; stroke: gray; stroke-width: 1; } " +
    115         ".inside-node { font-weight: bold; }";
    116
    117     /** Geometry bounds; only geometry within these bounds is rendered. */
    118     private final Bounds2D bounds;
    119
    120     /** The width of the SVG. */
    121     private int width = 750;
    122
    123     /** The height of the SVG. */
    124     private int height = 375;
    125
    126     /** The margin used in the SVG. */
    127     private int margin = 5;
    128
    129     /** Amount of the overall width of the SVG to use for the geometry area. */
    130     private double geometryAreaWidthFactor = 0.5;
    131
    132     /** Amount of the overall width of the SVG to use for the tree structure area. */
    133     private double treeAreaWidthFactor = 1.0 - geometryAreaWidthFactor;
    134
    135     /** Angle that arrow heads on lines make with the direction of the line. */
    136     private double arrowAngle = 0.8 * Math.PI;
    137
    138     /** Length of arrow head lines. */
    139     private double arrowLength = 8;
    140
    141     /** Distance between levels of the tree in the tree structure display. */
    142     private double treeVerticalSpacing = 45;
    143
    144     /** Line end margin used in the lines between nodes in the tree structure display. */
    145     private double treeLineMargin = 10;
    146
    147     /** Factor determining how much of the available horizontal width for a node should be used to
    148      * offset it from its parent.
    149      */
    150     private double treeParentOffsetFactor = 0.25;
    151
    152     /** Minimum horizontal offset for tree nodes from their parents. */
    153     private double treeParentXOffsetMin = 0;
    154
    155     /** Precision context used for floating point comparisons. */
    156     private DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
    157
    158     /** Construct a new instance that will render regions within the given bounds.
    159      * @param bounds bounds used to determine what output
    160      */
    161     public BSPTreeSVGWriter(final Bounds2D bounds) {
    162         this.bounds = bounds;
    163     }
    164
    165     /** Set the offset factor determining how much of the available horizontal width for
    166      * a node should be used to offset it from its parent.
    167      * @param treeParentOffsetFactor offset factor
    168      */
    169     public void setTreeParentOffsetFactor(final double treeParentOffsetFactor) {
    170         this.treeParentOffsetFactor = treeParentOffsetFactor;
    171     }
    172
    173     /** Set the minimum horizontal offset for tree nodes from their parents.
    174      * @param treeParentXOffsetMin minimum offset
    175      */
    176     public void setTreeParentXOffsetMin(final double treeParentXOffsetMin) {
    177         this.treeParentXOffsetMin = treeParentXOffsetMin;
    178     }
    179
    180     /** Write an SVG visualization of the given BSP tree. Default names are assigned to the tree nodes.
    181      * @param tree tree to output
    182      * @param file path of the svg file to write
    183      */
    184     public void write(final RegionBSPTree2D tree, final File file) {
    185         final Deque<RegionNode2D> nodeQueue = new LinkedList<>();
    186         nodeQueue.add(tree.getRoot());
    187
    188         final Map<RegionNode2D, String> nodeNames = new HashMap<>();
    189
    190         final String names = DEFAULT_NODE_NAMES;
    191         RegionNode2D node;
    192         for (int i = 0; i < names.length() && !nodeQueue.isEmpty(); ++i) {
    193             node = nodeQueue.removeFirst();
    194
    195             nodeNames.put(node, names.substring(i, i + 1));
    196
    197             if (node.isInternal()) {
    198                 nodeQueue.add(node.getMinus());
    199                 nodeQueue.add(node.getPlus());
    200             }
    201         }
    202
    203         write(tree, nodeNames, file);
    204     }
    205
    206     /** Write an SVG visualization of the given BSP tree.
    207      * @param tree tree to output
    208      * @param nodeNames map of node instances to the names that should be used for them in the svg
    209      * @param file path of the svg file to write
    210      */
    211     public void write(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames, final File file) {
    212         try {
    213             final DocumentBuilderFactory docBuilderFactory = DocumentBuilderFactory.newInstance();
    214             final DocumentBuilder docBuilder = docBuilderFactory.newDocumentBuilder();
    215
    216             final Document doc = docBuilder.newDocument();
    217
    218             // create the svg element
    219             final Element root = svgElement("svg", doc);
    220             doc.appendChild(root);
    221
    222             root.setAttribute("version", SVG_VERSION);
    223             root.setAttribute(WIDTH_ATTR, String.valueOf(width));
    224             root.setAttribute(HEIGHT_ATTR, String.valueOf(height));
    225
    226             // add a defs element for later use
    227             final Element defs = svgElement("defs", doc);
    228             root.appendChild(defs);
    229
    230             // add a style element
    231             final Element style = svgElement("style", doc);
    232             root.appendChild(style);
    233             style.setTextContent(STYLE);
    234
    235             // write the tree
    236             writeTreeGeometryArea(tree, nodeNames, root, defs, doc);
    237             writeTreeStructureArea(tree, nodeNames, root, doc);
    238
    239             // output to the target file
    240             final TransformerFactory transformerFactory = TransformerFactory.newInstance();
    241             final Transformer transformer = transformerFactory.newTransformer();
    242             transformer.setOutputProperty(OutputKeys.INDENT, "yes");
    243             transformer.setOutputProperty(INDENT_AMOUNT_KEY, String.valueOf(INDENT_AMOUNT));
    244
    245             final DOMSource source = new DOMSource(doc);
    246             final StreamResult target = new StreamResult(file);
    247
    248             transformer.transform(source, target);
    249
    250         } catch (ParserConfigurationException | TransformerException e) {
    251             // throw as a runtime exception for convenience
    252             throw new RuntimeException("Failed to create SVG", e);
    253         }
    254     }
    255
    256     /** Write the svg area containing the visual representation of the tree geometry.
    257      * @param tree tree to write
    258      * @param nodeNames map of nodes to the names that should be used to identify them
    259      * @param root root svg element
    260      * @param defs svg defs element
    261      * @param doc xml document
    262      */
    263     private void writeTreeGeometryArea(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames,
    264             final Element root, final Element defs, final Document doc) {
    265         final double geometrySvgX = margin;
    266         final double geometrySvgY = margin;
    267         final double geometrySvgWidth = (geometryAreaWidthFactor * width) - (2 * margin);
    268         final double geometrySvgHeight = height - (2 * margin);
    269
    270         defineClipRect(GEOMETRY_AREA_CLIP_PATH_ID,
    271                 geometrySvgX, geometrySvgY,
    272                 geometrySvgWidth, geometrySvgHeight,
    273                 defs, doc);
    274
    275         // create the box containing the 2D content
    276         final Element geometryGroup = svgElement("g", doc);
    277         root.appendChild(geometryGroup);
    278         geometryGroup.setAttribute(CLASS_ATTR, "geometry");
    279         geometryGroup.setAttribute("clip-path", "url(#" + GEOMETRY_AREA_CLIP_PATH_ID + ")");
    280
    281         // set up the transform so we can write geometry elements with their natural coordinates
    282         final AffineTransformMatrix2D transform = computeGeometryTransform(bounds, geometrySvgX, geometrySvgY,
    283                 geometrySvgWidth, geometrySvgHeight);
    284
    285         // add the tree geometry
    286         tree.accept(new TreeGeometryVisitor(transform, nodeNames, geometryGroup, doc));
    287
    288         // create a box outlining the geometry area
    289         final Element border = svgElement(RECT_ELEMENT, doc);
    290         border.setAttribute(CLASS_ATTR, "geometry-border");
    291         floatAttr(border, X_ATTR, geometrySvgX);
    292         floatAttr(border, Y_ATTR, geometrySvgY);
    293         floatAttr(border, WIDTH_ATTR, geometrySvgWidth);
    294         floatAttr(border, HEIGHT_ATTR, geometrySvgHeight);
    295
    296         root.appendChild(border);
    297
    298     }
    299
    300     /** Write the svg area containing the visual representation of the tree structure.
    301      * @param tree tree to write
    302      * @param nodeNames map of nodes to the names that should be used to identify them
    303      * @param root svg root element
    304      * @param doc xml document
    305      */
    306     private void writeTreeStructureArea(final RegionBSPTree2D tree, final Map<RegionNode2D, String> nodeNames,
    307             final Element root, final Document doc) {
    308         final Element treeGroup = svgElement("g", doc);
    309         root.appendChild(treeGroup);
    310         treeGroup.setAttribute(CLASS_ATTR, "tree");
    311
    312         final double offsetX = ((1 - treeAreaWidthFactor) * width) + margin;
    313         final double offsetY = margin;
    314
    315         final double svgWidth = (treeAreaWidthFactor * width) - (2 * margin);
    316         final double svgHeight = height - (2 * margin);
    317
    318         treeGroup.setAttribute("transform", "translate(" + offsetX + " " + offsetY + ")");
    319
    320         tree.accept(new TreeStructureVisitor(tree.height(), svgWidth, svgHeight, nodeNames, treeGroup, doc));
    321     }
    322
    323     /** Compute the transform required to convert from the geometry coordinate system given in {@code bounds}
    324      * to the one defined by the given svg coordinates. The y-axis from the geometry is oriented to point
    325      * upwards in the svg.
    326      * @param bounds the bounds of the geometry
    327      * @param svgX x coordinate in the upper-left corner of the svg target box
    328      * @param svgY y coordinate in the upper-left corner of the svg target box
    329      * @param svgWidth width of the svg target box
    330      * @param svgHeight height of the svg target box
    331      * @return a transform converting from geometry space to svg space
    332      */
    333     private static AffineTransformMatrix2D computeGeometryTransform(final Bounds2D bounds,
    334             final double svgX, final double svgY, final double svgWidth, final double svgHeight) {
    335
    336         final Vector2D boundsDiagonal = bounds.getDiagonal();
    337
    338         return AffineTransformMatrix2D
    339             .createTranslation(bounds.getMin().negate())
    340             .scale(svgWidth / boundsDiagonal.getX(), -svgHeight / boundsDiagonal.getY())
    341             .translate(svgX, svgY + svgHeight);
    342     }
    343
    344     /** Define an SVG clipping rectangle.
    345      * @param id id of the clipping rectangle to add
    346      * @param x x coordinate of the clipping rectangle
    347      * @param y y coordinate of the clipping rectangle
    348      * @param svgWidth width of the clipping rectangle
    349      * @param svgHeight height of the clipping rectangle
    350      * @param defs svg "defs" element
    351      * @param doc xml document
    352      */
    353     private void defineClipRect(final String id, final double x, final double y,
    354             final double svgWidth, final double svgHeight, final Element defs, final Document doc) {
    355
    356         final Element clipPath = svgElement("clipPath", doc);
    357         clipPath.setAttribute("id", id);
    358
    359         defs.appendChild(clipPath);
    360
    361         final Element rect = svgElement(RECT_ELEMENT, doc);
    362         floatAttr(rect, X_ATTR, x);
    363         floatAttr(rect, Y_ATTR, y);
    364         floatAttr(rect, WIDTH_ATTR, svgWidth);
    365         floatAttr(rect, HEIGHT_ATTR, svgHeight);
    366
    367         clipPath.appendChild(rect);
    368     }
    369
    370     /** Convenience method for setting a floating-point attribute on an element.
    371      * @param element element to set the attribute on
    372      * @param name name of the attribute to set
    373      * @param value value of the attribute to set
    374      */
    375     private static void floatAttr(final Element element, final String name, final double value) {
    376         element.setAttribute(name, String.valueOf(value));
    377     }
    378
    379     /** Convenience method for creating an element from the svg namespace.
    380      * @param name the name of the element
    381      * @param doc document to create the element in
    382      * @return the element from the svg namespace
    383      */
    384     private static Element svgElement(final String name, final Document doc) {
    385         return doc.createElementNS(SVG_NAMESPACE, name);
    386     }
    387
    388     /** Base class for BSP tree visitors that output SVG content.
    389      */
    390     private abstract class AbstractSVGTreeVisitor implements BSPTreeVisitor<Vector2D, RegionNode2D> {
    391
    392         /** Map of nodes to the names that should be used to identify them. */
    393         private final Map<RegionNode2D, String> nodeNames;
    394
    395         /** Parent SVG element to append new elements to. */
    396         private final Element parent;
    397
    398         /** Xml document. */
    399         private final Document doc;
    400
    401         /** Number of nodes visited so far. */
    402         private int count = 0;
    403
    404         /** Construct a new instance.
    405          * @param nodeNames map of nodes ot the names that should be used to identify them
    406          * @param parent parent SVG element
    407          * @param doc xml document
    408          */
    409         AbstractSVGTreeVisitor(final Map<RegionNode2D, String> nodeNames, final Element parent, final Document doc) {
    410             this.nodeNames = nodeNames;
    411             this.parent = parent;
    412             this.doc = doc;
    413         }
    414
    415         /** {@inheritDoc} */
    416         @Override
    417         public Order visitOrder(final RegionNode2D internalNode) {
    418             return Order.NODE_MINUS_PLUS;
    419         }
    420
    421         /** {@inheritDoc} */
    422         @Override
    423         public Result visit(final RegionNode2D node) {
    424             ++count;
    425
    426             final String name = (nodeNames != null && nodeNames.containsKey(node)) ?
    427                     nodeNames.get(node) :
    428                     String.valueOf(count);
    429
    430             visitNode(name, node);
    431
    432             return Result.CONTINUE;
    433         }
    434
    435         /** Create a new svg element with the given name and append it to the parent node.
    436          * @param name name of the element
    437          * @return the created element, already appended to the parent
    438          */
    439         protected Element createChild(final String name) {
    440             final Element child = createElement(name);
    441             parent.appendChild(child);
    442
    443             return child;
    444         }
    445
    446         /** Create an svg element with the given name. The element is <em>not</em> appended to the
    447          * parent node.
    448          * @param name name of the element
    449          * @return the created element
    450          */
    451         protected Element createElement(final String name) {
    452             return svgElement(name, doc);
    453         }
    454
    455         /** Create an SVG text element containing the name of a tree node. The returned element is
    456          * <em>not</em> appended to the parent.
    457          * @param name name of the tree node
    458          * @param svgPt location to place the text
    459          * @return text element containing the given node name
    460          */
    461         protected Element createNodeNameElement(final String name, final Vector2D svgPt) {
    462             final Element text = createElement("text");
    463             text.setAttribute(CLASS_ATTR, "node-name");
    464             text.setAttribute("dominant-baseline", "middle");
    465             floatAttr(text, X_ATTR, svgPt.getX());
    466             floatAttr(text, Y_ATTR, svgPt.getY());
    467             text.setTextContent(name);
    468
    469             return text;
    470         }
    471
    472         /** Create a path element representing a line from {@code svgStart} to {@code svgEnd}.
    473          * @param className class name to place on the element
    474          * @param svgStart start point
    475          * @param svgEnd end point
    476          * @return path element
    477          */
    478         protected Element createPathElement(final String className, final Vector2D svgStart, Vector2D svgEnd) {
    479             final Element path = createElement(PATH_ELEMENT);
    480             path.setAttribute(CLASS_ATTR, className);
    481
    482             final StringBuilder pathStr = new StringBuilder();
    483             pathStr.append(PATH_MOVE_TO)
    484                 .append(pointString(svgStart))
    485                 .append(SPACE)
    486                 .append(PATH_LINE_TO)
    487                 .append(pointString(svgEnd));
    488
    489             path.setAttribute("d", pathStr.toString());
    490
    491             return path;
    492         }
    493
    494         /** Create a string containing the coordinates of the given point in the format used by the SVG
    495          * {@code path} element.
    496          * @param pt point to represent as an SVG string
    497          * @return SVG string representation of the point
    498          */
    499         protected String pointString(final Vector2D pt) {
    500             return pt.getX() + " " + pt.getY();
    501         }
    502
    503         /** Visit a node in the tree.
    504          * @param name the name for the node in the visualization
    505          * @param node the node being visited
    506          */
    507         protected abstract void visitNode(String name, RegionNode2D node);
    508     }
    509
    510     /** BSP tree visitor that outputs SVG representing the tree geometry.
    511      */
    512     private final class TreeGeometryVisitor extends AbstractSVGTreeVisitor {
    513
    514         /** The geometry bounds as a region instance. */
    515         private final Parallelogram boundsRegion;
    516
    517         /** Transform converting from geometry space to SVG space. */
    518         private final AffineTransformMatrix2D transform;
    519
    520         /** Group element containing the tree geometry paths. */
    521         private final Element pathGroup;
    522
    523         /** Group element containing the tree node labels. */
    524         private final Element labelGroup;
    525
    526         /** Construct a new instance for generating SVG geometry content.
    527          * @param transform transform converting from geometry space to SVG space
    528          * @param nodeNames map of nodes to the names that should be used to identify them
    529          * @param parent parent SVG element
    530          * @param doc xml document
    531          */
    532         TreeGeometryVisitor(final AffineTransformMatrix2D transform, final Map<RegionNode2D, String> nodeNames,
    533                 final Element parent, final Document doc) {
    534             super(nodeNames, parent, doc);
    535
    536             this.boundsRegion = bounds.toRegion(precision);
    537
    538             this.transform = transform;
    539
    540             // place the label group after the geometry group so the labels appear on top
    541             this.pathGroup = svgElement("g", doc);
    542             pathGroup.setAttribute(CLASS_ATTR, "paths");
    543             parent.appendChild(pathGroup);
    544
    545             this.labelGroup = svgElement("g", doc);
    546             labelGroup.setAttribute(CLASS_ATTR, "labels");
    547             parent.appendChild(labelGroup);
    548         }
    549
    550         /** {@inheritDoc} */
    551         @Override
    552         protected void visitNode(final String name, final RegionNode2D node) {
    553             if (node.isLeaf()) {
    554                 visitLeafNode(name, node);
    555             } else {
    556                 visitInternalNode(name, node);
    557             }
    558         }
    559
    560         /** Visit a leaf node.
    561          * @param name name of the node
    562          * @param node the leaf node
    563          */
    564         private void visitLeafNode(final String name, final RegionNode2D node) {
    565             final RegionBSPTree2D tree = node.getNodeRegion().toTree();
    566             tree.intersection(boundsRegion.toTree());
    567
    568             final Vector2D svgCentroid = toSvgSpace(tree.getCentroid());
    569
    570             labelGroup.appendChild(createNodeNameElement(name, svgCentroid));
    571
    572             if (node.isInside()) {
    573                 for (LinePath linePath : tree.getBoundaryPaths()) {
    574                     final Element path = createElement(PATH_ELEMENT);
    575                     pathGroup.appendChild(path);
    576                     path.setAttribute(CLASS_ATTR, "inside");
    577
    578                     StringBuilder sb = new StringBuilder();
    579
    580                     for (final Vector2D pt : linePath.getVertexSequence()) {
    581                         if (sb.length() < 1) {
    582                             sb.append(PATH_MOVE_TO);
    583                         } else {
    584                             sb.append(SPACE)
    585                                 .append(PATH_LINE_TO);
    586                         }
    587
    588                         sb.append(pointString(toSvgSpace(pt)));
    589                     }
    590
    591                     path.setAttribute("d", sb.toString());
    592                 }
    593             }
    594         }
    595
    596         /** Visit an internal node.
    597          * @param name name of the node
    598          * @param node the internal node
    599          */
    600         private void visitInternalNode(final String name, final RegionNode2D node) {
    601             final LineConvexSubset trimmedCut = boundsRegion.trim(node.getCut());
    602
    603             final Vector2D svgStart = toSvgSpace(trimmedCut.getStartPoint());
    604             final Vector2D svgEnd = toSvgSpace(trimmedCut.getEndPoint());
    605
    606             final Vector2D svgMid = svgStart.lerp(svgEnd, 0.5);
    607
    608             labelGroup.appendChild(createNodeNameElement(name, svgMid));
    609
    610             pathGroup.appendChild(createPathElement("cut", svgStart, svgEnd));
    611
    612             final String arrowPathString = createCutArrowPathString(svgStart, svgEnd);
    613             if (arrowPathString != null) {
    614                 final Element arrowPath = createElement(PATH_ELEMENT);
    615                 pathGroup.appendChild(arrowPath);
    616                 arrowPath.setAttribute(CLASS_ATTR, "arrow");
    617                 arrowPath.setAttribute("d", arrowPathString);
    618             }
    619
    620             final RegionCutBoundary<Vector2D> boundary = node.getCutBoundary();
    621             if (boundary != null) {
    622                 addRegionBoundaries(boundary.getInsideFacing());
    623                 addRegionBoundaries(boundary.getOutsideFacing());
    624             }
    625         }
    626
    627         /** Add path elements for the given list of region boundaries.
    628          * @param boundaries boundaries to add path elements for
    629          */
    630         private void addRegionBoundaries(final List<HyperplaneConvexSubset<Vector2D>> boundaries) {
    631             LineConvexSubset trimmed;
    632             for (final HyperplaneConvexSubset<Vector2D> boundary : boundaries) {
    633                 trimmed = boundsRegion.trim(boundary);
    634
    635                 if (trimmed != null) {
    636                     pathGroup.appendChild(createPathElement(
    637                             "region-boundary",
    638                             toSvgSpace(trimmed.getStartPoint()),
    639                             toSvgSpace(trimmed.getEndPoint())));
    640                 }
    641             }
    642         }
    643
    644         /** Create an SVG path string defining an arrow head for the line segment that extends from
    645          * {@code svgStart} to {@code svgEnd}.
    646          * @param svgStart line segment start point
    647          * @param svgEnd line segment end point
    648          * @return an SVG path string defining an arrow head for the line segment
    649          */
    650         private String createCutArrowPathString(final Vector2D svgStart, final Vector2D svgEnd) {
    651             final Vector2D dir = svgStart.vectorTo(svgEnd);
    652             if (!dir.eq(Vector2D.ZERO, precision)) {
    653
    654                 final double az = Math.atan2(dir.getY(), dir.getX());
    655                 final Vector2D upperArrowPt = PolarCoordinates
    656                         .toCartesian(arrowLength, az + arrowAngle)
    657                         .add(svgEnd);
    658
    659                 final Vector2D lowerArrowPt = PolarCoordinates
    660                         .toCartesian(arrowLength, az - arrowAngle)
    661                         .add(svgEnd);
    662
    663                 final StringBuilder sb = new StringBuilder();
    664                 sb.append(PATH_MOVE_TO)
    665                     .append(pointString(upperArrowPt))
    666                     .append(SPACE)
    667                     .append(PATH_LINE_TO)
    668                     .append(pointString(svgEnd))
    669                     .append(SPACE)
    670                     .append(PATH_LINE_TO)
    671                     .append(pointString(lowerArrowPt));
    672
    673                 return sb.toString();
    674             }
    675
    676             return null;
    677         }
    678
    679         /** Convert the given point in geometry space to SVG space.
    680          * @param pt point in geometry space to convert
    681          * @return point in SVG space
    682          */
    683         private Vector2D toSvgSpace(final Vector2D pt) {
    684             return transform.apply(pt);
    685         }
    686     }
    687
    688     /** BSP tree visitor that outputs SVG representing the tree structure.
    689      */
    690     private final class TreeStructureVisitor extends AbstractSVGTreeVisitor {
    691
    692         /** Top of the content area. */
    693         private final double svgTop;
    694
    695         /** Width of the content area. */
    696         private final double svgWidth;
    697
    698         /** Map of nodes to their rendered locations in the content area. */
    699         private final Map<RegionNode2D, Vector2D> nodeLocations = new HashMap<>();;
    700
    701         /** Construct a new instance for rendering a representation of the structure of a BSP tree.
    702          * @param treeNodeHeight the height of the BSP tree
    703          * @param svgWidth available SVG width for the content
    704          * @param svgHeight available SVG height for the content
    705          * @param nodeNames map of nodes to the names that should be used to identify them
    706          * @param parent parent SVG element
    707          * @param doc xml document
    708          */
    709         TreeStructureVisitor(final int treeNodeHeight, final double svgWidth, final double svgHeight,
    710                 final Map<RegionNode2D, String> nodeNames, final Element parent, final Document doc) {
    711             super(nodeNames, parent, doc);
    712
    713             final double requiredSvgHeight = treeNodeHeight * treeVerticalSpacing;
    714             final double svgMid = 0.5 * svgHeight;
    715
    716             this.svgTop = svgMid - (0.5 * requiredSvgHeight);
    717             this.svgWidth = svgWidth;
    718         }
    719
    720         /** {@inheritDoc} */
    721         @Override
    722         protected void visitNode(final String name, final RegionNode2D node) {
    723             final Vector2D loc = getNodeLocation(node);
    724             nodeLocations.put(node, loc);
    725
    726             final Element nodeGroup = createChild("g");
    727             nodeGroup.setAttribute(CLASS_ATTR, getNodeClassNames(name, node));
    728
    729             nodeGroup.appendChild(createNodeNameElement(name, loc));
    730
    731             final Vector2D parentLoc = nodeLocations.get(node.getParent());
    732             if (parentLoc != null) {
    733                 final Vector2D offset = loc.vectorTo(parentLoc).withNorm(treeLineMargin);
    734                 nodeGroup.appendChild(createPathElement("tree-path", loc.add(offset), parentLoc.subtract(offset)));
    735             }
    736         }
    737
    738         /** Get a string containing the class names that should be used for the given node.
    739          * @param name name of the node
    740          * @param node the node
    741          * @return a string containing the class names that should be used for the given node
    742          */
    743         private String getNodeClassNames(final String name, final RegionNode2D node) {
    744             final StringBuilder sb = new StringBuilder();
    745             sb.append("node-" + name);
    746
    747             if (node.isLeaf()) {
    748                 sb.append(SPACE)
    749                     .append(node.isInside() ? "inside-node" : "outside-node");
    750             }
    751
    752             return sb.toString();
    753         }
    754
    755         /** Get the SVG location where the visual representation of the given node should be rendered.
    756          * @param node the node to determine the location for
    757          * @return the SVG location where the node should be rendered
    758          */
    759         private Vector2D getNodeLocation(final RegionNode2D node) {
    760             // find the node parent
    761             final RegionNode2D parent = node.getParent();
    762             final Vector2D parentLoc = nodeLocations.get(parent);
    763             if (parentLoc == null) {
    764                 // this is the root node
    765                 return Vector2D.of(
    766                         0.5 * svgWidth,
    767                         svgTop);
    768             } else {
    769                 // align with the parent
    770                 double parentXOffset = Math.max(
    771                         treeParentOffsetFactor * (svgWidth / (1 << parent.depth())),
    772                         treeParentXOffsetMin);
    773                 if (node.isMinus()) {
    774                     parentXOffset = -parentXOffset;
    775                 }
    776
    777                 return Vector2D.of(
    778                             parentLoc.getX() + parentXOffset,
    779                             parentLoc.getY() + treeVerticalSpacing
    780                         );
    781             }
    782         }
    783     }
    784 }