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.euclidean.threed;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.geometry.core.Transform;
023import org.apache.commons.geometry.core.partitioning.Hyperplane;
024import org.apache.commons.geometry.core.partitioning.Split;
025import org.apache.commons.geometry.euclidean.twod.ConvexArea;
026import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
027import org.apache.commons.geometry.euclidean.twod.Vector2D;
028import org.apache.commons.geometry.euclidean.twod.rotation.Rotation2D;
029import org.apache.commons.numbers.core.Precision;
030
031/** Class representing an arbitrary subset of a plane using a {@link RegionBSPTree2D}.
032 * This class can represent convex, non-convex, finite, infinite, and empty regions.
033 *
034 * <p>This class is mutable and <em>not</em> thread safe.</p>
035 */
036public final class EmbeddedTreePlaneSubset extends AbstractEmbeddedRegionPlaneSubset {
037
038    /** The 2D region representing the area on the plane. */
039    private final RegionBSPTree2D region;
040
041    /** Construct a new, empty plane subset for the given plane.
042     * @param plane plane containing the subset
043     */
044    public EmbeddedTreePlaneSubset(final EmbeddingPlane plane) {
045        this(plane, false);
046    }
047
048    /** Construct a new subset for the given plane. If {@code full}
049     * is true, then the subset will cover the entire plane; otherwise,
050     * it will be empty.
051     * @param plane plane containing the subset
052     * @param full if true, the subset will cover the entire space;
053     *      otherwise it will be empty
054     */
055    public EmbeddedTreePlaneSubset(final EmbeddingPlane plane, final boolean full) {
056        this(plane, new RegionBSPTree2D(full));
057    }
058
059    /** Construct a new instance from its defining plane and subspace region.
060     * @param plane plane containing the subset
061     * @param region subspace region for the plane subset
062     */
063    public EmbeddedTreePlaneSubset(final EmbeddingPlane plane, final RegionBSPTree2D region) {
064        super(plane);
065
066        this.region = region;
067    }
068
069    /** {@inheritDoc} */
070    @Override
071    public PlaneSubset.Embedded getEmbedded() {
072        return this;
073    }
074
075    /** {@inheritDoc} */
076    @Override
077    public RegionBSPTree2D getSubspaceRegion() {
078        return region;
079    }
080
081    /** {@inheritDoc} */
082    @Override
083    public List<PlaneConvexSubset> toConvex() {
084        final List<ConvexArea> areas = region.toConvex();
085
086        final List<PlaneConvexSubset> facets = new ArrayList<>(areas.size());
087
088        for (final ConvexArea area : areas) {
089            facets.add(Planes.subsetFromConvexArea(getPlane(), area));
090        }
091
092        return facets;
093    }
094
095    /** {@inheritDoc} */
096    @Override
097    public List<Triangle3D> toTriangles() {
098        final EmbeddingPlane plane = getPlane();
099        final List<Triangle3D> triangles = new ArrayList<>();
100
101        List<Vector3D> vertices;
102        for (final ConvexArea area : region.toConvex()) {
103            if (area.isInfinite()) {
104                throw new IllegalStateException("Cannot convert infinite plane subset to triangles: " + this);
105            }
106
107            vertices = plane.toSpace(area.getVertices());
108
109            triangles.addAll(Planes.convexPolygonToTriangleFan(plane, vertices));
110        }
111
112        return triangles;
113    }
114
115    /** {@inheritDoc} */
116    @Override
117    public Bounds3D getBounds() {
118        return getBoundsFromSubspace(region);
119    }
120
121    /** {@inheritDoc}
122     *
123     * <p>In all cases, the current instance is not modified. However, In order to avoid
124     * unnecessary copying, this method will use the current instance as the split value when
125     * the instance lies entirely on the plus or minus side of the splitter. For example, if
126     * this instance lies entirely on the minus side of the splitter, the plane subset
127     * returned by {@link Split#getMinus()} will be this instance. Similarly, {@link Split#getPlus()}
128     * will return the current instance if it lies entirely on the plus side. Callers need to make
129     * special note of this, since this class is mutable.</p>
130     */
131    @Override
132    public Split<EmbeddedTreePlaneSubset> split(final Hyperplane<Vector3D> splitter) {
133        return Planes.subspaceSplit((Plane) splitter, this,
134            (p, r) -> new EmbeddedTreePlaneSubset(p, (RegionBSPTree2D) r));
135    }
136
137    /** {@inheritDoc} */
138    @Override
139    public EmbeddedTreePlaneSubset transform(final Transform<Vector3D> transform) {
140        final EmbeddingPlane.SubspaceTransform subTransform =
141                getPlane().getEmbedding().subspaceTransform(transform);
142
143        final RegionBSPTree2D tRegion = RegionBSPTree2D.empty();
144        tRegion.copy(region);
145        tRegion.transform(subTransform.getTransform());
146
147        return new EmbeddedTreePlaneSubset(subTransform.getPlane(), tRegion);
148    }
149
150    /** Add a plane convex subset to this instance.
151     * @param subset plane convex subset to add
152     * @throws IllegalArgumentException if the given plane subset is not from
153     *      a plane equivalent to this instance
154     */
155    public void add(final PlaneConvexSubset subset) {
156        Planes.validatePlanesEquivalent(getPlane(), subset.getPlane());
157
158        final PlaneConvexSubset.Embedded embedded = subset.getEmbedded();
159        final Rotation2D rot = getEmbeddedRegionRotation(embedded);
160
161        final ConvexArea subspaceArea = embedded.getSubspaceRegion();
162
163        final ConvexArea toAdd = rot != null ?
164                subspaceArea.transform(rot) :
165                subspaceArea;
166
167        region.add(toAdd);
168    }
169
170    /** Add a plane subset to this instance.
171     * @param subset plane subset to add
172     * @throws IllegalArgumentException if the given plane subset is not from
173     *      a plane equivalent to this instance
174     */
175    public void add(final EmbeddedTreePlaneSubset subset) {
176        Planes.validatePlanesEquivalent(getPlane(), subset.getPlane());
177
178        final RegionBSPTree2D otherTree = subset.getSubspaceRegion();
179        final Rotation2D rot = getEmbeddedRegionRotation(subset);
180
181        final RegionBSPTree2D regionToAdd;
182        if (rot != null) {
183            // we need to transform the subspace region before adding
184            regionToAdd = otherTree.copy();
185            regionToAdd.transform(rot);
186        } else {
187            regionToAdd = otherTree;
188        }
189
190        region.union(regionToAdd);
191    }
192
193    /** Construct a rotation transform used to transform the subspace of the given embedded region plane
194     * subset into the subspace of this instance. Returns null if no transform is needed. This method must only
195     * be called with embedded regions that share an equivalent plane with this instance, meaning that the
196     * planes have the same origin point and normal
197     * @param embedded the embedded region plane subset to compare with the current instance
198     * @return a rotation transform to convert from the subspace of the argument into the current subspace; returns
199     *      null if no such transform is needed
200     */
201    private Rotation2D getEmbeddedRegionRotation(final PlaneSubset.Embedded embedded) {
202        // check if we need to apply a rotation to the given embedded subspace
203        final EmbeddingPlane thisPlane = getPlane();
204        final EmbeddingPlane otherPlane = embedded.getPlane();
205
206        final Precision.DoubleEquivalence precision = thisPlane.getPrecision();
207
208        final double uDot = thisPlane.getU().dot(otherPlane.getU());
209        if (!precision.eq(uDot, 1.0)) {
210            final Vector2D otherPlaneU = thisPlane.toSubspace(otherPlane.getOrigin().add(otherPlane.getU()));
211            final double angle = Math.atan2(otherPlaneU.getY(), otherPlaneU.getX());
212
213            return Rotation2D.of(angle);
214        }
215
216        return null;
217    }
218}