You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2019/12/11 08:33:27 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8620: Add CONTAINS
support for LatLonShape and XYShape (#872)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new a06a2ea LUCENE-8620: Add CONTAINS support for LatLonShape and XYShape (#872)
a06a2ea is described below
commit a06a2ea3da28457429b297ca178eaecb1c6c4a58
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Wed Dec 11 09:16:51 2019 +0100
LUCENE-8620: Add CONTAINS support for LatLonShape and XYShape (#872)
---
lucene/CHANGES.txt | 4 +-
.../java/org/apache/lucene/geo/Component2D.java | 27 +++
.../java/org/apache/lucene/geo/ComponentTree.java | 9 +
.../src/java/org/apache/lucene/geo/Polygon2D.java | 58 ++++++
.../org/apache/lucene/document/LatLonShape.java | 23 +++
.../document/LatLonShapeBoundingBoxQuery.java | 11 ++
.../lucene/document/LatLonShapeLineQuery.java | 16 +-
.../lucene/document/LatLonShapePolygonQuery.java | 14 ++
.../org/apache/lucene/document/ShapeField.java | 2 +-
.../org/apache/lucene/document/ShapeQuery.java | 72 ++++++-
.../java/org/apache/lucene/document/XYShape.java | 16 ++
.../lucene/document/XYShapeBoundingBoxQuery.java | 81 ++++++--
.../apache/lucene/document/XYShapeLineQuery.java | 14 ++
.../lucene/document/XYShapePolygonQuery.java | 14 ++
.../src/java/org/apache/lucene/geo/Line2D.java | 51 +++++
.../java/org/apache/lucene/geo/Rectangle2D.java | 60 ++++++
.../java/org/apache/lucene/geo/XYRectangle2D.java | 218 +++++++++++++++++++--
.../lucene/document/BaseLatLonShapeTestCase.java | 10 +
.../apache/lucene/document/BaseShapeTestCase.java | 29 ++-
.../lucene/document/BaseXYShapeTestCase.java | 9 +
.../document/TestLatLonLineShapeQueries.java | 28 +++
.../document/TestLatLonMultiLineShapeQueries.java | 8 +-
.../document/TestLatLonMultiPointShapeQueries.java | 8 +-
.../TestLatLonMultiPolygonShapeQueries.java | 39 +++-
.../document/TestLatLonPointShapeQueries.java | 6 +
.../document/TestLatLonPolygonShapeQueries.java | 41 +++-
.../apache/lucene/document/TestLatLonShape.java | 171 ++++++++++++++++
.../lucene/document/TestXYLineShapeQueries.java | 34 ++--
.../document/TestXYMultiLineShapeQueries.java | 22 +--
.../document/TestXYMultiPointShapeQueries.java | 22 +--
.../document/TestXYMultiPolygonShapeQueries.java | 53 +++--
.../lucene/document/TestXYPointShapeQueries.java | 21 +-
.../lucene/document/TestXYPolygonShapeQueries.java | 46 +++--
.../org/apache/lucene/document/TestXYShape.java | 56 ++++++
.../src/test/org/apache/lucene/geo/TestLine2D.java | 8 +-
.../org/apache/lucene/geo/TestRectangle2D.java | 58 +++++-
.../org/apache/lucene/geo/TestXYRectangle2D.java | 88 +++++++++
37 files changed, 1287 insertions(+), 160 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 4686cf7..51ba3f8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -11,8 +11,8 @@ API Changes
(Jack Conradson via Adrien Grand)
New Features
----------------------
-(No changes)
+
+* LUCENE-8620: Add CONTAINS support for LatLonShape and XYShape. (Ignacio Vera)
Improvements
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Component2D.java b/lucene/core/src/java/org/apache/lucene/geo/Component2D.java
index 10ced04..74fd1e3 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Component2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Component2D.java
@@ -60,6 +60,33 @@ public interface Component2D {
return relateTriangle(minX, maxX, minY, maxY, aX, aY, bX, bY, cX, cY);
}
+ /** Used by withinTriangle to check the within relationship between a triangle and the query shape
+ * (e.g. if the query shape is within the triangle). */
+ enum WithinRelation {
+ /** If the shape is a candidate for within. Typically this is return if the query shape is fully inside
+ * the triangle or if the query shape intersects only edges that do not belong to the original shape. */
+ CANDIDATE,
+ /** The query shape intersects an edge that does belong to the original shape or any point of
+ * the triangle is inside the shape. */
+ NOTWITHIN,
+ /** The query shape is disjoint with the triangle. */
+ DISJOINT
+ }
+
+ /** Compute the within relation of this component2D with a triangle **/
+ default WithinRelation withinTriangle(double aX, double aY, boolean ab, double bX, double bY, boolean bc, double cX, double cY, boolean ca) {
+ double minY = StrictMath.min(StrictMath.min(aY, bY), cY);
+ double minX = StrictMath.min(StrictMath.min(aX, bX), cX);
+ double maxY = StrictMath.max(StrictMath.max(aY, bY), cY);
+ double maxX = StrictMath.max(StrictMath.max(aX, bX), cX);
+ return withinTriangle(minX, maxX, minY, maxY, aX, aY, ab, bX, bY, bc, cX, cY, ca);
+ }
+
+ /** Compute the within relation of this component2D with a triangle **/
+ WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double aX, double aY, boolean ab, double bX, double bY, boolean bc, double cX, double cY, boolean ca);
+
+
/** Compute whether the bounding boxes are disjoint **/
static boolean disjoint(double minX1, double maxX1, double minY1, double maxY1, double minX2, double maxX2, double minY2, double maxY2) {
return (maxY1 < minY2 || minY1 > maxY2 || maxX1 < minX2 || minX1 > maxX2);
diff --git a/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java b/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
index 220c53d..8a2b5f3 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java
@@ -122,6 +122,15 @@ final class ComponentTree implements Component2D {
return Relation.CELL_OUTSIDE_QUERY;
}
+ @Override
+ public WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double aX, double aY, boolean ab, double bX, double bY, boolean bc, double cX, double cY, boolean ca) {
+ if (left != null || right != null) {
+ throw new IllegalArgumentException("withinTriangle is not supported for shapes with more than one component");
+ }
+ return component.withinTriangle(minX, maxX, minY, maxY, aX, aY, ab, bX, bY, bc, cX, cY, ca);
+ }
+
/** Returns relation to the provided rectangle */
@Override
public Relation relate(double minX, double maxX, double minY, double maxY) {
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
index bb39bd4..f8f1709 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -165,6 +165,64 @@ public class Polygon2D implements Component2D {
return relateIndexedTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy);
}
+ @Override
+ public WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, boolean ab, double bx, double by, boolean bc, double cx, double cy, boolean ca) {
+ // short cut, lines and points cannot contain this type of shape
+ if ((ax == bx && ay == by) || (ax == cx && ay == cy) || (bx == cx && by == cy)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ // if any of the points is inside the polygon, the polygon cannot be within this indexed
+ // shape because points belong to the original indexed shape.
+ if (contains(ax, ay) || contains(bx, by) || contains(cx, cy)) {
+ return WithinRelation.NOTWITHIN;
+ }
+
+ WithinRelation relation = WithinRelation.DISJOINT;
+ // if any of the edges intersects an the edge belongs to the shape then it cannot be within.
+ // if it only intersects edges that do not belong to the shape, then it is a candidate
+ // we skip edges at the dateline to support shapes crossing it
+ if (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by)) {
+ if (ab == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy)) {
+ if (bc == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay)) {
+ if (ca == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ // if any of the edges crosses and edge that does not belong to the shape
+ // then it is a candidate for within
+ if (relation == WithinRelation.CANDIDATE) {
+ return WithinRelation.CANDIDATE;
+ }
+
+ // Check if shape is within the triangle
+ if (Component2D.pointInTriangle(minX, maxX, minY, maxY, tree.x1, tree.y1, ax, ay, bx, by, cx, cy) == true) {
+ return WithinRelation.CANDIDATE;
+ }
+ return relation;
+ }
+
/** relates an indexed line segment (a "flat triangle") with the polygon */
private Relation relateIndexedLineSegment(double minX, double maxX, double minY, double maxY,
double a2x, double a2y, double b2x, double b2y) {
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
index cd54059..487afb8 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -21,10 +21,13 @@ import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
import org.apache.lucene.document.ShapeField.Triangle;
+import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.Line;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.index.PointValues; // javadoc
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.Query;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
@@ -93,6 +96,12 @@ public class LatLonShape {
/** create a query to find all indexed geo shapes that intersect a defined bounding box **/
public static Query newBoxQuery(String field, QueryRelation queryRelation, double minLatitude, double maxLatitude, double minLongitude, double maxLongitude) {
+ if (queryRelation == QueryRelation.CONTAINS && minLongitude > maxLongitude) {
+ BooleanQuery.Builder builder = new BooleanQuery.Builder();
+ builder.add(newBoxQuery(field, queryRelation, minLatitude, maxLatitude, minLongitude, GeoUtils.MAX_LON_INCL), BooleanClause.Occur.MUST);
+ builder.add(newBoxQuery(field, queryRelation, minLatitude, maxLatitude, GeoUtils.MIN_LON_INCL, maxLongitude), BooleanClause.Occur.MUST);
+ return builder.build();
+ }
return new LatLonShapeBoundingBoxQuery(field, queryRelation, minLatitude, maxLatitude, minLongitude, maxLongitude);
}
@@ -100,6 +109,13 @@ public class LatLonShape {
* note: does not support dateline crossing
**/
public static Query newLineQuery(String field, QueryRelation queryRelation, Line... lines) {
+ if (queryRelation == QueryRelation.CONTAINS && lines.length > 1) {
+ BooleanQuery.Builder builder = new BooleanQuery.Builder();
+ for (int i =0; i < lines.length; i++) {
+ builder.add(newLineQuery(field, queryRelation, lines[i]), BooleanClause.Occur.MUST);
+ }
+ return builder.build();
+ }
return new LatLonShapeLineQuery(field, queryRelation, lines);
}
@@ -107,6 +123,13 @@ public class LatLonShape {
* note: does not support dateline crossing
**/
public static Query newPolygonQuery(String field, QueryRelation queryRelation, Polygon... polygons) {
+ if (queryRelation == QueryRelation.CONTAINS && polygons.length > 1) {
+ BooleanQuery.Builder builder = new BooleanQuery.Builder();
+ for (int i =0; i < polygons.length; i++) {
+ builder.add(newPolygonQuery(field, queryRelation, polygons[i]), BooleanClause.Occur.MUST);
+ }
+ return builder.build();
+ }
return new LatLonShapePolygonQuery(field, queryRelation, polygons);
}
}
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
index aa1f93d..71f909a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -17,6 +17,7 @@
package org.apache.lucene.document;
import org.apache.lucene.document.ShapeField.QueryRelation;
+import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.geo.Rectangle2D;
import org.apache.lucene.index.PointValues.Relation;
@@ -70,6 +71,16 @@ final class LatLonShapeBoundingBoxQuery extends ShapeQuery {
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ // decode indexed triangle
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ return rectangle2D.withinTriangle(scratchTriangle.aX, scratchTriangle.aY, scratchTriangle.ab,
+ scratchTriangle.bX, scratchTriangle.bY, scratchTriangle.bc,
+ scratchTriangle.cX, scratchTriangle.cY, scratchTriangle.ca);
+ }
+
+ @Override
public boolean equals(Object o) {
return sameClassAs(o) && equalsTo(getClass().cast(o));
}
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
index 04eebcc..b8756361 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
@@ -74,7 +74,7 @@ final class LatLonShapeLineQuery extends ShapeQuery {
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
- int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
double minLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(minTriangle, minYOffset));
double minLon = GeoEncodingUtils.decodeLongitude(NumericUtils.sortableBytesToInt(minTriangle, minXOffset));
double maxLat = GeoEncodingUtils.decodeLatitude(NumericUtils.sortableBytesToInt(maxTriangle, maxYOffset));
@@ -104,6 +104,20 @@ final class LatLonShapeLineQuery extends ShapeQuery {
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ double alat = GeoEncodingUtils.decodeLatitude(scratchTriangle.aY);
+ double alon = GeoEncodingUtils.decodeLongitude(scratchTriangle.aX);
+ double blat = GeoEncodingUtils.decodeLatitude(scratchTriangle.bY);
+ double blon = GeoEncodingUtils.decodeLongitude(scratchTriangle.bX);
+ double clat = GeoEncodingUtils.decodeLatitude(scratchTriangle.cY);
+ double clon = GeoEncodingUtils.decodeLongitude(scratchTriangle.cX);
+
+ return line2D.withinTriangle(alon, alat, scratchTriangle.ab, blon, blat, scratchTriangle.bc, clon, clat, scratchTriangle.ca);
+ }
+
+ @Override
public String toString(String field) {
final StringBuilder sb = new StringBuilder();
sb.append(getClass().getSimpleName());
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
index a4d996b..38eee1d 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -98,6 +98,20 @@ final class LatLonShapePolygonQuery extends ShapeQuery {
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ double alat = GeoEncodingUtils.decodeLatitude(scratchTriangle.aY);
+ double alon = GeoEncodingUtils.decodeLongitude(scratchTriangle.aX);
+ double blat = GeoEncodingUtils.decodeLatitude(scratchTriangle.bY);
+ double blon = GeoEncodingUtils.decodeLongitude(scratchTriangle.bX);
+ double clat = GeoEncodingUtils.decodeLatitude(scratchTriangle.cY);
+ double clon = GeoEncodingUtils.decodeLongitude(scratchTriangle.cX);
+
+ return poly2D.withinTriangle(alon, alat, scratchTriangle.ab, blon, blat, scratchTriangle.bc, clon, clat, scratchTriangle.ca);
+ }
+
+ @Override
public String toString(String field) {
final StringBuilder sb = new StringBuilder();
sb.append(getClass().getSimpleName());
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/ShapeField.java b/lucene/sandbox/src/java/org/apache/lucene/document/ShapeField.java
index efbe17c..fee0862 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/ShapeField.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/ShapeField.java
@@ -88,7 +88,7 @@ public final class ShapeField {
/** Query Relation Types **/
public enum QueryRelation {
- INTERSECTS, WITHIN, DISJOINT
+ INTERSECTS, WITHIN, DISJOINT, CONTAINS
}
private static final int MINY_MINX_MAXY_MAXX_Y_X = 0;
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/ShapeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/ShapeQuery.java
index d27a3ea..ba7151a 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/ShapeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/ShapeQuery.java
@@ -20,6 +20,7 @@ import java.io.IOException;
import java.util.Objects;
import org.apache.lucene.document.ShapeField.QueryRelation;
+import org.apache.lucene.geo.Component2D;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.LeafReaderContext;
@@ -61,9 +62,11 @@ abstract class ShapeQuery extends Query {
/** field name */
final String field;
/** query relation
- * disjoint: {@code CELL_OUTSIDE_QUERY}
- * intersects: {@code CELL_CROSSES_QUERY},
- * within: {@code CELL_WITHIN_QUERY} */
+ * disjoint: {@link QueryRelation#DISJOINT},
+ * intersects: {@link QueryRelation#INTERSECTS},
+ * within: {@link QueryRelation#DISJOINT},
+ * contains: {@link QueryRelation#CONTAINS}
+ * */
final QueryRelation queryRelation;
protected ShapeQuery(String field, final QueryRelation queryType) {
@@ -85,6 +88,9 @@ abstract class ShapeQuery extends Query {
/** returns true if the provided triangle matches the query */
protected abstract boolean queryMatches(byte[] triangle, ShapeField.DecodedTriangle scratchTriangle, ShapeField.QueryRelation queryRelation);
+ /** Return the within relationship between the query and the indexed shape.*/
+ protected abstract Component2D.WithinRelation queryWithin(byte[] triangle, ShapeField.DecodedTriangle scratchTriangle);
+
/** relates a range of triangles (internal node) to the query */
protected Relation relateRangeToQuery(byte[] minTriangle, byte[] maxTriangle, QueryRelation queryRelation) {
// compute bounding box of internal node
@@ -132,11 +138,10 @@ abstract class ShapeQuery extends Query {
final Weight weight = this;
final Relation rel = relateRangeToQuery(values.getMinPackedValue(), values.getMaxPackedValue(), queryRelation);
- if (rel == Relation.CELL_OUTSIDE_QUERY) {
+ if (rel == Relation.CELL_OUTSIDE_QUERY || (rel == Relation.CELL_INSIDE_QUERY && queryRelation == QueryRelation.CONTAINS)) {
// no documents match the query
return null;
- }
- else if (values.getDocCount() == reader.maxDoc() && rel == Relation.CELL_INSIDE_QUERY) {
+ } else if (values.getDocCount() == reader.maxDoc() && rel == Relation.CELL_INSIDE_QUERY) {
// all documents match the query
return new ScorerSupplier() {
@Override
@@ -151,6 +156,7 @@ abstract class ShapeQuery extends Query {
};
} else {
if (queryRelation != QueryRelation.INTERSECTS
+ && queryRelation != QueryRelation.CONTAINS
&& hasAnyHits(query, values) == false) {
// First we check if we have any hits so we are fast in the adversarial case where
// the shape does not match any documents and we are in the dense case
@@ -226,6 +232,7 @@ abstract class ShapeQuery extends Query {
case INTERSECTS: return getSparseScorer(reader, weight, boost, scoreMode);
case WITHIN:
case DISJOINT: return getDenseScorer(reader, weight, boost, scoreMode);
+ case CONTAINS: return getContainsDenseScorer(reader, weight, boost, scoreMode);
default: throw new IllegalArgumentException("Unsupported query type :[" + query.getQueryRelation() + "]");
}
}
@@ -278,6 +285,17 @@ abstract class ShapeQuery extends Query {
return new ConstantScoreScorer(weight, boost, scoreMode, iterator);
}
+ private Scorer getContainsDenseScorer(LeafReader reader, Weight weight, final float boost, ScoreMode scoreMode) throws IOException {
+ final FixedBitSet result = new FixedBitSet(reader.maxDoc());
+ final long[] cost = new long[]{0};
+ // Get potential documents.
+ final FixedBitSet excluded = new FixedBitSet(reader.maxDoc());
+ values.intersect(getContainsDenseVisitor(query, result, excluded, cost));
+ result.andNot(excluded);
+ final DocIdSetIterator iterator = new BitSetIterator(result, cost[0]);
+ return new ConstantScoreScorer(weight, boost, scoreMode, iterator);
+ }
+
@Override
public long cost() {
if (cost == -1) {
@@ -389,6 +407,48 @@ abstract class ShapeQuery extends Query {
};
}
+ /** create a visitor that adds documents that match the query using a dense bitset; used with CONTAINS */
+ private static IntersectVisitor getContainsDenseVisitor(final ShapeQuery query, final FixedBitSet result, final FixedBitSet excluded, final long[] cost) {
+ return new IntersectVisitor() {
+ final ShapeField.DecodedTriangle scratchTriangle = new ShapeField.DecodedTriangle();
+
+ @Override
+ public void visit(int docID) {
+ excluded.set(docID);
+ }
+
+ @Override
+ public void visit(int docID, byte[] t) {
+ Component2D.WithinRelation within = query.queryWithin(t, scratchTriangle);
+ if (within == Component2D.WithinRelation.CANDIDATE) {
+ cost[0]++;
+ result.set(docID);
+ } else if (within == Component2D.WithinRelation.NOTWITHIN) {
+ excluded.set(docID);
+ }
+ }
+
+ @Override
+ public void visit(DocIdSetIterator iterator, byte[] t) throws IOException {
+ Component2D.WithinRelation within = query.queryWithin(t, scratchTriangle);
+ int docID;
+ while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+ if (within == Component2D.WithinRelation.CANDIDATE) {
+ cost[0]++;
+ result.set(docID);
+ } else if (within == Component2D.WithinRelation.NOTWITHIN) {
+ excluded.set(docID);
+ }
+ }
+ }
+
+ @Override
+ public Relation compare(byte[] minTriangle, byte[] maxTriangle) {
+ return query.relateRangeToQuery(minTriangle, maxTriangle, query.getQueryRelation());
+ }
+ };
+ }
+
/** create a visitor that clears documents that do not match the polygon query using a dense bitset; used with WITHIN & DISJOINT */
private static IntersectVisitor getInverseDenseVisitor(final ShapeQuery query, final FixedBitSet result, final long[] cost) {
return new IntersectVisitor() {
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java b/lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java
index d55356f..a289223 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/XYShape.java
@@ -25,6 +25,8 @@ import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.index.PointValues; // javadoc
import org.apache.lucene.geo.XYLine;
import org.apache.lucene.geo.XYPolygon;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.Query;
import static org.apache.lucene.geo.XYEncodingUtils.encode;
@@ -93,11 +95,25 @@ public class XYShape {
/** create a query to find all cartesian shapes that intersect a provided linestring (or array of linestrings) **/
public static Query newLineQuery(String field, QueryRelation queryRelation, XYLine... lines) {
+ if (queryRelation == QueryRelation.CONTAINS && lines.length > 1) {
+ BooleanQuery.Builder builder = new BooleanQuery.Builder();
+ for (int i =0; i < lines.length; i++) {
+ builder.add(newLineQuery(field, queryRelation, lines[i]), BooleanClause.Occur.MUST);
+ }
+ return builder.build();
+ }
return new XYShapeLineQuery(field, queryRelation, lines);
}
/** create a query to find all cartesian shapes that intersect a provided polygon (or array of polygons) **/
public static Query newPolygonQuery(String field, QueryRelation queryRelation, XYPolygon... polygons) {
+ if (queryRelation == QueryRelation.CONTAINS && polygons.length > 1) {
+ BooleanQuery.Builder builder = new BooleanQuery.Builder();
+ for (int i =0; i < polygons.length; i++) {
+ builder.add(newPolygonQuery(field, queryRelation, polygons[i]), BooleanClause.Occur.MUST);
+ }
+ return builder.build();
+ }
return new XYShapePolygonQuery(field, queryRelation, polygons);
}
}
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
index 4a9e465..f1d9f82 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
@@ -17,9 +17,13 @@
package org.apache.lucene.document;
import org.apache.lucene.document.ShapeField.QueryRelation;
+import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.XYRectangle;
import org.apache.lucene.geo.XYRectangle2D;
import org.apache.lucene.index.PointValues;
+import org.apache.lucene.util.NumericUtils;
+
+import static org.apache.lucene.geo.XYEncodingUtils.decode;
/**
* Finds all previously indexed cartesian shapes that intersect the specified bounding box.
@@ -30,21 +34,46 @@ import org.apache.lucene.index.PointValues;
* @lucene.experimental
**/
public class XYShapeBoundingBoxQuery extends ShapeQuery {
- final XYRectangle2D rectangle2D;
+ final Component2D rectangle2D;
+ final private XYRectangle rectangle;
+
public XYShapeBoundingBoxQuery(String field, QueryRelation queryRelation, double minX, double maxX, double minY, double maxY) {
super(field, queryRelation);
- XYRectangle rectangle = new XYRectangle(minX, maxX, minY, maxY);
- this.rectangle2D = XYRectangle2D.create(rectangle);
+ this.rectangle = new XYRectangle(minX, maxX, minY, maxY);
+ this.rectangle2D = XYRectangle2D.create(this.rectangle);
}
@Override
protected PointValues.Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- if (queryRelation == QueryRelation.INTERSECTS || queryRelation == QueryRelation.DISJOINT) {
- return rectangle2D.intersectRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ double minY = decode(NumericUtils.sortableBytesToInt(minTriangle, minYOffset));
+ double minX = decode(NumericUtils.sortableBytesToInt(minTriangle, minXOffset));
+ double maxY = decode(NumericUtils.sortableBytesToInt(maxTriangle, maxYOffset));
+ double maxX = decode(NumericUtils.sortableBytesToInt(maxTriangle, maxXOffset));
+ // check internal node against query
+ PointValues.Relation rel = rectangle2D.relate(minX, maxX, minY, maxY);
+ // TODO: Check if this really helps
+ if (queryRelation == QueryRelation.INTERSECTS && rel == PointValues.Relation.CELL_CROSSES_QUERY) {
+ // for intersects we can restrict the conditions by using the inner box
+ double innerMaxY = decode(NumericUtils.sortableBytesToInt(maxTriangle, minYOffset));
+ if (rectangle2D.relate(minX, maxX, minY, innerMaxY) == PointValues.Relation.CELL_INSIDE_QUERY) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ double innerMaX = decode(NumericUtils.sortableBytesToInt(maxTriangle, minXOffset));
+ if (rectangle2D.relate(minX, innerMaX, minY, maxY) == PointValues.Relation.CELL_INSIDE_QUERY) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ double innerMinY = decode(NumericUtils.sortableBytesToInt(minTriangle, maxYOffset));
+ if (rectangle2D.relate(minX, maxX, innerMinY, maxY) == PointValues.Relation.CELL_INSIDE_QUERY) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ double innerMinX = decode(NumericUtils.sortableBytesToInt(minTriangle, maxXOffset));
+ if (rectangle2D.relate(innerMinX, maxX, minY, maxY) == PointValues.Relation.CELL_INSIDE_QUERY) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
}
- return rectangle2D.relateRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ return rel;
}
/** returns true if the query matches the encoded triangle */
@@ -53,35 +82,49 @@ public class XYShapeBoundingBoxQuery extends ShapeQuery {
// decode indexed triangle
ShapeField.decodeTriangle(t, scratchTriangle);
- int aY = scratchTriangle.aY;
- int aX = scratchTriangle.aX;
- int bY = scratchTriangle.bY;
- int bX = scratchTriangle.bX;
- int cY = scratchTriangle.cY;
- int cX = scratchTriangle.cX;
+ double aY = decode(scratchTriangle.aY);
+ double aX = decode(scratchTriangle.aX);
+ double bY = decode(scratchTriangle.bY);
+ double bX = decode(scratchTriangle.bX);
+ double cY = decode(scratchTriangle.cY);
+ double cX = decode(scratchTriangle.cX);
switch (queryRelation) {
- case INTERSECTS: return rectangle2D.intersectsTriangle(aX, aY, bX, bY, cX, cY);
- case WITHIN: return rectangle2D.containsTriangle(aX, aY, bX, bY, cX, cY);
- case DISJOINT: return rectangle2D.intersectsTriangle(aX, aY, bX, bY, cX, cY) == false;
+ case INTERSECTS: return rectangle2D.relateTriangle(aX, aY, bX, bY, cX, cY) != PointValues.Relation.CELL_OUTSIDE_QUERY;
+ case WITHIN: return rectangle2D.contains(aX, aY) && rectangle2D.contains(bX, bY) && rectangle2D.contains(cX, cY);
+ case DISJOINT: return rectangle2D.relateTriangle(aX, aY, bX, bY, cX, cY) == PointValues.Relation.CELL_OUTSIDE_QUERY;
default: throw new IllegalArgumentException("Unsupported query type :[" + queryRelation + "]");
}
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ double aY = decode(scratchTriangle.aY);
+ double aX = decode(scratchTriangle.aX);
+ double bY = decode(scratchTriangle.bY);
+ double bX = decode(scratchTriangle.bX);
+ double cY = decode(scratchTriangle.cY);
+ double cX = decode(scratchTriangle.cX);
+
+ return rectangle2D.withinTriangle(aX, aY, scratchTriangle.ab, bX, bY, scratchTriangle.bc, cX, cY, scratchTriangle.ca);
+ }
+
+ @Override
public boolean equals(Object o) {
return sameClassAs(o) && equalsTo(getClass().cast(o));
}
@Override
protected boolean equalsTo(Object o) {
- return super.equalsTo(o) && rectangle2D.equals(((XYShapeBoundingBoxQuery)o).rectangle2D);
+ return super.equalsTo(o) && rectangle.equals(((XYShapeBoundingBoxQuery)o).rectangle);
}
@Override
public int hashCode() {
int hash = super.hashCode();
- hash = 31 * hash + rectangle2D.hashCode();
+ hash = 31 * hash + rectangle.hashCode();
return hash;
}
@@ -95,7 +138,7 @@ public class XYShapeBoundingBoxQuery extends ShapeQuery {
sb.append(this.field);
sb.append(':');
}
- sb.append(rectangle2D.toString());
+ sb.append(rectangle.toString());
return sb.toString();
}
-}
+}
\ No newline at end of file
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeLineQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeLineQuery.java
index 52da2f2..0fd9750 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeLineQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeLineQuery.java
@@ -106,6 +106,20 @@ final class XYShapeLineQuery extends ShapeQuery {
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ double alat = decode(scratchTriangle.aY);
+ double alon = decode(scratchTriangle.aX);
+ double blat = decode(scratchTriangle.bY);
+ double blon = decode(scratchTriangle.bX);
+ double clat = decode(scratchTriangle.cY);
+ double clon = decode(scratchTriangle.cX);
+
+ return line2D.withinTriangle(alon, alat, scratchTriangle.ab, blon, blat, scratchTriangle.bc, clon, clat, scratchTriangle.ca);
+ }
+
+ @Override
public String toString(String field) {
final StringBuilder sb = new StringBuilder();
sb.append(getClass().getSimpleName());
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapePolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapePolygonQuery.java
index 99acdb7..47fba09 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapePolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapePolygonQuery.java
@@ -97,6 +97,20 @@ final class XYShapePolygonQuery extends ShapeQuery {
}
@Override
+ protected Component2D.WithinRelation queryWithin(byte[] t, ShapeField.DecodedTriangle scratchTriangle) {
+ ShapeField.decodeTriangle(t, scratchTriangle);
+
+ double alat = decode(scratchTriangle.aY);
+ double alon = decode(scratchTriangle.aX);
+ double blat = decode(scratchTriangle.bY);
+ double blon = decode(scratchTriangle.bX);
+ double clat = decode(scratchTriangle.cY);
+ double clon = decode(scratchTriangle.cX);
+
+ return poly2D.withinTriangle(alon, alat, scratchTriangle.ab, blon, blat, scratchTriangle.bc, clon, clat, scratchTriangle.ca);
+ }
+
+ @Override
public String toString(String field) {
final StringBuilder sb = new StringBuilder();
sb.append(getClass().getSimpleName());
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
index 02d1422..ab9c087 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -133,6 +133,57 @@ public final class Line2D implements Component2D {
return Relation.CELL_OUTSIDE_QUERY;
}
+ @Override
+ public WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, boolean ab, double bx, double by, boolean bc, double cx, double cy, boolean ca) {
+ // short cut, lines and points cannot contain this type of shape
+ if ((ax == bx && ay == by) || (ax == cx && ay == cy) || (bx == cx && by == cy)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ WithinRelation relation = WithinRelation.DISJOINT;
+ // if any of the edges intersects an the edge belongs to the shape then it cannot be within.
+ // if it only intersects edges that do not belong to the shape, then it is a candidate
+ // we skip edges at the dateline to support shapes crossing it
+ if (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by)) {
+ if (ab == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy)) {
+ if (bc == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay)) {
+ if (ca == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ // if any of the edges crosses and edge that does not belong to the shape
+ // then it is a candidate for within
+ if (relation == WithinRelation.CANDIDATE) {
+ return WithinRelation.CANDIDATE;
+ }
+
+ // Check if shape is within the triangle
+ if (Component2D.pointInTriangle(minX, maxX, minY, maxY, tree.x1, tree.y1, ax, ay, bx, by, cx, cy) == true) {
+ return WithinRelation.CANDIDATE;
+ }
+ return relation;
+ }
+
/** create a Line2D edge tree from provided array of Linestrings */
public static Component2D create(Line... lines) {
Component2D components[] = new Component2D[lines.length];
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
index da33337..44fd8d8 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
@@ -170,6 +170,66 @@ public class Rectangle2D {
return false;
}
+ /** Returns the Within relation to the provided triangle */
+ public Component2D.WithinRelation withinTriangle(int ax, int ay, boolean ab, int bx, int by, boolean bc, int cx, int cy, boolean ca) {
+ if (this.crossesDateline() == true) {
+ throw new IllegalArgumentException("withinTriangle is not supported for rectangles crossing the date line");
+ }
+ // Short cut, lines and points cannot contain a bbox
+ if ((ax == bx && ay == by) || (ax == cx && ay == cy) || (bx == cx && by == cy)) {
+ return Component2D.WithinRelation.DISJOINT;
+ }
+ // Compute bounding box of triangle
+ int tMinX = StrictMath.min(StrictMath.min(ax, bx), cx);
+ int tMaxX = StrictMath.max(StrictMath.max(ax, bx), cx);
+ int tMinY = StrictMath.min(StrictMath.min(ay, by), cy);
+ int tMaxY = StrictMath.max(StrictMath.max(ay, by), cy);
+ // Bounding boxes disjoint?
+ if (boxesAreDisjoint(tMinX, tMaxX, tMinY, tMaxY, minX, maxX, minY, maxY)) {
+ return Component2D.WithinRelation.DISJOINT;
+ }
+ // Points belong to the shape so if points are inside the rectangle then it cannot be within.
+ if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY) ||
+ bboxContainsPoint(bx, by, minX, maxX, minY, maxY) ||
+ bboxContainsPoint(cx, cy, minX, maxX, minY, maxY)) {
+ return Component2D.WithinRelation.NOTWITHIN;
+ }
+ // If any of the edges intersects an edge belonging to the shape then it cannot be within.
+ Component2D.WithinRelation relation = Component2D.WithinRelation.DISJOINT;
+ if (edgeIntersectsBox(ax, ay, bx, by, minX, maxX, minY, maxY) == true) {
+ if (ab == true) {
+ return Component2D.WithinRelation.NOTWITHIN;
+ } else {
+ relation = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ if (edgeIntersectsBox(bx, by, cx, cy, minX, maxX, minY, maxY) == true) {
+ if (bc == true) {
+ return Component2D.WithinRelation.NOTWITHIN;
+ } else {
+ relation = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+
+ if (edgeIntersectsBox(cx, cy, ax, ay, minX, maxX, minY, maxY) == true) {
+ if (ca == true) {
+ return Component2D.WithinRelation.NOTWITHIN;
+ } else {
+ relation = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ // If any of the rectangle edges crosses a triangle edge that does not belong to the shape
+ // then it is a candidate for within
+ if (relation == Component2D.WithinRelation.CANDIDATE) {
+ return Component2D.WithinRelation.CANDIDATE;
+ }
+ // Check if shape is within the triangle
+ if (Tessellator.pointInTriangle(minX, minY, ax, ay, bx, by, cx, cy)) {
+ return Component2D.WithinRelation.CANDIDATE;
+ }
+ return relation;
+ }
+
/** Checks if the rectangle contains the provided triangle **/
public boolean containsTriangle(int ax, int ay, int bx, int by, int cx, int cy) {
if (this.crossesDateline() == true) {
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/XYRectangle2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/XYRectangle2D.java
index a125916..54b5078 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/XYRectangle2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/XYRectangle2D.java
@@ -16,42 +16,234 @@
*/
package org.apache.lucene.geo;
-import static org.apache.lucene.geo.XYEncodingUtils.decode;
-import static org.apache.lucene.geo.XYEncodingUtils.encode;
+import java.util.Objects;
+
+import org.apache.lucene.index.PointValues;
+
+import static org.apache.lucene.geo.GeoUtils.orient;
/**
* 2D rectangle implementation containing cartesian spatial logic.
*
* @lucene.internal
*/
-public class XYRectangle2D extends Rectangle2D {
+public class XYRectangle2D implements Component2D {
+
+ private final double minX;
+ private final double maxX;
+ private final double minY;
+ private final double maxY;
protected XYRectangle2D(double minX, double maxX, double minY, double maxY) {
- super(encode(minX), encode(maxX), encode(minY), encode(maxY));
+ this.minX = minX;
+ this.maxX = maxX;
+ this.minY = minY;
+ this.maxY = maxY;
+ }
+
+ @Override
+ public double getMinX() {
+ return minX;
+ }
+
+ @Override
+ public double getMaxX() {
+ return maxX;
+ }
+
+ @Override
+ public double getMinY() {
+ return minY;
+ }
+
+ @Override
+ public double getMaxY() {
+ return maxY;
}
- /** Builds a Rectangle2D from rectangle */
- public static XYRectangle2D create(XYRectangle rectangle) {
- return new XYRectangle2D(rectangle.minX, rectangle.maxX, rectangle.minY, rectangle.maxY);
+ @Override
+ public boolean contains(double x, double y) {
+ return Component2D.containsPoint(x, y, this.minX, this.maxX, this.minY, this.maxY);
+ }
+
+ @Override
+ public PointValues.Relation relate(double minX, double maxX, double minY, double maxY) {
+ if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
+ }
+ if (Component2D.within(minX, maxX, minY, maxY, this.minX, this.maxX, this.minY, this.maxY)) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+
+ @Override
+ public PointValues.Relation relateTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, double bx, double by, double cx, double cy) {
+
+
+ if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
+ }
+ int edgesContain = numberOfCorners(ax, ay, bx, by, cx, cy);
+ if (edgesContain == 3) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ } else if (edgesContain != 0) {
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ } else if (Component2D.pointInTriangle(minX, maxX, minY, maxY, this.minX, this.minY,ax, ay, bx, by, cx, cy)
+ || edgesIntersect(ax, ay, bx, by)
+ || edgesIntersect(bx, by, cx, cy)
+ || edgesIntersect(cx, cy, ax, ay)) {
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
}
@Override
- public boolean crossesDateline() {
+ public WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, boolean ab, double bx, double by, boolean bc, double cx, double cy, boolean ca) {
+ // Short cut, lines and points cannot contain a bbox
+ if ((ax == bx && ay == by) || (ax == cx && ay == cy) || (bx == cx && by == cy)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ // Bounding boxes disjoint?
+ if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ // Points belong to the shape so if points are inside the rectangle then it cannot be within.
+ if (contains(ax, ay) || contains(bx, by) || contains(cx, cy)) {
+ return WithinRelation.NOTWITHIN;
+ }
+ // If any of the edges intersects an edge belonging to the shape then it cannot be within.
+ WithinRelation relation = WithinRelation.DISJOINT;
+ if (edgesIntersect(ax, ay, bx, by) == true) {
+ if (ab == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ if (edgesIntersect(bx, by, cx, cy) == true) {
+ if (bc == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ if (edgesIntersect(cx, cy, ax, ay) == true) {
+ if (ca == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ // If any of the rectangle edges crosses a triangle edge that does not belong to the shape
+ // then it is a candidate for within
+ if (relation == WithinRelation.CANDIDATE) {
+ return WithinRelation.CANDIDATE;
+ }
+ // Check if shape is within the triangle
+ if (Component2D.pointInTriangle(minX, maxX, minY, maxY, this.minX, this.minY, ax, ay, bx, by, cx, cy)) {
+ return WithinRelation.CANDIDATE;
+ }
+ return relation;
+ }
+
+ private boolean edgesIntersect(double ax, double ay, double bx, double by) {
+ // shortcut: if edge is a point (occurs w/ Line shapes); simply check bbox w/ point
+ if (ax == bx && ay == by) {
+ return false;
+ }
+
+ // shortcut: check bboxes of edges are disjoint
+ if ( Math.max(ax, bx) < minX || Math.min(ax, bx) > maxX || Math.min(ay, by) > maxY || Math.max(ay, by) < minY) {
+ return false;
+ }
+
+ // top
+ if (orient(ax, ay, bx, by, minX, maxY) * orient(ax, ay, bx, by, maxX, maxY) <= 0 &&
+ orient(minX, maxY, maxX, maxY, ax, ay) * orient(minX, maxY, maxX, maxY, bx, by) <= 0) {
+ return true;
+ }
+
+ // right
+ if (orient(ax, ay, bx, by, maxX, maxY) * orient(ax, ay, bx, by, maxX, minY) <= 0 &&
+ orient(maxX, maxY, maxX, minY, ax, ay) * orient(maxX, maxY, maxX, minY, bx, by) <= 0) {
+ return true;
+ }
+
+ // bottom
+ if (orient(ax, ay, bx, by, maxX, minY) * orient(ax, ay, bx, by, minX, minY) <= 0 &&
+ orient(maxX, minY, minX, minY, ax, ay) * orient(maxX, minY, minX, minY, bx, by) <= 0) {
+ return true;
+ }
+
+ // left
+ if (orient(ax, ay, bx, by, minX, minY) * orient(ax, ay, bx, by, minX, maxY) <= 0 &&
+ orient(minX, minY, minX, maxY, ax, ay) * orient(minX, minY, minX, maxY, bx, by) <= 0) {
+ return true;
+ }
return false;
}
+ private int numberOfCorners(double ax, double ay, double bx, double by, double cx, double cy) {
+ int containsCount = 0;
+ if (contains(ax, ay)) {
+ containsCount++;
+ }
+ if (contains(bx, by)) {
+ containsCount++;
+ }
+ if (contains(cx, cy)) {
+ containsCount++;
+ }
+ return containsCount;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof XYRectangle2D)) return false;
+ XYRectangle2D that = (XYRectangle2D) o;
+ return minX == that.minX &&
+ maxX == that.maxX &&
+ minY == that.minY &&
+ maxY == that.maxY;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = Objects.hash(minX, maxX, minY, maxY);
+ return result;
+ }
+
@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
sb.append("XYRectangle(x=");
- sb.append(decode(minX));
+ sb.append(minX);
sb.append(" TO ");
- sb.append(decode(maxX));
+ sb.append(maxX);
sb.append(" y=");
- sb.append(decode(minY));
+ sb.append(minY);
sb.append(" TO ");
- sb.append(decode(maxY));
+ sb.append(maxY);
sb.append(")");
return sb.toString();
}
-}
+
+ /** create a component2D from provided array of rectangles */
+ public static Component2D create(XYRectangle... rectangles) {
+ XYRectangle2D[] components = new XYRectangle2D[rectangles.length];
+ for (int i = 0; i < components.length; ++i) {
+ components[i] = new XYRectangle2D(XYEncodingUtils.decode(XYEncodingUtils.encode(rectangles[i].minX)),
+ XYEncodingUtils.decode(XYEncodingUtils.encode(rectangles[i].maxX)),
+ XYEncodingUtils.decode(XYEncodingUtils.encode(rectangles[i].minY)),
+ XYEncodingUtils.decode(XYEncodingUtils.encode(rectangles[i].maxY)));
+ }
+ return ComponentTree.create(components);
+ }
+}
\ No newline at end of file
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
index 91b0706..d5f2ddd 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
@@ -225,6 +225,16 @@ public abstract class BaseLatLonShapeTestCase extends BaseShapeTestCase {
protected Encoder getEncoder() {
return new Encoder() {
@Override
+ double decodeX(int encoded) {
+ return decodeLongitude(encoded);
+ }
+
+ @Override
+ double decodeY(int encoded) {
+ return decodeLatitude(encoded);
+ }
+
+ @Override
double quantizeX(double raw) {
return decodeLongitude(encodeLongitude(raw));
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/BaseShapeTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/document/BaseShapeTestCase.java
index 615d802..606790d 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseShapeTestCase.java
@@ -24,6 +24,7 @@ import java.util.Set;
import com.carrotsearch.randomizedtesting.generators.RandomPicks;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
+import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
@@ -60,7 +61,7 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
protected static final String FIELD_NAME = "shape";
public final Encoder ENCODER;
public final Validator VALIDATOR;
- protected static final QueryRelation[] POINT_LINE_RELATIONS = {QueryRelation.INTERSECTS, QueryRelation.DISJOINT};
+ protected static final QueryRelation[] POINT_LINE_RELATIONS = {QueryRelation.INTERSECTS, QueryRelation.DISJOINT, QueryRelation.CONTAINS};
public BaseShapeTestCase() {
ENCODER = getEncoder();
@@ -312,17 +313,25 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
} else if (shapes[id] == null) {
expected = false;
} else {
- // check quantized poly against quantized query
- if (qMinLon > qMaxLon && rectCrossesDateline(rect) == false) {
- // if the quantization creates a false dateline crossing (because of encodeCeil):
- // then do not use encodeCeil
- qMinLon = ENCODER.quantizeX(rectMinX(rect));
- }
-
if (qMinLat > qMaxLat) {
qMinLat = ENCODER.quantizeY(rectMaxY(rect));
}
- expected = VALIDATOR.setRelation(queryRelation).testBBoxQuery(qMinLat, qMaxLat, qMinLon, qMaxLon, shapes[id]);
+ if (queryRelation == QueryRelation.CONTAINS && rectCrossesDateline(rect)) {
+ //For contains we need to call the validator for each section. It is only expected
+ //if both sides are contained.
+ expected = VALIDATOR.setRelation(queryRelation).testBBoxQuery(qMinLat, qMaxLat, qMinLon, GeoUtils.MAX_LON_INCL, shapes[id]);
+ if (expected) {
+ expected = VALIDATOR.setRelation(queryRelation).testBBoxQuery(qMinLat, qMaxLat, GeoUtils.MIN_LON_INCL, qMaxLon, shapes[id]);
+ }
+ } else {
+ // check quantized poly against quantized query
+ if (qMinLon > qMaxLon && rectCrossesDateline(rect) == false) {
+ // if the quantization creates a false dateline crossing (because of encodeCeil):
+ // then do not use encodeCeil
+ qMinLon = ENCODER.quantizeX(rectMinX(rect));
+ }
+ expected = VALIDATOR.setRelation(queryRelation).testBBoxQuery(qMinLat, qMaxLat, qMinLon, qMaxLon, shapes[id]);
+ }
}
if (hits.get(docID) != expected) {
@@ -541,6 +550,8 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
protected abstract Validator getValidator();
protected static abstract class Encoder {
+ abstract double decodeX(int encoded);
+ abstract double decodeY(int encoded);
abstract double quantizeX(double raw);
abstract double quantizeXCeil(double raw);
abstract double quantizeY(double raw);
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
index bc65426..a60356a 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
@@ -125,6 +125,15 @@ public abstract class BaseXYShapeTestCase extends BaseShapeTestCase {
protected Encoder getEncoder() {
return new Encoder() {
@Override
+ double decodeX(int encoded) {
+ return decode(encoded);
+ }
+
+ @Override
+ double decodeY(int encoded) {
+ return decode(encoded);
+ }
+ @Override
double quantizeX(double raw) {
return decode(encode(raw));
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
index 2bc8098..11b10da 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
@@ -80,24 +80,38 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
Line line = (Line)shape;
Rectangle2D rectangle2D = Rectangle2D.create(new Rectangle(minLat, maxLat, minLon, maxLon));
+ Component2D.WithinRelation withinRelation = Component2D.WithinRelation.DISJOINT;
for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
ShapeField.DecodedTriangle decoded = encoder.encodeDecodeTriangle(line.getLon(i), line.getLat(i), true, line.getLon(j), line.getLat(j), true, line.getLon(i), line.getLat(i), true);
if (queryRelation == QueryRelation.WITHIN) {
if (rectangle2D.containsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == false) {
return false;
}
+ } else if (queryRelation == QueryRelation.CONTAINS) {
+ Component2D.WithinRelation relation = rectangle2D.withinTriangle(decoded.aX, decoded.aY, decoded.ab, decoded.bX, decoded.bY, decoded.bc, decoded.cX, decoded.cY, decoded.ca);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ withinRelation = Component2D.WithinRelation.CANDIDATE;
+ }
} else {
if (rectangle2D.intersectsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == true) {
return queryRelation == QueryRelation.INTERSECTS;
}
}
}
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return withinRelation == Component2D.WithinRelation.CANDIDATE;
+ }
return queryRelation != QueryRelation.INTERSECTS;
}
@Override
public boolean testComponentQuery(Component2D component2D, Object shape) {
Line line = (Line) shape;
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return testWithinLine(component2D, (Line) shape);
+ }
for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
double[] qTriangle = encoder.quantizeTriangle(line.getLon(i), line.getLat(i), true, line.getLon(j), line.getLat(j), true, line.getLon(i), line.getLat(i), true);
Relation r = component2D.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
@@ -111,5 +125,19 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
}
return queryRelation == QueryRelation.INTERSECTS ? false : true;
}
+
+ private boolean testWithinLine(Component2D component2D, Line line) {
+ Component2D.WithinRelation answer = Component2D.WithinRelation.DISJOINT;
+ for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
+ double[] qTriangle = encoder.quantizeTriangle(line.getLon(i), line.getLat(i), true, line.getLon(j), line.getLat(j), true, line.getLon(i), line.getLat(i), true);
+ Component2D.WithinRelation relation = component2D.withinTriangle(qTriangle[1], qTriangle[0], true, qTriangle[3], qTriangle[2], true, qTriangle[5], qTriangle[4], true);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ answer = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ return answer == Component2D.WithinRelation.CANDIDATE;
+ }
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiLineShapeQueries.java
index 4416331..aff1eef 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiLineShapeQueries.java
@@ -80,13 +80,15 @@ public class TestLatLonMultiLineShapeQueries extends BaseLatLonShapeTestCase {
boolean b = LINEVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, l);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
@Override
@@ -96,13 +98,15 @@ public class TestLatLonMultiLineShapeQueries extends BaseLatLonShapeTestCase {
boolean b = LINEVALIDATOR.testComponentQuery(query, l);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPointShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPointShapeQueries.java
index 8214bf0..311c7a6 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPointShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPointShapeQueries.java
@@ -79,13 +79,15 @@ public class TestLatLonMultiPointShapeQueries extends BaseLatLonShapeTestCase {
boolean b = POINTVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
@Override
@@ -95,13 +97,15 @@ public class TestLatLonMultiPointShapeQueries extends BaseLatLonShapeTestCase {
boolean b = POINTVALIDATOR.testComponentQuery(query, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPolygonShapeQueries.java
index 7436df8..b1b180d 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonMultiPolygonShapeQueries.java
@@ -34,17 +34,26 @@ public class TestLatLonMultiPolygonShapeQueries extends BaseLatLonShapeTestCase
@Override
protected Polygon[] nextShape() {
-
int n = random().nextInt(4) + 1;
Polygon[] polygons = new Polygon[n];
for (int i =0; i < n; i++) {
+ int repetitions =0;
while (true) {
// if we can't tessellate; then random polygon generator created a malformed shape
Polygon p = (Polygon) getShapeType().nextShape();
try {
Tessellator.tessellate(p);
- polygons[i] = p;
- break;
+ //polygons are disjoint so CONTAINS works. Note that if we intersect
+ //any shape then contains return false.
+ if (isDisjoint(polygons, p)) {
+ polygons[i] = p;
+ break;
+ }
+ repetitions++;
+ if (repetitions > 50) {
+ //try again
+ return nextShape();
+ }
} catch (IllegalArgumentException e) {
continue;
}
@@ -53,6 +62,22 @@ public class TestLatLonMultiPolygonShapeQueries extends BaseLatLonShapeTestCase
return polygons;
}
+ private boolean isDisjoint(Polygon[] polygons, Polygon check) {
+ // we use bounding boxes so we do not get intersecting polygons.
+ for (Polygon polygon : polygons) {
+ if (polygon != null) {
+ if (getEncoder().quantizeY(polygon.minLat) > getEncoder().quantizeY(check.maxLat)
+ || getEncoder().quantizeY(polygon.maxLat) < getEncoder().quantizeY(check.minLat)
+ || getEncoder().quantizeX(polygon.minLon) > getEncoder().quantizeX(check.maxLon)
+ || getEncoder().quantizeX(polygon.maxLon) < getEncoder().quantizeX(check.minLon)) {
+ continue;
+ }
+ return false;
+ }
+ }
+ return true;
+ }
+
@Override
protected Field[] createIndexableFields(String name, Object o) {
Polygon[] polygons = (Polygon[]) o;
@@ -92,13 +117,15 @@ public class TestLatLonMultiPolygonShapeQueries extends BaseLatLonShapeTestCase
boolean b = POLYGONVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
@Override
@@ -108,13 +135,15 @@ public class TestLatLonMultiPolygonShapeQueries extends BaseLatLonShapeTestCase
boolean b = POLYGONVALIDATOR.testComponentQuery(query, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
index 4a8540b..dd741d7 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
@@ -74,6 +74,9 @@ public class TestLatLonPointShapeQueries extends BaseLatLonShapeTestCase {
@Override
public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return false;
+ }
Point p = (Point)shape;
double lat = encoder.quantizeY(p.lat);
double lon = encoder.quantizeX(p.lon);
@@ -90,6 +93,9 @@ public class TestLatLonPointShapeQueries extends BaseLatLonShapeTestCase {
@Override
public boolean testComponentQuery(Component2D query, Object shape) {
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return false;
+ }
Point p = (Point) shape;
double lat = encoder.quantizeY(p.lat);
double lon = encoder.quantizeX(p.lon);
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
index b9e4a3e..609398f 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
@@ -68,32 +68,46 @@ public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
Polygon p = (Polygon)shape;
Rectangle2D rectangle2D = Rectangle2D.create(new Rectangle(minLat, maxLat, minLon, maxLon));
+ Component2D.WithinRelation withinRelation = Component2D.WithinRelation.DISJOINT;
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(p);
for (Tessellator.Triangle t : tessellation) {
ShapeField.DecodedTriangle decoded = encoder.encodeDecodeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
- t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
- t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
+ t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
+ t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
if (queryRelation == QueryRelation.WITHIN) {
if (rectangle2D.containsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == false) {
return false;
}
+ } else if (queryRelation == QueryRelation.CONTAINS) {
+ Component2D.WithinRelation relation = rectangle2D.withinTriangle(decoded.aX, decoded.aY, decoded.ab, decoded.bX, decoded.bY, decoded.bc, decoded.cX, decoded.cY, decoded.ca);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ withinRelation = Component2D.WithinRelation.CANDIDATE;
+ }
} else {
if (rectangle2D.intersectsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == true) {
return queryRelation == QueryRelation.INTERSECTS;
}
}
}
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return withinRelation == Component2D.WithinRelation.CANDIDATE;
+ }
return queryRelation != QueryRelation.INTERSECTS;
}
@Override
public boolean testComponentQuery(Component2D query, Object o) {
Polygon shape = (Polygon) o;
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return testWithinPolygon(query, (Polygon) shape);
+ }
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
for (Tessellator.Triangle t : tessellation) {
double[] qTriangle = encoder.quantizeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
- t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
- t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
+ t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
+ t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
Relation r = query.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
if (queryRelation == QueryRelation.DISJOINT) {
if (r != Relation.CELL_OUTSIDE_QUERY) return false;
@@ -105,6 +119,25 @@ public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
}
return queryRelation == QueryRelation.INTERSECTS ? false : true;
}
+
+ private boolean testWithinPolygon(Component2D component2D, Polygon shape) {
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
+ Component2D.WithinRelation answer = Component2D.WithinRelation.DISJOINT;
+ for (Tessellator.Triangle t : tessellation) {
+ ShapeField.DecodedTriangle qTriangle = encoder.encodeDecodeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
+ t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
+ t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
+ Component2D.WithinRelation relation = component2D.withinTriangle(encoder.decodeX(qTriangle.aX), encoder.decodeY(qTriangle.aY), qTriangle.ab,
+ encoder.decodeX(qTriangle.bX), encoder.decodeY(qTriangle.bY), qTriangle.bc,
+ encoder.decodeX(qTriangle.cX), encoder.decodeY(qTriangle.cY), qTriangle.ca);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ answer = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ return answer == Component2D.WithinRelation.CANDIDATE;
+ }
}
@Nightly
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
index 0102bf7..644bfbe 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -151,6 +151,49 @@ public class TestLatLonShape extends LuceneTestCase {
IOUtils.close(reader, dir);
}
+ public void testBasicContains() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+
+ // add a random polygon document
+ double[] polyLats = new double[] {-10, -10, 10, 10, -10};
+ double[] polyLons = new double[] {-10, 10, 10, -10, -10};
+ Polygon p = new Polygon(polyLats, polyLons);
+ Document document = new Document();
+ addPolygonsToDoc(FIELDNAME, document, p);
+ writer.addDocument(document);
+
+ // add a line document
+ document = new Document();
+ // add a line string
+ double lats[] = new double[p.numPoints() - 1];
+ double lons[] = new double[p.numPoints() - 1];
+ for (int i = 0; i < lats.length; ++i) {
+ lats[i] = p.getPolyLat(i);
+ lons[i] = p.getPolyLon(i);
+ }
+ Line l = new Line(lats, lons);
+ addLineToDoc(FIELDNAME, document, l);
+ writer.addDocument(document);
+
+ ////// search /////
+ // search a Polygon
+ IndexReader reader = writer.getReader();
+ writer.close();
+ IndexSearcher searcher = newSearcher(reader);
+ polyLats = new double[] {-5, -5, 5, 5, -5};
+ polyLons = new double[] {-5, 5, 5, -5, -5};
+ Polygon query = new Polygon(polyLats, polyLons);
+ Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.CONTAINS, query);
+ assertEquals(1, searcher.count(q));
+
+ // search a bounding box
+ searcher = newSearcher(reader);
+ q = new LatLonShapeBoundingBoxQuery(FIELDNAME, QueryRelation.CONTAINS,0, 0, 0, 0);
+ assertEquals(1, searcher.count(q));
+ IOUtils.close(reader, dir);
+ }
+
/** test random polygons with a single hole */
public void testPolygonWithHole() throws Exception {
int numVertices = TestUtil.nextInt(random(), 50, 100);
@@ -224,6 +267,134 @@ public class TestLatLonShape extends LuceneTestCase {
IOUtils.close(reader, dir);
}
+ public void testWithinDateLine() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+ Document doc = new Document();
+
+ Polygon indexPoly1 = new Polygon(
+ new double[] {-7.5d, 15d, 15d, 0d, -7.5d},
+ new double[] {-180d, -180d, -176d, -176d, -180d}
+ );
+
+ Polygon indexPoly2 = new Polygon(
+ new double[] {15d, -7.5d, -15d, -10d, 15d, 15d},
+ new double[] {180d, 180d, 176d, 174d, 176d, 180d}
+ );
+
+ Field[] fields = LatLonShape.createIndexableFields("test", indexPoly1);
+ for (Field f : fields) {
+ doc.add(f);
+ }
+ fields = LatLonShape.createIndexableFields("test", indexPoly2);
+ for (Field f : fields) {
+ doc.add(f);
+ }
+ w.addDocument(doc);
+ w.forceMerge(1);
+
+ ///// search //////
+ IndexReader reader = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(reader);
+
+ Polygon[] searchPoly = new Polygon[] {
+ new Polygon(new double[] {-20d, 20d, 20d, -20d, -20d},
+ new double[] {-180d, -180d, -170d, -170d, -180d}),
+ new Polygon(new double[] {20d, -20d, -20d, 20d, 20d},
+ new double[] {180d, 180d, 170d, 170d, 180d})
+ };
+
+ Query q = LatLonShape.newPolygonQuery("test", QueryRelation.WITHIN, searchPoly);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.INTERSECTS, searchPoly);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.DISJOINT, searchPoly);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.CONTAINS, searchPoly);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.WITHIN, -20, 20, 170, -170);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.INTERSECTS, -20, 20, 170, -170);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.DISJOINT, -20, 20, 170, -170);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.CONTAINS, -20, 20, 170, -170);
+ assertEquals(0, searcher.count(q));
+
+ IOUtils.close(w, reader, dir);
+ }
+
+ public void testContainsDateLine() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+ Document doc = new Document();
+
+ Polygon indexPoly1 = new Polygon(
+ new double[] {-2d, -2d, 2d, 2d, -2d},
+ new double[] {178d, 180d, 180d, 178d, 178d}
+ );
+
+ Polygon indexPoly2 = new Polygon(
+ new double[] {-2d, -2d, 2d, 2d, -2d},
+ new double[] {-180d, -178d, -178d, -180d, -180d}
+ );
+
+ Field[] fields = LatLonShape.createIndexableFields("test", indexPoly1);
+ for (Field f : fields) {
+ doc.add(f);
+ }
+ fields = LatLonShape.createIndexableFields("test", indexPoly2);
+ for (Field f : fields) {
+ doc.add(f);
+ }
+ w.addDocument(doc);
+ w.forceMerge(1);
+
+ ///// search //////
+ IndexReader reader = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(reader);
+
+ Polygon[] searchPoly = new Polygon[] {
+ new Polygon(new double[] {-1d, -1d, 1d, 1d, -1d},
+ new double[] {179d, 180d, 180d, 179d, 179d}),
+ new Polygon(new double[] {-1d, -1d, 1d, 1d, -1d},
+ new double[] {-180d, -179d, -179d, -180d, -180d})
+ };
+ Query q;
+ // Not supported due to encoding
+ //Query q = LatLonShape.newPolygonQuery("test", QueryRelation.CONTAINS, searchPoly);
+ //assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.INTERSECTS, searchPoly);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.DISJOINT, searchPoly);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newPolygonQuery("test", QueryRelation.WITHIN, searchPoly);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.INTERSECTS, -1, 1, 179, -179);
+ assertEquals(1, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.WITHIN, -1, 1, 179, -179);
+ assertEquals(0, searcher.count(q));
+
+ q = LatLonShape.newBoxQuery("test", QueryRelation.DISJOINT, -1, 1, 179, -179);
+ assertEquals(0, searcher.count(q));
+
+ IOUtils.close(w, reader, dir);
+ }
+
public void testLUCENE8454() throws Exception {
Directory dir = newDirectory();
RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYLineShapeQueries.java
index f560291..4bbc76b 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYLineShapeQueries.java
@@ -76,26 +76,16 @@ public class TestXYLineShapeQueries extends BaseXYShapeTestCase {
@Override
public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
- XYLine line = (XYLine)shape;
- XYRectangle2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
- for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
- ShapeField.DecodedTriangle decoded = encoder.encodeDecodeTriangle(line.getX(i), line.getY(i), true, line.getX(j), line.getY(j), true, line.getX(i), line.getY(i), true);
- if (queryRelation == QueryRelation.WITHIN) {
- if (rectangle2D.containsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == false) {
- return false;
- }
- } else {
- if (rectangle2D.intersectsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == true) {
- return queryRelation == QueryRelation.INTERSECTS;
- }
- }
- }
- return queryRelation != QueryRelation.INTERSECTS;
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
public boolean testComponentQuery(Component2D query, Object shape) {
XYLine line = (XYLine) shape;
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return testWithinLine(query, (XYLine) shape);
+ }
for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
double[] qTriangle = encoder.quantizeTriangle(line.getX(i), line.getY(i), true, line.getX(j), line.getY(j), true, line.getX(i), line.getY(i), true);
Relation r = query.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
@@ -109,5 +99,19 @@ public class TestXYLineShapeQueries extends BaseXYShapeTestCase {
}
return queryRelation == QueryRelation.INTERSECTS ? false : true;
}
+
+ private boolean testWithinLine(Component2D tree, XYLine line) {
+ Component2D.WithinRelation answer = Component2D.WithinRelation.DISJOINT;
+ for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {
+ double[] qTriangle = encoder.quantizeTriangle(line.getX(i), line.getY(i), true, line.getX(j), line.getY(j), true, line.getX(i), line.getY(i), true);
+ Component2D.WithinRelation relation = tree.withinTriangle(qTriangle[1], qTriangle[0], true, qTriangle[3], qTriangle[2], true, qTriangle[5], qTriangle[4], true);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ answer = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ return answer == Component2D.WithinRelation.CANDIDATE;
+ }
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiLineShapeQueries.java
index 8139669..6e153c3 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiLineShapeQueries.java
@@ -22,6 +22,8 @@ import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.XYLine;
+import org.apache.lucene.geo.XYRectangle;
+import org.apache.lucene.geo.XYRectangle2D;
/** random cartesian bounding box, line, and polygon query tests for random indexed arrays of cartesian {@link XYLine} types */
public class TestXYMultiLineShapeQueries extends BaseXYShapeTestCase {
@@ -73,19 +75,9 @@ public class TestXYMultiLineShapeQueries extends BaseXYShapeTestCase {
}
@Override
- public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
- XYLine[] lines = (XYLine[])shape;
- for (XYLine l : lines) {
- boolean b = LINEVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, l);
- if (b == true && queryRelation == ShapeField.QueryRelation.INTERSECTS) {
- return true;
- } else if (b == false && queryRelation == ShapeField.QueryRelation.DISJOINT) {
- return false;
- } else if (b == false && queryRelation == ShapeField.QueryRelation.WITHIN) {
- return false;
- }
- }
- return queryRelation != ShapeField.QueryRelation.INTERSECTS;
+ public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
@@ -95,13 +87,15 @@ public class TestXYMultiLineShapeQueries extends BaseXYShapeTestCase {
boolean b = LINEVALIDATOR.testComponentQuery(query, l);
if (b == true && queryRelation == ShapeField.QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == ShapeField.QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == ShapeField.QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != ShapeField.QueryRelation.INTERSECTS;
+ return queryRelation != ShapeField.QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPointShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPointShapeQueries.java
index da65ffc..0c2f50c 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPointShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPointShapeQueries.java
@@ -21,6 +21,8 @@ import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
+import org.apache.lucene.geo.XYRectangle;
+import org.apache.lucene.geo.XYRectangle2D;
/** random cartesian bounding box, line, and polygon query tests for random indexed arrays of {@code x, y} points */
public class TestXYMultiPointShapeQueries extends BaseXYShapeTestCase {
@@ -72,19 +74,9 @@ public class TestXYMultiPointShapeQueries extends BaseXYShapeTestCase {
}
@Override
- public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
- Point[] points = (Point[]) shape;
- for (Point p : points) {
- boolean b = POINTVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, p);
- if (b == true && queryRelation == QueryRelation.INTERSECTS) {
- return true;
- } else if (b == false && queryRelation == QueryRelation.DISJOINT) {
- return false;
- } else if (b == false && queryRelation == QueryRelation.WITHIN) {
- return false;
- }
- }
- return queryRelation != QueryRelation.INTERSECTS;
+ public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
@@ -94,13 +86,15 @@ public class TestXYMultiPointShapeQueries extends BaseXYShapeTestCase {
boolean b = POINTVALIDATOR.testComponentQuery(query, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPolygonShapeQueries.java
index ed62364..29a6334 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYMultiPolygonShapeQueries.java
@@ -23,6 +23,8 @@ import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.geo.XYPolygon;
+import org.apache.lucene.geo.XYRectangle;
+import org.apache.lucene.geo.XYRectangle2D;
/** random cartesian bounding box, line, and polygon query tests for random indexed arrays of cartesian {@link XYPolygon} types */
public class TestXYMultiPolygonShapeQueries extends BaseXYShapeTestCase {
@@ -33,17 +35,26 @@ public class TestXYMultiPolygonShapeQueries extends BaseXYShapeTestCase {
@Override
protected XYPolygon[] nextShape() {
-
int n = random().nextInt(4) + 1;
XYPolygon[] polygons = new XYPolygon[n];
for (int i =0; i < n; i++) {
+ int repetitions =0;
while (true) {
// if we can't tessellate; then random polygon generator created a malformed shape
XYPolygon p = (XYPolygon) getShapeType().nextShape();
try {
Tessellator.tessellate(p);
- polygons[i] = p;
- break;
+ //polygons are disjoint so CONTAINS works. Note that if we intersect
+ //any shape then contains return false.
+ if (isDisjoint(polygons, p, i)) {
+ polygons[i] = p;
+ break;
+ }
+ repetitions++;
+ if (repetitions > 50) {
+ //try again
+ return nextShape();
+ }
} catch (IllegalArgumentException e) {
continue;
}
@@ -52,6 +63,22 @@ public class TestXYMultiPolygonShapeQueries extends BaseXYShapeTestCase {
return polygons;
}
+ private boolean isDisjoint(XYPolygon[] polygons, XYPolygon check, int totalPolygons) {
+ // we use bounding boxes so we do not get polygons with shared points.
+ for (XYPolygon polygon : polygons) {
+ if (polygon != null) {
+ if (getEncoder().quantizeY(polygon.minY) > getEncoder().quantizeY(check.maxY)
+ || getEncoder().quantizeY(polygon.maxY) < getEncoder().quantizeY(check.minY)
+ || getEncoder().quantizeX(polygon.minX) > getEncoder().quantizeX(check.maxX)
+ || getEncoder().quantizeX(polygon.maxX) < getEncoder().quantizeX(check.minX)) {
+ continue;
+ }
+ return false;
+ }
+ }
+ return true;
+ }
+
@Override
protected Field[] createIndexableFields(String name, Object o) {
XYPolygon[] polygons = (XYPolygon[]) o;
@@ -85,19 +112,9 @@ public class TestXYMultiPolygonShapeQueries extends BaseXYShapeTestCase {
}
@Override
- public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
- XYPolygon[] polygons = (XYPolygon[])shape;
- for (XYPolygon p : polygons) {
- boolean b = POLYGONVALIDATOR.testBBoxQuery(minLat, maxLat, minLon, maxLon, p);
- if (b == true && queryRelation == QueryRelation.INTERSECTS) {
- return true;
- } else if (b == false && queryRelation == QueryRelation.DISJOINT) {
- return false;
- } else if (b == false && queryRelation == QueryRelation.WITHIN) {
- return false;
- }
- }
- return queryRelation != QueryRelation.INTERSECTS;
+ public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
@@ -107,13 +124,15 @@ public class TestXYMultiPolygonShapeQueries extends BaseXYShapeTestCase {
boolean b = POLYGONVALIDATOR.testComponentQuery(query, p);
if (b == true && queryRelation == QueryRelation.INTERSECTS) {
return true;
+ } else if (b == true && queryRelation == QueryRelation.CONTAINS) {
+ return true;
} else if (b == false && queryRelation == QueryRelation.DISJOINT) {
return false;
} else if (b == false && queryRelation == QueryRelation.WITHIN) {
return false;
}
}
- return queryRelation != QueryRelation.INTERSECTS;
+ return queryRelation != QueryRelation.INTERSECTS && queryRelation != QueryRelation.CONTAINS;
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPointShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPointShapeQueries.java
index 5a401c4..b53e90a 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPointShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPointShapeQueries.java
@@ -21,6 +21,8 @@ import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.ShapeTestUtil;
import org.apache.lucene.geo.XYLine;
+import org.apache.lucene.geo.XYRectangle;
+import org.apache.lucene.geo.XYRectangle2D;
import org.apache.lucene.index.PointValues.Relation;
/** random cartesian bounding box, line, and polygon query tests for random generated {@code x, y} points */
@@ -73,23 +75,16 @@ public class TestXYPointShapeQueries extends BaseXYShapeTestCase {
}
@Override
- public boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape) {
- Point p = (Point)shape;
- double lat = encoder.quantizeY(p.y);
- double lon = encoder.quantizeX(p.x);
- boolean isDisjoint = lat < minLat || lat > maxLat;
-
- isDisjoint = isDisjoint || ((minLon > maxLon)
- ? lon < minLon && lon > maxLon
- : lon < minLon || lon > maxLon);
- if (queryRelation == QueryRelation.DISJOINT) {
- return isDisjoint;
- }
- return isDisjoint == false;
+ public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
public boolean testComponentQuery(Component2D query, Object shape) {
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return false;
+ }
Point p = (Point) shape;
double lat = encoder.quantizeY(p.y);
double lon = encoder.quantizeX(p.x);
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPolygonShapeQueries.java
index a261d9e..2df2f6e 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYPolygonShapeQueries.java
@@ -66,34 +66,21 @@ public class TestXYPolygonShapeQueries extends BaseXYShapeTestCase {
@Override
public boolean testBBoxQuery(double minY, double maxY, double minX, double maxX, Object shape) {
- XYPolygon p = (XYPolygon)shape;
- XYRectangle2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
- List<Tessellator.Triangle> tessellation = Tessellator.tessellate(p);
- for (Tessellator.Triangle t : tessellation) {
- ShapeField.DecodedTriangle decoded = encoder.encodeDecodeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
- t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
- t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
- if (queryRelation == QueryRelation.WITHIN) {
- if (rectangle2D.containsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == false) {
- return false;
- }
- } else {
- if (rectangle2D.intersectsTriangle(decoded.aX, decoded.aY, decoded.bX, decoded.bY, decoded.cX, decoded.cY) == true) {
- return queryRelation == QueryRelation.INTERSECTS;
- }
- }
- }
- return queryRelation != QueryRelation.INTERSECTS;
+ Component2D rectangle2D = XYRectangle2D.create(new XYRectangle(minX, maxX, minY, maxY));
+ return testComponentQuery(rectangle2D, shape);
}
@Override
public boolean testComponentQuery(Component2D query, Object o) {
XYPolygon shape = (XYPolygon) o;
+ if (queryRelation == QueryRelation.CONTAINS) {
+ return testWithinPolygon(query, (XYPolygon) shape);
+ }
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
for (Tessellator.Triangle t : tessellation) {
double[] qTriangle = encoder.quantizeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
- t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
- t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
+ t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
+ t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
Relation r = query.relateTriangle(qTriangle[1], qTriangle[0], qTriangle[3], qTriangle[2], qTriangle[5], qTriangle[4]);
if (queryRelation == QueryRelation.DISJOINT) {
if (r != Relation.CELL_OUTSIDE_QUERY) return false;
@@ -105,6 +92,25 @@ public class TestXYPolygonShapeQueries extends BaseXYShapeTestCase {
}
return queryRelation == QueryRelation.INTERSECTS ? false : true;
}
+
+ private boolean testWithinPolygon(Component2D tree, XYPolygon shape) {
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
+ Component2D.WithinRelation answer = Component2D.WithinRelation.DISJOINT;
+ for (Tessellator.Triangle t : tessellation) {
+ ShapeField.DecodedTriangle qTriangle = encoder.encodeDecodeTriangle(t.getX(0), t.getY(0), t.isEdgefromPolygon(0),
+ t.getX(1), t.getY(1), t.isEdgefromPolygon(1),
+ t.getX(2), t.getY(2), t.isEdgefromPolygon(2));
+ Component2D.WithinRelation relation = tree.withinTriangle(encoder.decodeX(qTriangle.aX), encoder.decodeY(qTriangle.aY), qTriangle.ab,
+ encoder.decodeX(qTriangle.bX), encoder.decodeY(qTriangle.bY), qTriangle.bc,
+ encoder.decodeX(qTriangle.cX), encoder.decodeY(qTriangle.cY), qTriangle.ca);
+ if (relation == Component2D.WithinRelation.NOTWITHIN) {
+ return false;
+ } else if (relation == Component2D.WithinRelation.CANDIDATE) {
+ answer = Component2D.WithinRelation.CANDIDATE;
+ }
+ }
+ return answer == Component2D.WithinRelation.CANDIDATE;
+ }
}
@Nightly
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYShape.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYShape.java
index 1fc1a79..efab57b 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestXYShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestXYShape.java
@@ -18,8 +18,10 @@ package org.apache.lucene.document;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.ShapeTestUtil;
+import org.apache.lucene.geo.Tessellator;
import org.apache.lucene.geo.XYLine;
import org.apache.lucene.geo.XYPolygon;
+import org.apache.lucene.geo.XYRectangle;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.RandomIndexWriter;
import org.apache.lucene.search.IndexSearcher;
@@ -108,4 +110,58 @@ public class TestXYShape extends LuceneTestCase {
IOUtils.close(reader, dir);
}
+
+ public void testBoundingBoxQueries() throws Exception {
+ XYRectangle r1 = ShapeTestUtil.nextBox();
+ XYRectangle r2 = ShapeTestUtil.nextBox();
+ XYPolygon p;
+ //find two boxes so that r1 contains r2
+ while (true) {
+ // TODO: Should XYRectangle hold values as float?
+ if (areBoxDisjoint(r1, r2)) {
+ p = toPolygon(r2);
+ try {
+ Tessellator.tessellate(p);
+ break;
+ } catch (Exception e) {
+ // ignore, try other combination
+ }
+ }
+ r1 = ShapeTestUtil.nextBox();
+ r2 = ShapeTestUtil.nextBox();
+ }
+
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+
+ // add the polygon to the index
+ Document document = new Document();
+ addPolygonsToDoc(FIELDNAME, document, p);
+ writer.addDocument(document);
+
+ ////// search /////
+ IndexReader reader = writer.getReader();
+ writer.close();
+ IndexSearcher searcher = newSearcher(reader);
+ // Query by itself should match
+ Query q = newRectQuery(FIELDNAME, r2.minX, r2.maxX, r2.minY, r2.maxY);
+ assertEquals(1, searcher.count(q));
+ // r1 contains r2, intersects should match
+ q = newRectQuery(FIELDNAME, r1.minX, r1.maxX, r1.minY, r1.maxY);
+ assertEquals(1, searcher.count(q));
+ // r1 contains r2, WITHIN should match
+ q = XYShape.newBoxQuery(FIELDNAME, QueryRelation.WITHIN, (float) r1.minX, (float) r1.maxX, (float) r1.minY, (float) r1.maxY);
+ assertEquals(1, searcher.count(q));
+
+ IOUtils.close(reader, dir);
+ }
+
+ private static boolean areBoxDisjoint(XYRectangle r1, XYRectangle r2) {
+ return ((float) r1.minX <= (float) r2.minX && (float) r1.minY <= (float) r2.minY && (float) r1.maxX >= (float) r2.maxX && (float) r1.maxY >= (float) r2.maxY);
+ }
+
+ private static XYPolygon toPolygon(XYRectangle r) {
+ return new XYPolygon(new float[]{(float) r.minX, (float) r.maxX, (float) r.maxX, (float) r.minX, (float) r.minX},
+ new float[]{(float) r.minY, (float) r.minY, (float) r.maxY, (float) r.maxY, (float) r.minY});
+ }
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestLine2D.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestLine2D.java
index 6a701b1..8198141 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestLine2D.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestLine2D.java
@@ -32,7 +32,8 @@ public class TestLine2D extends LuceneTestCase {
int by = GeoEncodingUtils.encodeLatitude(5);
int cx = GeoEncodingUtils.encodeLongitude(5);
int cy = GeoEncodingUtils.encodeLatitude(4);
- assertEquals(Relation.CELL_OUTSIDE_QUERY, line2D.relateTriangle(ax, ay, bx, by , cx, cy));;
+ assertEquals(Relation.CELL_OUTSIDE_QUERY, line2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.DISJOINT, line2D.withinTriangle(ax, ay, true, bx, by , true, cx, cy, true));
}
public void testTriangleIntersects() {
@@ -45,6 +46,7 @@ public class TestLine2D extends LuceneTestCase {
int cx = GeoEncodingUtils.encodeLongitude(0);
int cy = GeoEncodingUtils.encodeLatitude(1);
assertEquals(Relation.CELL_CROSSES_QUERY, line2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, line2D.withinTriangle(ax, ay, true, bx, by , true, cx, cy, true));
}
public void testTriangleContains() {
@@ -57,6 +59,7 @@ public class TestLine2D extends LuceneTestCase {
int cx = GeoEncodingUtils.encodeLongitude(4);
int cy = GeoEncodingUtils.encodeLatitude(30);
assertEquals(Relation.CELL_CROSSES_QUERY, line2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.CANDIDATE, line2D.withinTriangle(ax, ay, true, bx, by , true, cx, cy, true));
}
public void testRandomTriangles() {
@@ -79,6 +82,9 @@ public class TestLine2D extends LuceneTestCase {
Relation r = line2D.relate(tMinX, tMaxX, tMinY, tMaxY);
if (r == Relation.CELL_OUTSIDE_QUERY) {
assertEquals(Relation.CELL_OUTSIDE_QUERY, line2D.relateTriangle(ax, ay, bx, by, cx, cy));
+ assertEquals(Component2D.WithinRelation.DISJOINT, line2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ } else if (line2D.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_INSIDE_QUERY) {
+ assertNotEquals(Component2D.WithinRelation.CANDIDATE, line2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
}
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
index 787a2a5..e69d354 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
@@ -36,6 +36,7 @@ public class TestRectangle2D extends LuceneTestCase {
int cy = GeoEncodingUtils.encodeLatitude(4);
assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.DISJOINT, rectangle2D.withinTriangle(ax, ay, true, bx, by , true, cx, cy, true));
}
public void testTriangleIntersects() {
@@ -49,6 +50,7 @@ public class TestRectangle2D extends LuceneTestCase {
int cy = GeoEncodingUtils.encodeLatitude(2);
assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
}
public void testTriangleContains() {
@@ -62,10 +64,58 @@ public class TestRectangle2D extends LuceneTestCase {
int cy = GeoEncodingUtils.encodeLatitude(0.25);
assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
assertTrue(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleContainsEdgeCase() {
+ Rectangle rectangle = new Rectangle(0, 1, 0, 1);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(0.0);
+ int ay = GeoEncodingUtils.encodeLatitude(0.0);
+ int bx = GeoEncodingUtils.encodeLongitude(0.0);
+ int by = GeoEncodingUtils.encodeLatitude(0.5);
+ int cx = GeoEncodingUtils.encodeLongitude(0.5);
+ int cy = GeoEncodingUtils.encodeLatitude(0.25);
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertTrue(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleWithin() {
+ Rectangle rectangle = new Rectangle(0, 1, 0, 1);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(-10);
+ int ay = GeoEncodingUtils.encodeLatitude(-10);
+ int bx = GeoEncodingUtils.encodeLongitude(10);
+ int by = GeoEncodingUtils.encodeLatitude(-10);
+ int cx = GeoEncodingUtils.encodeLongitude(10);
+ int cy = GeoEncodingUtils.encodeLatitude(20);
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.CANDIDATE, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleWithinCrossingDateLine() {
+ Rectangle rectangle = new Rectangle(0, 2, 179, -179);
+ Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
+ int ax = GeoEncodingUtils.encodeLongitude(169);
+ int ay = GeoEncodingUtils.encodeLatitude(-10);
+ int bx = GeoEncodingUtils.encodeLongitude(180);
+ int by = GeoEncodingUtils.encodeLatitude(-10);
+ int cx = GeoEncodingUtils.encodeLongitude(180);
+ int cy = GeoEncodingUtils.encodeLatitude(30);
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
+ expectThrows(IllegalArgumentException.class, () -> {
+ rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true);
+ });
}
public void testRandomTriangles() {
Rectangle rectangle = GeoTestUtil.nextBox();
+ while(rectangle.crossesDateline()) {
+ rectangle = GeoTestUtil.nextBox();
+ }
Rectangle2D rectangle2D = Rectangle2D.create(rectangle);
for (int i =0; i < 100; i++) {
@@ -97,9 +147,13 @@ public class TestRectangle2D extends LuceneTestCase {
if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
- }
- else if (rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy)) {
+ assertEquals(Component2D.WithinRelation.DISJOINT, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ } else if (rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy)) {
+ assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertTrue(rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true) != Component2D.WithinRelation.CANDIDATE);
+ } else if (rectangle2D.withinTriangle(ax, ay, true, bx, by , true, cx, cy, true) == Component2D.WithinRelation.CANDIDATE) {
assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
+ assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
}
}
}
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestXYRectangle2D.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestXYRectangle2D.java
new file mode 100644
index 0000000..0ba7ab1
--- /dev/null
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestXYRectangle2D.java
@@ -0,0 +1,88 @@
+/*
+ * 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.geo;
+
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.util.LuceneTestCase;
+
+
+public class TestXYRectangle2D extends LuceneTestCase {
+
+ public void testTriangleDisjoint() {
+ XYRectangle rectangle = new XYRectangle(0d, 1d, 0d, 1d);
+ Component2D rectangle2D = XYRectangle2D.create(rectangle);
+ float ax = 4f;
+ float ay = 4f;
+ float bx = 5f;
+ float by = 5f;
+ float cx = 5f;
+ float cy = 4f;
+ assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, rectangle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testTriangleIntersects() {
+ XYRectangle rectangle = new XYRectangle(0d, 1d, 0d, 1d);
+ Component2D rectangle2D = XYRectangle2D.create(rectangle);
+ float ax = 0.5f;
+ float ay = 0.5f;
+ float bx = 2f;
+ float by = 2f;
+ float cx = 0.5f;
+ float cy = 2f;
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rectangle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testTriangleContains() {
+ XYRectangle rectangle = new XYRectangle(0, 1, 0, 1);
+ Component2D rectangle2D = XYRectangle2D.create(rectangle);
+ float ax = 0.25f;
+ float ay = 0.25f;
+ float bx = 0.5f;
+ float by = 0.5f;
+ float cx = 0.5f;
+ float cy = 0.25f;
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rectangle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ }
+
+ public void testRandomTriangles() {
+ XYRectangle rectangle = ShapeTestUtil.nextBox();
+ Component2D rectangle2D = XYRectangle2D.create(rectangle);
+ for (int i =0; i < 100; i++) {
+ float ax = (float) ShapeTestUtil.nextDouble();
+ float ay = (float) ShapeTestUtil.nextDouble();
+ float bx = (float) ShapeTestUtil.nextDouble();
+ float by = (float) ShapeTestUtil.nextDouble();
+ float cx = (float) ShapeTestUtil.nextDouble();
+ float cy = (float) ShapeTestUtil.nextDouble();
+
+ float tMinX = StrictMath.min(StrictMath.min(ax, bx), cx);
+ float tMaxX = StrictMath.max(StrictMath.max(ax, bx), cx);
+ float tMinY = StrictMath.min(StrictMath.min(ay, by), cy);
+ float tMaxY = StrictMath.max(StrictMath.max(ay, by), cy);
+
+
+ PointValues.Relation r = rectangle2D.relate(tMinX, tMaxX, tMinY, tMaxY);
+ if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
+ assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, rectangle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ }
+ else if (r == PointValues.Relation.CELL_INSIDE_QUERY) {
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rectangle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ }
+ }
+ }
+}
\ No newline at end of file