home | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Lucene example source code file (Ellipse.java)

This example Lucene source code file (Ellipse.java) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Java - Lucene tags/keywords

ellipse, ellipse, geometry2d, intersectcase, linesegment, linesegment, point2d, point2d, sqr, sqr, unsupportedoperationexception

The Lucene Ellipse.java source code

/**
 * 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>NOTE: This API is still in
 * flux and might change in incompatible ways in the next
 * release.</font>
 */
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();
  }

}

Other Lucene examples (source code examples)

Here is a short list of links related to this Lucene Ellipse.java source code file:



my book on functional programming

 

new blog posts

 

Copyright 1998-2019 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.