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 2019/04/11 15:50:04 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8736: Fix
LatLonShapePolygonQuery and Polygon2D.contains to correctly include points
that fall on the boundary
This is an automated email from the ASF dual-hosted git repository.
nknize 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 b518bed LUCENE-8736: Fix LatLonShapePolygonQuery and Polygon2D.contains to correctly include points that fall on the boundary
b518bed is described below
commit b518bed8b3ba9a8c1d3c20a1f4e113ea1731f644
Author: Nicholas Knize <nk...@gmail.com>
AuthorDate: Thu Apr 11 09:27:36 2019 -0500
LUCENE-8736: Fix LatLonShapePolygonQuery and Polygon2D.contains to correctly include points that fall on the boundary
---
lucene/CHANGES.txt | 5 +
.../src/java/org/apache/lucene/geo/EdgeTree.java | 154 +++++++--------
.../src/java/org/apache/lucene/geo/GeoUtils.java | 16 +-
.../src/java/org/apache/lucene/geo/Polygon2D.java | 79 ++++++--
.../test/org/apache/lucene/geo/TestPolygon2D.java | 18 +-
.../src/java/org/apache/lucene/geo/Line2D.java | 45 ++++-
.../java/org/apache/lucene/geo/Rectangle2D.java | 9 +-
.../apache/lucene/document/TestLatLonShape.java | 218 ++++++++++++++-------
.../java/org/apache/lucene/geo/GeoTestUtil.java | 15 +-
9 files changed, 364 insertions(+), 195 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 024a9f9..9ca2e7b 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -36,6 +36,11 @@ New Features
Bug fixes
+* LUCENE-8736: LatLonShapePolygonQuery returns incorrect WITHIN results
+ with shared boundaries. Point in Polygon now correctly includes boundary
+ points. Box and Polygon relations with triangles have also been improved to
+ correctly include boundary points. (Nick Knize)
+
* LUCENE-8712: Polygon2D does not detect crossings through segment edges.
(Ignacio Vera)
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 aa25ff0..cbecd25 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -23,6 +23,7 @@ import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.ArrayUtil;
import static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
+import static org.apache.lucene.geo.GeoUtils.lineCrossesLineWithBoundary;
import static org.apache.lucene.geo.GeoUtils.orient;
/**
@@ -76,11 +77,9 @@ public abstract class EdgeTree {
/** Returns relation to the provided triangle */
public Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
// compute bounding box of triangle
- double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
- double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
- double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
- double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
- if (minLat <= maxY && minLon <= maxX) {
+ double triMinLat = StrictMath.min(StrictMath.min(ay, by), cy);
+ double triMinLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+ if (triMinLat <= maxY && triMinLon <= maxX) {
Relation relation = internalComponentRelateTriangle(ax, ay, bx, by, cx, cy);
if (relation != Relation.CELL_OUTSIDE_QUERY) {
return relation;
@@ -91,7 +90,9 @@ public abstract class EdgeTree {
return relation;
}
}
- if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
+ double triMaxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+ double triMaxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+ if (right != null && ((splitX == false && triMaxLat >= this.minLat) || (splitX && triMaxLon >= this.minLon))) {
relation = right.relateTriangle(ax, ay, bx, by, cx, cy);
if (relation != Relation.CELL_OUTSIDE_QUERY) {
return relation;
@@ -236,62 +237,47 @@ public abstract class EdgeTree {
/** Returns true if the triangle crosses any edge in this edge subtree */
boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
- // compute bounding box of triangle
- double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
- double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
- double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
- double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
-
- if (minLat <= max) {
+ // compute min lat of triangle bounding box
+ double triMinLat = StrictMath.min(StrictMath.min(ay, by), cy);
+ if (triMinLat <= max) {
double dy = lat1;
double ey = lat2;
double dx = lon1;
double ex = lon2;
+ // compute remaining bounding box of triangle
+ double triMinLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+ double triMaxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+ double triMaxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+
// optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
// if not, don't waste our time trying more complicated stuff
- boolean outside = (dy < minLat && ey < minLat) ||
- (dy > maxLat && ey > maxLat) ||
- (dx < minLon && ex < minLon) ||
- (dx > maxLon && ex > maxLon);
-
- if (dateline == false && outside == false) {
- // does triangle's first edge intersect polyline?
- // ax, ay -> bx, by
- if (lineCrossesLine(ax, ay, bx, by, dx, dy, ex, ey)) {
- return true;
- }
+ boolean outside = (dy < triMinLat && ey < triMinLat) ||
+ (dy > triMaxLat && ey > triMaxLat) ||
+ (dx < triMinLon && ex < triMinLon) ||
+ (dx > triMaxLon && ex > triMaxLon);
- // does triangle's second edge intersect polyline?
- // bx, by -> cx, cy
- if (lineCrossesLine(bx, by, cx, cy, dx, dy, ex, ey)) {
- return true;
- }
-
- // does triangle's third edge intersect polyline?
- // cx, cy -> ax, ay
- if (lineCrossesLine(cx, cy, ax, ay, dx, dy, ex, ey)) {
+ if (outside == false) {
+ if (lineCrossesLine(dx, dy, ex, ey, ax, ay, bx, by) ||
+ lineCrossesLine(dx, dy, ex, ey, bx, by, cx, cy) ||
+ lineCrossesLine(dx, dy, ex, ey, cx, cy, ax, ay)) {
return true;
}
}
- if (left != null) {
- if (left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
- return true;
- }
+ if (left != null && left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ return true;
}
- if (right != null && maxLat >= low) {
- if (right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
- return true;
- }
+ if (right != null && triMaxLat >= low && right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ return true;
}
}
return false;
}
/** Returns true if the box crosses any edge in this edge subtree */
- boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
+ boolean crossesBox(double minLat, double maxLat, double minLon, double maxLon, boolean includeBoundary) {
// we just have to cross one edge to answer the question, so we descend the tree and return when we do.
if (minLat <= max) {
// we compute line intersections of every polygon edge with every box line.
@@ -304,58 +290,72 @@ public abstract class EdgeTree {
double cx = lon1;
double dx = lon2;
+ // optimization: see if either end of the line segment is contained by the rectangle
+ if (Rectangle.containsPoint(cy, cx, minLat, maxLat, minLon, maxLon) ||
+ Rectangle.containsPoint(dy, dx, minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+
// optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
// if not, don't waste our time trying more complicated stuff
boolean outside = (cy < minLat && dy < minLat) ||
(cy > maxLat && dy > maxLat) ||
(cx < minLon && dx < minLon) ||
(cx > maxLon && dx > maxLon);
- // optimization: see if either end of the line segment is contained by the rectangle
- if (Rectangle.containsPoint(cy, cx, minLat, maxLat, minLon, maxLon)
- || Rectangle.containsPoint(dy, dx, minLat, maxLat, minLon, maxLon)) {
- return true;
- }
if (outside == false) {
- // does box's top edge intersect polyline?
- // ax = minLon, bx = maxLon, ay = maxLat, by = maxLat
- if (orient(cx, cy, dx, dy, minLon, maxLat) * orient(cx, cy, dx, dy, maxLon, maxLat) <= 0 &&
- orient(minLon, maxLat, maxLon, maxLat, cx, cy) * orient(minLon, maxLat, maxLon, maxLat, dx, dy) <= 0) {
+ if (includeBoundary == true &&
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, minLat, maxLon, minLat) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, minLat, maxLon, maxLat) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, maxLat, maxLon, minLat) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, maxLat, minLon, minLat)) {
+ // include boundaries: ensures box edges that terminate on the polygon are included
return true;
- }
-
- // does box's right edge intersect polyline?
- // ax = maxLon, bx = maxLon, ay = maxLat, by = minLat
- if (orient(cx, cy, dx, dy, maxLon, maxLat) * orient(cx, cy, dx, dy, maxLon, minLat) <= 0 &&
- orient(maxLon, maxLat, maxLon, minLat, cx, cy) * orient(maxLon, maxLat, maxLon, minLat, dx, dy) <= 0) {
+ } else if (lineCrossesLine(cx, cy, dx, dy, minLon, minLat, maxLon, minLat) ||
+ lineCrossesLine(cx, cy, dx, dy, maxLon, minLat, maxLon, maxLat) ||
+ lineCrossesLine(cx, cy, dx, dy, maxLon, maxLat, maxLon, minLat) ||
+ lineCrossesLine(cx, cy, dx, dy, minLon, maxLat, minLon, minLat)) {
return true;
}
+ }
- // does box's bottom edge intersect polyline?
- // ax = maxLon, bx = minLon, ay = minLat, by = minLat
- if (orient(cx, cy, dx, dy, maxLon, minLat) * orient(cx, cy, dx, dy, minLon, minLat) <= 0 &&
- orient(maxLon, minLat, minLon, minLat, cx, cy) * orient(maxLon, minLat, minLon, minLat, dx, dy) <= 0) {
- return true;
- }
+ if (left != null && left.crossesBox(minLat, maxLat, minLon, maxLon, includeBoundary)) {
+ return true;
+ }
- // does box's left edge intersect polyline?
- // ax = minLon, bx = minLon, ay = minLat, by = maxLat
- if (orient(cx, cy, dx, dy, minLon, minLat) * orient(cx, cy, dx, dy, minLon, maxLat) <= 0 &&
- orient(minLon, minLat, minLon, maxLat, cx, cy) * orient(minLon, minLat, minLon, maxLat, dx, dy) <= 0) {
- return true;
- }
+ if (right != null && maxLat >= low && right.crossesBox(minLat, maxLat, minLon, maxLon, includeBoundary)) {
+ return true;
}
+ }
+ return false;
+ }
- if (left != null) {
- if (left.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
+ /** Returns true if the line crosses any edge in this edge subtree */
+ boolean crossesLine(double a2x, double a2y, double b2x, double b2y) {
+ double minY = StrictMath.min(a2y, b2y);
+ double maxY = StrictMath.max(a2y, b2y);
+ if (minY <= max) {
+ double a1x = lon1;
+ double a1y = lat1;
+ double b1x = lon2;
+ double b1y = lat2;
+
+ double minX = StrictMath.min(a2x, b2x);
+ double maxX = StrictMath.max(a2x, b2x);
+
+ boolean outside = (a1y < minY && b1y < minY) ||
+ (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 (right != null && maxLat >= low) {
- if (right.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
+ if (left != null && left.crossesLine(a2x, a2y, b2x, b2y)) {
+ return true;
+ }
+ if (right != null && maxY >= low && right.crossesLine(a2x, a2y, b2x, b2y)) {
+ return true;
}
}
return false;
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index 0c73032..52ef59b 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -196,11 +196,21 @@ public final class GeoUtils {
/** uses orient method to compute whether two line segments cross */
public static boolean lineCrossesLine(double a1x, double a1y, double b1x, double b1y, double a2x, double a2y, double b2x, double b2y) {
- // shortcut: either "line" is actually a point
- if ((a1x == b1x && a1y == b1y) || (a2x == b2x && a2y == b2y)) {
- return false;
+ if (orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) < 0 &&
+ orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) < 0) {
+ return true;
}
+ return false;
+ }
+ /** uses orient method to compute whether two line segments cross; boundaries included - returning true for
+ * lines that terminate on each other.
+ *
+ * e.g., (plus sign) + == true, and (capital 't') T == true
+ *
+ * Use {@link #lineCrossesLine} to exclude lines that terminate on each other from the truth table
+ **/
+ public static boolean lineCrossesLineWithBoundary(double a1x, double a1y, double b1x, double b1y, double a2x, double a2y, double b2x, double b2y) {
if (orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) <= 0 &&
orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) <= 0) {
return true;
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 47ab259..c0931b0 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -16,6 +16,8 @@
*/
package org.apache.lucene.geo;
+import java.util.concurrent.atomic.AtomicBoolean;
+
import org.apache.lucene.index.PointValues.Relation;
/**
@@ -32,6 +34,7 @@ public final class Polygon2D extends EdgeTree {
// and pull up max values for both dimensions to each parent node (regardless of split).
/** tree of holes, or null */
private final Polygon2D holes;
+ private final AtomicBoolean containsBoundary = new AtomicBoolean(false);
private Polygon2D(Polygon polygon, Polygon2D holes) {
super(polygon.minLat, polygon.maxLat, polygon.minLon, polygon.maxLon, polygon.getPolyLats(), polygon.getPolyLons());
@@ -69,7 +72,8 @@ public final class Polygon2D extends EdgeTree {
if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
return false;
}
- if (contains(tree, latitude, longitude)) {
+ containsBoundary.set(false);
+ if (contains(tree, latitude, longitude, containsBoundary)) {
if (holes != null && holes.contains(latitude, longitude)) {
return false;
}
@@ -92,7 +96,7 @@ public final class Polygon2D extends EdgeTree {
// check each corner: if < 4 && > 0 are present, its cheaper than crossesSlowly
int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
if (numCorners == 4) {
- if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+ if (tree.crossesBox(minLat, maxLat, minLon, maxLon, false)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_INSIDE_QUERY;
@@ -100,7 +104,7 @@ public final class Polygon2D extends EdgeTree {
if (minLat >= tree.lat1 && maxLat <= tree.lat1 && minLon >= tree.lon2 && maxLon <= tree.lon2) {
return Relation.CELL_CROSSES_QUERY;
}
- if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+ if (tree.crossesBox(minLat, maxLat, minLon, maxLon, false)) {
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
@@ -119,6 +123,48 @@ public final class Polygon2D extends EdgeTree {
return Relation.CELL_OUTSIDE_QUERY;
}
}
+ if (ax == bx && bx == cx && ay == by && by == cy) {
+ // indexed "triangle" is a point:
+ if (Rectangle.containsPoint(ay, ax, minLat, maxLat, minLon, maxLon) == false) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ // shortcut by checking contains
+ return contains(ay, ax) ? Relation.CELL_INSIDE_QUERY : Relation.CELL_OUTSIDE_QUERY;
+ } else if (ax == cx && ay == cy) {
+ // indexed "triangle" is a line segment: shortcut by calling appropriate method
+ return relateIndexedLineSegment(ax, ay, bx, by);
+ }
+ // indexed "triangle" is a triangle:
+ return relateIndexedTriangle(ax, ay, bx, by, cx, cy);
+ }
+
+ /** relates an indexed line segment (a "flat triangle") with the polygon */
+ private Relation relateIndexedLineSegment(double a2x, double a2y, double b2x, double b2y) {
+ // check endpoints of the line segment
+ int numCorners = 0;
+ if (componentContains(a2y, a2x)) {
+ ++numCorners;
+ }
+ if (componentContains(b2y, b2x)) {
+ ++numCorners;
+ }
+
+ if (numCorners == 2) {
+ if (tree.crossesLine(a2x, a2y, b2x, b2y)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_INSIDE_QUERY;
+ } else if (numCorners == 0) {
+ if (tree.crossesLine(a2x, a2y, b2x, b2y)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ /** relates an indexed triangle with the polygon */
+ private Relation relateIndexedTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
// check each corner: if < 3 && > 0 are present, its cheaper than crossesSlowly
int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
if (numCorners == 3) {
@@ -224,22 +270,27 @@ public final class Polygon2D extends EdgeTree {
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
// CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
- private static boolean contains(Edge tree, double latitude, double longitude) {
- // crossings algorithm is an odd-even algorithm, so we descend the tree xor'ing results along our path
+ private static boolean contains(Edge edge, double lat, double lon, AtomicBoolean isOnEdge) {
boolean res = false;
- if (latitude <= tree.max) {
- if (tree.lat1 > latitude != tree.lat2 > latitude) {
- if (longitude < (tree.lon1 - tree.lon2) * (latitude - tree.lat2) / (tree.lat1 - tree.lat2) + tree.lon2) {
- res = true;
+ if (isOnEdge.get() == false && lat <= edge.max) {
+ if (lat == edge.lat1 && lat == edge.lat2 ||
+ (lat <= edge.lat1 && lat >= edge.lat2) != (lat >= edge.lat1 && lat <= edge.lat2)) {
+ if (GeoUtils.orient(edge.lon1, edge.lat1, edge.lon2, edge.lat2, lon, lat) == 0) {
+ // if its on the boundary return true
+ isOnEdge.set(true);
+ return true;
+ } else if (edge.lat1 > lat != edge.lat2 > lat) {
+ res = lon < (edge.lon2 - edge.lon1) * (lat - edge.lat1) / (edge.lat2 - edge.lat1) + edge.lon1;
}
}
- if (tree.left != null) {
- res ^= contains(tree.left, latitude, longitude);
+ if (edge.left != null) {
+ res ^= contains(edge.left, lat, lon, isOnEdge);
}
- if (tree.right != null && latitude >= tree.low) {
- res ^= contains(tree.right, latitude, longitude);
+
+ if (edge.right != null && lat >= edge.low) {
+ res ^= contains(edge.right, lat, lon, isOnEdge);
}
}
- return res;
+ return isOnEdge.get() || res;
}
}
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 ff2c894..c43517b 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -255,18 +255,18 @@ public class TestPolygon2D extends LuceneTestCase {
public void testEdgeInsideness() {
Polygon2D poly = Polygon2D.create(new Polygon(new double[] { -2, -2, 2, 2, -2 }, new double[] { -2, 2, 2, -2, -2 }));
assertTrue(poly.contains(-2, -2)); // bottom left corner: true
- assertFalse(poly.contains(-2, 2)); // bottom right corner: false
- assertFalse(poly.contains(2, -2)); // top left corner: false
- assertFalse(poly.contains(2, 2)); // top right corner: false
+ assertTrue(poly.contains(-2, 2)); // bottom right corner: true
+ assertTrue(poly.contains(2, -2)); // top left corner: true
+ assertTrue(poly.contains(2, 2)); // top right corner: true
assertTrue(poly.contains(-2, -1)); // bottom side: true
assertTrue(poly.contains(-2, 0)); // bottom side: true
assertTrue(poly.contains(-2, 1)); // bottom side: true
- assertFalse(poly.contains(2, -1)); // top side: false
- assertFalse(poly.contains(2, 0)); // top side: false
- assertFalse(poly.contains(2, 1)); // top side: false
- assertFalse(poly.contains(-1, 2)); // right side: false
- assertFalse(poly.contains(0, 2)); // right side: false
- assertFalse(poly.contains(1, 2)); // right side: false
+ assertTrue(poly.contains(2, -1)); // top side: true
+ assertTrue(poly.contains(2, 0)); // top side: true
+ assertTrue(poly.contains(2, 1)); // top side: true
+ assertTrue(poly.contains(-1, 2)); // right side: true
+ assertTrue(poly.contains(0, 2)); // right side: true
+ assertTrue(poly.contains(1, 2)); // right side: true
assertTrue(poly.contains(-1, -2)); // left side: true
assertTrue(poly.contains(0, -2)); // left side: true
assertTrue(poly.contains(1, -2)); // left side: true
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 10c692e..797892e 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -18,6 +18,8 @@ package org.apache.lucene.geo;
import org.apache.lucene.index.PointValues.Relation;
+import static org.apache.lucene.geo.GeoUtils.orient;
+
/**
* 2D line implementation represented as a balanced interval tree of edges.
* <p>
@@ -42,22 +44,51 @@ public final class Line2D extends EdgeTree {
@Override
protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
- if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+ if (tree.crossesBox(minLat, maxLat, minLon, maxLon, true)) {
return Relation.CELL_CROSSES_QUERY;
}
-
return Relation.CELL_OUTSIDE_QUERY;
}
@Override
protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
- if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
- return Relation.CELL_CROSSES_QUERY;
- }
- //check if line is inside triangle
- if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy)) {
+ if (ax == bx && bx == cx && ay == by && by == cy) {
+ // indexed "triangle" is a point: check if point lies on any line segment
+ if (isPointOnLine(tree, ax, ay)) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ } else if (ax == cx && ay == cy) {
+ // indexed "triangle" is a line:
+ if (tree.crossesLine(ax, ay, bx, by)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
+ } else if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy) == true ||
+ tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ // indexed "triangle" is a triangle:
return Relation.CELL_CROSSES_QUERY;
}
return Relation.CELL_OUTSIDE_QUERY;
}
+
+ /** returns true if the provided x, y point lies on the line */
+ private boolean isPointOnLine(Edge tree, double x, double y) {
+ if (y <= tree.max) {
+ double minY = StrictMath.min(tree.lat1, tree.lat2);
+ double maxY = StrictMath.max(tree.lat1, tree.lat2);
+ double minX = StrictMath.min(tree.lon1, tree.lon2);
+ double maxX = StrictMath.max(tree.lon1, tree.lon2);
+ if (Rectangle.containsPoint(y, x, minY, maxY, minX, maxX) &&
+ orient(tree.lon1, tree.lat1, tree.lon2, tree.lat2, x, y) == 0) {
+ return true;
+ }
+ if (tree.left != null && isPointOnLine(tree.left, x, y)) {
+ return true;
+ }
+ if (tree.right != null && maxY >= tree.low && isPointOnLine(tree.right, x, y)) {
+ return true;
+ }
+ }
+ return false;
+ }
}
\ No newline at end of file
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 430f77b..3f64608 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
@@ -233,8 +233,8 @@ public class Rectangle2D {
}
// shortcut: check if either of the end points fall inside the box
- if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
- || bboxContainsPoint(bx, by, minX, maxX, minY, maxY)) {
+ if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY) ||
+ bboxContainsPoint(bx, by, minX, maxX, minY, maxY)) {
return true;
}
@@ -244,11 +244,6 @@ public class Rectangle2D {
return false;
}
- // shortcut: edge is a point
- if (ax == bx && ay == by) {
- 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) {
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 79af141..a325bc7 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -18,9 +18,9 @@ package org.apache.lucene.document;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.document.LatLonShape.QueryRelation;
-import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.GeoTestUtil;
import org.apache.lucene.geo.Line;
+import org.apache.lucene.geo.Line2D;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Polygon2D;
import org.apache.lucene.geo.Rectangle;
@@ -41,12 +41,25 @@ import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.TestUtil;
import org.junit.Ignore;
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
+import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.encodeLongitude;
/** Test case for indexing polygons and querying by bounding box */
public class TestLatLonShape extends LuceneTestCase {
protected static String FIELDNAME = "field";
+
+ /** quantizes a latitude value to be consistent with index encoding */
+ protected static double quantizeLat(double rawLat) {
+ return decodeLatitude(encodeLatitude(rawLat));
+ }
+
+ /** quantizes a longitude value to be consistent with index encoding */
+ protected static double quantizeLon(double rawLon) {
+ return decodeLongitude(encodeLongitude(rawLon));
+ }
+
protected void addPolygonsToDoc(String field, Document doc, Polygon polygon) {
Field[] fields = LatLonShape.createIndexableFields(field, polygon);
for (Field f : fields) {
@@ -283,14 +296,8 @@ public class TestLatLonShape extends LuceneTestCase {
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);
- }
+ addPolygonsToDoc(FIELDNAME, doc, indexPoly1);
+ addPolygonsToDoc(FIELDNAME, doc, indexPoly2);
w.addDocument(doc);
w.forceMerge(1);
@@ -306,22 +313,22 @@ public class TestLatLonShape extends LuceneTestCase {
new double[] {180d, 180d, 170d, 170d, 180d})
};
- Query q = LatLonShape.newPolygonQuery("test", QueryRelation.WITHIN, searchPoly);
+ Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, searchPoly);
assertEquals(1, searcher.count(q));
- q = LatLonShape.newPolygonQuery("test", QueryRelation.INTERSECTS, searchPoly);
+ q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.INTERSECTS, searchPoly);
assertEquals(1, searcher.count(q));
- q = LatLonShape.newPolygonQuery("test", QueryRelation.DISJOINT, searchPoly);
+ q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.DISJOINT, searchPoly);
assertEquals(0, searcher.count(q));
- q = LatLonShape.newBoxQuery("test", QueryRelation.WITHIN, -20, 20, 170, -170);
+ q = LatLonShape.newBoxQuery(FIELDNAME, QueryRelation.WITHIN, -20, 20, 170, -170);
assertEquals(1, searcher.count(q));
- q = LatLonShape.newBoxQuery("test", QueryRelation.INTERSECTS, -20, 20, 170, -170);
+ q = LatLonShape.newBoxQuery(FIELDNAME, QueryRelation.INTERSECTS, -20, 20, 170, -170);
assertEquals(1, searcher.count(q));
- q = LatLonShape.newBoxQuery("test", QueryRelation.DISJOINT, -20, 20, 170, -170);
+ q = LatLonShape.newBoxQuery(FIELDNAME, QueryRelation.DISJOINT, -20, 20, 170, -170);
assertEquals(0, searcher.count(q));
IOUtils.close(w, reader, dir);
@@ -333,23 +340,19 @@ public class TestLatLonShape extends LuceneTestCase {
double blat = 34.26468306870807;
double blon = -52.67048754768767;
Polygon polygon = new Polygon(new double[] {-14.448264200949083, 0, 0, -14.448264200949083, -14.448264200949083},
- new double[] {0.9999999403953552, 0.9999999403953552, 124.50086371762484, 124.50086371762484, 0.9999999403953552});
+ new double[] {0.9999999403953552, 0.9999999403953552, 124.50086371762484, 124.50086371762484, 0.9999999403953552});
Polygon2D polygon2D = Polygon2D.create(polygon);
- PointValues.Relation rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(blon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(alat)));
+ PointValues.Relation rel = polygon2D.relateTriangle(
+ quantizeLon(alon), quantizeLat(blat),
+ quantizeLon(blon), quantizeLat(blat),
+ quantizeLon(alon), quantizeLat(alat));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(alon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(alat)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(blon)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(blat)));
+ rel = polygon2D.relateTriangle(
+ quantizeLon(alon), quantizeLat(blat),
+ quantizeLon(alon), quantizeLat(alat),
+ quantizeLon(blon), quantizeLat(blat));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
}
@@ -358,62 +361,129 @@ public class TestLatLonShape extends LuceneTestCase {
Polygon p = new Polygon(new double[] {0, 0, 1, 1, 0}, new double[] {0, 1, 1, 0, 0});
Polygon2D polygon2D = Polygon2D.create(p);
//3 shared points
- PointValues.Relation rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)));
- assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ PointValues.Relation rel = polygon2D.relateTriangle(
+ quantizeLon(0.5), quantizeLat(0),
+ quantizeLon(1), quantizeLat(0.5),
+ quantizeLon(0.5), quantizeLat(1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
//2 shared points
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.75)));
- assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ rel = polygon2D.relateTriangle(
+ quantizeLon(0.5), quantizeLat(0),
+ quantizeLon(1), quantizeLat(0.5),
+ quantizeLon(0.5), quantizeLat(0.75));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
//1 shared point
rel = polygon2D.relateTriangle(
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.75)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.75)));
- assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ quantizeLon(0.5), quantizeLat(0.5),
+ quantizeLon(0.5), quantizeLat(0),
+ quantizeLon(0.75), quantizeLat(0.75));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
// 1 shared point but out
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(2)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(2)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(2)));
+ rel = polygon2D.relateTriangle(
+ quantizeLon(1), quantizeLat(0.5),
+ quantizeLon(2), quantizeLat(0),
+ quantizeLon(2), quantizeLat(2));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
// 1 shared point but crossing
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(2)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)));
+ rel = polygon2D.relateTriangle(
+ quantizeLon(0.5), quantizeLat(0),
+ quantizeLon(2), quantizeLat(0.5),
+ quantizeLon(0.5), quantizeLat(1));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
//share one edge
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(0.5)));
- assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ rel = polygon2D.relateTriangle(
+ quantizeLon(0), quantizeLat(0),
+ quantizeLon(0), quantizeLat(1),
+ quantizeLon(0.5), quantizeLat(0.5));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, rel);
//share one edge outside
- rel = polygon2D.relateTriangle(GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(0)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1.5)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1.5)),
- GeoEncodingUtils.decodeLongitude(GeoEncodingUtils.encodeLongitude(1)),
- GeoEncodingUtils.decodeLatitude(GeoEncodingUtils.encodeLatitude(1)));
+ rel = polygon2D.relateTriangle(
+ quantizeLon(0), quantizeLat(1),
+ quantizeLon(1.5), quantizeLat(1.5),
+ quantizeLon(1), quantizeLat(1));
assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
}
+ public void testLUCENE8736() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+
+ // test polygons:
+ Polygon indexPoly1 = new Polygon(
+ new double[] {4d, 4d, 3d, 3d, 4d},
+ new double[] {3d, 4d, 4d, 3d, 3d}
+ );
+
+ Polygon indexPoly2 = new Polygon(
+ new double[] {2d, 2d, 1d, 1d, 2d},
+ new double[] {6d, 7d, 7d, 6d, 6d}
+ );
+
+ Polygon indexPoly3 = new Polygon(
+ new double[] {1d, 1d, 0d, 0d, 1d},
+ new double[] {3d, 4d, 4d, 3d, 3d}
+ );
+
+ Polygon indexPoly4 = new Polygon(
+ new double[] {2d, 2d, 1d, 1d, 2d},
+ new double[] {0d, 1d, 1d, 0d, 0d}
+ );
+
+ // index polygons:
+ Document doc;
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly1);
+ w.addDocument(doc);
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly2);
+ w.addDocument(doc);
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly3);
+ w.addDocument(doc);
+ addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly4);
+ 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[] {4d, 4d, 0d, 0d, 4d},
+ new double[] {0d, 7d, 7d, 0d, 0d})
+ };
+
+ Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, searchPoly);
+ assertEquals(4, searcher.count(q));
+
+ IOUtils.close(w, reader, dir);
+ }
+
+ public void testTriangleCrossingPolygonVertices() {
+ Polygon p = new Polygon(new double[] {0, 0, -5, -10, -5, 0}, new double[] {-1, 1, 5, 0, -5, -1});
+ Polygon2D polygon2D = Polygon2D.create(p);
+ PointValues.Relation rel = polygon2D.relateTriangle(
+ quantizeLon(-5), quantizeLat(0),
+ quantizeLon(10), quantizeLat(0),
+ quantizeLon(-5), quantizeLat(-15));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ }
+
+ public void testLineCrossingPolygonVertices() {
+ Polygon p = new Polygon(new double[] {0, -1, 0, 1, 0}, new double[] {-1, 0, 1, 0, -1});
+ Polygon2D polygon2D = Polygon2D.create(p);
+ PointValues.Relation rel = polygon2D.relateTriangle(
+ quantizeLon(-1.5), quantizeLat(0),
+ quantizeLon(1.5), quantizeLat(0),
+ quantizeLon(-1.5), quantizeLat(0));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, rel);
+ }
+
+ public void testLineSharedLine() {
+ Line l = new Line(new double[] {0, 0, 0, 0}, new double[] {-2, -1, 0, 1});
+ Line2D l2d = Line2D.create(l);
+ PointValues.Relation r = l2d.relateTriangle(
+ quantizeLon(-5), quantizeLat(0),
+ quantizeLon(5), quantizeLat(0),
+ quantizeLon(-5), quantizeLat(0));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, r);
+ }
}
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
index fe81fd6..de21ee2 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
@@ -695,10 +695,17 @@ public class GeoTestUtil {
double vertx[] = polyLons;
double testy = latitude;
double testx = longitude;
- for (i = 0, j = nvert-1; i < nvert; j = i++) {
- if ( ((verty[i]>testy) != (verty[j]>testy)) &&
- (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
- c = !c;
+ for (i = 0, j = 1; j < nvert; ++i, ++j) {
+ if (testy == verty[j] && testy == verty[i] ||
+ ((testy <= verty[j] && testy >= verty[i]) != (testy >= verty[j] && testy <= verty[i]))) {
+ if (GeoUtils.orient(vertx[i], verty[i], vertx[j], verty[j], testx, testy) == 0) {
+ // return true if point is on boundary
+ return true;
+ } else if ( ((verty[i] > testy) != (verty[j] > testy)) &&
+ (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) {
+ c = !c;
+ }
+ }
}
return c;
}