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 2020/01/29 18:27:07 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9152: Improve line
intersection detection for polygons (#1187)
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 29542c7 LUCENE-9152: Improve line intersection detection for polygons (#1187)
29542c7 is described below
commit 29542c7f59ee157a57415af2ccf2829c669c6e5e
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Wed Jan 29 19:24:51 2020 +0100
LUCENE-9152: Improve line intersection detection for polygons (#1187)
---
lucene/CHANGES.txt | 2 ++
.../src/java/org/apache/lucene/geo/EdgeTree.java | 19 ++++++----
.../src/java/org/apache/lucene/geo/Line2D.java | 12 +++----
.../src/java/org/apache/lucene/geo/Polygon2D.java | 12 +++----
.../apache/lucene/document/TestLatLonShape.java | 42 ++++++++++++++++++++++
.../test/org/apache/lucene/geo/TestPolygon2D.java | 17 +++++++++
6 files changed, 86 insertions(+), 18 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a241ce6..655c55c 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -53,6 +53,8 @@ Improvements
* LUCENE-4702: Better compression of terms dictionaries. (Adrien Grand)
+* LUCENE-9152: Improve line intersections with polygons when they are touching from the outside. (Ignacio Vera)
+
Optimizations
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
index 239dfcf..f13e1a8 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -261,7 +261,7 @@ public class EdgeTree {
}
/** Returns true if the line crosses any edge in this edge subtree */
- protected boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y) {
+ protected boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary) {
if (minY <= max) {
double a1x = x1;
double a1y = y1;
@@ -272,14 +272,21 @@ public class EdgeTree {
(a1y > maxY && b1y > maxY) ||
(a1x < minX && b1x < minX) ||
(a1x > maxX && b1x > maxX);
- if (outside == false && lineCrossesLineWithBoundary(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
- return true;
+ if (outside == false) {
+ if (includeBoundary) {
+ if (lineCrossesLineWithBoundary(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
+ return true;
+ }
+ } else {
+ if (lineCrossesLine(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
+ return true;
+ }
+ }
}
-
- if (left != null && left.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y)) {
+ if (left != null && left.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, includeBoundary)) {
return true;
}
- if (right != null && maxY >= low && right.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y)) {
+ if (right != null && maxY >= low && right.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, includeBoundary)) {
return true;
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Line2D.java b/lucene/core/src/java/org/apache/lucene/geo/Line2D.java
index 04deee9..ed247bf 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Line2D.java
@@ -109,19 +109,19 @@ public final class Line2D implements Component2D {
}
} else if (ax == cx && ay == cy) {
// indexed "triangle" is a line:
- if (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
} else if (ax == bx && ay == by) {
// indexed "triangle" is a line:
- if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
} else if (bx == cx && by == cy) {
// indexed "triangle" is a line:
- if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -149,7 +149,7 @@ public final class Line2D implements Component2D {
// 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 (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by, true)) {
if (ab == true) {
return WithinRelation.NOTWITHIN;
} else {
@@ -157,14 +157,14 @@ public final class Line2D implements Component2D {
}
}
- if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy, true)) {
if (bc == true) {
return WithinRelation.NOTWITHIN;
} else {
relation = WithinRelation.CANDIDATE;
}
}
- if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay, true)) {
if (ca == true) {
return WithinRelation.NOTWITHIN;
} else {
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 e6eefd8..c36d6aa 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -187,7 +187,7 @@ public class Polygon2D implements Component2D {
// 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 (tree.crossesLine(minX, maxX, minY, maxY, ax, ay, bx, by, true)) {
if (ab == true) {
return WithinRelation.NOTWITHIN;
} else {
@@ -195,14 +195,14 @@ public class Polygon2D implements Component2D {
}
}
- if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, bx, by, cx, cy, true)) {
if (bc == true) {
return WithinRelation.NOTWITHIN;
} else {
relation = WithinRelation.CANDIDATE;
}
}
- if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, cx, cy, ax, ay, true)) {
if (ca == true) {
return WithinRelation.NOTWITHIN;
} else {
@@ -236,12 +236,12 @@ public class Polygon2D implements Component2D {
}
if (numCorners == 2) {
- if (tree.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, false)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_INSIDE_QUERY;
} else if (numCorners == 0) {
- if (tree.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y)) {
+ if (tree.crossesLine(minX, maxX, minY, maxY, a2x, a2y, b2x, b2y, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -263,7 +263,7 @@ public class Polygon2D implements Component2D {
if (Component2D.pointInTriangle(minX, maxX, minY, maxY, tree.x1, tree.y1, ax, ay, bx, by, cx, cy) == true) {
return Relation.CELL_CROSSES_QUERY;
}
- if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, false)) {
+ if (tree.crossesTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy, true)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
index 37b32c2..3bc64ac 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -19,6 +19,7 @@ package org.apache.lucene.document;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
+import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.GeoTestUtil;
import org.apache.lucene.geo.Line;
import org.apache.lucene.geo.Line2D;
@@ -699,4 +700,45 @@ public class TestLatLonShape extends LuceneTestCase {
IOUtils.close(w, reader, dir);
}
+
+ public void testIndexAndQuerySamePolygon() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+ Document doc = new Document();
+ Polygon polygon;
+ while(true) {
+ try {
+ polygon = GeoTestUtil.nextPolygon();
+ // quantize the polygon
+ double[] lats = new double[polygon.numPoints()];
+ double[] lons = new double[polygon.numPoints()];
+ for (int i = 0; i < polygon.numPoints(); i++) {
+ lats[i] = GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(polygon.getPolyLat(i)));
+ lons[i] = GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(polygon.getPolyLon(i)));
+ }
+ polygon = new Polygon(lats, lons);
+ Tessellator.tessellate(polygon);
+ break;
+ } catch (Exception e) {
+ // invalid polygon, try a new one
+ }
+ }
+ addPolygonsToDoc(FIELDNAME, doc, polygon);
+ w.addDocument(doc);
+ w.forceMerge(1);
+
+ ///// search //////
+ IndexReader reader = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(reader);
+
+ Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, polygon);
+ assertEquals(1, searcher.count(q));
+ q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.INTERSECTS, polygon);
+ assertEquals(1, searcher.count(q));
+ q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.DISJOINT, polygon);
+ assertEquals(0, searcher.count(q));
+
+ IOUtils.close(w, reader, dir);
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
index 61cd2b5..0206623 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -271,6 +271,23 @@ public class TestPolygon2D extends LuceneTestCase {
assertTrue(poly.contains(-2, 0)); // left side: true
assertTrue(poly.contains(-2, 1)); // left side: true
}
+
+ /** Tests edge case behavior with respect to insideness */
+ public void testIntersectsSameEdge() {
+ Component2D poly = Polygon2D.create(new Polygon(new double[] { -2, -2, 2, 2, -2 }, new double[] { -2, 2, 2, -2, -2 }));
+ // line inside edge
+ assertEquals(Relation.CELL_INSIDE_QUERY, poly.relateTriangle(-1, -1, 1, 1, -1, -1));
+ assertEquals(Relation.CELL_INSIDE_QUERY, poly.relateTriangle(-2, -2, 2, 2, -2, -2));
+ // line over edge
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-4, -4, 4, 4, -4, -4));
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-2, -2, 4, 4, 4, 4));
+ // line inside edge
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-1, -1, 3, 3, 1, 1));
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-2, -2, 3, 3, 2, 2));
+ // line over edge
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-4, -4, 7, 7, 4, 4));
+ assertEquals(Relation.CELL_CROSSES_QUERY, poly.relateTriangle(-2, -2, 7, 7, 4, 4));
+ }
/** Tests current impl against original algorithm */
public void testContainsAgainstOriginal() {