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.twod.path;
018
019import java.util.Collection;
020import java.util.List;
021
022import org.apache.commons.geometry.euclidean.twod.Line;
023import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
024
025/** Line subset connector that selects between multiple connection options
026 * based on the resulting interior angle. An interior angle in this
027 * case is the angle created between an incoming line subset and an outgoing
028 * line subset as measured on the minus (interior) side of the incoming line.
029 * If looking along the direction of the incoming line subset, smaller interior
030 * angles point more to the left and larger ones point more to the right.
031 *
032 * <p>This class provides two concrete implementations: {@link Maximize} and
033 * {@link Minimize}, which choose connections with the largest or smallest interior
034 * angles respectively.
035 * </p>
036 */
037public abstract class InteriorAngleLinePathConnector extends AbstractLinePathConnector {
038    /** {@inheritDoc} */
039    @Override
040    protected ConnectableLineSubset selectConnection(final ConnectableLineSubset incoming,
041            final List<ConnectableLineSubset> outgoing) {
042
043        // search for the best connection
044        final Line incomingLine = incoming.getLineSubset().getLine();
045
046        double selectedInteriorAngle = Double.POSITIVE_INFINITY;
047        ConnectableLineSubset selected = null;
048
049        for (final ConnectableLineSubset candidate : outgoing) {
050            final double interiorAngle =
051                    Math.PI - incomingLine.angle(candidate.getLineSubset().getLine());
052
053            if (selected == null || isBetterAngle(interiorAngle, selectedInteriorAngle)) {
054                selectedInteriorAngle = interiorAngle;
055                selected = candidate;
056            }
057        }
058
059        return selected;
060    }
061
062    /** Return true if {@code newAngle} represents a better interior angle than {@code previousAngle}.
063     * @param newAngle the new angle under consideration
064     * @param previousAngle the previous best angle
065     * @return true if {@code newAngle} represents a better interior angle than {@code previousAngle}
066     */
067    protected abstract boolean isBetterAngle(double newAngle, double previousAngle);
068
069    /** Convenience method for connecting a collection of line subsets with interior angles
070     * maximized when possible. This method is equivalent to {@code new Maximize().connect(subsets)}.
071     * @param subsets line subsets to connect
072     * @return a list of connected line subset paths
073     * @see Maximize
074     */
075    public static List<LinePath> connectMaximized(final Collection<LineConvexSubset> subsets) {
076        return new Maximize().connectAll(subsets);
077    }
078
079    /** Convenience method for connecting a collection of line subsets with interior angles minimized
080     * when possible. This method is equivalent to {@code new Minimize().connect(subsets)}.
081     * @param subsets line subsets to connect
082     * @return a list of connected line subset paths
083     * @see Minimize
084     */
085    public static List<LinePath> connectMinimized(final Collection<LineConvexSubset> subsets) {
086        return new Minimize().connectAll(subsets);
087    }
088
089    /** Implementation of {@link InteriorAngleLinePathConnector} that chooses line subset
090     * connections that produce the largest interior angles. Another way to visualize this is
091     * that when presented multiple connection options for a given line subset, this class will
092     * choose the option that points most to the right when viewed in the direction of the incoming
093     * line subset.
094     */
095    public static final class Maximize extends InteriorAngleLinePathConnector {
096        /** {@inheritDoc} */
097        @Override
098        protected boolean isBetterAngle(final double newAngle, final double previousAngle) {
099            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}