/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.lucene.spatial.geometry.shape;


/**
 * Ellipse shape. From C++ gl.
 *
 * <p><font color="red"><b>NOTE:</b> This API is still in
 * flux and might change in incompatible ways in the next
 * release.</font>
 */
@Deprecated
public class Ellipse implements Geometry2D {
  private Point2D center;

  /**
   * Half length of major axis
   */
  private double a;

  /**
   * Half length of minor axis
   */
  private double b;

  private double k1, k2, k3;

  /**
   * sin of rotation angle
   */
  private double s;

  /**
   * cos of rotation angle
   */
  private double c;

  public Ellipse() {
    center = new Point2D(0, 0);
  }

  private double SQR(double d) {
    return d * d;
  }

  /**
   * Constructor given bounding rectangle and a rotation.
   */
  public Ellipse(Point2D p1, Point2D p2, double angle) {
    center = new Point2D();

    // Set the center
    center.x((p1.x() + p2.x()) * 0.5f);
    center.y((p1.y() + p2.y()) * 0.5f);

    // Find sin and cos of the angle
    double angleRad = Math.toRadians(angle);
    c = Math.cos(angleRad);
    s = Math.sin(angleRad);

    // Find the half lengths of the semi-major and semi-minor axes
    double dx = Math.abs(p2.x() - p1.x()) * 0.5;
    double dy = Math.abs(p2.y() - p1.y()) * 0.5;
    if (dx >= dy) {
      a = dx;
      b = dy;
    } else {
      a = dy;
      b = dx;
    }

    // Find k1, k2, k3 - define when a point x,y is on the ellipse
    k1 = SQR(c / a) + SQR(s / b);
    k2 = 2 * s * c * ((1 / SQR(a)) - (1 / SQR(b)));
    k3 = SQR(s / a) + SQR(c / b);
  }

  /**
   * Determines if a line segment intersects the ellipse and if so finds the
   * point(s) of intersection.
   * 
   * @param seg
   *            Line segment to test for intersection
   * @param pt0
   *            OUT - intersection point (if it exists)
   * @param pt1
   *            OUT - second intersection point (if it exists)
   * 
   * @return Returns the number of intersection points (0, 1, or 2).
   */
  public int intersect(LineSegment seg, Point2D pt0, Point2D pt1) {
    if (pt0 == null)
      pt0 = new Point2D();
    if (pt1 == null)
      pt1 = new Point2D();

    // Solution is found by parameterizing the line segment and
    // substituting those values into the ellipse equation.
    // Results in a quadratic equation.
    double x1 = center.x();
    double y1 = center.y();
    double u1 = seg.A.x();
    double v1 = seg.A.y();
    double u2 = seg.B.x();
    double v2 = seg.B.y();
    double dx = u2 - u1;
    double dy = v2 - v1;
    double q0 = k1 * SQR(u1 - x1) + k2 * (u1 - x1) * (v1 - y1) + k3
        * SQR(v1 - y1) - 1;
    double q1 = (2 * k1 * dx * (u1 - x1)) + (k2 * dx * (v1 - y1))
        + (k2 * dy * (u1 - x1)) + (2 * k3 * dy * (v1 - y1));
    double q2 = (k1 * SQR(dx)) + (k2 * dx * dy) + (k3 * SQR(dy));

    // Compare q1^2 to 4*q0*q2 to see how quadratic solves
    double d = SQR(q1) - (4 * q0 * q2);
    if (d < 0) {
      // Roots are complex valued. Line containing the segment does
      // not intersect the ellipse
      return 0;
    }

    if (d == 0) {
      // One real-valued root - line is tangent to the ellipse
      double t = -q1 / (2 * q2);
      if (0 <= t && t <= 1) {
        // Intersection occurs along line segment
        pt0.x(u1 + t * dx);
        pt0.y(v1 + t * dy);
        return 1;
      } else
        return 0;
    } else {
      // Two distinct real-valued roots. Solve for the roots and see if
      // they fall along the line segment
      int n = 0;
      double q = Math.sqrt(d);
      double t = (-q1 - q) / (2 * q2);
      if (0 <= t && t <= 1) {
        // Intersection occurs along line segment
        pt0.x(u1 + t * dx);
        pt0.y(v1 + t * dy);
        n++;
      }

      // 2nd root
      t = (-q1 + q) / (2 * q2);
      if (0 <= t && t <= 1) {
        if (n == 0) {
          pt0.x(u1 + t * dx);
          pt0.y(v1 + t * dy);
          n++;
        } else {
          pt1.x(u1 + t * dx);
          pt1.y(v1 + t * dy);
          n++;
        }
      }
      return n;
    }
  }

  public IntersectCase intersect(Rectangle r) {
    // Test if all 4 corners of the rectangle are inside the ellipse
    Point2D ul = new Point2D(r.MinPt().x(), r.MaxPt().y());
    Point2D ur = new Point2D(r.MaxPt().x(), r.MaxPt().y());
    Point2D ll = new Point2D(r.MinPt().x(), r.MinPt().y());
    Point2D lr = new Point2D(r.MaxPt().x(), r.MinPt().y());
    if (contains(ul) && contains(ur) && contains(ll) && contains(lr))
      return IntersectCase.CONTAINS;

    // Test if any of the rectangle edges intersect
    Point2D pt0 = new Point2D(), pt1 = new Point2D();
    LineSegment bottom = new LineSegment(ll, lr);
    if (intersect(bottom, pt0, pt1) > 0)
      return IntersectCase.INTERSECTS;

    LineSegment top = new LineSegment(ul, ur);
    if (intersect(top, pt0, pt1) > 0)
      return IntersectCase.INTERSECTS;

    LineSegment left = new LineSegment(ll, ul);
    if (intersect(left, pt0, pt1) > 0)
      return IntersectCase.INTERSECTS;

    LineSegment right = new LineSegment(lr, ur);
    if (intersect(right, pt0, pt1) > 0)
      return IntersectCase.INTERSECTS;

    // Ellipse does not intersect any edge : since the case for the ellipse
    // containing the rectangle was considered above then if the center
    // is inside the ellipse is fully inside and if center is outside
    // the ellipse is fully outside
    return (r.contains(center)) ? IntersectCase.WITHIN
        : IntersectCase.OUTSIDE;
  }

  public double area() {
    throw new UnsupportedOperationException();
  }

  public Point2D centroid() {
    throw new UnsupportedOperationException();
  }

  public boolean contains(Point2D pt) {
    // Plug in equation for ellipse, If evaluates to <= 0 then the
    // point is in or on the ellipse.
    double dx = pt.x() - center.x();
    double dy = pt.y() - center.y();
    double eq=(((k1 * SQR(dx)) + (k2 * dx * dy) + (k3 * SQR(dy)) - 1));
    
    return eq<=0;
  }

  public void translate(Vector2D v) {
    throw new UnsupportedOperationException();
  }

}
