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