agoss94 commented on code in PR #225: URL: https://github.com/apache/commons-geometry/pull/225#discussion_r1404368676
########## commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/hull/ConvexHull3D.java: ########## @@ -0,0 +1,697 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.geometry.euclidean.threed.hull; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.stream.Collectors; + +import org.apache.commons.geometry.core.ConvexHull; +import org.apache.commons.geometry.core.collection.PointSet; +import org.apache.commons.geometry.euclidean.EuclideanCollections; +import org.apache.commons.geometry.euclidean.threed.ConvexPolygon3D; +import org.apache.commons.geometry.euclidean.threed.ConvexVolume; +import org.apache.commons.geometry.euclidean.threed.Plane; +import org.apache.commons.geometry.euclidean.threed.Planes; +import org.apache.commons.geometry.euclidean.threed.Vector3D; +import org.apache.commons.geometry.euclidean.threed.line.Line3D; +import org.apache.commons.geometry.euclidean.threed.line.Lines3D; +import org.apache.commons.numbers.core.Precision.DoubleEquivalence; + +/** + * This class represents a convex hull in three-dimensional Euclidean space. + */ +public class ConvexHull3D implements ConvexHull<Vector3D> { + + /** The vertices of the convex hull. */ + private final List<Vector3D> vertices; + + /** The region defined by the hull. */ + private final ConvexVolume region; + + /** A collection of all facets that form the convex volume of the hull. */ + private final Collection<ConvexPolygon3D> facets; + + /** Flag for when the hull is degenerate. */ + private final boolean isDegenerate; + + /** + * Simple constructor no validation performed. This constructor is called if the + * hull is well-formed and non-degenerative. + * + * @param facets the facets of the hull. + */ + ConvexHull3D(Collection<? extends ConvexPolygon3D> facets) { + vertices = Collections + .unmodifiableList(facets.stream().flatMap(f -> f.getVertices().stream()).collect(Collectors.toList())); + region = ConvexVolume.fromBounds(() -> facets.stream().map(ConvexPolygon3D::getPlane).iterator()); + this.facets = Collections.unmodifiableSet(new HashSet<>(facets)); + this.isDegenerate = false; + } + + /** + * Simple constructor no validation performed. No Region is formed as it is + * assumed that the hull is degenerate. + * + * @param points the given vertices of the hull. + * @param isDegenerate boolean flag + */ + ConvexHull3D(Collection<Vector3D> points, boolean isDegenerate) { + vertices = Collections.unmodifiableList(new ArrayList<>(points)); + region = null; + this.facets = Collections.emptySet(); + this.isDegenerate = isDegenerate; + } + + /** {@inheritDoc} */ + @Override + public List<Vector3D> getVertices() { + return vertices; + } + + /** {@inheritDoc} */ + @Override + public ConvexVolume getRegion() { + return region; + } + + /** + * Return a collection of all two-dimensional faces (called facets) of the + * convex hull. + * + * @return a collection of all two-dimensional faces. + */ + public Collection<? extends ConvexPolygon3D> getFacets() { + return Collections.unmodifiableCollection(facets); + } + + /** + * Return {@code true} if the hull is degenerate. + * + * @return the isDegenerate + */ + public boolean isDegenerate() { + return isDegenerate; + } + + /** + * Implementation of quick-hull algorithm by Barber, Dobkin and Huhdanpaa. The + * algorithm constructs the convex hull for a given finite set of points. + * Empirically, the number of points processed by Quickhull is proportional to + * the number of vertices in the output. The algorithm runs on an input of size + * n with r processed points in time O(n log r). We define a point of the given + * set to be extreme, if and only if the point is part of the final hull. The + * algorithm runs in multiple stages: + * <ol> + * <li>First we construct a simplex with extreme properties from the given point + * set to maximize the possibility of choosing extreme points as initial simplex + * vertices.</li> + * <li>We partition all the remaining points into outside sets. Each polygon + * face of the simplex defines a positive and negative half-space. A point can + * be assigned to the outside set of the polygon if it is an element of the + * positive half space.</li> + * <li>For each polygon-face (facet) with a non empty outside set we choose a + * point with maximal distance to the given facet.</li> + * <li>We determine all the visible facets from the given outside point and find + * a path around the horizon.</li> + * <li>We construct a new cone of polygons from the edges of the horizon to the + * outside point. All visible facets are removed and the points in the outside + * sets of the visible facets are redistributed.</li> + * <li>We repeat step 3-5 until each outside set is empty.</li> + * </ol> + */ + public static class Builder { + + /** Set of possible candidates. */ + private final PointSet<Vector3D> candidates; + + /** Precision context used to compare floating point numbers. */ + private final DoubleEquivalence precision; + + /** Simplex for testing new points and starting the algorithm. */ + private Simplex simplex; + + /** The minX, maxX, minY, maxY, minZ, maxZ points. */ + private final Vector3D[] box; + + /** + * A map which contains all the vertices of the current hull as keys and the + * associated facets as values. + */ + private Map<Vector3D, Set<Facet>> vertexToFacetMap; + + /** + * Constructor for a builder with the given precision. + * + * @param precision the given precision. + */ + public Builder(DoubleEquivalence precision) { + candidates = EuclideanCollections.pointSet3D(precision); + this.precision = precision; + vertexToFacetMap = EuclideanCollections.pointMap3D(precision); + box = new Vector3D[6]; + simplex = new Simplex(Collections.emptySet()); + } + + /** + * Appends to the point to the set of possible candidates. + * + * @param point the given point. + * @return this instance. + */ + public Builder append(Vector3D point) { + if (box[0] == null) { + box[0] = box[1] = box[2] = box[3] = box[4] = box[5] = point; + candidates.add(point); + return this; + } + boolean hasBeenModified = false; + if (box[0].getX() > point.getX()) { + box[0] = point; + hasBeenModified = true; + } + if (box[1].getX() < point.getX()) { + box[1] = point; + hasBeenModified = true; + } + if (box[2].getY() > point.getY()) { + box[2] = point; + hasBeenModified = true; + } + if (box[3].getY() < point.getY()) { + box[3] = point; + hasBeenModified = true; + } + if (box[4].getZ() > point.getZ()) { + box[4] = point; + hasBeenModified = true; + } + if (box[5].getZ() < point.getZ()) { + box[5] = point; + hasBeenModified = true; + } + candidates.add(point); + if (hasBeenModified) { Review Comment: I added a similar check as in the append(Vector3D) case. After playing around with a few approaches this seemed to be the most performant. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
