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.hull.euclidean.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Collection;
    21  import java.util.Collections;
    22  import java.util.List;
    23
    24  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    25  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    26  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    27  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    28  import org.apache.commons.geometry.hull.ConvexHull;
    29
    30  /**
    31   * This class represents a convex hull in two-dimensional Euclidean space.
    32   */
    33  public final class ConvexHull2D implements ConvexHull<Vector2D> {
    34
    35      /** Vertices for the convex hull, in order. */
    36      private final List<Vector2D> vertices;
    37
    38      /** Polyline path for the convex hull. */
    39      private final LinePath path;
    40
    41      /** Simple constructor; no validation is performed.
    42       * @param vertices the vertices of the convex hull; callers are responsible for ensuring that
    43       *      the given vertices are in order, unique, and define a convex hull.
    44       * @param precision precision context used to compare floating point numbers
    45       */
    46      ConvexHull2D(final Collection<Vector2D> vertices, final DoublePrecisionContext precision) {
    47          this.vertices = Collections.unmodifiableList(new ArrayList<>(vertices));
    48          this.path = buildHullPath(vertices, precision);
    49      }
    50
    51      /** {@inheritDoc} */
    52      @Override
    53      public List<Vector2D> getVertices() {
    54          return vertices;
    55      }
    56
    57      /** Get a path defining the convex hull. The path will contain
    58       * <ul>
    59       *      <li>zero segments if the hull consists of only a single point,</li>
    60       *      <li>one segment if the hull consists of two points,</li>
    61       *      <li>three or more segments defining a closed loop if the hull consists of more than
    62       *          two non-collinear points.</li>
    63       * </ul>
    64       * @return polyline path defining the convex hull
    65       */
    66      public LinePath getPath() {
    67          return path;
    68      }
    69
    70      /** {@inheritDoc} */
    71      @Override
    72      public ConvexArea getRegion() {
    73          return path.isClosed() ?
    74                  ConvexArea.convexPolygonFromPath(path) :
    75                  null;
    76      }
    77
    78      /** {@inheritDoc} */
    79      @Override
    80      public String toString() {
    81          final StringBuilder sb = new StringBuilder();
    82          sb.append(getClass().getSimpleName())
    83              .append("[vertices= ")
    84              .append(getVertices())
    85              .append(']');
    86
    87          return sb.toString();
    88      }
    89
    90      /** Build a polyline representing the path for a convex hull.
    91       * @param vertices convex hull vertices
    92       * @param precision precision context used to compare floating point values
    93       * @return path for the convex hull defined by the given vertices
    94       */
    95      private static LinePath buildHullPath(final Collection<Vector2D> vertices, final DoublePrecisionContext precision) {
    96          if (vertices.size() < 2) {
    97              return LinePath.empty();
    98          }
    99
    100         final boolean closeLoop = vertices.size() > 2;
    101
    102         return LinePath.builder(precision)
    103                 .appendVertices(vertices)
    104                 .build(closeLoop);
    105     }
    106 }