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.math3.geometry.euclidean.twod; 018 019import java.util.List; 020 021import org.apache.commons.math3.fraction.BigFraction; 022import org.apache.commons.math3.geometry.enclosing.EnclosingBall; 023import org.apache.commons.math3.geometry.enclosing.SupportBallGenerator; 024import org.apache.commons.math3.util.FastMath; 025 026/** Class generating an enclosing ball from its support points. 027 * @since 3.3 028 */ 029public class DiskGenerator implements SupportBallGenerator<Euclidean2D, Vector2D> { 030 031 /** {@inheritDoc} */ 032 public EnclosingBall<Euclidean2D, Vector2D> ballOnSupport(final List<Vector2D> support) { 033 034 if (support.size() < 1) { 035 return new EnclosingBall<Euclidean2D, Vector2D>(Vector2D.ZERO, Double.NEGATIVE_INFINITY); 036 } else { 037 final Vector2D vA = support.get(0); 038 if (support.size() < 2) { 039 return new EnclosingBall<Euclidean2D, Vector2D>(vA, 0, vA); 040 } else { 041 final Vector2D vB = support.get(1); 042 if (support.size() < 3) { 043 return new EnclosingBall<Euclidean2D, Vector2D>(new Vector2D(0.5, vA, 0.5, vB), 044 0.5 * vA.distance(vB), 045 vA, vB); 046 } else { 047 final Vector2D vC = support.get(2); 048 // a disk is 2D can be defined as: 049 // (1) (x - x_0)^2 + (y - y_0)^2 = r^2 050 // which can be written: 051 // (2) (x^2 + y^2) - 2 x_0 x - 2 y_0 y + (x_0^2 + y_0^2 - r^2) = 0 052 // or simply: 053 // (3) (x^2 + y^2) + a x + b y + c = 0 054 // with disk center coordinates -a/2, -b/2 055 // If the disk exists, a, b and c are a non-zero solution to 056 // [ (x^2 + y^2 ) x y 1 ] [ 1 ] [ 0 ] 057 // [ (xA^2 + yA^2) xA yA 1 ] [ a ] [ 0 ] 058 // [ (xB^2 + yB^2) xB yB 1 ] * [ b ] = [ 0 ] 059 // [ (xC^2 + yC^2) xC yC 1 ] [ c ] [ 0 ] 060 // So the determinant of the matrix is zero. Computing this determinant 061 // by expanding it using the minors m_ij of first row leads to 062 // (4) m_11 (x^2 + y^2) - m_12 x + m_13 y - m_14 = 0 063 // So by identifying equations (2) and (4) we get the coordinates 064 // of center as: 065 // x_0 = +m_12 / (2 m_11) 066 // y_0 = -m_13 / (2 m_11) 067 // Note that the minors m_11, m_12 and m_13 all have the last column 068 // filled with 1.0, hence simplifying the computation 069 final BigFraction[] c2 = new BigFraction[] { 070 new BigFraction(vA.getX()), new BigFraction(vB.getX()), new BigFraction(vC.getX()) 071 }; 072 final BigFraction[] c3 = new BigFraction[] { 073 new BigFraction(vA.getY()), new BigFraction(vB.getY()), new BigFraction(vC.getY()) 074 }; 075 final BigFraction[] c1 = new BigFraction[] { 076 c2[0].multiply(c2[0]).add(c3[0].multiply(c3[0])), 077 c2[1].multiply(c2[1]).add(c3[1].multiply(c3[1])), 078 c2[2].multiply(c2[2]).add(c3[2].multiply(c3[2])) 079 }; 080 final BigFraction twoM11 = minor(c2, c3).multiply(2); 081 final BigFraction m12 = minor(c1, c3); 082 final BigFraction m13 = minor(c1, c2); 083 final BigFraction centerX = m12.divide(twoM11); 084 final BigFraction centerY = m13.divide(twoM11).negate(); 085 final BigFraction dx = c2[0].subtract(centerX); 086 final BigFraction dy = c3[0].subtract(centerY); 087 final BigFraction r2 = dx.multiply(dx).add(dy.multiply(dy)); 088 return new EnclosingBall<Euclidean2D, Vector2D>(new Vector2D(centerX.doubleValue(), 089 centerY.doubleValue()), 090 FastMath.sqrt(r2.doubleValue()), 091 vA, vB, vC); 092 } 093 } 094 } 095 } 096 097 /** Compute a dimension 3 minor, when 3<sup>d</sup> column is known to be filled with 1.0. 098 * @param c1 first column 099 * @param c2 second column 100 * @return value of the minor computed has an exact fraction 101 */ 102 private BigFraction minor(final BigFraction[] c1, final BigFraction[] c2) { 103 return c2[0].multiply(c1[2].subtract(c1[1])). 104 add(c2[1].multiply(c1[0].subtract(c1[2]))). 105 add(c2[2].multiply(c1[1].subtract(c1[0]))); 106 } 107 108}