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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.euclidean.twod;
23
24 import java.util.List;
25
26 import org.hipparchus.fraction.BigFraction;
27 import org.hipparchus.geometry.enclosing.EnclosingBall;
28 import org.hipparchus.geometry.enclosing.SupportBallGenerator;
29 import org.hipparchus.util.FastMath;
30
31 /** Class generating an enclosing ball from its support points.
32 */
33 public class DiskGenerator implements SupportBallGenerator<Euclidean2D, Vector2D> {
34
35 /** Empty constructor.
36 * <p>
37 * This constructor is not strictly necessary, but it prevents spurious
38 * javadoc warnings with JDK 18 and later.
39 * </p>
40 * @since 3.0
41 */
42 public DiskGenerator() { // NOPMD - unnecessary constructor added intentionally to make javadoc happy
43 // nothing to do
44 }
45
46 /** {@inheritDoc} */
47 @Override
48 public EnclosingBall<Euclidean2D, Vector2D> ballOnSupport(final List<Vector2D> support) {
49
50 if (support.isEmpty()) {
51 return new EnclosingBall<>(Vector2D.ZERO, Double.NEGATIVE_INFINITY);
52 } else {
53 final Vector2D vA = support.get(0);
54 if (support.size() < 2) {
55 return new EnclosingBall<>(vA, 0, vA);
56 } else {
57 final Vector2D vB = support.get(1);
58 if (support.size() < 3) {
59 final Vector2D center = new Vector2D(0.5, vA, 0.5, vB);
60
61 // we could have computed r directly from the vA and vB
62 // (it was done this way up to Hipparchus 1.0), but as center
63 // is approximated in the computation above, it is better to
64 // take the final value of center and compute r from the distances
65 // to center of all support points, using a max to ensure all support
66 // points belong to the ball
67 // see <https://github.com/Hipparchus-Math/hipparchus/issues/20>
68 final double r = FastMath.max(Vector2D.distance(vA, center),
69 Vector2D.distance(vB, center));
70 return new EnclosingBall<>(center, r, vA, vB);
71
72 } else {
73 final Vector2D vC = support.get(2);
74 // a disk is 2D can be defined as:
75 // (1) (x - x_0)^2 + (y - y_0)^2 = r^2
76 // which can be written:
77 // (2) (x^2 + y^2) - 2 x_0 x - 2 y_0 y + (x_0^2 + y_0^2 - r^2) = 0
78 // or simply:
79 // (3) (x^2 + y^2) + a x + b y + c = 0
80 // with disk center coordinates -a/2, -b/2
81 // If the disk exists, a, b and c are a non-zero solution to
82 // [ (x^2 + y^2 ) x y 1 ] [ 1 ] [ 0 ]
83 // [ (xA^2 + yA^2) xA yA 1 ] [ a ] [ 0 ]
84 // [ (xB^2 + yB^2) xB yB 1 ] * [ b ] = [ 0 ]
85 // [ (xC^2 + yC^2) xC yC 1 ] [ c ] [ 0 ]
86 // So the determinant of the matrix is zero. Computing this determinant
87 // by expanding it using the minors m_ij of first row leads to
88 // (4) m_11 (x^2 + y^2) - m_12 x + m_13 y - m_14 = 0
89 // So by identifying equations (2) and (4) we get the coordinates
90 // of center as:
91 // x_0 = +m_12 / (2 m_11)
92 // y_0 = -m_13 / (2 m_11)
93 // Note that the minors m_11, m_12 and m_13 all have the last column
94 // filled with 1.0, hence simplifying the computation
95 final BigFraction[] c2 = {
96 new BigFraction(vA.getX()), new BigFraction(vB.getX()), new BigFraction(vC.getX())
97 };
98 final BigFraction[] c3 = {
99 new BigFraction(vA.getY()), new BigFraction(vB.getY()), new BigFraction(vC.getY())
100 };
101 final BigFraction[] c1 = {
102 c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])),
103 c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])),
104 c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2]))
105 };
106 final BigFraction twoM11 = minor(c2, c3).multiply(2);
107 final BigFraction m12 = minor(c1, c3);
108 final BigFraction m13 = minor(c1, c2);
109 final Vector2D center = new Vector2D( m12.divide(twoM11).doubleValue(),
110 -m13.divide(twoM11).doubleValue());
111
112 // we could have computed r directly from the minors above
113 // (it was done this way up to Hipparchus 1.0), but as center
114 // is approximated in the computation above, it is better to
115 // take the final value of center and compute r from the distances
116 // to center of all support points, using a max to ensure all support
117 // points belong to the ball
118 // see <https://github.com/Hipparchus-Math/hipparchus/issues/20>
119 final double r = FastMath.max(Vector2D.distance(vA, center),
120 FastMath.max(Vector2D.distance(vB, center),
121 Vector2D.distance(vC, center)));
122 return new EnclosingBall<>(center, r, vA, vB, vC);
123
124 }
125 }
126 }
127 }
128
129 /** Compute a dimension 3 minor, when 3<sup>d</sup> column is known to be filled with 1.0.
130 * @param c1 first column
131 * @param c2 second column
132 * @return value of the minor computed has an exact fraction
133 */
134 private BigFraction minor(final BigFraction[] c1, final BigFraction[] c2) {
135 return c2[0].multiply(c1[2].subtract(c1[1])).
136 add(c2[1].multiply(c1[0].subtract(c1[2]))).
137 add(c2[2].multiply(c1[1].subtract(c1[0])));
138 }
139
140 }