001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.geometry.examples.tutorials.bsp;
018
019import java.io.File;
020import java.util.HashMap;
021import java.util.Map;
022
023import org.apache.commons.geometry.euclidean.twod.Bounds2D;
024import org.apache.commons.geometry.euclidean.twod.Line;
025import org.apache.commons.geometry.euclidean.twod.Lines;
026import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
027import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.RegionNode2D;
028import org.apache.commons.geometry.euclidean.twod.Vector2D;
029import org.apache.commons.numbers.core.Precision;
030
031/** Class containing tutorial code for constructing a 2D BSP tree using
032 * a bottom-up approach.
033 */
034public final class BottomUpBSPTreeConstruction {
035
036    /** String defining the name format of output svg files. */
037    private static final String OUTPUT_FILE_FORMAT = "bu-cut-%d.svg";
038
039    /** No instantiation. */
040    private BottomUpBSPTreeConstruction() {}
041
042    /** Tutorial code entry point.
043     * @param args command arguments; if given, the first argument is used as the location of
044     *      output folder
045     */
046    public static void main(final String[] args) {
047        final File outputFolder = new File(args.length > 0 ? args[0] : ".");
048        final BSPTreeSVGWriter svgWriter = new BSPTreeSVGWriter(Bounds2D.from(Vector2D.of(-8, -8), Vector2D.of(8, 8)));
049
050        final Map<RegionNode2D, String> nodeNames = new HashMap<>();
051        int cutCount = -1;
052
053        // create a precision context for floating point comparisons
054        final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
055
056        // construct an empty tree
057        final RegionBSPTree2D tree = RegionBSPTree2D.empty();
058
059        final Line rootCut = Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision);
060        final RegionNode2D a = tree.getRoot();
061
062        nodeNames.put(a, "a");
063        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
064
065        // add a single cut
066        a.cut(rootCut);
067
068        final RegionNode2D b = a.getMinus();
069        final RegionNode2D c = a.getPlus();
070
071        nodeNames.put(b, "b");
072        nodeNames.put(c, "c");
073        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
074
075        // add another cut
076        b.insertCut(Lines.fromPoints(Vector2D.of(1, 0), Vector2D.of(-1, 1), precision));
077
078        final RegionNode2D d = b.getMinus();
079        final RegionNode2D e = b.getPlus();
080
081        nodeNames.put(d, "d");
082        nodeNames.put(e, "e");
083        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
084
085        d.insertCut(Lines.fromPointAndDirection(Vector2D.of(-5, 1), Vector2D.Unit.MINUS_Y, precision));
086
087        final RegionNode2D f = d.getMinus();
088        final RegionNode2D g = d.getPlus();
089
090        nodeNames.put(f, "f");
091        nodeNames.put(g, "g");
092        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
093
094        // other side
095        c.insertCut(Lines.fromPoints(Vector2D.of(-1, 0), Vector2D.of(1, -1), precision));
096
097        final RegionNode2D h = c.getMinus();
098        final RegionNode2D i = c.getPlus();
099
100        nodeNames.put(h, "h");
101        nodeNames.put(i, "i");
102        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
103
104        h.insertCut(Lines.fromPointAndDirection(Vector2D.of(5, -1), Vector2D.Unit.PLUS_Y, precision));
105
106        final RegionNode2D j = h.getMinus();
107        final RegionNode2D k = h.getPlus();
108
109        nodeNames.put(j, "j");
110        nodeNames.put(k, "k");
111        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
112    }
113}