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.euclidean.twod.path;
    18
    19  import java.util.Collection;
    20  import java.util.List;
    21
    22  import org.apache.commons.geometry.euclidean.twod.Line;
    23  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    24  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    25
    26  /** Line subset connector that selects between multiple connection options
    27   * based on the resulting interior angle. An interior angle in this
    28   * case is the angle created between an incoming line subset and an outgoing
    29   * line subset as measured on the minus (interior) side of the incoming line.
    30   * If looking along the direction of the incoming line subset, smaller interior
    31   * angles point more to the left and larger ones point more to the right.
    32   *
    33   * <p>This class provides two concrete implementations: {@link Maximize} and
    34   * {@link Minimize}, which choose connections with the largest or smallest interior
    35   * angles respectively.
    36   * </p>
    37   */
    38  public abstract class InteriorAngleLinePathConnector extends AbstractLinePathConnector {
    39      /** {@inheritDoc} */
    40      @Override
    41      protected ConnectableLineSubset selectConnection(final ConnectableLineSubset incoming,
    42              final List<ConnectableLineSubset> outgoing) {
    43
    44          // search for the best connection
    45          final Line incomingLine = incoming.getLineSubset().getLine();
    46
    47          double selectedInteriorAngle = Double.POSITIVE_INFINITY;
    48          ConnectableLineSubset selected = null;
    49
    50          for (final ConnectableLineSubset candidate : outgoing) {
    51              final double interiorAngle =
    52                      PlaneAngleRadians.PI - incomingLine.angle(candidate.getLineSubset().getLine());
    53
    54              if (selected == null || isBetterAngle(interiorAngle, selectedInteriorAngle)) {
    55                  selectedInteriorAngle = interiorAngle;
    56                  selected = candidate;
    57              }
    58          }
    59
    60          return selected;
    61      }
    62
    63      /** Return true if {@code newAngle} represents a better interior angle than {@code previousAngle}.
    64       * @param newAngle the new angle under consideration
    65       * @param previousAngle the previous best angle
    66       * @return true if {@code newAngle} represents a better interior angle than {@code previousAngle}
    67       */
    68      protected abstract boolean isBetterAngle(double newAngle, double previousAngle);
    69
    70      /** Convenience method for connecting a collection of line subsets with interior angles
    71       * maximized when possible. This method is equivalent to {@code new Maximize().connect(subsets)}.
    72       * @param subsets line subsets to connect
    73       * @return a list of connected line subset paths
    74       * @see Maximize
    75       */
    76      public static List<LinePath> connectMaximized(final Collection<LineConvexSubset> subsets) {
    77          return new Maximize().connectAll(subsets);
    78      }
    79
    80      /** Convenience method for connecting a collection of line subsets with interior angles minimized
    81       * when possible. This method is equivalent to {@code new Minimize().connect(subsets)}.
    82       * @param subsets line subsets to connect
    83       * @return a list of connected line subset paths
    84       * @see Minimize
    85       */
    86      public static List<LinePath> connectMinimized(final Collection<LineConvexSubset> subsets) {
    87          return new Minimize().connectAll(subsets);
    88      }
    89
    90      /** Implementation of {@link InteriorAngleLinePathConnector} that chooses line subset
    91       * connections that produce the largest interior angles. Another way to visualize this is
    92       * that when presented multiple connection options for a given line subset, this class will
    93       * choose the option that points most to the right when viewed in the direction of the incoming
    94       * line subset.
    95       */
    96      public static final class Maximize extends InteriorAngleLinePathConnector {
    97          /** {@inheritDoc} */
    98          @Override
    99          protected boolean isBetterAngle(final double newAngle, final double previousAngle) {
    100             return newAngle > previousAngle;
    101         }
    102     }
    103
    104     /** Implementation of {@link InteriorAngleLinePathConnector} that chooses line subset
    105      * connections that produce the smallest interior angles. Another way to visualize this is
    106      * that when presented multiple connection options for a given line subset, this class will
    107      * choose the option that points most to the left when viewed in the direction of the incoming
    108      * line subset.
    109      */
    110     public static final class Minimize extends InteriorAngleLinePathConnector {
    111         /** {@inheritDoc} */
    112         @Override
    113         protected boolean isBetterAngle(final double newAngle, final double previousAngle) {
    114             return newAngle < previousAngle;
    115         }
    116     }
    117 }