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.internal;
    18
    19  import java.util.ArrayList;
    20  import java.util.List;
    21  import java.util.NavigableSet;
    22  import java.util.TreeSet;
    23
    24  /** Abstract base class for joining unconnected path elements into connected, directional
    25   * paths. The connection algorithm is exposed as a set of protected methods, allowing subclasses
    26   * to define their own public API. Implementations must supply their own subclass of {@link ConnectableElement}
    27   * specific for the objects being connected.
    28   *
    29   * <p>The connection algorithm proceeds as follows:
    30   * <ul>
    31   *      <li>Create a sorted list of {@link ConnectableElement}s.</li>
    32   *      <li>For each element, attempt to find other elements with start points next the
    33   *      first instance's end point by calling {@link ConnectableElement#getConnectionSearchKey()} and
    34   *      using the returned instance to locate a search start location in the sorted element list.</li>
    35   *      <li>Search up through the sorted list from the start location, testing each element for possible connectivity
    36   *      with {@link ConnectableElement#canConnectTo(AbstractPathConnector.ConnectableElement)}. Collect possible
    37   *      connections in a list. Terminate the search when
    38   *      {@link ConnectableElement#shouldContinueConnectionSearch(AbstractPathConnector.ConnectableElement, boolean)}
    39   *      returns false.
    40   *      <li>Repeat the previous step searching downward through the list from the start location.</li>
    41   *      <li>Select the best connection option from the list of possible connections, using
    42   *      {@link #selectPointConnection(AbstractPathConnector.ConnectableElement, List)}
    43   *      and/or {@link #selectConnection(AbstractPathConnector.ConnectableElement, List)} when multiple possibilities
    44   *      are found.</li>
    45   *      <li>Repeat the above steps for each element. When done, the elements represent a linked list
    46   *      of connected paths.</li>
    47   * </ul>
    48   *
    49   * <p>This class is not thread-safe.</p>
    50   *
    51   * @param <E> Element type
    52   * @see ConnectableElement
    53   */
    54  public abstract class AbstractPathConnector<E extends AbstractPathConnector.ConnectableElement<E>> {
    55      /** List of path elements. */
    56      private final NavigableSet<E> pathElements = new TreeSet<>();
    57
    58      /** View of the path element set in descending order. */
    59      private final NavigableSet<E> pathElementsDescending = pathElements.descendingSet();
    60
    61      /** List used to store possible connections for the current element. */
    62      private final List<E> possibleConnections = new ArrayList<>();
    63
    64      /** List used to store possible point-like (zero-length) connections for the current element. */
    65      private final List<E> possiblePointConnections = new ArrayList<>();
    66
    67      /** Add a collection of path elements to the connector and attempt to connect each new element
    68       * with previously added ones.
    69       * @param elements path elements to connect
    70       */
    71      protected void connectPathElements(final Iterable<E> elements) {
    72          elements.forEach(this::addPathElement);
    73
    74          for (final E element : elements) {
    75              makeForwardConnection(element);
    76          }
    77      }
    78
    79      /** Add a single path element to the connector, leaving it unconnected until a later call to
    80       * to {@link #connectPathElements(Iterable)} or {@link #computePathRoots()}.
    81       * @param element value to add to the connector
    82       * @see #connectPathElements(Iterable)
    83       * @see #computePathRoots()
    84       */
    85      protected void addPathElement(final E element) {
    86          pathElements.add(element);
    87      }
    88
    89      /** Compute all connected paths and return a list of path elements representing
    90       * the roots (start locations) of each. Each returned element is the head of a
    91       * (possibly circular) linked list that follows a connected path.
    92       *
    93       * <p>The connector is reset after this call. Further calls to add elements
    94       * will result in new paths being generated.</p>
    95       * @return a list of root elements for the computed connected paths
    96       */
    97      protected List<E> computePathRoots() {
    98          for (final E element : pathElements) {
    99              followForwardConnections(element);
    100         }
    101
    102         final List<E> rootEntries = new ArrayList<>();
    103         E root;
    104         for (final E element : pathElements) {
    105             root = element.exportPath();
    106             if (root != null) {
    107                 rootEntries.add(root);
    108             }
    109         }
    110
    111         pathElements.clear();
    112         possibleConnections.clear();
    113         possiblePointConnections.clear();
    114
    115         return rootEntries;
    116     }
    117
    118     /** Find and follow forward connections from the given start element.
    119      * @param start element to begin the connection operation with
    120      */
    121     private void followForwardConnections(final E start) {
    122         E current = start;
    123
    124         while (current != null && current.hasEnd() && !current.hasNext()) {
    125             current = makeForwardConnection(current);
    126         }
    127     }
    128
    129     /** Connect the end point of the given element to the start point of another element. Returns
    130      * the newly connected element or null if no forward connection was made.
    131      * @param element element to connect
    132      * @return the next element in the path or null if no connection was made
    133      */
    134     private E makeForwardConnection(final E element) {
    135         findPossibleConnections(element);
    136
    137         E next = null;
    138
    139         // select from all available connections, handling point-like segments first
    140         if (!possiblePointConnections.isEmpty()) {
    141             next = (possiblePointConnections.size() == 1) ?
    142                     possiblePointConnections.get(0) :
    143                     selectPointConnection(element, possiblePointConnections);
    144         } else if (!possibleConnections.isEmpty()) {
    145
    146             next = (possibleConnections.size() == 1) ?
    147                     possibleConnections.get(0) :
    148                     selectConnection(element, possibleConnections);
    149         }
    150
    151         if (next != null) {
    152             element.connectTo(next);
    153         }
    154
    155         return next;
    156     }
    157
    158     /** Find possible connections for the given element and place them in the
    159      * {@link #possibleConnections} and {@link #possiblePointConnections} lists.
    160      * @param element the element to find connections for
    161      */
    162     private void findPossibleConnections(final E element) {
    163         possibleConnections.clear();
    164         possiblePointConnections.clear();
    165
    166         if (element.hasEnd()) {
    167             final E searchKey = element.getConnectionSearchKey();
    168
    169             // search up
    170             for (final E candidate : pathElements.tailSet(searchKey)) {
    171                 if (!addPossibleConnection(element, candidate) &&
    172                         !element.shouldContinueConnectionSearch(candidate, true)) {
    173                     break;
    174                 }
    175             }
    176
    177             // search down
    178             for (final E candidate : pathElementsDescending.tailSet(searchKey, false)) {
    179                 if (!addPossibleConnection(element, candidate) &&
    180                         !element.shouldContinueConnectionSearch(candidate, false)) {
    181                     break;
    182                 }
    183             }
    184         }
    185     }
    186
    187     /** Add the candidate to one of the connection lists if it represents a possible connection. Returns
    188      * true if the candidate was added, otherwise false.
    189      * @param element element to check for connections with
    190      * @param candidate candidate connection element
    191      * @return true if the candidate is a possible connection
    192      */
    193     private boolean addPossibleConnection(final E element, final E candidate) {
    194         if (element != candidate &&
    195                 !candidate.hasPrevious() &&
    196                 candidate.hasStart() &&
    197                 element.canConnectTo(candidate)) {
    198
    199             if (element.endPointsEq(candidate)) {
    200                 possiblePointConnections.add(candidate);
    201             } else {
    202                 possibleConnections.add(candidate);
    203             }
    204
    205             return true;
    206         }
    207
    208         return false;
    209     }
    210
    211     /** Method called to select a connection to use for a given element when multiple zero-length connections are
    212      * available. The algorithm here attempts to choose the point most likely to produce a logical path by selecting
    213      * the outgoing element with the smallest relative angle with the incoming element, with unconnected element
    214      * preferred over ones that are already connected (thereby allowing other connections to occur in the path).
    215      * @param incoming the incoming element
    216      * @param outgoingList list of available outgoing point-like connections
    217      * @return the connection to use
    218      */
    219     protected E selectPointConnection(final E incoming, final List<E> outgoingList) {
    220
    221         double angle;
    222         boolean isUnconnected;
    223
    224         double smallestAngle = 0.0;
    225         E bestElement = null;
    226         boolean bestIsUnconnected = false;
    227
    228         for (final E outgoing : outgoingList) {
    229             angle = Math.abs(incoming.getRelativeAngle(outgoing));
    230             isUnconnected = !outgoing.hasNext();
    231
    232             if (bestElement == null || (!bestIsUnconnected && isUnconnected) ||
    233                     (bestIsUnconnected == isUnconnected && angle < smallestAngle)) {
    234
    235                 smallestAngle = angle;
    236                 bestElement = outgoing;
    237                 bestIsUnconnected = isUnconnected;
    238             }
    239         }
    240
    241         return bestElement;
    242     }
    243
    244     /** Method called to select a connection to use for a given segment when multiple non-length-zero
    245      * connections are available. In this case, the selection of the outgoing connection depends only
    246      * on the desired characteristics of the connected path.
    247      * @param incoming the incoming segment
    248      * @param outgoing list of available outgoing connections; will always contain at least
    249      *      two elements
    250      * @return the connection to use
    251      */
    252     protected abstract E selectConnection(E incoming, List<E> outgoing);
    253
    254     /** Class used to represent connectable path elements for use with {@link AbstractPathConnector}.
    255      * Subclasses must fulfill the following requirements in order for path connection operations
    256      * to work correctly:
    257      * <ul>
    258      *      <li>Implement {@link #compareTo(Object)} such that elements are sorted by their start
    259      *      point locations. Other criteria may be used as well but elements with start points in close
    260      *      proximity must be grouped together.</li>
    261      *      <li>Implement {@link #getConnectionSearchKey()} such that it returns an instance that will be placed
    262      *      next to elements with start points close to the current instance's end point when sorted with
    263      *      {@link #compareTo(Object)}.</li>
    264      *      <li>Implement {@link #shouldContinueConnectionSearch(AbstractPathConnector.ConnectableElement, boolean)}
    265      *      such that it returns false when the search for possible connections through a sorted list of elements
    266      *      may terminate.</li>
    267      * </ul>
    268      *
    269      * @param <E> Element type
    270      * @see AbstractPathConnector
    271      */
    272     public abstract static class ConnectableElement<E extends ConnectableElement<E>>
    273         implements Comparable<E> {
    274         /** Next connected element. */
    275         private E next;
    276
    277         /** Previous connected element. */
    278         private E previous;
    279
    280         /** Flag set to true when this element has exported its value to a path. */
    281         private boolean exported;
    282
    283         /** Return true if the instance is connected to another element's start point.
    284          * @return true if the instance has a next element
    285          */
    286         public boolean hasNext() {
    287             return next != null;
    288         }
    289
    290         /** Get the next connected element in the path, if any.
    291          * @return the next connected segment in the path; may be null
    292          */
    293         public E getNext() {
    294             return next;
    295         }
    296
    297         /** Set the next connected element for this path. This is intended for
    298          * internal use only. Callers should use the {@link #connectTo(AbstractPathConnector.ConnectableElement)}
    299          * method instead.
    300          * @param next next path element
    301          */
    302         protected void setNext(final E next) {
    303             this.next = next;
    304         }
    305
    306         /** Return true if another element is connected to this instance's start point.
    307          * @return true if the instance has a previous element
    308          */
    309         public boolean hasPrevious() {
    310             return previous != null;
    311         }
    312
    313         /** Get the previous connected element in the path, if any.
    314          * @return the previous connected element in the path; may be null
    315          */
    316         public E getPrevious() {
    317             return previous;
    318         }
    319
    320         /** Set the previous connected element for this path. This is intended for
    321          * internal use only. Callers should use the {@link #connectTo(AbstractPathConnector.ConnectableElement)}
    322          * method instead.
    323          * @param previous previous path element
    324          */
    325         protected void setPrevious(final E previous) {
    326             this.previous = previous;
    327         }
    328
    329         /** Connect this instance's end point to the given element's start point. No validation
    330          * is performed in this method. The {@link #canConnectTo(AbstractPathConnector.ConnectableElement)}
    331          * method must have been called previously.
    332          * @param nextElement the next element in the path
    333          */
    334         public void connectTo(final E nextElement) {
    335             setNext(nextElement);
    336             nextElement.setPrevious(getSelf());
    337         }
    338
    339         /** Export the path that this element belongs to, returning the root
    340          * segment. This method traverses all connected element, sets their
    341          * exported flags to true, and returns the root element of the path
    342          * (or this element in the case of a loop). Each path can only be
    343          * exported once. Later calls to this method on this instance or any of its
    344          * connected elements will return null.
    345          * @return the root of the path or null if the path that this element
    346          *      belongs to has already been exported
    347          */
    348         public E exportPath() {
    349             if (markExported()) {
    350
    351                 // export the connected portions of the path, moving both
    352                 // forward and backward
    353                 E current;
    354                 E root = getSelf();
    355
    356                 // forward
    357                 current = next;
    358                 while (current != null && current.markExported()) {
    359                     current = current.getNext();
    360                 }
    361
    362                 // backward
    363                 current = previous;
    364                 while (current != null && current.markExported()) {
    365                     root = current;
    366                     current = current.getPrevious();
    367                 }
    368
    369                 return root;
    370             }
    371
    372             return null;
    373         }
    374
    375         /** Set the export flag for this instance to true. Returns true
    376          * if the flag was changed and false otherwise.
    377          * @return true if the flag was changed and false if it was
    378          *      already set to true
    379          */
    380         protected boolean markExported() {
    381             if (!exported) {
    382                 exported = true;
    383                 return true;
    384             }
    385             return false;
    386         }
    387
    388         /** Return true if this instance has a start point that can be
    389          * connected to another element's end point.
    390          * @return true if this instance has a start point that can be
    391          *      connected to another element's end point
    392          */
    393         public abstract boolean hasStart();
    394
    395         /** Return true if this instance has an end point that can be
    396          * connected to another element's start point.
    397          * @return true if this instance has an end point that can be
    398          *      connected to another element's start point
    399          */
    400         public abstract boolean hasEnd();
    401
    402         /** Return true if the end point of this instance should be considered
    403          * equivalent to the end point of the argument.
    404          * @param other element to compare end points with
    405          * @return true if this instance has an end point equivalent to that
    406          *      of the argument
    407          */
    408         public abstract boolean endPointsEq(E other);
    409
    410         /** Return true if this instance's end point can be connected to
    411          * the argument's start point.
    412          * @param nextElement candidate for the next element in the path; this value
    413          *      is guaranteed to not be null and to contain a start point
    414          * @return true if this instance's end point can be connected to
    415          *      the argument's start point
    416          */
    417         public abstract boolean canConnectTo(E nextElement);
    418
    419         /** Return the relative angle between this element and the argument.
    420          * @param other element to compute the angle with
    421          * @return the relative angle between this element and the argument
    422          */
    423         public abstract double getRelativeAngle(E other);
    424
    425         /** Get a new instance used as a search key to help locate other elements
    426          * with start points matching this instance's end point. The only restriction
    427          * on the returned instance is that it be compatible with the implementation
    428          * class' {@link #compareTo(Object)} method.
    429          * @return a new instance used to help locate other path elements with start
    430          *      points equivalent to this instance's end point
    431          */
    432         public abstract E getConnectionSearchKey();
    433
    434         /** Return true if the search for possible connections should continue through
    435          * the sorted set of possible path elements given the current candidate element
    436          * and search direction. The search operation stops for the given direction
    437          * when this method returns false.
    438          * @param candidate last tested candidate connection element
    439          * @param ascending true if the search is proceeding in an ascending direction;
    440          *      false otherwise
    441          * @return true if the connection search should continue
    442          */
    443         public abstract boolean shouldContinueConnectionSearch(E candidate, boolean ascending);
    444
    445         /** Return the current instance as the generic type.
    446          * @return the current instance as the generic type.
    447          */
    448         protected abstract E getSelf();
    449     }
    450 }