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