You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2018/07/19 18:56:23 UTC
lucene-solr:branch_7x: LUCENE-8399: Fix LatLonShapeBoundingBoxQuery
to use orient method for computing edge intersections
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x a7fe95007 -> 524d1157c
LUCENE-8399: Fix LatLonShapeBoundingBoxQuery to use orient method for computing edge intersections
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/524d1157
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/524d1157
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/524d1157
Branch: refs/heads/branch_7x
Commit: 524d1157c711f5f0b2c1c62528c401d028ff5278
Parents: a7fe950
Author: Nicholas Knize <nk...@gmail.com>
Authored: Thu Jul 19 10:38:37 2018 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Thu Jul 19 13:34:50 2018 -0500
----------------------------------------------------------------------
.../document/LatLonShapeBoundingBoxQuery.java | 57 +++++++++++---------
.../lucene/document/TestLatLonShapeQueries.java | 2 -
2 files changed, 32 insertions(+), 27 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/524d1157/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
----------------------------------------------------------------------
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 99c39c5..215cf59 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -47,6 +47,7 @@ import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitudeCeil;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
+import static org.apache.lucene.geo.GeoUtils.orient;
/**
* Finds all previously indexed shapes that intersect the specified bounding box.
@@ -84,6 +85,33 @@ class LatLonShapeBoundingBoxQuery extends Query {
public final Weight createWeight(IndexSearcher searcher, boolean needsScores, float boost) throws IOException {
return new ConstantScoreWeight(this, boost) {
+ private boolean edgeIntersectsQuery(double ax, double ay, double bx, double by) {
+ // 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 boolean queryContains(byte[] t, int point) {
final int yIdx = 2 * LatLonPoint.BYTES * point;
final int xIdx = yIdx + LatLonPoint.BYTES;
@@ -98,31 +126,10 @@ class LatLonShapeBoundingBoxQuery extends Query {
}
private boolean queryIntersects(int ax, int ay, int bx, int by, int cx, int cy) {
- // top
- if (Tessellator.linesIntersect(minX, maxY, maxX, maxY, ax, ay, bx, by) ||
- Tessellator.linesIntersect(minX, maxY, maxX, maxY, bx, by, cx, cy) ||
- Tessellator.linesIntersect(minX, maxY, maxX, maxY, cx, cy, ax, ay)) {
- return true;
- }
-
- // bottom
- if (Tessellator.linesIntersect(minX, minY, maxX, minY, ax, ay, bx, by) ||
- Tessellator.linesIntersect(minX, minY, maxX, minY, bx, by, cx, cy) ||
- Tessellator.linesIntersect(minX, minY, maxX, minY, cx, cy, ax, ay)) {
- return true;
- }
-
- // left
- if (Tessellator.linesIntersect(minX, minY, minX, maxY, ax, ay, bx, by) ||
- Tessellator.linesIntersect(minX, minY, minX, maxY, bx, by, cx, cy) ||
- Tessellator.linesIntersect(minX, minY, minX, maxY, cx, cy, ax, ay)) {
- return true;
- }
-
- // right
- if (Tessellator.linesIntersect(maxX, minY, maxX, maxY, ax, ay, bx, by) ||
- Tessellator.linesIntersect(maxX, minY, maxX, maxY, bx, by, cx, cy) ||
- Tessellator.linesIntersect(maxX, minY, maxX, maxY, cx, cy, ax, ay)) {
+ // check each edge of the triangle against the query
+ if (edgeIntersectsQuery(ax, ay, bx, by) ||
+ edgeIntersectsQuery(bx, by, cx, cy) ||
+ edgeIntersectsQuery(cx, cy, ax, ay)) {
return true;
}
return false;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/524d1157/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
index 8af72a5..fd04741 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShapeQueries.java
@@ -43,7 +43,6 @@ import org.apache.lucene.util.Bits;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.LuceneTestCase;
-import org.apache.lucene.util.LuceneTestCase.AwaitsFix;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
@@ -53,7 +52,6 @@ import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitudeCeil;
/** base Test case for {@link LatLonShape} indexing and search */
-@AwaitsFix(bugUrl="https://issues.apache.org/jira/browse/LUCENE-8399")
public class TestLatLonShapeQueries extends LuceneTestCase {
protected static final String FIELD_NAME = "shape";