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}