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.ArrayList;
    20  import java.util.List;
    21  import java.util.Objects;
    22
    23  import org.apache.commons.geometry.euclidean.internal.AbstractPathConnector;
    24  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    25  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    26  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    27
    28  /** Abstract class for joining collections of line subsets into connected
    29   * paths. This class is not thread-safe.
    30   */
    31  public abstract class AbstractLinePathConnector
    32      extends AbstractPathConnector<AbstractLinePathConnector.ConnectableLineSubset> {
    33      /** Add a line subset to the connector, leaving it unconnected until a later call to
    34       * to {@link #connect(Iterable)} or {@link #connectAll()}.
    35       * @param subset line subset to add
    36       * @see #connect(Iterable)
    37       * @see #connectAll()
    38       */
    39      public void add(final LineConvexSubset subset) {
    40          addPathElement(new ConnectableLineSubset(subset));
    41      }
    42
    43      /** Add a collection of line subsets to the connector, leaving them unconnected
    44       * until a later call to {@link #connect(Iterable)} or
    45       * {@link #connectAll()}.
    46       * @param subsets line subsets to add
    47       * @see #connect(Iterable)
    48       * @see #connectAll()
    49       * @see #add(LineConvexSubset)
    50       */
    51      public void add(final Iterable<LineConvexSubset> subsets) {
    52          for (final LineConvexSubset subset : subsets) {
    53              add(subset);
    54          }
    55      }
    56
    57      /** Add a collection of line subsets to the connector and attempt to connect each new
    58       * line subset with existing subsets. Connections made at this time will not be
    59       * overwritten by subsequent calls to this or other connection methods.
    60       * (eg, {@link #connectAll()}).
    61       *
    62       * <p>The connector is not reset by this call. Additional line subsets can still be added
    63       * to the current set of paths.</p>
    64       * @param subsets line subsets to connect
    65       * @see #connectAll()
    66       */
    67      public void connect(final Iterable<LineConvexSubset> subsets) {
    68          final List<ConnectableLineSubset> newEntries = new ArrayList<>();
    69
    70          for (final LineConvexSubset subset : subsets) {
    71              newEntries.add(new ConnectableLineSubset(subset));
    72          }
    73
    74          connectPathElements(newEntries);
    75      }
    76
    77      /** Add the given line subsets to this instance and connect all current
    78       * subsets into connected paths. This call is equivalent to
    79       * <pre>
    80       *      connector.add(subsets);
    81       *      List&lt;LinePath&gt; result = connector.connectAll();
    82       * </pre>
    83       *
    84       * <p>The connector is reset after this call. Further calls to
    85       * add or connect line subsets will result in new paths being generated.</p>
    86       * @param subsets line subsets to add
    87       * @return the connected 2D paths
    88       * @see #add(Iterable)
    89       * @see #connectAll()
    90       */
    91      public List<LinePath> connectAll(final Iterable<LineConvexSubset> subsets) {
    92          add(subsets);
    93          return connectAll();
    94      }
    95
    96      /** Connect all current line subsets into connected paths, returning the result as a
    97       * list of line paths.
    98       *
    99       * <p>The connector is reset after this call. Further calls to
    100      * add or connect line subsets will result in new paths being generated.</p>
    101      * @return the connected 2D paths
    102      */
    103     public List<LinePath> connectAll() {
    104         final List<ConnectableLineSubset> roots = computePathRoots();
    105         final List<LinePath> paths = new ArrayList<>(roots.size());
    106
    107         for (final ConnectableLineSubset root : roots) {
    108             paths.add(toPath(root));
    109         }
    110
    111         return paths;
    112     }
    113
    114     /** Convert the linked list of path elements starting at the argument
    115      * into a {@link LinePath}.
    116      * @param root root of a connected path linked list
    117      * @return a line path representing the linked list path
    118      */
    119     private LinePath toPath(final ConnectableLineSubset root) {
    120         final LinePath.Builder builder = LinePath.builder(null);
    121
    122         builder.append(root.getLineSubset());
    123
    124         ConnectableLineSubset current = root.getNext();
    125
    126         while (current != null && current != root) {
    127             builder.append(current.getLineSubset());
    128             current = current.getNext();
    129         }
    130
    131         return builder.build();
    132     }
    133
    134     /** Internal class used to connect line subsets together.
    135      */
    136     protected static class ConnectableLineSubset
    137         extends AbstractPathConnector.ConnectableElement<ConnectableLineSubset> {
    138         /** Line subset start point. This will be used to connect to other path elements. */
    139         private final Vector2D start;
    140
    141         /** Line subset for the entry. */
    142         private final LineConvexSubset subset;
    143
    144         /** Create a new instance with the given start point. This constructor is
    145          * intended only for performing searches for other path elements.
    146          * @param start start point
    147          */
    148         public ConnectableLineSubset(final Vector2D start) {
    149             this(start, null);
    150         }
    151
    152         /** Create a new instance from the given line subset.
    153          * @param subset subset instance
    154          */
    155         public ConnectableLineSubset(final LineConvexSubset subset) {
    156             this(subset.getStartPoint(), subset);
    157         }
    158
    159         /** Create a new instance with the given start point and line subset.
    160          * @param start start point
    161          * @param subset line subset instance
    162          */
    163         private ConnectableLineSubset(final Vector2D start, final LineConvexSubset subset) {
    164             this.start = start;
    165             this.subset = subset;
    166         }
    167
    168         /** Get the line subset for this instance.
    169          * @return the line subset for this instance
    170          */
    171         public LineConvexSubset getLineSubset() {
    172             return subset;
    173         }
    174
    175         /** {@inheritDoc} */
    176         @Override
    177         public boolean hasStart() {
    178             return start != null;
    179         }
    180
    181         /** {@inheritDoc} */
    182         @Override
    183         public boolean hasEnd() {
    184             return subset != null && subset.getEndPoint() != null;
    185         }
    186
    187         /** Return true if this instance has a size equivalent to zero.
    188          * @return true if this instance has a size equivalent to zero.
    189          */
    190         public boolean hasZeroSize() {
    191             return subset != null && subset.getPrecision().eqZero(subset.getSize());
    192         }
    193
    194         /** {@inheritDoc} */
    195         @Override
    196         public boolean endPointsEq(final ConnectableLineSubset other) {
    197             if (hasEnd() && other.hasEnd()) {
    198                 return subset.getEndPoint()
    199                         .eq(other.subset.getEndPoint(), subset.getPrecision());
    200             }
    201
    202             return false;
    203         }
    204
    205         /** {@inheritDoc} */
    206         @Override
    207         public boolean canConnectTo(final ConnectableLineSubset next) {
    208             final Vector2D end = subset.getEndPoint();
    209             final Vector2D nextStart = next.start;
    210
    211             return end != null && nextStart != null &&
    212                     end.eq(nextStart, subset.getPrecision());
    213         }
    214
    215         /** {@inheritDoc} */
    216         @Override
    217         public double getRelativeAngle(final ConnectableLineSubset next) {
    218             return subset.getLine().angle(next.getLineSubset().getLine());
    219         }
    220
    221         /** {@inheritDoc} */
    222         @Override
    223         public ConnectableLineSubset getConnectionSearchKey() {
    224             return new ConnectableLineSubset(subset.getEndPoint());
    225         }
    226
    227         /** {@inheritDoc} */
    228         @Override
    229         public boolean shouldContinueConnectionSearch(final ConnectableLineSubset candidate, final boolean ascending) {
    230
    231             if (candidate.hasStart()) {
    232                 final double candidateX = candidate.getLineSubset().getStartPoint().getX();
    233                 final double thisX = subset.getEndPoint().getX();
    234                 final int cmp = subset.getPrecision().compare(candidateX, thisX);
    235
    236                 return ascending ? cmp <= 0 : cmp >= 0;
    237             }
    238
    239             return true;
    240         }
    241
    242         /** {@inheritDoc} */
    243         @Override
    244         public int compareTo(final ConnectableLineSubset other) {
    245             // sort by coordinates
    246             int cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(start, other.start);
    247             if (cmp == 0) {
    248                 // sort entries without line subsets before ones with
    249                 final boolean thisHasSubset = subset != null;
    250                 final boolean otherHasSubset = other.subset != null;
    251
    252                 cmp = Boolean.compare(thisHasSubset, otherHasSubset);
    253
    254                 if (cmp == 0 && thisHasSubset) {
    255                     // place point-like line subsets before ones with non-zero length
    256                     cmp = Boolean.compare(this.hasZeroSize(), other.hasZeroSize());
    257
    258                     if (cmp == 0) {
    259                         // sort by line angle
    260                         final double aAngle = PlaneAngleRadians.normalizeBetweenMinusPiAndPi(
    261                                 this.getLineSubset().getLine().getAngle());
    262                         final double bAngle = PlaneAngleRadians.normalizeBetweenMinusPiAndPi(
    263                                 other.getLineSubset().getLine().getAngle());
    264
    265                         cmp = Double.compare(aAngle, bAngle);
    266                     }
    267                 }
    268             }
    269             return cmp;
    270         }
    271
    272         /** {@inheritDoc} */
    273         @Override
    274         public int hashCode() {
    275             return Objects.hash(start, subset);
    276         }
    277
    278         /** {@inheritDoc} */
    279         @Override
    280         public boolean equals(final Object obj) {
    281             if (this == obj) {
    282                 return true;
    283             }
    284             if (obj == null || !this.getClass().equals(obj.getClass())) {
    285                 return false;
    286             }
    287
    288             final ConnectableLineSubset other = (ConnectableLineSubset) obj;
    289             return Objects.equals(this.start, other.start) &&
    290                     Objects.equals(this.subset, other.subset);
    291         }
    292
    293         /** {@inheritDoc} */
    294         @Override
    295         protected ConnectableLineSubset getSelf() {
    296             return this;
    297         }
    298     }
    299 }