001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.math.geometry.shape;
031
032import org.openimaj.math.geometry.point.Point2d;
033
034/**
035 * Methods for computing the area of intersection of two ellipses.
036 * 
037 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
038 *
039 */
040public class EllipseAreaOfIntersection {
041
042        class Polynomial2{
043                
044        }
045        class Polynomial1{
046                
047        }
048        
049        class ComputedRoots{
050
051                public int numDistinctRoots;
052                public int[] multiplicity;
053                
054        }
055        
056        /**
057         * Compute area of intersection.
058         * @param E0 first ellipse.
059         * @param E1 second ellipse
060         * @return area of intersection.
061         */
062        public static double AreaOfIntersection(Ellipse E0, Ellipse E1) {
063                Polynomial2 Q0 = GetQuadraticRepresentation(E0); // Q0(x,y)
064                Polynomial2 Q1 = GetQuadraticRepresentation(E1); // Q1(x,y)
065                Polynomial1 B = GetBezoutDeterminant(Q0, Q1); // B(y)
066                // Compute the roots of B. The input to ComputeRoots is B. The output numDistinctRoots is the number of distinct
067                // real-valued roots. The output root[] stores the distinct roots, where only array elements 0 through
068                // numDistinctRoots-1 are valid. The output multiplicity[] stores the number of times the roots occur. For a
069                // distinct root, the multiplicity is 1. For a repeated root, the multiplicity is 2.
070                
071                ComputedRoots roots = ComputeRoots(B);
072                // Compute the intersection points. The points are ordered counterclockwise about their centroid.
073                Point2d[] intr = ComputeIntersections(E0, E1, Q0, Q1, roots);
074                if (roots.numDistinctRoots == 0)
075                {
076                        // Returns area(E0) [E0 is contained in E1], area(E1) [E1 is contained in E0], or zero [E0 and E1 are separated].
077                        return AreaOfIntersectionCS(E0, E1);
078                }
079                else if (roots.numDistinctRoots == 1) // multiplicity[0] must be 2.
080                {
081                        return AreaOfIntersectionCS(E0, E1);
082                }
083                else if (roots.numDistinctRoots == 2)
084                {
085                        if (roots.multiplicity[0] == 2) // Two roots, each repeated. multiplicity[1] must be 2.
086                        {
087                                return AreaOfIntersectionCS(E0, E1);
088                        }
089                        else // Two distinct roots. Region bounded by two arcs, one from each ellipse.
090                        {
091                                return AreaOfIntersection2(E0, E1, intr[0], intr[1]);
092                        }
093                }
094                else if (roots.numDistinctRoots == 3)
095                {
096                        if (roots.multiplicity[0] == 2)
097                        {
098                                return AreaOfIntersection2(E0, E1, intr[1], intr[2]);
099                        }
100                        else if (roots.multiplicity[1] == 2)
101                        {
102                                return AreaOfIntersection2(E0, E1, intr[2], intr[0]);
103                        }
104                        else // multiplicity[2] == 2
105                        {
106                                return AreaOfIntersection2(E0, E1, intr[0], intr[1]);
107                        }
108                }
109                else // numDistinctRoots == 4
110                {
111                        return AreaOfIntersection4(E0, E1, intr);
112                }
113
114        }
115        private static Point2d[] ComputeIntersections(Ellipse e0, Ellipse e1, Polynomial2 q0, Polynomial2 q1, ComputedRoots roots) {
116                // TODO Auto-generated method stub
117                return null;
118        }
119        private static double AreaOfIntersection4(Ellipse e0, Ellipse e1, Point2d[] intr) {
120                // TODO Auto-generated method stub
121                return 0;
122        }
123        private static double AreaOfIntersection2(Ellipse e0, Ellipse e1, Point2d point2d, Point2d point2d2) {
124                // TODO Auto-generated method stub
125                return 0;
126        }
127        private static double AreaOfIntersectionCS(Ellipse e0, Ellipse e1) {
128                // TODO Auto-generated method stub
129                return 0;
130        }
131        private static ComputedRoots ComputeRoots(Polynomial1 b) {
132                // TODO Auto-generated method stub
133                return null;
134        }
135        
136        private static Polynomial1 GetBezoutDeterminant(Polynomial2 q0, Polynomial2 q1) {
137                // TODO Auto-generated method stub
138                return null;
139        }
140        private static Polynomial2 GetQuadraticRepresentation(Ellipse e0) {
141                // TODO Auto-generated method stub
142                return null;
143        }
144
145}