You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/09/02 21:59:32 UTC
svn commit: r1700883 [4/5] - in /lucene/dev/trunk/lucene: ./
sandbox/src/java/org/apache/lucene/bkdtree/
sandbox/src/java/org/apache/lucene/rangetree/
spatial/src/java/org/apache/lucene/spatial/spatial4j/
spatial/src/test/org/apache/lucene/spatial/spat...
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,377 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits
+ *
+ * @lucene.internal
+ */
+public class XYZSolid extends BaseXYZSolid {
+
+ /** Whole world? */
+ protected final boolean isWholeWorld;
+ /** Min-X plane */
+ protected final SidedPlane minXPlane;
+ /** Max-X plane */
+ protected final SidedPlane maxXPlane;
+ /** Min-Y plane */
+ protected final SidedPlane minYPlane;
+ /** Max-Y plane */
+ protected final SidedPlane maxYPlane;
+ /** Min-Z plane */
+ protected final SidedPlane minZPlane;
+ /** Max-Z plane */
+ protected final SidedPlane maxZPlane;
+
+ /** These are the edge points of the shape, which are defined to be at least one point on
+ * each surface area boundary. In the case of a solid, this includes points which represent
+ * the intersection of XYZ bounding planes and the planet, as well as points representing
+ * the intersection of single bounding planes with the planet itself.
+ */
+ protected final GeoPoint[] edgePoints;
+
+ /** Notable points for minXPlane */
+ protected final GeoPoint[] notableMinXPoints;
+ /** Notable points for maxXPlane */
+ protected final GeoPoint[] notableMaxXPoints;
+ /** Notable points for minYPlane */
+ protected final GeoPoint[] notableMinYPoints;
+ /** Notable points for maxYPlane */
+ protected final GeoPoint[] notableMaxYPoints;
+ /** Notable points for minZPlane */
+ protected final GeoPoint[] notableMinZPoints;
+ /** Notable points for maxZPlane */
+ protected final GeoPoint[] notableMaxZPoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param minX is the minimum X value.
+ *@param maxX is the maximum X value.
+ *@param minY is the minimum Y value.
+ *@param maxY is the maximum Y value.
+ *@param minZ is the minimum Z value.
+ *@param maxZ is the maximum Z value.
+ */
+ public XYZSolid(final PlanetModel planetModel,
+ final double minX,
+ final double maxX,
+ final double minY,
+ final double maxY,
+ final double minZ,
+ final double maxZ) {
+ super(planetModel);
+ // Argument checking
+ if (maxX - minX < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("X values in wrong order or identical");
+ if (maxY - minY < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Y values in wrong order or identical");
+ if (maxZ - minZ < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Z values in wrong order or identical");
+
+ final double worldMinX = planetModel.getMinimumXValue();
+ final double worldMaxX = planetModel.getMaximumXValue();
+ final double worldMinY = planetModel.getMinimumYValue();
+ final double worldMaxY = planetModel.getMaximumYValue();
+ final double worldMinZ = planetModel.getMinimumZValue();
+ final double worldMaxZ = planetModel.getMaximumZValue();
+
+ // We must distinguish between the case where the solid represents the entire world,
+ // and when the solid has no overlap with any part of the surface. In both cases,
+ // there will be no edgepoints.
+ isWholeWorld =
+ (minX - worldMinX < -Vector.MINIMUM_RESOLUTION) &&
+ (maxX - worldMaxX > Vector.MINIMUM_RESOLUTION) &&
+ (minY - worldMinY < -Vector.MINIMUM_RESOLUTION) &&
+ (maxY - worldMaxY > Vector.MINIMUM_RESOLUTION) &&
+ (minZ - worldMinZ < -Vector.MINIMUM_RESOLUTION) &&
+ (maxZ - worldMaxZ > Vector.MINIMUM_RESOLUTION);
+
+ if (isWholeWorld) {
+ minXPlane = null;
+ maxXPlane = null;
+ minYPlane = null;
+ maxYPlane = null;
+ minZPlane = null;
+ maxZPlane = null;
+ notableMinXPoints = null;
+ notableMaxXPoints = null;
+ notableMinYPoints = null;
+ notableMaxYPoints = null;
+ notableMinZPoints = null;
+ notableMaxZPoints = null;
+ edgePoints = null;
+ } else {
+ // Construct the planes
+ minXPlane = new SidedPlane(maxX,0.0,0.0,xUnitVector,-minX);
+ maxXPlane = new SidedPlane(minX,0.0,0.0,xUnitVector,-maxX);
+ minYPlane = new SidedPlane(0.0,maxY,0.0,yUnitVector,-minY);
+ maxYPlane = new SidedPlane(0.0,minY,0.0,yUnitVector,-maxY);
+ minZPlane = new SidedPlane(0.0,0.0,maxZ,zUnitVector,-minZ);
+ maxZPlane = new SidedPlane(0.0,0.0,minZ,zUnitVector,-maxZ);
+
+ // We need at least one point on the planet surface for each manifestation of the shape.
+ // There can be up to 2 (on opposite sides of the world). But we have to go through
+ // 12 combinations of adjacent planes in order to find out if any have 2 intersection solution.
+ // Typically, this requires 12 square root operations.
+ final GeoPoint[] minXminY = minXPlane.findIntersections(planetModel,minYPlane,maxXPlane,maxYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] minXmaxY = minXPlane.findIntersections(planetModel,maxYPlane,maxXPlane,minYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] minXminZ = minXPlane.findIntersections(planetModel,minZPlane,maxXPlane,maxZPlane,minYPlane,maxYPlane);
+ final GeoPoint[] minXmaxZ = minXPlane.findIntersections(planetModel,maxZPlane,maxXPlane,minZPlane,minYPlane,maxYPlane);
+
+ final GeoPoint[] maxXminY = maxXPlane.findIntersections(planetModel,minYPlane,minXPlane,maxYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] maxXmaxY = maxXPlane.findIntersections(planetModel,maxYPlane,minXPlane,minYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] maxXminZ = maxXPlane.findIntersections(planetModel,minZPlane,minXPlane,maxZPlane,minYPlane,maxYPlane);
+ final GeoPoint[] maxXmaxZ = maxXPlane.findIntersections(planetModel,maxZPlane,minXPlane,minZPlane,minYPlane,maxYPlane);
+
+ final GeoPoint[] minYminZ = minYPlane.findIntersections(planetModel,minZPlane,maxYPlane,maxZPlane,minXPlane,maxXPlane);
+ final GeoPoint[] minYmaxZ = minYPlane.findIntersections(planetModel,maxZPlane,maxYPlane,minZPlane,minXPlane,maxXPlane);
+ final GeoPoint[] maxYminZ = maxYPlane.findIntersections(planetModel,minZPlane,minYPlane,maxZPlane,minXPlane,maxXPlane);
+ final GeoPoint[] maxYmaxZ = maxYPlane.findIntersections(planetModel,maxZPlane,minYPlane,minZPlane,minXPlane,maxXPlane);
+
+ notableMinXPoints = glueTogether(minXminY, minXmaxY, minXminZ, minXmaxZ);
+ notableMaxXPoints = glueTogether(maxXminY, maxXmaxY, maxXminZ, maxXmaxZ);
+ notableMinYPoints = glueTogether(minXminY, maxXminY, minYminZ, minYmaxZ);
+ notableMaxYPoints = glueTogether(minXmaxY, maxXmaxY, maxYminZ, maxYmaxZ);
+ notableMinZPoints = glueTogether(minXminZ, maxXminZ, minYminZ, maxYminZ);
+ notableMaxZPoints = glueTogether(minXmaxZ, maxXmaxZ, minYmaxZ, maxYmaxZ);
+
+ // Now, compute the edge points.
+ // This is the trickiest part of setting up an XYZSolid. We've computed intersections already, so
+ // we'll start there.
+ // There can be a number of shapes, each of which needs an edgepoint. Each side by itself might contribute
+ // an edgepoint, for instance, if the plane describing that side intercepts the planet in such a way that the ellipse
+ // of interception does not meet any other planes. Plane intersections can each contribute 0, 1, or 2 edgepoints.
+ //
+ // All of this makes for a lot of potential edgepoints, but I believe these can be pruned back with careful analysis.
+ // I haven't yet done that analysis, however, so I will treat them all as individual edgepoints.
+
+ // The cases we are looking for are when the four corner points for any given
+ // plane are all outside of the world, AND that plane intersects the world.
+ // There are eight corner points all told; we must evaluate these WRT the planet surface.
+ final boolean minXminYminZ = planetModel.pointOutside(minX, minY, minZ);
+ final boolean minXminYmaxZ = planetModel.pointOutside(minX, minY, maxZ);
+ final boolean minXmaxYminZ = planetModel.pointOutside(minX, maxY, minZ);
+ final boolean minXmaxYmaxZ = planetModel.pointOutside(minX, maxY, maxZ);
+ final boolean maxXminYminZ = planetModel.pointOutside(maxX, minY, minZ);
+ final boolean maxXminYmaxZ = planetModel.pointOutside(maxX, minY, maxZ);
+ final boolean maxXmaxYminZ = planetModel.pointOutside(maxX, maxY, minZ);
+ final boolean maxXmaxYmaxZ = planetModel.pointOutside(maxX, maxY, maxZ);
+
+ // Look at single-plane/world intersections.
+ // We detect these by looking at the world model and noting its x, y, and z bounds.
+
+ final GeoPoint[] minXEdges;
+ if (minX - worldMinX >= -Vector.MINIMUM_RESOLUTION && minX - worldMaxX <= Vector.MINIMUM_RESOLUTION &&
+ minY < 0.0 && maxY > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ minXminYminZ && minXminYmaxZ && minXmaxYminZ && minXmaxYmaxZ) {
+ // Find any point on the minX plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0)
+ // Then use it to compute a sample point.
+ minXEdges = new GeoPoint[]{minXPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ minXEdges = EMPTY_POINTS;
+ }
+
+ final GeoPoint[] maxXEdges;
+ if (maxX - worldMinX >= -Vector.MINIMUM_RESOLUTION && maxX - worldMaxX <= Vector.MINIMUM_RESOLUTION &&
+ minY < 0.0 && maxY > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ maxXminYminZ && maxXminYmaxZ && maxXmaxYminZ && maxXmaxYmaxZ) {
+ // Find any point on the maxX plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0)
+ // Then use it to compute a sample point.
+ maxXEdges = new GeoPoint[]{maxXPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ maxXEdges = EMPTY_POINTS;
+ }
+
+ final GeoPoint[] minYEdges;
+ if (minY - worldMinY >= -Vector.MINIMUM_RESOLUTION && minY - worldMaxY <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ minXminYminZ && minXminYmaxZ && maxXminYminZ && maxXminYmaxZ) {
+ // Find any point on the minY plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (0,1,0)
+ // Then use it to compute a sample point.
+ minYEdges = new GeoPoint[]{minYPlane.getSampleIntersectionPoint(planetModel, yVerticalPlane)};
+ } else {
+ minYEdges = EMPTY_POINTS;
+ }
+
+ final GeoPoint[] maxYEdges;
+ if (maxY - worldMinY >= -Vector.MINIMUM_RESOLUTION && maxY - worldMaxY <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ minXmaxYminZ && minXmaxYmaxZ && maxXmaxYminZ && maxXmaxYmaxZ) {
+ // Find any point on the maxY plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (0,1,0)
+ // Then use it to compute a sample point.
+ maxYEdges = new GeoPoint[]{maxYPlane.getSampleIntersectionPoint(planetModel, yVerticalPlane)};
+ } else {
+ maxYEdges = EMPTY_POINTS;
+ }
+
+ final GeoPoint[] minZEdges;
+ if (minZ - worldMinZ >= -Vector.MINIMUM_RESOLUTION && minZ - worldMaxZ <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minY < 0.0 && maxY > 0.0 &&
+ minXminYminZ && minXmaxYminZ && maxXminYminZ && maxXmaxYminZ) {
+ // Find any point on the minZ plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0)
+ // Then use it to compute a sample point.
+ minZEdges = new GeoPoint[]{minZPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ minZEdges = EMPTY_POINTS;
+ }
+
+ final GeoPoint[] maxZEdges;
+ if (maxZ - worldMinZ >= -Vector.MINIMUM_RESOLUTION && maxZ - worldMaxZ <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minY < 0.0 && maxY > 0.0 &&
+ minXminYmaxZ && minXmaxYmaxZ && maxXminYmaxZ && maxXmaxYmaxZ) {
+ // Find any point on the maxZ plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0) (that is, its orientation doesn't matter)
+ // Then use it to compute a sample point.
+ maxZEdges = new GeoPoint[]{maxZPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ maxZEdges = EMPTY_POINTS;
+ }
+
+ // Glue everything together. This is not a minimal set of edgepoints, as of now, but it does completely describe all shapes on the
+ // planet.
+ this.edgePoints = glueTogether(minXminY, minXmaxY, minXminZ, minXmaxZ,
+ maxXminY, maxXmaxY, maxXminZ, maxXmaxZ,
+ minYminZ, minYmaxZ, maxYminZ, maxYmaxZ,
+ minXEdges, maxXEdges, minYEdges, maxYEdges, minZEdges, maxZEdges);
+ }
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ if (isWholeWorld) {
+ return true;
+ }
+ return minXPlane.isWithin(x, y, z) &&
+ maxXPlane.isWithin(x, y, z) &&
+ minYPlane.isWithin(x, y, z) &&
+ maxYPlane.isWithin(x, y, z) &&
+ minZPlane.isWithin(x, y, z) &&
+ maxZPlane.isWithin(x, y, z);
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ if (isWholeWorld) {
+ if (path.getEdgePoints().length > 0)
+ return WITHIN;
+ return OVERLAPS;
+ }
+
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some shape points inside area");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ //System.err.println(" some area points inside shape");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (path.intersects(minXPlane, notableMinXPoints, maxXPlane, minYPlane, maxYPlane, minZPlane, maxZPlane) ||
+ path.intersects(maxXPlane, notableMaxXPoints, minXPlane, minYPlane, maxYPlane, minZPlane, maxZPlane) ||
+ path.intersects(minYPlane, notableMinYPoints, maxYPlane, minXPlane, maxXPlane, minZPlane, maxZPlane) ||
+ path.intersects(maxYPlane, notableMaxYPoints, minYPlane, minXPlane, maxXPlane, minZPlane, maxZPlane) ||
+ path.intersects(minZPlane, notableMinZPoints, maxZPlane, minXPlane, maxXPlane, minYPlane, maxYPlane) ||
+ path.intersects(maxZPlane, notableMaxZPoints, minZPlane, minXPlane, maxXPlane, minYPlane, maxYPlane)) {
+ //System.err.println(" edges intersect");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ //System.err.println(" all shape points inside area");
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" all area points inside shape");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof XYZSolid))
+ return false;
+ XYZSolid other = (XYZSolid) o;
+ if (!super.equals(other) ||
+ other.isWholeWorld != isWholeWorld) {
+ return false;
+ }
+ if (!isWholeWorld) {
+ return other.minXPlane.equals(minXPlane) &&
+ other.maxXPlane.equals(maxXPlane) &&
+ other.minYPlane.equals(minYPlane) &&
+ other.maxYPlane.equals(maxYPlane) &&
+ other.minZPlane.equals(minZPlane) &&
+ other.maxZPlane.equals(maxZPlane);
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + (isWholeWorld?1:0);
+ if (!isWholeWorld) {
+ result = 31 * result + minXPlane.hashCode();
+ result = 31 * result + maxXPlane.hashCode();
+ result = 31 * result + minYPlane.hashCode();
+ result = 31 * result + maxYPlane.hashCode();
+ result = 31 * result + minZPlane.hashCode();
+ result = 31 * result + maxZPlane.hashCode();
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "XYZSolid: {planetmodel="+planetModel+", isWholeWorld="+isWholeWorld+", minXplane="+minXPlane+", maxXplane="+maxXPlane+", minYplane="+minYPlane+", maxYplane="+maxYPlane+", minZplane="+minZPlane+", maxZplane="+maxZPlane+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYdZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYdZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYdZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XYdZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,209 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in Z
+ *
+ * @lucene.internal
+ */
+public class XYdZSolid extends BaseXYZSolid {
+
+ /** Min-X plane */
+ protected final SidedPlane minXPlane;
+ /** Max-X plane */
+ protected final SidedPlane maxXPlane;
+ /** Min-Y plane */
+ protected final SidedPlane minYPlane;
+ /** Max-Y plane */
+ protected final SidedPlane maxYPlane;
+ /** Z plane */
+ protected final Plane zPlane;
+
+ /** These are the edge points of the shape, which are defined to be at least one point on
+ * each surface area boundary. In the case of a solid, this includes points which represent
+ * the intersection of XYZ bounding planes and the planet, as well as points representing
+ * the intersection of single bounding planes with the planet itself.
+ */
+ protected final GeoPoint[] edgePoints;
+
+ /** Notable points for ZPlane */
+ protected final GeoPoint[] notableZPoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param minX is the minimum X value.
+ *@param maxX is the maximum X value.
+ *@param minY is the minimum Y value.
+ *@param maxY is the maximum Y value.
+ *@param Z is the Z value.
+ */
+ public XYdZSolid(final PlanetModel planetModel,
+ final double minX,
+ final double maxX,
+ final double minY,
+ final double maxY,
+ final double Z) {
+ super(planetModel);
+ // Argument checking
+ if (maxX - minX < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("X values in wrong order or identical");
+ if (maxY - minY < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Y values in wrong order or identical");
+
+ final double worldMinZ = planetModel.getMinimumZValue();
+ final double worldMaxZ = planetModel.getMaximumZValue();
+
+ // Construct the planes
+ minXPlane = new SidedPlane(maxX,0.0,0.0,xUnitVector,-minX);
+ maxXPlane = new SidedPlane(minX,0.0,0.0,xUnitVector,-maxX);
+ minYPlane = new SidedPlane(0.0,maxY,0.0,yUnitVector,-minY);
+ maxYPlane = new SidedPlane(0.0,minY,0.0,yUnitVector,-maxY);
+ zPlane = new Plane(zUnitVector,-Z);
+
+ // We need at least one point on the planet surface for each manifestation of the shape.
+ // There can be up to 2 (on opposite sides of the world). But we have to go through
+ // 4 combinations of adjacent planes in order to find out if any have 2 intersection solution.
+ // Typically, this requires 4 square root operations.
+ final GeoPoint[] minXZ = minXPlane.findIntersections(planetModel,zPlane,maxXPlane,minYPlane,maxYPlane);
+ final GeoPoint[] maxXZ = maxXPlane.findIntersections(planetModel,zPlane,minXPlane,minYPlane,maxYPlane);
+ final GeoPoint[] minYZ = minYPlane.findIntersections(planetModel,zPlane,maxYPlane,minXPlane,maxXPlane);
+ final GeoPoint[] maxYZ = maxYPlane.findIntersections(planetModel,zPlane,minYPlane,minXPlane,maxXPlane);
+
+ notableZPoints = glueTogether(minXZ, maxXZ, minYZ, maxYZ);
+
+ // Now, compute the edge points.
+ // This is the trickiest part of setting up an XYZSolid. We've computed intersections already, so
+ // we'll start there. We know that at most there will be two disconnected shapes on the planet surface.
+ // But there's also a case where exactly one plane slices through the world, and none of the bounding plane
+ // intersections do. Thus, if we don't find any of the edge intersection cases, we have to look for that last case.
+
+ // If we still haven't encountered anything, we need to look at single-plane/world intersections.
+ // We detect these by looking at the world model and noting its x, y, and z bounds.
+ // The cases we are looking for are when the four corner points for any given
+ // plane are all outside of the world, AND that plane intersects the world.
+ // There are four corner points all told; we must evaluate these WRT the planet surface.
+ final boolean minXminYZ = planetModel.pointOutside(minX, minY, Z);
+ final boolean minXmaxYZ = planetModel.pointOutside(minX, maxY, Z);
+ final boolean maxXminYZ = planetModel.pointOutside(maxX, minY, Z);
+ final boolean maxXmaxYZ = planetModel.pointOutside(maxX, maxY, Z);
+
+ final GeoPoint[] zEdges;
+ if (Z - worldMinZ >= -Vector.MINIMUM_RESOLUTION && Z - worldMaxZ <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minY < 0.0 && maxY > 0.0 &&
+ minXminYZ && minXmaxYZ && maxXminYZ && maxXmaxYZ) {
+ // Find any point on the minZ plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0)
+ // Then use it to compute a sample point.
+ zEdges = new GeoPoint[]{zPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ zEdges= EMPTY_POINTS;
+ }
+
+ this.edgePoints = glueTogether(minXZ, maxXZ, minYZ, maxYZ, zEdges);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ return minXPlane.isWithin(x, y, z) &&
+ maxXPlane.isWithin(x, y, z) &&
+ minYPlane.isWithin(x, y, z) &&
+ maxYPlane.isWithin(x, y, z) &&
+ zPlane.evaluateIsZero(x, y, z);
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some inside");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (path.intersects(zPlane, notableZPoints, minXPlane, maxXPlane, minYPlane, maxYPlane)) {
+ //System.err.println(" edges intersect");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ //System.err.println(" shape inside rectangle");
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains rectangle");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof XYdZSolid))
+ return false;
+ XYdZSolid other = (XYdZSolid) o;
+ if (!super.equals(other)) {
+ return false;
+ }
+ return other.minXPlane.equals(minXPlane) &&
+ other.maxXPlane.equals(maxXPlane) &&
+ other.minYPlane.equals(minYPlane) &&
+ other.maxYPlane.equals(maxYPlane) &&
+ other.zPlane.equals(zPlane);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + minXPlane.hashCode();
+ result = 31 * result + maxXPlane.hashCode();
+ result = 31 * result + minYPlane.hashCode();
+ result = 31 * result + maxYPlane.hashCode();
+ result = 31 * result + zPlane.hashCode();
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "XYdZSolid: {planetmodel="+planetModel+", minXplane="+minXPlane+", maxXplane="+maxXPlane+", minYplane="+minYPlane+", maxYplane="+maxYPlane+", zplane="+zPlane+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,208 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in Y
+ *
+ * @lucene.internal
+ */
+public class XdYZSolid extends BaseXYZSolid {
+
+ /** Min-X plane */
+ protected final SidedPlane minXPlane;
+ /** Max-X plane */
+ protected final SidedPlane maxXPlane;
+ /** Y plane */
+ protected final Plane yPlane;
+ /** Min-Z plane */
+ protected final SidedPlane minZPlane;
+ /** Max-Z plane */
+ protected final SidedPlane maxZPlane;
+
+ /** These are the edge points of the shape, which are defined to be at least one point on
+ * each surface area boundary. In the case of a solid, this includes points which represent
+ * the intersection of XYZ bounding planes and the planet, as well as points representing
+ * the intersection of single bounding planes with the planet itself.
+ */
+ protected final GeoPoint[] edgePoints;
+
+ /** Notable points for YPlane */
+ protected final GeoPoint[] notableYPoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param minX is the minimum X value.
+ *@param maxX is the maximum X value.
+ *@param Y is the Y value.
+ *@param minZ is the minimum Z value.
+ *@param maxZ is the maximum Z value.
+ */
+ public XdYZSolid(final PlanetModel planetModel,
+ final double minX,
+ final double maxX,
+ final double Y,
+ final double minZ,
+ final double maxZ) {
+ super(planetModel);
+ // Argument checking
+ if (maxX - minX < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("X values in wrong order or identical");
+ if (maxZ - minZ < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Z values in wrong order or identical");
+
+ final double worldMinY = planetModel.getMinimumYValue();
+ final double worldMaxY = planetModel.getMaximumYValue();
+
+ // Construct the planes
+ minXPlane = new SidedPlane(maxX,0.0,0.0,xUnitVector,-minX);
+ maxXPlane = new SidedPlane(minX,0.0,0.0,xUnitVector,-maxX);
+ yPlane = new Plane(yUnitVector,-Y);
+ minZPlane = new SidedPlane(0.0,0.0,maxZ,zUnitVector,-minZ);
+ maxZPlane = new SidedPlane(0.0,0.0,minZ,zUnitVector,-maxZ);
+
+ // We need at least one point on the planet surface for each manifestation of the shape.
+ // There can be up to 2 (on opposite sides of the world). But we have to go through
+ // 4 combinations of adjacent planes in order to find out if any have 2 intersection solution.
+ // Typically, this requires 4 square root operations.
+ final GeoPoint[] minXY = minXPlane.findIntersections(planetModel,yPlane,maxXPlane,minZPlane,maxZPlane);
+ final GeoPoint[] maxXY = maxXPlane.findIntersections(planetModel,yPlane,minXPlane,minZPlane,maxZPlane);
+ final GeoPoint[] YminZ = yPlane.findIntersections(planetModel,minZPlane,maxZPlane,minXPlane,maxXPlane);
+ final GeoPoint[] YmaxZ = yPlane.findIntersections(planetModel,maxZPlane,minZPlane,minXPlane,maxXPlane);
+
+ notableYPoints = glueTogether(minXY, maxXY, YminZ, YmaxZ);
+
+ // Now, compute the edge points.
+ // This is the trickiest part of setting up an XYZSolid. We've computed intersections already, so
+ // we'll start there. We know that at most there will be two disconnected shapes on the planet surface.
+ // But there's also a case where exactly one plane slices through the world, and none of the bounding plane
+ // intersections do. Thus, if we don't find any of the edge intersection cases, we have to look for that last case.
+
+ // We need to look at single-plane/world intersections.
+ // We detect these by looking at the world model and noting its x, y, and z bounds.
+ // The cases we are looking for are when the four corner points for any given
+ // plane are all outside of the world, AND that plane intersects the world.
+ // There are four corner points all told; we must evaluate these WRT the planet surface.
+ final boolean minXYminZ = planetModel.pointOutside(minX, Y, minZ);
+ final boolean minXYmaxZ = planetModel.pointOutside(minX, Y, maxZ);
+ final boolean maxXYminZ = planetModel.pointOutside(maxX, Y, minZ);
+ final boolean maxXYmaxZ = planetModel.pointOutside(maxX, Y, maxZ);
+
+ final GeoPoint[] yEdges;
+ if (Y - worldMinY >= -Vector.MINIMUM_RESOLUTION && Y - worldMaxY <= Vector.MINIMUM_RESOLUTION &&
+ minX < 0.0 && maxX > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ minXYminZ && minXYmaxZ && maxXYminZ && maxXYmaxZ) {
+ // Find any point on the minY plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (0,1,0)
+ // Then use it to compute a sample point.
+ yEdges = new GeoPoint[]{yPlane.getSampleIntersectionPoint(planetModel, yVerticalPlane)};
+ } else {
+ yEdges = EMPTY_POINTS;
+ }
+
+ this.edgePoints = glueTogether(minXY, maxXY, YminZ, YmaxZ, yEdges);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ return minXPlane.isWithin(x, y, z) &&
+ maxXPlane.isWithin(x, y, z) &&
+ yPlane.evaluateIsZero(x, y, z) &&
+ minZPlane.isWithin(x, y, z) &&
+ maxZPlane.isWithin(x, y, z);
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some inside");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (path.intersects(yPlane, notableYPoints, minXPlane, maxXPlane, minZPlane, maxZPlane)) {
+ //System.err.println(" edges intersect");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ //System.err.println(" shape inside rectangle");
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains rectangle");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof XdYZSolid))
+ return false;
+ XdYZSolid other = (XdYZSolid) o;
+ if (!super.equals(other)) {
+ return false;
+ }
+ return other.minXPlane.equals(minXPlane) &&
+ other.maxXPlane.equals(maxXPlane) &&
+ other.yPlane.equals(yPlane) &&
+ other.minZPlane.equals(minZPlane) &&
+ other.maxZPlane.equals(maxZPlane);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + minXPlane.hashCode();
+ result = 31 * result + maxXPlane.hashCode();
+ result = 31 * result + yPlane.hashCode();
+ result = 31 * result + minZPlane.hashCode();
+ result = 31 * result + maxZPlane.hashCode();
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "XdYZSolid: {planetmodel="+planetModel+", minXplane="+minXPlane+", maxXplane="+maxXPlane+", yplane="+yPlane+", minZplane="+minZPlane+", maxZplane="+maxZPlane+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYdZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYdZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYdZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/XdYdZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,139 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in Y and Z.
+ * This figure, in fact, represents either zero, one, or two points, so the
+ * actual data stored is minimal.
+ *
+ * @lucene.internal
+ */
+public class XdYdZSolid extends BaseXYZSolid {
+
+ /** The points in this figure on the planet surface; also doubles for edge points */
+ protected final GeoPoint[] surfacePoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param minX is the minimum X value.
+ *@param maxX is the maximum X value.
+ *@param Y is the Y value.
+ *@param Z is the Z value.
+ */
+ public XdYdZSolid(final PlanetModel planetModel,
+ final double minX,
+ final double maxX,
+ final double Y,
+ final double Z) {
+ super(planetModel);
+ // Argument checking
+ if (maxX - minX < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("X values in wrong order or identical");
+
+ // Build the planes and intersect them.
+ final Plane yPlane = new Plane(yUnitVector,-Y);
+ final Plane zPlane = new Plane(zUnitVector,-Z);
+ final SidedPlane minXPlane = new SidedPlane(maxX,0.0,0.0,xUnitVector,-minX);
+ final SidedPlane maxXPlane = new SidedPlane(minX,0.0,0.0,xUnitVector,-maxX);
+ surfacePoints = yPlane.findIntersections(planetModel,zPlane,minXPlane,maxXPlane);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return surfacePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ for (final GeoPoint p : surfacePoints) {
+ if (p.isIdentical(x,y,z))
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some inside");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains rectangle");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof XdYdZSolid))
+ return false;
+ XdYdZSolid other = (XdYdZSolid) o;
+ if (!super.equals(other) || surfacePoints.length != other.surfacePoints.length ) {
+ return false;
+ }
+ for (int i = 0; i < surfacePoints.length; i++) {
+ if (!surfacePoints[i].equals(other.surfacePoints[i]))
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ for (final GeoPoint p : surfacePoints) {
+ result = 31 * result + p.hashCode();
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ for (final GeoPoint p : surfacePoints) {
+ sb.append(" ").append(p).append(" ");
+ }
+ return "XdYdZSolid: {planetmodel="+planetModel+", "+sb.toString()+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,212 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in X.
+ *
+ * @lucene.internal
+ */
+public class dXYZSolid extends BaseXYZSolid {
+
+ /** X plane */
+ protected final Plane xPlane;
+ /** Min-Y plane */
+ protected final SidedPlane minYPlane;
+ /** Max-Y plane */
+ protected final SidedPlane maxYPlane;
+ /** Min-Z plane */
+ protected final SidedPlane minZPlane;
+ /** Max-Z plane */
+ protected final SidedPlane maxZPlane;
+
+ /** These are the edge points of the shape, which are defined to be at least one point on
+ * each surface area boundary. In the case of a solid, this includes points which represent
+ * the intersection of XYZ bounding planes and the planet, as well as points representing
+ * the intersection of single bounding planes with the planet itself.
+ */
+ protected final GeoPoint[] edgePoints;
+
+ /** Notable points for XPlane */
+ protected final GeoPoint[] notableXPoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param X is the X value.
+ *@param minY is the minimum Y value.
+ *@param maxY is the maximum Y value.
+ *@param minZ is the minimum Z value.
+ *@param maxZ is the maximum Z value.
+ */
+ public dXYZSolid(final PlanetModel planetModel,
+ final double X,
+ final double minY,
+ final double maxY,
+ final double minZ,
+ final double maxZ) {
+ super(planetModel);
+ // Argument checking
+ if (maxY - minY < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Y values in wrong order or identical");
+ if (maxZ - minZ < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Z values in wrong order or identical");
+
+ final double worldMinX = planetModel.getMinimumXValue();
+ final double worldMaxX = planetModel.getMaximumXValue();
+
+ // Construct the planes
+ xPlane = new Plane(xUnitVector,-X);
+ minYPlane = new SidedPlane(0.0,maxY,0.0,yUnitVector,-minY);
+ maxYPlane = new SidedPlane(0.0,minY,0.0,yUnitVector,-maxY);
+ minZPlane = new SidedPlane(0.0,0.0,maxZ,zUnitVector,-minZ);
+ maxZPlane = new SidedPlane(0.0,0.0,minZ,zUnitVector,-maxZ);
+
+ // We need at least one point on the planet surface for each manifestation of the shape.
+ // There can be up to 2 (on opposite sides of the world). But we have to go through
+ // 4 combinations of adjacent planes in order to find out if any have 2 intersection solution.
+ // Typically, this requires 4 square root operations.
+ final GeoPoint[] XminY = xPlane.findIntersections(planetModel,minYPlane,maxYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] XmaxY = xPlane.findIntersections(planetModel,maxYPlane,minYPlane,minZPlane,maxZPlane);
+ final GeoPoint[] XminZ = xPlane.findIntersections(planetModel,minZPlane,maxZPlane,minYPlane,maxYPlane);
+ final GeoPoint[] XmaxZ = xPlane.findIntersections(planetModel,maxZPlane,minZPlane,minYPlane,maxYPlane);
+
+ notableXPoints = glueTogether(XminY, XmaxY, XminZ, XmaxZ);
+
+ // Now, compute the edge points.
+ // This is the trickiest part of setting up an XYZSolid. We've computed intersections already, so
+ // we'll start there. We know that at most there will be two disconnected shapes on the planet surface.
+ // But there's also a case where exactly one plane slices through the world, and none of the bounding plane
+ // intersections do. Thus, if we don't find any of the edge intersection cases, we have to look for that last case.
+
+ // We need to look at single-plane/world intersections.
+ // We detect these by looking at the world model and noting its x, y, and z bounds.
+ // For the single-dimension degenerate case, there's really only one plane that can possibly intersect the world.
+ // The cases we are looking for are when the four corner points for any given
+ // plane are all outside of the world, AND that plane intersects the world.
+ // There are four corner points all told; we must evaluate these WRT the planet surface.
+ final boolean XminYminZ = planetModel.pointOutside(X, minY, minZ);
+ final boolean XminYmaxZ = planetModel.pointOutside(X, minY, maxZ);
+ final boolean XmaxYminZ = planetModel.pointOutside(X, maxY, minZ);
+ final boolean XmaxYmaxZ = planetModel.pointOutside(X, maxY, maxZ);
+
+ final GeoPoint[] xEdges;
+ if (X - worldMinX >= -Vector.MINIMUM_RESOLUTION && X - worldMaxX <= Vector.MINIMUM_RESOLUTION &&
+ minY < 0.0 && maxY > 0.0 && minZ < 0.0 && maxZ > 0.0 &&
+ XminYminZ && XminYmaxZ && XmaxYminZ && XmaxYmaxZ) {
+ // Find any point on the X plane that intersects the world
+ // First construct a perpendicular plane that will allow us to find a sample point.
+ // This plane is vertical and goes through the points (0,0,0) and (1,0,0)
+ // Then use it to compute a sample point.
+ xEdges = new GeoPoint[]{xPlane.getSampleIntersectionPoint(planetModel, xVerticalPlane)};
+ } else {
+ xEdges = EMPTY_POINTS;
+ }
+
+ this.edgePoints = glueTogether(XminY,XmaxY,XminZ,XmaxZ,xEdges);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ return xPlane.evaluateIsZero(x, y, z) &&
+ minYPlane.isWithin(x, y, z) &&
+ maxYPlane.isWithin(x, y, z) &&
+ minZPlane.isWithin(x, y, z) &&
+ maxZPlane.isWithin(x, y, z);
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some shape points inside area");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ //System.err.println(" some area points inside shape");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ // The entire locus of points in this shape is on a single plane, so we only need ot look for an intersection with that plane.
+ //System.err.println("xPlane = "+xPlane);
+ if (path.intersects(xPlane, notableXPoints, minYPlane, maxYPlane, minZPlane, maxZPlane)) {
+ //System.err.println(" edges intersect");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ //System.err.println(" shape points inside area");
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains all area");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof dXYZSolid))
+ return false;
+ dXYZSolid other = (dXYZSolid) o;
+ if (!super.equals(other)) {
+ return false;
+ }
+ return other.xPlane.equals(xPlane) &&
+ other.minYPlane.equals(minYPlane) &&
+ other.maxYPlane.equals(maxYPlane) &&
+ other.minZPlane.equals(minZPlane) &&
+ other.maxZPlane.equals(maxZPlane);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + xPlane.hashCode();
+ result = 31 * result + minYPlane.hashCode();
+ result = 31 * result + maxYPlane.hashCode();
+ result = 31 * result + minZPlane.hashCode();
+ result = 31 * result + maxZPlane.hashCode();
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "dXYZSolid: {planetmodel="+planetModel+", xplane="+xPlane+", minYplane="+minYPlane+", maxYplane="+maxYPlane+", minZplane="+minZPlane+", maxZplane="+maxZPlane+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYdZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYdZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYdZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXYdZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,139 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in X and Z.
+ * This figure, in fact, represents either zero, one, or two points, so the
+ * actual data stored is minimal.
+ *
+ * @lucene.internal
+ */
+public class dXYdZSolid extends BaseXYZSolid {
+
+ /** The points in this figure on the planet surface; also doubles for edge points */
+ protected final GeoPoint[] surfacePoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param X is the X value.
+ *@param minY is the minimum Y value.
+ *@param maxY is the maximum Y value.
+ *@param Z is the Z value.
+ */
+ public dXYdZSolid(final PlanetModel planetModel,
+ final double X,
+ final double minY,
+ final double maxY,
+ final double Z) {
+ super(planetModel);
+ // Argument checking
+ if (maxY - minY < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Y values in wrong order or identical");
+
+ // Build the planes and intersect them.
+ final Plane xPlane = new Plane(xUnitVector,-X);
+ final Plane zPlane = new Plane(zUnitVector,-Z);
+ final SidedPlane minYPlane = new SidedPlane(0.0,maxY,0.0,yUnitVector,-minY);
+ final SidedPlane maxYPlane = new SidedPlane(0.0,minY,0.0,yUnitVector,-maxY);
+ surfacePoints = xPlane.findIntersections(planetModel,zPlane,minYPlane,maxYPlane);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return surfacePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ for (final GeoPoint p : surfacePoints) {
+ if (p.isIdentical(x,y,z))
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some inside");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains rectangle");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof dXYdZSolid))
+ return false;
+ dXYdZSolid other = (dXYdZSolid) o;
+ if (!super.equals(other) || surfacePoints.length != other.surfacePoints.length ) {
+ return false;
+ }
+ for (int i = 0; i < surfacePoints.length; i++) {
+ if (!surfacePoints[i].equals(other.surfacePoints[i]))
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ for (final GeoPoint p : surfacePoints) {
+ result = 31 * result + p.hashCode();
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ for (final GeoPoint p : surfacePoints) {
+ sb.append(" ").append(p).append(" ");
+ }
+ return "dXYdZSolid: {planetmodel="+planetModel+", "+sb.toString()+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,139 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in X and Y.
+ * This figure, in fact, represents either zero, one, or two points, so the
+ * actual data stored is minimal.
+ *
+ * @lucene.internal
+ */
+public class dXdYZSolid extends BaseXYZSolid {
+
+ /** The points in this figure on the planet surface; also doubles for edge points */
+ protected final GeoPoint[] surfacePoints;
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param X is the X value.
+ *@param Y is the Y value.
+ *@param minZ is the minimum Z value.
+ *@param maxZ is the maximum Z value.
+ */
+ public dXdYZSolid(final PlanetModel planetModel,
+ final double X,
+ final double Y,
+ final double minZ,
+ final double maxZ) {
+ super(planetModel);
+ // Argument checking
+ if (maxZ - minZ < Vector.MINIMUM_RESOLUTION)
+ throw new IllegalArgumentException("Z values in wrong order or identical");
+
+ // Build the planes and intersect them.
+ final Plane xPlane = new Plane(xUnitVector,-X);
+ final Plane yPlane = new Plane(yUnitVector,-Y);
+ final SidedPlane minZPlane = new SidedPlane(0.0,0.0,maxZ,zUnitVector,-minZ);
+ final SidedPlane maxZPlane = new SidedPlane(0.0,0.0,minZ,zUnitVector,-maxZ);
+ surfacePoints = xPlane.findIntersections(planetModel,yPlane,minZPlane,maxZPlane);
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return surfacePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ for (final GeoPoint p : surfacePoints) {
+ if (p.isIdentical(x,y,z))
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some inside");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains rectangle");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof dXdYZSolid))
+ return false;
+ dXdYZSolid other = (dXdYZSolid) o;
+ if (!super.equals(other) || surfacePoints.length != other.surfacePoints.length ) {
+ return false;
+ }
+ for (int i = 0; i < surfacePoints.length; i++) {
+ if (!surfacePoints[i].equals(other.surfacePoints[i]))
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ for (final GeoPoint p : surfacePoints) {
+ result = 31 * result + p.hashCode();
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ for (final GeoPoint p : surfacePoints) {
+ sb.append(" ").append(p).append(" ");
+ }
+ return "dXdYZSolid: {planetmodel="+planetModel+", "+sb.toString()+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYdZSolid.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYdZSolid.java?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYdZSolid.java (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/java/org/apache/lucene/geo3d/dXdYdZSolid.java Wed Sep 2 19:59:31 2015
@@ -0,0 +1,147 @@
+package org.apache.lucene.geo3d;
+
+/*
+ * 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.
+ */
+
+/**
+ * 3D rectangle, bounded on six sides by X,Y,Z limits, degenerate in all dimensions
+ *
+ * @lucene.internal
+ */
+public class dXdYdZSolid extends BaseXYZSolid {
+
+ /** On surface? */
+ protected final boolean isOnSurface;
+ /** The point */
+ protected final GeoPoint thePoint;
+
+ /** These are the edge points of the shape, which are defined to be at least one point on
+ * each surface area boundary. In the case of a solid, this includes points which represent
+ * the intersection of XYZ bounding planes and the planet, as well as points representing
+ * the intersection of single bounding planes with the planet itself.
+ */
+ protected final GeoPoint[] edgePoints;
+
+ /** Empty array of {@link GeoPoint}. */
+ protected static final GeoPoint[] nullPoints = new GeoPoint[0];
+
+ /**
+ * Sole constructor
+ *
+ *@param planetModel is the planet model.
+ *@param X is the X value.
+ *@param Y is the Y value.
+ *@param Z is the Z value.
+ */
+ public dXdYdZSolid(final PlanetModel planetModel,
+ final double X,
+ final double Y,
+ final double Z) {
+ super(planetModel);
+ isOnSurface = planetModel.pointOnSurface(X,Y,Z);
+ if (isOnSurface) {
+ thePoint = new GeoPoint(X,Y,Z);
+ edgePoints = new GeoPoint[]{thePoint};
+ } else {
+ thePoint = null;
+ edgePoints = nullPoints;
+ }
+ }
+
+ @Override
+ protected GeoPoint[] getEdgePoints() {
+ return edgePoints;
+ }
+
+ @Override
+ public boolean isWithin(final double x, final double y, final double z) {
+ if (!isOnSurface) {
+ return false;
+ }
+ return thePoint.isIdentical(x,y,z);
+ }
+
+ @Override
+ public int getRelationship(final GeoShape path) {
+ if (!isOnSurface) {
+ return DISJOINT;
+ }
+
+ //System.err.println(this+" getrelationship with "+path);
+ final int insideRectangle = isShapeInsideArea(path);
+ if (insideRectangle == SOME_INSIDE) {
+ //System.err.println(" some shape points inside area");
+ return OVERLAPS;
+ }
+
+ // Figure out if the entire XYZArea is contained by the shape.
+ final int insideShape = isAreaInsideShape(path);
+ if (insideShape == SOME_INSIDE) {
+ //System.err.println(" some area points inside shape");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
+ //System.err.println(" inside of each other");
+ return OVERLAPS;
+ }
+
+ if (insideRectangle == ALL_INSIDE) {
+ //System.err.println(" shape inside area entirely");
+ return WITHIN;
+ }
+
+ if (insideShape == ALL_INSIDE) {
+ //System.err.println(" shape contains area entirely");
+ return CONTAINS;
+ }
+ //System.err.println(" disjoint");
+ return DISJOINT;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof dXdYdZSolid))
+ return false;
+ dXdYdZSolid other = (dXdYdZSolid) o;
+ if (!super.equals(other) ||
+ other.isOnSurface != isOnSurface) {
+ return false;
+ }
+ if (isOnSurface) {
+ return other.thePoint.equals(thePoint);
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + (isOnSurface?1:0);
+ if (isOnSurface) {
+ result = 31 * result + thePoint.hashCode();
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "dXdYdZSolid: {planetmodel="+planetModel+", isOnSurface="+isOnSurface+", thePoint="+thePoint+"}";
+ }
+
+}
+
Added: lucene/dev/trunk/lucene/spatial3d/src/resources/META-INF/services/org.apache.lucene.codecs.DocValuesFormat
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial3d/src/resources/META-INF/services/org.apache.lucene.codecs.DocValuesFormat?rev=1700883&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/spatial3d/src/resources/META-INF/services/org.apache.lucene.codecs.DocValuesFormat (added)
+++ lucene/dev/trunk/lucene/spatial3d/src/resources/META-INF/services/org.apache.lucene.codecs.DocValuesFormat Wed Sep 2 19:59:31 2015
@@ -0,0 +1,17 @@
+# 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.
+
+org.apache.lucene.bkdtree3d.Geo3DDocValuesFormat
+