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.enclosing.euclidean.twod;
    18
    19  import java.util.Arrays;
    20  import java.util.Collections;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.enclosing.EnclosingBall;
    24  import org.apache.commons.geometry.enclosing.SupportBallGenerator;
    25  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    26  import org.apache.commons.numbers.fraction.BigFraction;
    27
    28  /** Class generating a disk from its support points.
    29   */
    30  public class DiskGenerator implements SupportBallGenerator<Vector2D> {
    31
    32      /** {@inheritDoc} */
    33      @Override
    34      public EnclosingBall<Vector2D> ballOnSupport(final List<Vector2D> support) {
    35          if (support.isEmpty()) {
    36              return new EnclosingBall<>(Vector2D.ZERO, Double.NEGATIVE_INFINITY, Collections.emptyList());
    37          }
    38          final Vector2D vA = support.get(0);
    39          if (support.size() < 2) {
    40              return new EnclosingBall<>(vA, 0, Collections.singletonList(vA));
    41          }
    42          final Vector2D vB = support.get(1);
    43          if (support.size() < 3) {
    44              return new EnclosingBall<>(Vector2D.linearCombination(0.5, vA, 0.5, vB),
    45                                         0.5 * vA.distance(vB),
    46                                         Arrays.asList(vA, vB));
    47          }
    48          final Vector2D vC = support.get(2);
    49          // a disk is 2D can be defined as:
    50          // (1)   (x - x_0)^2 + (y - y_0)^2 = r^2
    51          // which can be written:
    52          // (2)   (x^2 + y^2) - 2 x_0 x - 2 y_0 y + (x_0^2 + y_0^2 - r^2) = 0
    53          // or simply:
    54          // (3)   (x^2 + y^2) + a x + b y + c = 0
    55          // with disk center coordinates -a/2, -b/2
    56          // If the disk exists, a, b and c are a non-zero solution to
    57          // [ (x^2  + y^2 )   x    y   1 ]   [ 1 ]   [ 0 ]
    58          // [ (xA^2 + yA^2)   xA   yA  1 ]   [ a ]   [ 0 ]
    59          // [ (xB^2 + yB^2)   xB   yB  1 ] * [ b ] = [ 0 ]
    60          // [ (xC^2 + yC^2)   xC   yC  1 ]   [ c ]   [ 0 ]
    61          // So the determinant of the matrix is zero. Computing this determinant
    62          // by expanding it using the minors m_ij of first row leads to
    63          // (4)   m_11 (x^2 + y^2) - m_12 x + m_13 y - m_14 = 0
    64          // So by identifying equations (2) and (4) we get the coordinates
    65          // of center as:
    66          //      x_0 = +m_12 / (2 m_11)
    67          //      y_0 = -m_13 / (2 m_11)
    68          // Note that the minors m_11, m_12 and m_13 all have the last column
    69          // filled with 1.0, hence simplifying the computation
    70          final BigFraction[] c2 = {
    71              BigFraction.from(vA.getX()), BigFraction.from(vB.getX()), BigFraction.from(vC.getX())
    72          };
    73          final BigFraction[] c3 = {
    74              BigFraction.from(vA.getY()), BigFraction.from(vB.getY()), BigFraction.from(vC.getY())
    75          };
    76          final BigFraction[] c1 = {
    77              c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])),
    78              c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])),
    79              c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2]))
    80          };
    81          final BigFraction twoM11 = minor(c2, c3).multiply(2);
    82          final BigFraction m12 = minor(c1, c3);
    83          final BigFraction m13 = minor(c1, c2);
    84          final BigFraction centerX = m12.divide(twoM11);
    85          final BigFraction centerY = m13.divide(twoM11).negate();
    86          final BigFraction dx = c2[0].subtract(centerX);
    87          final BigFraction dy = c3[0].subtract(centerY);
    88          final BigFraction r2 = dx.multiply(dx).add(dy.multiply(dy));
    89          return new EnclosingBall<>(Vector2D.of(centerX.doubleValue(),
    90                                                 centerY.doubleValue()),
    91                                     Math.sqrt(r2.doubleValue()),
    92                                     Arrays.asList(vA, vB, vC));
    93      }
    94
    95      /** Compute a dimension 3 minor, when 3<sup>d</sup> column is known to be filled with 1.0.
    96       * @param c1 first column
    97       * @param c2 second column
    98       * @return value of the minor computed has an exact fraction
    99       */
    100     private BigFraction minor(final BigFraction[] c1, final BigFraction[] c2) {
    101         return c2[0].multiply(c1[2].subtract(c1[1])).
    102             add(c2[1].multiply(c1[0].subtract(c1[2]))).
    103             add(c2[2].multiply(c1[1].subtract(c1[0])));
    104     }
    105 }