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.Arrays;
021import java.util.HashMap;
022import java.util.Map;
023
024import org.apache.commons.geometry.euclidean.twod.Bounds2D;
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.Segment;
029import org.apache.commons.geometry.euclidean.twod.Vector2D;
030import org.apache.commons.geometry.euclidean.twod.path.LinePath;
031import org.apache.commons.numbers.core.Precision;
032
033/** Class containing tutorial code for constructing a 2D BSP tree using
034 * a top-down approach.
035 */
036public final class TopDownBSPTreeConstruction {
037
038    /** String defining the name format of output svg files. */
039    private static final String OUTPUT_FILE_FORMAT = "td-cut-%d.svg";
040
041    /** No instantiation. */
042    private TopDownBSPTreeConstruction() {}
043
044    /** Tutorial code entry point.
045     * @param args command arguments; if given, the first argument is used as the location of
046     *      output folder
047     */
048    public static void main(final String[] args) {
049        final File outputFolder = new File(args.length > 0 ? args[0] : ".");
050        final BSPTreeSVGWriter svgWriter = new BSPTreeSVGWriter(Bounds2D.from(Vector2D.of(-8, -8), Vector2D.of(8, 8)));
051
052        final Map<RegionNode2D, String> nodeNames = new HashMap<>();
053        int cutCount = 0;
054
055        // create a precision context for floating point comparisons
056        final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
057
058        // construct an empty tree
059        final RegionBSPTree2D tree = RegionBSPTree2D.empty();
060
061        final Segment firstBoundary = Lines.segmentFromPoints(Vector2D.of(-5, 0), Vector2D.of(-1, 0), precision);
062        tree.insert(firstBoundary);
063
064        final RegionNode2D a = tree.getRoot();
065        final RegionNode2D b = a.getMinus();
066        final RegionNode2D c = a.getPlus();
067
068        nodeNames.put(a, "a");
069        nodeNames.put(b, "b");
070        nodeNames.put(c, "c");
071        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
072
073        tree.insert(Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(-5, 3), precision));
074        tree.insert(Lines.segmentFromPoints(Vector2D.of(-5, 3), Vector2D.of(-5, 0), precision));
075
076        final RegionNode2D d = b.getMinus();
077        final RegionNode2D e = b.getPlus();
078        final RegionNode2D f = d.getMinus();
079        final RegionNode2D g = d.getPlus();
080
081        nodeNames.put(d, "d");
082        nodeNames.put(e, "e");
083        nodeNames.put(f, "f");
084        nodeNames.put(g, "g");
085        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
086
087        final LinePath path = LinePath.fromVertices(Arrays.asList(
088                Vector2D.of(-1, 0),
089                Vector2D.of(5, -3),
090                Vector2D.of(5, 0),
091                Vector2D.of(1, 0)), precision);
092        tree.insert(path);
093
094        final RegionNode2D h = c.getMinus();
095        final RegionNode2D i = c.getPlus();
096        final RegionNode2D j = h.getMinus();
097        final RegionNode2D k = h.getPlus();
098
099        nodeNames.put(h, "h");
100        nodeNames.put(i, "i");
101        nodeNames.put(j, "j");
102        nodeNames.put(k, "k");
103        svgWriter.write(tree, nodeNames, new File(outputFolder, String.format(OUTPUT_FILE_FORMAT, ++cutCount)));
104    }
105}