X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.5.0/lucene/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java diff --git a/lucene-java-3.5.0/lucene/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java b/lucene-java-3.5.0/lucene/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java new file mode 100644 index 0000000..e8e6571 --- /dev/null +++ b/lucene-java-3.5.0/lucene/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java @@ -0,0 +1,234 @@ +/** + * 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. + * + *

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