You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2016/04/25 21:38:59 UTC
[1/2] lucene-solr:master: LUCENE-7251: remove LatLonGrid,
remove slow polygon methods, speed up multiple components
Repository: lucene-solr
Updated Branches:
refs/heads/master fe795c9f7 -> 837264a42
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
deleted file mode 100644
index f7a2927..0000000
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
+++ /dev/null
@@ -1,396 +0,0 @@
-/*
- * 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.document;
-
-import java.util.Arrays;
-
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.index.PointValues.Relation;
-
-/**
- * 2D polygon implementation represented as a balanced interval tree of edges.
- * <p>
- * contains() and crosses() are still O(n), but for most practical polygons
- * are much faster than brute force.
- * <p>
- * Loosely based on the algorithm described in <a href="http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf">
- * http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf</a>.
- */
-// Both Polygon.contains() and Polygon.crossesSlowly() loop all edges, and first check that the edge is within a range.
-// we just organize the edges to do the same computations on the same subset of edges more efficiently.
-// TODO: clean this up, call it Polygon2D, and remove all the 2D methods from Polygon?
-final class LatLonTree {
- private final LatLonTree[] holes;
-
- /** minimum latitude of this polygon's bounding box area */
- final double minLat;
- /** maximum latitude of this polygon's bounding box area */
- final double maxLat;
- /** minimum longitude of this polygon's bounding box area */
- final double minLon;
- /** maximum longitude of this polygon's bounding box area */
- final double maxLon;
-
- /** root node of our tree */
- final Edge tree;
-
- // TODO: "pack" all the gons and holes into one tree with separator.
- // the algorithms support this, but we have to be careful.
- LatLonTree(Polygon polygon, LatLonTree... holes) {
- this.holes = holes.clone();
- this.minLat = polygon.minLat;
- this.maxLat = polygon.maxLat;
- this.minLon = polygon.minLon;
- this.maxLon = polygon.maxLon;
-
- // create interval tree of edges
- this.tree = createTree(polygon.getPolyLats(), polygon.getPolyLons());
- }
-
- /**
- * Returns true if the point is contained within this polygon.
- * <p>
- * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
- * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
- */
- boolean contains(double latitude, double longitude) {
- // check bounding box
- if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
- return false;
- }
-
- if (tree.contains(latitude, longitude)) {
- for (LatLonTree hole : holes) {
- if (hole.contains(latitude, longitude)) {
- return false;
- }
- }
- return true;
- }
-
- return false;
- }
-
- /** Returns relation to the provided rectangle */
- Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
- // if the bounding boxes are disjoint then the shape does not cross
- if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
- return Relation.CELL_OUTSIDE_QUERY;
- }
- // if the rectangle fully encloses us, we cross.
- if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
- return Relation.CELL_CROSSES_QUERY;
- }
- // check any holes
- for (LatLonTree hole : holes) {
- Relation holeRelation = hole.relate(minLat, maxLat, minLon, maxLon);
- if (holeRelation == Relation.CELL_CROSSES_QUERY) {
- return Relation.CELL_CROSSES_QUERY;
- } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
- return Relation.CELL_OUTSIDE_QUERY;
- }
- }
- // check each corner: if < 4 are present, its cheaper than crossesSlowly
- int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
- if (numCorners == 4) {
- if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
- return Relation.CELL_CROSSES_QUERY;
- }
- return Relation.CELL_INSIDE_QUERY;
- } else if (numCorners > 0) {
- return Relation.CELL_CROSSES_QUERY;
- }
-
- // we cross
- if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
- return Relation.CELL_CROSSES_QUERY;
- }
-
- return Relation.CELL_OUTSIDE_QUERY;
- }
-
- // returns 0, 4, or something in between
- private int numberOfCorners(double minLat, double maxLat, double minLon, double maxLon) {
- int containsCount = 0;
- if (contains(minLat, minLon)) {
- containsCount++;
- }
- if (contains(minLat, maxLon)) {
- containsCount++;
- }
- if (containsCount == 1) {
- return containsCount;
- }
- if (contains(maxLat, maxLon)) {
- containsCount++;
- }
- if (containsCount == 2) {
- return containsCount;
- }
- if (contains(maxLat, minLon)) {
- containsCount++;
- }
- return containsCount;
- }
-
- /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the point */
- static boolean contains(LatLonTree[] polygons, double latitude, double longitude) {
- for (LatLonTree polygon : polygons) {
- if (polygon.contains(latitude, longitude)) {
- return true;
- }
- }
- return false;
- }
-
- /** Returns the multipolygon relation for the rectangle */
- static Relation relate(LatLonTree[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
- for (LatLonTree polygon : polygons) {
- Relation relation = polygon.relate(minLat, maxLat, minLon, maxLon);
- if (relation != Relation.CELL_OUTSIDE_QUERY) {
- // note: we optimize for non-overlapping multipolygons. so if we cross one,
- // we won't keep iterating to try to find a contains.
- return relation;
- }
- }
- return Relation.CELL_OUTSIDE_QUERY;
- }
-
- /** Builds a tree from multipolygon */
- static LatLonTree[] build(Polygon... polygons) {
- // TODO: use one tree with separators (carefully!)
- LatLonTree trees[] = new LatLonTree[polygons.length];
- for (int i = 0; i < trees.length; i++) {
- Polygon gon = polygons[i];
- Polygon gonHoles[] = gon.getHoles();
- LatLonTree holes[] = new LatLonTree[gonHoles.length];
- for (int j = 0; j < holes.length; j++) {
- holes[j] = new LatLonTree(gonHoles[j]);
- }
- trees[i] = new LatLonTree(gon, holes);
- }
- return trees;
- }
-
- /**
- * Internal tree node: represents polygon edge from lat1,lon1 to lat2,lon2.
- * The sort value is {@code low}, which is the minimum latitude of the edge.
- * {@code max} stores the maximum latitude of this edge or any children.
- */
- static final class Edge {
- // lat-lon pair (in original order) of the two vertices
- final double lat1, lat2;
- final double lon1, lon2;
- /** min of this edge */
- final double low;
- /** max latitude of this edge or any children */
- double max;
-
- /** left child edge, or null */
- Edge left;
- /** right child edge, or null */
- Edge right;
-
- Edge(double lat1, double lon1, double lat2, double lon2, double low, double max) {
- this.lat1 = lat1;
- this.lon1 = lon1;
- this.lat2 = lat2;
- this.lon2 = lon2;
- this.low = low;
- this.max = max;
- }
-
- /**
- * Returns true if the point crosses this edge subtree an odd number of times
- * <p>
- * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
- * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
- */
- // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
- // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
- //
- // Copyright (c) 1970-2003, Wm. Randolph Franklin
- //
- // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
- // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
- // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
- // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
- //
- // 1. Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimers.
- // 2. Redistributions in binary form must reproduce the above copyright
- // notice in the documentation and/or other materials provided with
- // the distribution.
- // 3. The name of W. Randolph Franklin may not be used to endorse or
- // promote products derived from this Software without specific
- // prior written permission.
- //
- // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
- // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
- // 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.
- boolean contains(double latitude, double longitude) {
- // crossings algorithm is an odd-even algorithm, so we descend the tree xor'ing results along our path
- boolean res = false;
- if (latitude <= max) {
- if (lat1 > latitude != lat2 > latitude) {
- if (longitude < (lon1 - lon2) * (latitude - lat2) / (lat1 - lat2) + lon2) {
- res = true;
- }
- }
- if (left != null) {
- res ^= left.contains(latitude, longitude);
- }
- if (right != null && latitude >= low) {
- res ^= right.contains(latitude, longitude);
- }
- }
- return res;
- }
-
- /** Returns true if the box crosses any edge in this edge subtree */
- boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
- // 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.
- // if we find one, return true.
- // for each box line (AB):
- // for each poly line (CD):
- // intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
- double cy = lat1;
- double dy = lat2;
- double cx = lon1;
- double dx = lon2;
-
- // 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);
- 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) {
- 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) {
- 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;
- }
-
- // 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 (left != null) {
- if (left.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
- }
-
- if (right != null && maxLat >= low) {
- if (right.crosses(minLat, maxLat, minLon, maxLon)) {
- return true;
- }
- }
- }
- return false;
- }
- }
-
- /**
- * Creates an edge interval tree from a set of polygon vertices.
- * @return root node of the tree.
- */
- private static Edge createTree(double polyLats[], double polyLons[]) {
- Edge edges[] = new Edge[polyLats.length - 1];
- for (int i = 1; i < polyLats.length; i++) {
- double lat1 = polyLats[i-1];
- double lon1 = polyLons[i-1];
- double lat2 = polyLats[i];
- double lon2 = polyLons[i];
- edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
- }
- // sort the edges then build a balanced tree from them
- Arrays.sort(edges, (left, right) -> {
- int ret = Double.compare(left.low, right.low);
- if (ret == 0) {
- ret = Double.compare(left.max, right.max);
- }
- return ret;
- });
- return createTree(edges, 0, edges.length - 1);
- }
-
- /** Creates tree from sorted edges (with range low and high inclusive) */
- private static Edge createTree(Edge edges[], int low, int high) {
- if (low > high) {
- return null;
- }
- // add midpoint
- int mid = (low + high) >>> 1;
- Edge newNode = edges[mid];
- // add children
- newNode.left = createTree(edges, low, mid - 1);
- newNode.right = createTree(edges, mid + 1, high);
- // pull up max values to this node
- if (newNode.left != null) {
- newNode.max = Math.max(newNode.max, newNode.left.max);
- }
- if (newNode.right != null) {
- newNode.max = Math.max(newNode.max, newNode.right.max);
- }
- return newNode;
- }
-
- /**
- * Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
- * negative value if clockwise, zero if collinear.
- */
- // see the "Orient2D" method described here:
- // http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf
- // https://www.cs.cmu.edu/~quake/robust.html
- // Note that this one does not yet have the floating point tricks to be exact!
- private static int orient(double ax, double ay, double bx, double by, double cx, double cy) {
- double v1 = (bx - ax) * (cy - ay);
- double v2 = (cx - ax) * (by - ay);
- if (v1 > v2) {
- return 1;
- } else if (v1 < v2) {
- return -1;
- } else {
- return 0;
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
deleted file mode 100644
index 0c185ea..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonGrid.java
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * 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.document;
-
-import org.apache.lucene.geo.GeoTestUtil;
-import org.apache.lucene.geo.GeoUtils;
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.geo.Rectangle;
-import org.apache.lucene.util.LuceneTestCase;
-import org.apache.lucene.util.TestUtil;
-
-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;
-
-/** tests against LatLonGrid (avoiding indexing/queries) */
-public class TestLatLonGrid extends LuceneTestCase {
-
- /** If the grid returns true, then any point in that cell should return true as well */
- public void testRandom() throws Exception {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = GeoTestUtil.nextPolygon();
- Rectangle box = Rectangle.fromPolygon(new Polygon[] { polygon });
- int minLat = encodeLatitude(box.minLat);
- int maxLat = encodeLatitude(box.maxLat);
- int minLon = encodeLongitude(box.minLon);
- int maxLon = encodeLongitude(box.maxLon);
- LatLonGrid grid = new LatLonGrid(minLat, maxLat, minLon, maxLon, LatLonTree.build(polygon));
- // we are in integer space... but exhaustive testing is slow!
- for (int j = 0; j < 10000; j++) {
- int lat = TestUtil.nextInt(random(), minLat, maxLat);
- int lon = TestUtil.nextInt(random(), minLon, maxLon);
-
- boolean expected = polygon.contains(decodeLatitude(lat),
- decodeLongitude(lon));
- boolean actual = grid.contains(lat, lon);
- assertEquals(expected, actual);
- }
- }
- }
-
- public void testGrowingPolygon() {
- double centerLat = -80.0 + random().nextDouble() * 160.0;
- double centerLon = -170.0 + random().nextDouble() * 340.0;
- double radiusMeters = 0.0;
- for(int i=0;i<10;i++) {
- radiusMeters = Math.nextUp(radiusMeters);
- }
-
- // Start with a miniscule polygon, and grow it:
- int gons = TestUtil.nextInt(random(), 4, 10);
- while (radiusMeters < GeoUtils.EARTH_MEAN_RADIUS_METERS * Math.PI / 2.0 + 1.0) {
- Polygon polygon;
- try {
- polygon = GeoTestUtil.createRegularPolygon(centerLat, centerLon, radiusMeters, gons);
- } catch (IllegalArgumentException iae) {
- // OK: we made a too-big poly and it crossed a pole or dateline
- break;
- }
- radiusMeters *= 1.1;
-
- Rectangle box = Rectangle.fromPolygon(new Polygon[] { polygon });
- int minLat = encodeLatitude(box.minLat);
- int maxLat = encodeLatitude(box.maxLat);
- int minLon = encodeLongitude(box.minLon);
- int maxLon = encodeLongitude(box.maxLon);
- LatLonGrid grid = new LatLonGrid(minLat, maxLat, minLon, maxLon, LatLonTree.build(polygon));
- // we are in integer space... but exhaustive testing is slow!
- for (int j = 0; j < 1000; j++) {
- int lat = TestUtil.nextInt(random(), minLat, maxLat);
- int lon = TestUtil.nextInt(random(), minLon, maxLon);
-
- boolean expected = polygon.contains(decodeLatitude(lat),
- decodeLongitude(lon));
- boolean actual = grid.contains(lat, lon);
- assertEquals(expected, actual);
- }
- }
- }
-
- /** create ever-increasing grids and check that too-small polygons don't blow it up */
- public void testTinyGrids() {
- double ZERO = decodeLatitude(0);
- double ONE = decodeLatitude(1);
- Polygon tiny = new Polygon(new double[] { ZERO, ZERO, ONE, ONE, ZERO }, new double[] { ZERO, ONE, ONE, ZERO, ZERO });
- for (int max = 1; max < 500000; max++) {
- LatLonGrid grid = new LatLonGrid(0, max, 0, max, LatLonTree.build(tiny));
- assertEquals(tiny.contains(decodeLatitude(max), decodeLongitude(max)), grid.contains(max, max));
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonTree.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonTree.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonTree.java
deleted file mode 100644
index c939026..0000000
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonTree.java
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
- * 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.document;
-
-import org.apache.lucene.geo.GeoTestUtil;
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.geo.Rectangle;
-import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.util.LuceneTestCase;
-
-/** Test LatLonTree against the slower implementation for now */
-public class TestLatLonTree extends LuceneTestCase {
-
- /** test that contains() works the same as brute force */
- public void testContainsRandom() {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = GeoTestUtil.nextPolygon();
- LatLonTree tree = new LatLonTree(polygon);
- for (int j = 0; j < 1000; j++) {
- double point[] = GeoTestUtil.nextPointNear(polygon);
- boolean expected = polygon.contains(point[0], point[1]);
- assertEquals(expected, tree.contains(point[0], point[1]));
- }
- }
- }
-
- /** test that relate() works the same as brute force */
- public void testRelateRandom() {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = GeoTestUtil.nextPolygon();
- LatLonTree tree = new LatLonTree(polygon);
- for (int j = 0; j < 1000; j++) {
- Rectangle box = GeoTestUtil.nextBoxNear(polygon);
- Relation expected = polygon.relate(box.minLat, box.maxLat, box.minLon, box.maxLon);
- assertEquals(expected, tree.relate(box.minLat, box.maxLat, box.minLon, box.maxLon));
- }
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
index 14b7cc7..047bf27 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
@@ -20,7 +20,7 @@ import java.util.Objects;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
-import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Polygon2D;
import org.apache.lucene.index.PointValues.Relation;
/** Package private implementation for the public facing GeoPointInPolygonQuery delegate class.
@@ -29,13 +29,13 @@ import org.apache.lucene.index.PointValues.Relation;
*/
final class GeoPointInPolygonQueryImpl extends GeoPointInBBoxQueryImpl {
private final GeoPointInPolygonQuery polygonQuery;
- private final Polygon[] polygons;
+ private final Polygon2D polygons;
GeoPointInPolygonQueryImpl(final String field, final TermEncoding termEncoding, final GeoPointInPolygonQuery q,
final double minLat, final double maxLat, final double minLon, final double maxLon) {
super(field, termEncoding, minLat, maxLat, minLon, maxLon);
this.polygonQuery = Objects.requireNonNull(q);
- this.polygons = Objects.requireNonNull(q.polygons);
+ this.polygons = Polygon2D.create(q.polygons);
}
@Override
@@ -59,17 +59,17 @@ final class GeoPointInPolygonQueryImpl extends GeoPointInBBoxQueryImpl {
@Override
protected boolean cellCrosses(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return Polygon.relate(polygons, minLat, maxLat, minLon, maxLon) == Relation.CELL_CROSSES_QUERY;
+ return polygons.relate(minLat, maxLat, minLon, maxLon) == Relation.CELL_CROSSES_QUERY;
}
@Override
protected boolean cellWithin(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return Polygon.relate(polygons, minLat, maxLat, minLon, maxLon) == Relation.CELL_INSIDE_QUERY;
+ return polygons.relate(minLat, maxLat, minLon, maxLon) == Relation.CELL_INSIDE_QUERY;
}
@Override
protected boolean cellIntersectsShape(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return Polygon.relate(polygons, minLat, maxLat, minLon, maxLon) != Relation.CELL_OUTSIDE_QUERY;
+ return polygons.relate(minLat, maxLat, minLon, maxLon) != Relation.CELL_OUTSIDE_QUERY;
}
/**
@@ -77,11 +77,11 @@ final class GeoPointInPolygonQueryImpl extends GeoPointInBBoxQueryImpl {
* {@link org.apache.lucene.spatial.geopoint.search.GeoPointTermsEnum#accept} method is called to match
* encoded terms that fall within the bounding box of the polygon. Those documents that pass the initial
* bounding box filter are then compared to the provided polygon using the
- * {@link Polygon#contains(Polygon[], double, double)} method.
+ * {@link Polygon2D#contains(double, double)} method.
*/
@Override
protected boolean postFilter(final double lat, final double lon) {
- return Polygon.contains(polygons, lat, lon);
+ return polygons.contains(lat, lon);
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/test-framework/src/java/org/apache/lucene/geo/BaseGeoPointTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/BaseGeoPointTestCase.java b/lucene/test-framework/src/java/org/apache/lucene/geo/BaseGeoPointTestCase.java
index 6bc1e6e..bda4cde 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/geo/BaseGeoPointTestCase.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/BaseGeoPointTestCase.java
@@ -1112,7 +1112,7 @@ public abstract class BaseGeoPointTestCase extends LuceneTestCase {
} else if (Double.isNaN(lats[id])) {
expected = false;
} else {
- expected = polygon.contains(lats[id], lons[id]);
+ expected = GeoTestUtil.containsSlowly(polygon, lats[id], lons[id]);
}
if (hits.get(docID) != expected) {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
----------------------------------------------------------------------
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 98e2966..62b824f 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
@@ -642,4 +642,58 @@ public class GeoTestUtil {
sb.append("</svg>\n");
return sb.toString();
}
+
+ /**
+ * Simple slow point in polygon check (for testing)
+ */
+ // direct port of PNPOLY C code (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html)
+ // this allows us to improve the code yet still ensure we have its properties
+ // it is under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
+ //
+ // Copyright (c) 1970-2003, Wm. Randolph Franklin
+ //
+ // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
+ // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
+ // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
+ // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+ //
+ // 1. Redistributions of source code must retain the above copyright
+ // notice, this list of conditions and the following disclaimers.
+ // 2. Redistributions in binary form must reproduce the above copyright
+ // notice in the documentation and/or other materials provided with
+ // the distribution.
+ // 3. The name of W. Randolph Franklin may not be used to endorse or
+ // promote products derived from this Software without specific
+ // prior written permission.
+ //
+ // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+ // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ // 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.
+ public static boolean containsSlowly(Polygon polygon, double latitude, double longitude) {
+ if (polygon.getHoles().length > 0) {
+ throw new UnsupportedOperationException("this testing method does not support holes");
+ }
+ double polyLats[] = polygon.getPolyLats();
+ double polyLons[] = polygon.getPolyLons();
+ // bounding box check required due to rounding errors (we don't solve that problem)
+ if (latitude < polygon.minLat || latitude > polygon.maxLat || longitude < polygon.minLon || longitude > polygon.maxLon) {
+ return false;
+ }
+
+ boolean c = false;
+ int i, j;
+ int nvert = polyLats.length;
+ double verty[] = polyLats;
+ 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;
+ }
+ return c;
+ }
}
[2/2] lucene-solr:master: LUCENE-7251: remove LatLonGrid,
remove slow polygon methods, speed up multiple components
Posted by rm...@apache.org.
LUCENE-7251: remove LatLonGrid, remove slow polygon methods, speed up multiple components
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/837264a4
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/837264a4
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/837264a4
Branch: refs/heads/master
Commit: 837264a42ebe3e6091a64b2d0410ee7c63eebb1f
Parents: fe795c9
Author: Robert Muir <rm...@apache.org>
Authored: Mon Apr 25 15:29:54 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Mon Apr 25 15:31:54 2016 -0400
----------------------------------------------------------------------
.../src/java/org/apache/lucene/geo/Polygon.java | 221 ---------
.../java/org/apache/lucene/geo/Polygon2D.java | 473 +++++++++++++++++++
.../test/org/apache/lucene/geo/TestPolygon.java | 330 -------------
.../org/apache/lucene/geo/TestPolygon2D.java | 289 +++++++++++
.../org/apache/lucene/document/LatLonGrid.java | 168 -------
.../document/LatLonPointInPolygonQuery.java | 22 +-
.../org/apache/lucene/document/LatLonTree.java | 396 ----------------
.../apache/lucene/document/TestLatLonGrid.java | 106 -----
.../apache/lucene/document/TestLatLonTree.java | 53 ---
.../search/GeoPointInPolygonQueryImpl.java | 16 +-
.../apache/lucene/geo/BaseGeoPointTestCase.java | 2 +-
.../java/org/apache/lucene/geo/GeoTestUtil.java | 54 +++
12 files changed, 830 insertions(+), 1300 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
index 361c199..3b5dec9 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon.java
@@ -18,8 +18,6 @@ package org.apache.lucene.geo;
import java.util.Arrays;
-import org.apache.lucene.index.PointValues.Relation;
-
/**
* Represents a closed polygon on the earth's surface.
* <p>
@@ -48,8 +46,6 @@ public final class Polygon {
/** maximum longitude of this polygon's bounding box area */
public final double maxLon;
- // TODO: we could also compute the maximal inner bounding box, to make relations faster to compute?
-
/**
* Creates a new Polygon from the supplied latitude/longitude array, and optionally any holes.
*/
@@ -110,200 +106,6 @@ public final class Polygon {
this.maxLon = maxLon;
}
- /**
- * Returns true if the point is contained within this polygon.
- * <p>
- * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
- * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
- */
- // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
- // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
- //
- // Copyright (c) 1970-2003, Wm. Randolph Franklin
- //
- // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
- // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
- // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
- // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
- //
- // 1. Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimers.
- // 2. Redistributions in binary form must reproduce the above copyright
- // notice in the documentation and/or other materials provided with
- // the distribution.
- // 3. The name of W. Randolph Franklin may not be used to endorse or
- // promote products derived from this Software without specific
- // prior written permission.
- //
- // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
- // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
- // 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.
- public boolean contains(double latitude, double longitude) {
- // check bounding box
- if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
- return false;
- }
-
- boolean inPoly = false;
- boolean previous = polyLats[0] > latitude;
- for (int i = 1; i < polyLats.length; i++) {
- boolean current = polyLats[i] > latitude;
- if (current != previous) {
- if (longitude < (polyLons[i-1] - polyLons[i]) * (latitude - polyLats[i]) / (polyLats[i-1] - polyLats[i]) + polyLons[i]) {
- inPoly = !inPoly;
- }
- previous = current;
- }
- }
- if (inPoly) {
- for (Polygon hole : holes) {
- if (hole.contains(latitude, longitude)) {
- return false;
- }
- }
- return true;
- } else {
- return false;
- }
- }
-
- /** Returns relation to the provided rectangle */
- public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
- // if the bounding boxes are disjoint then the shape does not cross
- if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
- return Relation.CELL_OUTSIDE_QUERY;
- }
- // if the rectangle fully encloses us, we cross.
- if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
- return Relation.CELL_CROSSES_QUERY;
- }
- // check any holes
- for (Polygon hole : holes) {
- Relation holeRelation = hole.relate(minLat, maxLat, minLon, maxLon);
- if (holeRelation == Relation.CELL_CROSSES_QUERY) {
- return Relation.CELL_CROSSES_QUERY;
- } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
- return Relation.CELL_OUTSIDE_QUERY;
- }
- }
- // check each corner: if < 4 are present, its cheaper than crossesSlowly
- int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
- if (numCorners == 4) {
- if (crossesSlowly(minLat, maxLat, minLon, maxLon)) {
- return Relation.CELL_CROSSES_QUERY;
- }
- return Relation.CELL_INSIDE_QUERY;
- } else if (numCorners > 0) {
- return Relation.CELL_CROSSES_QUERY;
- }
-
- // we cross
- if (crossesSlowly(minLat, maxLat, minLon, maxLon)) {
- return Relation.CELL_CROSSES_QUERY;
- }
-
- return Relation.CELL_OUTSIDE_QUERY;
- }
-
- // returns 0, 4, or something in between
- private int numberOfCorners(double minLat, double maxLat, double minLon, double maxLon) {
- int containsCount = 0;
- if (contains(minLat, minLon)) {
- containsCount++;
- }
- if (contains(minLat, maxLon)) {
- containsCount++;
- }
- if (containsCount == 1) {
- return containsCount;
- }
- if (contains(maxLat, maxLon)) {
- containsCount++;
- }
- if (containsCount == 2) {
- return containsCount;
- }
- if (contains(maxLat, minLon)) {
- containsCount++;
- }
- return containsCount;
- }
-
- /** Returns true if the box crosses our polygon */
- private boolean crossesSlowly(double minLat, double maxLat, double minLon, double maxLon) {
- // we compute line intersections of every polygon edge with every box line.
- // if we find one, return true.
- // for each box line (AB):
- // for each poly line (CD):
- // intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
- for (int i = 1; i < polyLons.length; i++) {
- double cy = polyLats[i - 1];
- double dy = polyLats[i];
- double cx = polyLons[i - 1];
- double dx = polyLons[i];
-
- // 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
- if ((cy < minLat && dy < minLat) ||
- (cy > maxLat && dy > maxLat) ||
- (cx < minLon && dx < minLon) ||
- (cx > maxLon && dx > maxLon)) {
- continue;
- }
-
- // 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) {
- 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) {
- 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;
- }
-
- // 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;
- }
- }
- return false;
- }
-
- /**
- * Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
- * negative value if clockwise, zero if collinear.
- */
- // see the "Orient2D" method described here:
- // http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf
- // https://www.cs.cmu.edu/~quake/robust.html
- // Note that this one does not yet have the floating point tricks to be exact!
- private static int orient(double ax, double ay, double bx, double by, double cx, double cy) {
- double v1 = (bx - ax) * (cy - ay);
- double v2 = (cx - ax) * (by - ay);
- if (v1 > v2) {
- return 1;
- } else if (v1 < v2) {
- return -1;
- } else {
- return 0;
- }
- }
-
/** Returns a copy of the internal latitude array */
public double[] getPolyLats() {
return polyLats.clone();
@@ -319,29 +121,6 @@ public final class Polygon {
return holes.clone();
}
- /** Helper for multipolygon logic: returns true if any of the supplied polygons contain the point */
- public static boolean contains(Polygon[] polygons, double latitude, double longitude) {
- for (Polygon polygon : polygons) {
- if (polygon.contains(latitude, longitude)) {
- return true;
- }
- }
- return false;
- }
-
- /** Returns the multipolygon relation for the rectangle */
- public static Relation relate(Polygon[] polygons, double minLat, double maxLat, double minLon, double maxLon) {
- for (Polygon polygon : polygons) {
- Relation relation = polygon.relate(minLat, maxLat, minLon, maxLon);
- if (relation != Relation.CELL_OUTSIDE_QUERY) {
- // note: we optimize for non-overlapping multipolygons. so if we cross one,
- // we won't keep iterating to try to find a contains.
- return relation;
- }
- }
- return Relation.CELL_OUTSIDE_QUERY;
- }
-
@Override
public int hashCode() {
final int prime = 31;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
new file mode 100644
index 0000000..320d71a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -0,0 +1,473 @@
+/*
+ * 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 java.util.Arrays;
+
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.index.PointValues.Relation;
+
+/**
+ * 2D polygon implementation represented as a balanced interval tree of edges.
+ * <p>
+ * Construction takes {@code O(n log n)} time for sorting and tree construction.
+ * {@link #contains contains()} and {@link #relate relate()} are {@code O(n)}, but for most
+ * practical polygons are much faster than brute force.
+ * <p>
+ * Loosely based on the algorithm described in <a href="http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf">
+ * http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf</a>.
+ * @lucene.internal
+ */
+// Both Polygon.contains() and Polygon.crossesSlowly() loop all edges, and first check that the edge is within a range.
+// we just organize the edges to do the same computations on the same subset of edges more efficiently.
+public final class Polygon2D {
+ /** minimum latitude of this polygon's bounding box area */
+ public final double minLat;
+ /** maximum latitude of this polygon's bounding box area */
+ public final double maxLat;
+ /** minimum longitude of this polygon's bounding box area */
+ public final double minLon;
+ /** maximum longitude of this polygon's bounding box area */
+ public final double maxLon;
+
+ // each component/hole is a node in an augmented 2d kd-tree: we alternate splitting between latitude/longitude,
+ // and pull up max values for both dimensions to each parent node (regardless of split).
+
+ /** maximum latitude of this component or any of its children */
+ private double maxY;
+ /** maximum longitude of this component or any of its children */
+ private double maxX;
+ /** which dimension was this node split on */
+ // TODO: its implicit based on level, but boolean keeps code simple
+ private boolean splitX;
+
+ // child components, or null
+ private Polygon2D left;
+ private Polygon2D right;
+
+ /** tree of holes, or null */
+ private final Polygon2D holes;
+
+ /** root node of edge tree */
+ private final Edge tree;
+
+ private Polygon2D(Polygon polygon, Polygon2D holes) {
+ this.holes = holes;
+ this.minLat = polygon.minLat;
+ this.maxLat = polygon.maxLat;
+ this.minLon = polygon.minLon;
+ this.maxLon = polygon.maxLon;
+ this.maxY = maxLat;
+ this.maxX = maxLon;
+
+ // create interval tree of edges
+ this.tree = createTree(polygon.getPolyLats(), polygon.getPolyLons());
+ }
+
+ /**
+ * Returns true if the point is contained within this polygon.
+ * <p>
+ * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
+ * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
+ */
+ public boolean contains(double latitude, double longitude) {
+ if (latitude <= maxY && longitude <= maxX) {
+ if (componentContains(latitude, longitude)) {
+ return true;
+ }
+ if (left != null) {
+ if (left.contains(latitude, longitude)) {
+ return true;
+ }
+ }
+ if (right != null && ((splitX == false && latitude >= minLat) || (splitX && longitude >= minLon))) {
+ if (right.contains(latitude, longitude)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ /** Returns true if the point is contained within this polygon component. */
+ private boolean componentContains(double latitude, double longitude) {
+ // check bounding box
+ if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
+ return false;
+ }
+
+ if (tree.contains(latitude, longitude)) {
+ if (holes != null && holes.contains(latitude, longitude)) {
+ return false;
+ }
+ return true;
+ }
+
+ return false;
+ }
+
+ /** Returns relation to the provided rectangle */
+ public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
+ if (minLat <= maxY && minLon <= maxX) {
+ Relation relation = componentRelate(minLat, maxLat, minLon, maxLon);
+ if (relation != Relation.CELL_OUTSIDE_QUERY) {
+ return relation;
+ }
+ if (left != null) {
+ relation = left.relate(minLat, maxLat, minLon, maxLon);
+ if (relation != Relation.CELL_OUTSIDE_QUERY) {
+ return relation;
+ }
+ }
+ if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
+ relation = right.relate(minLat, maxLat, minLon, maxLon);
+ if (relation != Relation.CELL_OUTSIDE_QUERY) {
+ return relation;
+ }
+ }
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+
+ /** Returns relation to the provided rectangle for this component */
+ private Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
+ // if the bounding boxes are disjoint then the shape does not cross
+ if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ // if the rectangle fully encloses us, we cross.
+ if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ // check any holes
+ if (holes != null) {
+ Relation holeRelation = holes.relate(minLat, maxLat, minLon, maxLon);
+ if (holeRelation == Relation.CELL_CROSSES_QUERY) {
+ return Relation.CELL_CROSSES_QUERY;
+ } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ }
+ // check each corner: if < 4 are present, its cheaper than crossesSlowly
+ int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
+ if (numCorners == 4) {
+ if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_INSIDE_QUERY;
+ } else if (numCorners > 0) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ // we cross
+ if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+
+ // returns 0, 4, or something in between
+ private int numberOfCorners(double minLat, double maxLat, double minLon, double maxLon) {
+ int containsCount = 0;
+ if (componentContains(minLat, minLon)) {
+ containsCount++;
+ }
+ if (componentContains(minLat, maxLon)) {
+ containsCount++;
+ }
+ if (containsCount == 1) {
+ return containsCount;
+ }
+ if (componentContains(maxLat, maxLon)) {
+ containsCount++;
+ }
+ if (containsCount == 2) {
+ return containsCount;
+ }
+ if (componentContains(maxLat, minLon)) {
+ containsCount++;
+ }
+ return containsCount;
+ }
+
+ /** Creates tree from sorted components (with range low and high inclusive) */
+ private static Polygon2D createTree(Polygon2D components[], int low, int high, boolean splitX) {
+ if (low > high) {
+ return null;
+ } else if (low < high) {
+ // TODO: do one sort instead! there are better algorithms!
+ if (splitX) {
+ Arrays.sort(components, low, high+1, (left, right) -> {
+ int ret = Double.compare(left.minLon, right.minLon);
+ if (ret == 0) {
+ ret = Double.compare(left.maxX, right.maxX);
+ }
+ return ret;
+ });
+ } else {
+ Arrays.sort(components, low, high+1, (left, right) -> {
+ int ret = Double.compare(left.minLat, right.minLat);
+ if (ret == 0) {
+ ret = Double.compare(left.maxY, right.maxY);
+ }
+ return ret;
+ });
+ }
+ }
+ // add midpoint
+ int mid = (low + high) >>> 1;
+ Polygon2D newNode = components[mid];
+ newNode.splitX = splitX;
+ // add children
+ newNode.left = createTree(components, low, mid - 1, !splitX);
+ newNode.right = createTree(components, mid + 1, high, !splitX);
+ // pull up max values to this node
+ if (newNode.left != null) {
+ newNode.maxX = Math.max(newNode.maxX, newNode.left.maxX);
+ newNode.maxY = Math.max(newNode.maxY, newNode.left.maxY);
+ }
+ if (newNode.right != null) {
+ newNode.maxX = Math.max(newNode.maxX, newNode.right.maxX);
+ newNode.maxY = Math.max(newNode.maxY, newNode.right.maxY);
+ }
+ return newNode;
+ }
+
+ /** Builds a Polygon2D from multipolygon */
+ public static Polygon2D create(Polygon... polygons) {
+ Polygon2D components[] = new Polygon2D[polygons.length];
+ for (int i = 0; i < components.length; i++) {
+ Polygon gon = polygons[i];
+ Polygon gonHoles[] = gon.getHoles();
+ Polygon2D holes = null;
+ if (gonHoles.length > 0) {
+ holes = create(gonHoles);
+ }
+ components[i] = new Polygon2D(gon, holes);
+ }
+ return createTree(components, 0, components.length - 1, false);
+ }
+
+ /**
+ * Internal tree node: represents polygon edge from lat1,lon1 to lat2,lon2.
+ * The sort value is {@code low}, which is the minimum latitude of the edge.
+ * {@code max} stores the maximum latitude of this edge or any children.
+ */
+ static final class Edge {
+ // lat-lon pair (in original order) of the two vertices
+ final double lat1, lat2;
+ final double lon1, lon2;
+ /** min of this edge */
+ final double low;
+ /** max latitude of this edge or any children */
+ double max;
+
+ /** left child edge, or null */
+ Edge left;
+ /** right child edge, or null */
+ Edge right;
+
+ Edge(double lat1, double lon1, double lat2, double lon2, double low, double max) {
+ this.lat1 = lat1;
+ this.lon1 = lon1;
+ this.lat2 = lat2;
+ this.lon2 = lon2;
+ this.low = low;
+ this.max = max;
+ }
+
+ /**
+ * Returns true if the point crosses this edge subtree an odd number of times
+ * <p>
+ * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
+ * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
+ */
+ // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
+ // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
+ //
+ // Copyright (c) 1970-2003, Wm. Randolph Franklin
+ //
+ // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
+ // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
+ // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
+ // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+ //
+ // 1. Redistributions of source code must retain the above copyright
+ // notice, this list of conditions and the following disclaimers.
+ // 2. Redistributions in binary form must reproduce the above copyright
+ // notice in the documentation and/or other materials provided with
+ // the distribution.
+ // 3. The name of W. Randolph Franklin may not be used to endorse or
+ // promote products derived from this Software without specific
+ // prior written permission.
+ //
+ // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+ // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ // 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.
+ boolean contains(double latitude, double longitude) {
+ // crossings algorithm is an odd-even algorithm, so we descend the tree xor'ing results along our path
+ boolean res = false;
+ if (latitude <= max) {
+ if (lat1 > latitude != lat2 > latitude) {
+ if (longitude < (lon1 - lon2) * (latitude - lat2) / (lat1 - lat2) + lon2) {
+ res = true;
+ }
+ }
+ if (left != null) {
+ res ^= left.contains(latitude, longitude);
+ }
+ if (right != null && latitude >= low) {
+ res ^= right.contains(latitude, longitude);
+ }
+ }
+ return res;
+ }
+
+ /** Returns true if the box crosses any edge in this edge subtree */
+ boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
+ // 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.
+ // if we find one, return true.
+ // for each box line (AB):
+ // for each poly line (CD):
+ // intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
+ double cy = lat1;
+ double dy = lat2;
+ double cx = lon1;
+ double dx = lon2;
+
+ // 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);
+ 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) {
+ 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) {
+ 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;
+ }
+
+ // 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 (left != null) {
+ if (left.crosses(minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+ }
+
+ if (right != null && maxLat >= low) {
+ if (right.crosses(minLat, maxLat, minLon, maxLon)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+ }
+
+ /**
+ * Creates an edge interval tree from a set of polygon vertices.
+ * @return root node of the tree.
+ */
+ private static Edge createTree(double polyLats[], double polyLons[]) {
+ Edge edges[] = new Edge[polyLats.length - 1];
+ for (int i = 1; i < polyLats.length; i++) {
+ double lat1 = polyLats[i-1];
+ double lon1 = polyLons[i-1];
+ double lat2 = polyLats[i];
+ double lon2 = polyLons[i];
+ edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
+ }
+ // sort the edges then build a balanced tree from them
+ Arrays.sort(edges, (left, right) -> {
+ int ret = Double.compare(left.low, right.low);
+ if (ret == 0) {
+ ret = Double.compare(left.max, right.max);
+ }
+ return ret;
+ });
+ return createTree(edges, 0, edges.length - 1);
+ }
+
+ /** Creates tree from sorted edges (with range low and high inclusive) */
+ private static Edge createTree(Edge edges[], int low, int high) {
+ if (low > high) {
+ return null;
+ }
+ // add midpoint
+ int mid = (low + high) >>> 1;
+ Edge newNode = edges[mid];
+ // add children
+ newNode.left = createTree(edges, low, mid - 1);
+ newNode.right = createTree(edges, mid + 1, high);
+ // pull up max values to this node
+ if (newNode.left != null) {
+ newNode.max = Math.max(newNode.max, newNode.left.max);
+ }
+ if (newNode.right != null) {
+ newNode.max = Math.max(newNode.max, newNode.right.max);
+ }
+ return newNode;
+ }
+
+ /**
+ * Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
+ * negative value if clockwise, zero if collinear.
+ */
+ // see the "Orient2D" method described here:
+ // http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf
+ // https://www.cs.cmu.edu/~quake/robust.html
+ // Note that this one does not yet have the floating point tricks to be exact!
+ private static int orient(double ax, double ay, double bx, double by, double cx, double cy) {
+ double v1 = (bx - ax) * (cy - ay);
+ double v2 = (cx - ax) * (by - ay);
+ if (v1 > v2) {
+ return 1;
+ } else if (v1 < v2) {
+ return -1;
+ } else {
+ return 0;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/core/src/test/org/apache/lucene/geo/TestPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon.java b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon.java
index 12c3690..401092f 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon.java
@@ -16,17 +16,8 @@
*/
package org.apache.lucene.geo;
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.LuceneTestCase;
-import static org.apache.lucene.geo.GeoTestUtil.nextLatitude;
-import static org.apache.lucene.geo.GeoTestUtil.nextLongitude;
-import static org.apache.lucene.geo.GeoTestUtil.nextPolygon;
-
-import java.util.ArrayList;
-import java.util.List;
-
public class TestPolygon extends LuceneTestCase {
/** null polyLats not allowed */
@@ -68,325 +59,4 @@ public class TestPolygon extends LuceneTestCase {
});
assertTrue(expected.getMessage(), expected.getMessage().contains("it must close itself"));
}
-
- /** Three boxes, an island inside a hole inside a shape */
- public void testMultiPolygon() {
- Polygon hole = new Polygon(new double[] { -10, -10, 10, 10, -10 }, new double[] { -10, 10, 10, -10, -10 });
- Polygon outer = new Polygon(new double[] { -50, -50, 50, 50, -50 }, new double[] { -50, 50, 50, -50, -50 }, hole);
- Polygon island = new Polygon(new double[] { -5, -5, 5, 5, -5 }, new double[] { -5, 5, 5, -5, -5 } );
- Polygon polygons[] = new Polygon[] { outer, island };
-
- // contains(point)
- assertTrue(Polygon.contains(polygons, -2, 2)); // on the island
- assertFalse(Polygon.contains(polygons, -6, 6)); // in the hole
- assertTrue(Polygon.contains(polygons, -25, 25)); // on the mainland
- assertFalse(Polygon.contains(polygons, -51, 51)); // in the ocean
-
- // relate(box): this can conservatively return CELL_CROSSES_QUERY
- assertEquals(Relation.CELL_INSIDE_QUERY, Polygon.relate(polygons, -2, 2, -2, 2)); // on the island
- assertEquals(Relation.CELL_OUTSIDE_QUERY, Polygon.relate(polygons, 6, 7, 6, 7)); // in the hole
- assertEquals(Relation.CELL_INSIDE_QUERY, Polygon.relate(polygons, 24, 25, 24, 25)); // on the mainland
- assertEquals(Relation.CELL_OUTSIDE_QUERY, Polygon.relate(polygons, 51, 52, 51, 52)); // in the ocean
- assertEquals(Relation.CELL_CROSSES_QUERY, Polygon.relate(polygons, -60, 60, -60, 60)); // enclosing us completely
- assertEquals(Relation.CELL_CROSSES_QUERY, Polygon.relate(polygons, 49, 51, 49, 51)); // overlapping the mainland
- assertEquals(Relation.CELL_CROSSES_QUERY, Polygon.relate(polygons, 9, 11, 9, 11)); // overlapping the hole
- assertEquals(Relation.CELL_CROSSES_QUERY, Polygon.relate(polygons, 5, 6, 5, 6)); // overlapping the island
- }
-
- public void testPacMan() throws Exception {
- // pacman
- double[] px = {0, 10, 10, 0, -8, -10, -8, 0, 10, 10, 0};
- double[] py = {0, 5, 9, 10, 9, 0, -9, -10, -9, -5, 0};
-
- // candidate crosses cell
- double xMin = 2;//-5;
- double xMax = 11;//0.000001;
- double yMin = -1;//0;
- double yMax = 1;//5;
-
- // test cell crossing poly
- Polygon polygon = new Polygon(py, px);
- assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(yMin, yMax, xMin, xMax));
- }
-
- public void testBoundingBox() throws Exception {
- for (int i = 0; i < 100; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 100; j++) {
- double latitude = nextLatitude();
- double longitude = nextLongitude();
- // if the point is within poly, then it should be in our bounding box
- if (polygon.contains(latitude, longitude)) {
- assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
- assertTrue(longitude >= polygon.minLon && longitude <= polygon.maxLon);
- }
- }
- }
- }
-
- // targets the bounding box directly
- public void testBoundingBoxEdgeCases() throws Exception {
- for (int i = 0; i < 100; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 100; j++) {
- double point[] = GeoTestUtil.nextPointNear(polygon);
- double latitude = point[0];
- double longitude = point[1];
- // if the point is within poly, then it should be in our bounding box
- if (polygon.contains(latitude, longitude)) {
- assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
- assertTrue(longitude >= polygon.minLon && longitude <= polygon.maxLon);
- }
- }
- }
- }
-
- /** If polygon.contains(box) returns true, then any point in that box should return true as well */
- public void testContainsRandom() throws Exception {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 100; j++) {
- Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
- // allowed to conservatively return false
- if (polygon.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_INSIDE_QUERY) {
- for (int k = 0; k < 500; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(rectangle);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertTrue(polygon.contains(latitude, longitude));
- }
- }
- for (int k = 0; k < 100; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(polygon);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertTrue(polygon.contains(latitude, longitude));
- }
- }
- }
- }
- }
- }
-
- /** If polygon.contains(box) returns true, then any point in that box should return true as well */
- // different from testContainsRandom in that its not a purely random test. we iterate the vertices of the polygon
- // and generate boxes near each one of those to try to be more efficient.
- public void testContainsEdgeCases() throws Exception {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 10; j++) {
- Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
- // allowed to conservatively return false
- if (polygon.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_INSIDE_QUERY) {
- for (int k = 0; k < 100; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(rectangle);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertTrue(polygon.contains(latitude, longitude));
- }
- }
- for (int k = 0; k < 20; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(polygon);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertTrue(polygon.contains(latitude, longitude));
- }
- }
- }
- }
- }
- }
-
- /** If polygon.intersects(box) returns false, then any point in that box should return false as well */
- public void testIntersectRandom() {
- for (int i = 0; i < 100; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 100; j++) {
- Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
- // allowed to conservatively return true.
- if (polygon.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_OUTSIDE_QUERY) {
- for (int k = 0; k < 1000; k++) {
- double point[] = GeoTestUtil.nextPointNear(rectangle);
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertFalse(polygon.contains(latitude, longitude));
- }
- }
- for (int k = 0; k < 100; k++) {
- double point[] = GeoTestUtil.nextPointNear(polygon);
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertFalse(polygon.contains(latitude, longitude));
- }
- }
- }
- }
- }
- }
-
- /** If polygon.intersects(box) returns false, then any point in that box should return false as well */
- // different from testIntersectsRandom in that its not a purely random test. we iterate the vertices of the polygon
- // and generate boxes near each one of those to try to be more efficient.
- public void testIntersectEdgeCases() {
- for (int i = 0; i < 100; i++) {
- Polygon polygon = nextPolygon();
-
- for (int j = 0; j < 10; j++) {
- Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
- // allowed to conservatively return false.
- if (polygon.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_OUTSIDE_QUERY) {
- for (int k = 0; k < 100; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(rectangle);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertFalse(polygon.contains(latitude, longitude));
- }
- }
- for (int k = 0; k < 50; k++) {
- // this tests in our range but sometimes outside! so we have to double-check its really in other box
- double point[] = GeoTestUtil.nextPointNear(polygon);
- double latitude = point[0];
- double longitude = point[1];
- // check for sure its in our box
- if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
- assertFalse(polygon.contains(latitude, longitude));
- }
- }
- }
- }
- }
- }
-
- /** Tests edge case behavior with respect to insideness */
- public void testEdgeInsideness() {
- Polygon poly = 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, -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(-1, -2)); // left side: true
- assertTrue(poly.contains(0, -2)); // left side: true
- assertTrue(poly.contains(1, -2)); // left side: true
- }
-
- /** Tests that our impl supports multiple components and holes (not currently used) */
- public void testMultiPolygonContains() {
- // this is the equivalent of the following: we don't recommend anyone do this (e.g. relation logic will not work)
- // but lets not lose the property that it works.
- ///
- // Polygon hole = new Polygon(new double[] { -10, -10, 10, 10, -10 }, new double[] { -10, 10, 10, -10, -10 });
- // Polygon outer = new Polygon(new double[] { -50, -50, 50, 50, -50 }, new double[] { -50, 50, 50, -50, -50 }, hole);
- // Polygon island = new Polygon(new double[] { -5, -5, 5, 5, -5 }, new double[] { -5, 5, 5, -5, -5 } );
- // Polygon polygons[] = new Polygon[] { outer, island };
-
- Polygon polygon = new Polygon(new double[] { 0, -50, -50, 50, 50, -50, 0, -5, -5, 5, 5, -5, 0, -10, -10, 10, 10, -10, 0 },
- new double[] { 0, -50, 50, 50, -50, -50, 0, -5, 5, 5, -5, -5, 0, -10, 10, 10, -10, -10, 0 });
-
- assertTrue(polygon.contains(-2, 2)); // on the island
- assertFalse(polygon.contains(-6, 6)); // in the hole
- assertTrue(polygon.contains(-25, 25)); // on the mainland
- assertFalse(polygon.contains(-51, 51)); // in the ocean
- }
-
- /** Tests current impl against original algorithm */
- public void testContainsAgainstOriginal() {
- for (int i = 0; i < 1000; i++) {
- Polygon polygon = nextPolygon();
- // currently we don't generate these, but this test does not want holes.
- while (polygon.getHoles().length > 0) {
- polygon = nextPolygon();
- }
-
- double polyLats[] = polygon.getPolyLats();
- double polyLons[] = polygon.getPolyLons();
-
- // random lat/lons against polygon
- for (int j = 0; j < 1000; j++) {
- double point[] = GeoTestUtil.nextPointNear(polygon);
- double latitude = point[0];
- double longitude = point[1];
- // bounding box check required due to rounding errors (we don't solve that problem)
- if (latitude >= polygon.minLat && latitude <= polygon.maxLat && longitude >= polygon.minLon && longitude <= polygon.maxLon) {
- boolean expected = containsOriginal(polyLats, polyLons, latitude, longitude);
- assertEquals(expected, polygon.contains(latitude, longitude));
- }
- }
- }
- }
-
- // direct port of PNPOLY C code (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html)
- // this allows us to improve the code yet still ensure we have its properties
- // it is under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
- //
- // Copyright (c) 1970-2003, Wm. Randolph Franklin
- //
- // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
- // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
- // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
- // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
- //
- // 1. Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimers.
- // 2. Redistributions in binary form must reproduce the above copyright
- // notice in the documentation and/or other materials provided with
- // the distribution.
- // 3. The name of W. Randolph Franklin may not be used to endorse or
- // promote products derived from this Software without specific
- // prior written permission.
- //
- // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
- // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
- // 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 containsOriginal(double polyLats[], double polyLons[], double latitude, double longitude) {
- boolean c = false;
- int i, j;
- int nvert = polyLats.length;
- double verty[] = polyLats;
- 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;
- }
- return c;
- }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
new file mode 100644
index 0000000..70281ca
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestPolygon2D.java
@@ -0,0 +1,289 @@
+/*
+ * 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 static org.apache.lucene.geo.GeoTestUtil.nextLatitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextLongitude;
+import static org.apache.lucene.geo.GeoTestUtil.nextPolygon;
+
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.LuceneTestCase;
+
+/** Test Polygon2D impl */
+public class TestPolygon2D extends LuceneTestCase {
+
+ /** Three boxes, an island inside a hole inside a shape */
+ public void testMultiPolygon() {
+ Polygon hole = new Polygon(new double[] { -10, -10, 10, 10, -10 }, new double[] { -10, 10, 10, -10, -10 });
+ Polygon outer = new Polygon(new double[] { -50, -50, 50, 50, -50 }, new double[] { -50, 50, 50, -50, -50 }, hole);
+ Polygon island = new Polygon(new double[] { -5, -5, 5, 5, -5 }, new double[] { -5, 5, 5, -5, -5 } );
+ Polygon2D polygon = Polygon2D.create(outer, island);
+
+ // contains(point)
+ assertTrue(polygon.contains(-2, 2)); // on the island
+ assertFalse(polygon.contains(-6, 6)); // in the hole
+ assertTrue(polygon.contains(-25, 25)); // on the mainland
+ assertFalse(polygon.contains(-51, 51)); // in the ocean
+
+ // relate(box): this can conservatively return CELL_CROSSES_QUERY
+ assertEquals(Relation.CELL_INSIDE_QUERY, polygon.relate(-2, 2, -2, 2)); // on the island
+ assertEquals(Relation.CELL_OUTSIDE_QUERY, polygon.relate(6, 7, 6, 7)); // in the hole
+ assertEquals(Relation.CELL_INSIDE_QUERY, polygon.relate(24, 25, 24, 25)); // on the mainland
+ assertEquals(Relation.CELL_OUTSIDE_QUERY, polygon.relate(51, 52, 51, 52)); // in the ocean
+ assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(-60, 60, -60, 60)); // enclosing us completely
+ assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(49, 51, 49, 51)); // overlapping the mainland
+ assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(9, 11, 9, 11)); // overlapping the hole
+ assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(5, 6, 5, 6)); // overlapping the island
+ }
+
+ public void testPacMan() throws Exception {
+ // pacman
+ double[] px = {0, 10, 10, 0, -8, -10, -8, 0, 10, 10, 0};
+ double[] py = {0, 5, 9, 10, 9, 0, -9, -10, -9, -5, 0};
+
+ // candidate crosses cell
+ double xMin = 2;//-5;
+ double xMax = 11;//0.000001;
+ double yMin = -1;//0;
+ double yMax = 1;//5;
+
+ // test cell crossing poly
+ Polygon2D polygon = Polygon2D.create(new Polygon(py, px));
+ assertEquals(Relation.CELL_CROSSES_QUERY, polygon.relate(yMin, yMax, xMin, xMax));
+ }
+
+ public void testBoundingBox() throws Exception {
+ for (int i = 0; i < 100; i++) {
+ Polygon2D polygon = Polygon2D.create(nextPolygon());
+
+ for (int j = 0; j < 100; j++) {
+ double latitude = nextLatitude();
+ double longitude = nextLongitude();
+ // if the point is within poly, then it should be in our bounding box
+ if (polygon.contains(latitude, longitude)) {
+ assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
+ assertTrue(longitude >= polygon.minLon && longitude <= polygon.maxLon);
+ }
+ }
+ }
+ }
+
+ // targets the bounding box directly
+ public void testBoundingBoxEdgeCases() throws Exception {
+ for (int i = 0; i < 100; i++) {
+ Polygon polygon = nextPolygon();
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ for (int j = 0; j < 100; j++) {
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ double latitude = point[0];
+ double longitude = point[1];
+ // if the point is within poly, then it should be in our bounding box
+ if (impl.contains(latitude, longitude)) {
+ assertTrue(latitude >= polygon.minLat && latitude <= polygon.maxLat);
+ assertTrue(longitude >= polygon.minLon && longitude <= polygon.maxLon);
+ }
+ }
+ }
+ }
+
+ /** If polygon.contains(box) returns true, then any point in that box should return true as well */
+ public void testContainsRandom() throws Exception {
+ for (int i = 0; i < 1000; i++) {
+ Polygon polygon = nextPolygon();
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ for (int j = 0; j < 100; j++) {
+ Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
+ // allowed to conservatively return false
+ if (impl.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_INSIDE_QUERY) {
+ for (int k = 0; k < 500; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(rectangle);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertTrue(impl.contains(latitude, longitude));
+ }
+ }
+ for (int k = 0; k < 100; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertTrue(impl.contains(latitude, longitude));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /** If polygon.contains(box) returns true, then any point in that box should return true as well */
+ // different from testContainsRandom in that its not a purely random test. we iterate the vertices of the polygon
+ // and generate boxes near each one of those to try to be more efficient.
+ public void testContainsEdgeCases() throws Exception {
+ for (int i = 0; i < 1000; i++) {
+ Polygon polygon = nextPolygon();
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ for (int j = 0; j < 10; j++) {
+ Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
+ // allowed to conservatively return false
+ if (impl.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_INSIDE_QUERY) {
+ for (int k = 0; k < 100; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(rectangle);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertTrue(impl.contains(latitude, longitude));
+ }
+ }
+ for (int k = 0; k < 20; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertTrue(impl.contains(latitude, longitude));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /** If polygon.intersects(box) returns false, then any point in that box should return false as well */
+ public void testIntersectRandom() {
+ for (int i = 0; i < 100; i++) {
+ Polygon polygon = nextPolygon();
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ for (int j = 0; j < 100; j++) {
+ Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
+ // allowed to conservatively return true.
+ if (impl.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_OUTSIDE_QUERY) {
+ for (int k = 0; k < 1000; k++) {
+ double point[] = GeoTestUtil.nextPointNear(rectangle);
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertFalse(impl.contains(latitude, longitude));
+ }
+ }
+ for (int k = 0; k < 100; k++) {
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertFalse(impl.contains(latitude, longitude));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /** If polygon.intersects(box) returns false, then any point in that box should return false as well */
+ // different from testIntersectsRandom in that its not a purely random test. we iterate the vertices of the polygon
+ // and generate boxes near each one of those to try to be more efficient.
+ public void testIntersectEdgeCases() {
+ for (int i = 0; i < 100; i++) {
+ Polygon polygon = nextPolygon();
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ for (int j = 0; j < 10; j++) {
+ Rectangle rectangle = GeoTestUtil.nextBoxNear(polygon);
+ // allowed to conservatively return false.
+ if (impl.relate(rectangle.minLat, rectangle.maxLat, rectangle.minLon, rectangle.maxLon) == Relation.CELL_OUTSIDE_QUERY) {
+ for (int k = 0; k < 100; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(rectangle);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertFalse(impl.contains(latitude, longitude));
+ }
+ }
+ for (int k = 0; k < 50; k++) {
+ // this tests in our range but sometimes outside! so we have to double-check its really in other box
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ double latitude = point[0];
+ double longitude = point[1];
+ // check for sure its in our box
+ if (latitude >= rectangle.minLat && latitude <= rectangle.maxLat && longitude >= rectangle.minLon && longitude <= rectangle.maxLon) {
+ assertFalse(impl.contains(latitude, longitude));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /** Tests edge case behavior with respect to insideness */
+ 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, -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(-1, -2)); // left side: true
+ assertTrue(poly.contains(0, -2)); // left side: true
+ assertTrue(poly.contains(1, -2)); // left side: true
+ }
+
+ /** Tests current impl against original algorithm */
+ public void testContainsAgainstOriginal() {
+ for (int i = 0; i < 1000; i++) {
+ Polygon polygon = nextPolygon();
+ // currently we don't generate these, but this test does not want holes.
+ while (polygon.getHoles().length > 0) {
+ polygon = nextPolygon();
+ }
+ Polygon2D impl = Polygon2D.create(polygon);
+
+ // random lat/lons against polygon
+ for (int j = 0; j < 1000; j++) {
+ double point[] = GeoTestUtil.nextPointNear(polygon);
+ double latitude = point[0];
+ double longitude = point[1];
+ boolean expected = GeoTestUtil.containsSlowly(polygon, latitude, longitude);
+ assertEquals(expected, impl.contains(latitude, longitude));
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
deleted file mode 100644
index 4b3b2b2..0000000
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonGrid.java
+++ /dev/null
@@ -1,168 +0,0 @@
-/*
- * 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.document;
-
-import org.apache.lucene.geo.Polygon;
-import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.util.FixedBitSet;
-
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
-import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
-
-/**
- * This is a temporary hack, until some polygon methods have better performance!
- * <p>
- * When this file is removed then we have made good progress! In general we don't call
- * the point-in-polygon algorithm that much, because of how BKD divides up the data. But
- * today the method is very slow (general to all polygons, linear with the number of vertices).
- * At the same time polygon-rectangle relation operations are also slow in the same way, this
- * just really ensures they are the bottleneck by removing most of the point-in-polygon calls.
- * <p>
- * See the "grid" algorithm description here: http://erich.realtimerendering.com/ptinpoly/
- * A few differences:
- * <ul>
- * <li> We work in an integer encoding, so edge cases are simpler.
- * <li> We classify each grid cell as "contained", "not contained", or "don't know".
- * <li> We form a grid over a potentially complex multipolygon with holes.
- * <li> Construction is less efficient because we do not do anything "smart" such
- * as following polygon edges.
- * <li> Instead we construct a baby tree to reduce the number of relation operations,
- * which are currently expensive.
- * </ul>
- */
-// TODO: just make a more proper tree (maybe in-ram BKD)? then we can answer most
-// relational operations as rectangle <-> rectangle relations in integer space in log(n) time..
-final class LatLonGrid {
- // must be a power of two!
- static final int GRID_SIZE = 1<<7;
- final int minLat;
- final int maxLat;
- final int minLon;
- final int maxLon;
- // TODO: something more efficient than parallel bitsets? maybe one bitset?
- final FixedBitSet haveAnswer = new FixedBitSet(GRID_SIZE * GRID_SIZE);
- final FixedBitSet answer = new FixedBitSet(GRID_SIZE * GRID_SIZE);
-
- final long latPerCell;
- final long lonPerCell;
-
- final LatLonTree[] tree;
-
- LatLonGrid(int minLat, int maxLat, int minLon, int maxLon, LatLonTree[] tree) {
- this.minLat = minLat;
- this.maxLat = maxLat;
- this.minLon = minLon;
- this.maxLon = maxLon;
- this.tree = tree;
- if (minLon > maxLon) {
- // maybe make 2 grids if you want this?
- throw new IllegalArgumentException("Grid cannot cross the dateline");
- }
- if (minLat > maxLat) {
- throw new IllegalArgumentException("bogus grid");
- }
- long latitudeRange = maxLat - (long) minLat;
- long longitudeRange = maxLon - (long) minLon;
-
- // if the range is too small, we can't divide it up in our grid nicely.
- // in this case of a tiny polygon, we just make an empty grid instead of complicating/slowing down code.
- final long minRange = (GRID_SIZE - 1) * (GRID_SIZE - 1);
- if (latitudeRange < minRange || longitudeRange < minRange) {
- latPerCell = lonPerCell = Long.MAX_VALUE;
- } else {
- // we spill over the edge of the bounding box in each direction a bit,
- // but it prevents edge case bugs.
- latPerCell = latitudeRange / (GRID_SIZE - 1);
- lonPerCell = longitudeRange / (GRID_SIZE - 1);
- fill(0, GRID_SIZE, 0, GRID_SIZE);
- }
- }
-
- /** fills a 2D range of grid cells [minLatIndex .. maxLatIndex) X [minLonIndex .. maxLonIndex) */
- void fill(int minLatIndex, int maxLatIndex, int minLonIndex, int maxLonIndex) {
- // grid cells at the edge of the bounding box are typically smaller than normal, because we spill over.
- long cellMinLat = minLat + (minLatIndex * latPerCell);
- long cellMaxLat = Math.min(maxLat, minLat + (maxLatIndex * latPerCell) - 1);
- long cellMinLon = minLon + (minLonIndex * lonPerCell);
- long cellMaxLon = Math.min(maxLon, minLon + (maxLonIndex * lonPerCell) - 1);
-
- assert cellMinLat <= maxLat && cellMinLon <= maxLon;
- assert cellMaxLat >= cellMinLat;
- assert cellMaxLon >= cellMinLon;
-
- Relation relation = LatLonTree.relate(tree, decodeLatitude((int) cellMinLat),
- decodeLatitude((int) cellMaxLat),
- decodeLongitude((int) cellMinLon),
- decodeLongitude((int) cellMaxLon));
- if (relation != Relation.CELL_CROSSES_QUERY) {
- // we know the answer for this region, fill the cell range
- for (int i = minLatIndex; i < maxLatIndex; i++) {
- for (int j = minLonIndex; j < maxLonIndex; j++) {
- int index = i * GRID_SIZE + j;
- assert haveAnswer.get(index) == false;
- haveAnswer.set(index);
- if (relation == Relation.CELL_INSIDE_QUERY) {
- answer.set(index);
- }
- }
- }
- } else if (minLatIndex == maxLatIndex - 1) {
- // nothing more to do: this is a single grid cell (leaf node) and
- // is an edge case for the polygon.
- } else {
- // grid range crosses our polygon, keep recursing.
- int midLatIndex = (minLatIndex + maxLatIndex) >>> 1;
- int midLonIndex = (minLonIndex + maxLonIndex) >>> 1;
- fill(minLatIndex, midLatIndex, minLonIndex, midLonIndex);
- fill(minLatIndex, midLatIndex, midLonIndex, maxLonIndex);
- fill(midLatIndex, maxLatIndex, minLonIndex, midLonIndex);
- fill(midLatIndex, maxLatIndex, midLonIndex, maxLonIndex);
- }
- }
-
- /** Returns true if inside one of our polygons, false otherwise */
- boolean contains(int latitude, int longitude) {
- // first see if the grid knows the answer
- int index = index(latitude, longitude);
- if (index == -1) {
- return false; // outside of bounding box range
- } else if (haveAnswer.get(index)) {
- return answer.get(index);
- }
-
- // the grid is unsure (boundary): do a real test.
- double docLatitude = decodeLatitude(latitude);
- double docLongitude = decodeLongitude(longitude);
- return LatLonTree.contains(tree, docLatitude, docLongitude);
- }
-
- /** Returns grid index of lat/lon, or -1 if the value is outside of the bounding box. */
- private int index(int latitude, int longitude) {
- if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
- return -1; // outside of bounding box range
- }
-
- long latRel = latitude - (long) minLat;
- long lonRel = longitude - (long) minLon;
-
- int latIndex = (int) (latRel / latPerCell);
- assert latIndex < GRID_SIZE;
- int lonIndex = (int) (lonRel / lonPerCell);
- assert lonIndex < GRID_SIZE;
- return latIndex * GRID_SIZE + lonIndex;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/837264a4/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
index e68cb45..ee7c1e8 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
@@ -38,6 +38,7 @@ import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.StringHelper;
import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Polygon2D;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
@@ -92,11 +93,7 @@ final class LatLonPointInPolygonQuery extends Query {
NumericUtils.intToSortableBytes(encodeLongitude(box.minLon), minLon, 0);
NumericUtils.intToSortableBytes(encodeLongitude(box.maxLon), maxLon, 0);
- final LatLonTree[] tree = LatLonTree.build(polygons);
- final LatLonGrid grid = new LatLonGrid(encodeLatitude(box.minLat),
- encodeLatitude(box.maxLat),
- encodeLongitude(box.minLon),
- encodeLongitude(box.maxLon), tree);
+ final Polygon2D tree = Polygon2D.create(polygons);
return new ConstantScoreWeight(this) {
@@ -132,17 +129,8 @@ final class LatLonPointInPolygonQuery extends Query {
@Override
public void visit(int docID, byte[] packedValue) {
- // we bounds check individual values, as subtrees may cross, but we are being sent the values anyway:
- // this reduces the amount of docvalues fetches (improves approximation)
- if (StringHelper.compare(Integer.BYTES, packedValue, 0, maxLat, 0) > 0 ||
- StringHelper.compare(Integer.BYTES, packedValue, 0, minLat, 0) < 0 ||
- StringHelper.compare(Integer.BYTES, packedValue, Integer.BYTES, maxLon, 0) > 0 ||
- StringHelper.compare(Integer.BYTES, packedValue, Integer.BYTES, minLon, 0) < 0) {
- // outside of global bounding box range
- return;
- }
- if (grid.contains(NumericUtils.sortableBytesToInt(packedValue, 0),
- NumericUtils.sortableBytesToInt(packedValue, Integer.BYTES))) {
+ if (tree.contains(decodeLatitude(packedValue, 0),
+ decodeLongitude(packedValue, Integer.BYTES))) {
result.add(docID);
}
}
@@ -162,7 +150,7 @@ final class LatLonPointInPolygonQuery extends Query {
double cellMaxLat = decodeLatitude(maxPackedValue, 0);
double cellMaxLon = decodeLongitude(maxPackedValue, Integer.BYTES);
- return LatLonTree.relate(tree, cellMinLat, cellMaxLat, cellMinLon, cellMaxLon);
+ return tree.relate(cellMinLat, cellMaxLat, cellMinLon, cellMaxLon);
}
});