You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2016/08/25 22:10:52 UTC
[1/2] lucene-solr:master: LUCENE-7424: GeoPolygon computation of
intersection bounds was incorrect.
Repository: lucene-solr
Updated Branches:
refs/heads/master d489b8c05 -> 8683da80e
LUCENE-7424: GeoPolygon computation of intersection bounds was incorrect.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/884aa160
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/884aa160
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/884aa160
Branch: refs/heads/master
Commit: 884aa1609a72e273307a93a6a07f181eab25faad
Parents: e325973
Author: Karl Wright <Da...@gmail.com>
Authored: Thu Aug 25 18:09:50 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu Aug 25 18:09:50 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoConcavePolygon.java | 51 ++++++++------------
.../lucene/spatial3d/geom/GeoConvexPolygon.java | 47 ++++++++----------
.../lucene/spatial3d/geom/GeoPolygonTest.java | 39 +++++++++++++++
3 files changed, 79 insertions(+), 58 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
index 1abc06c..e2a4c1e 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
@@ -50,10 +50,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
protected boolean isDone = false;
/** A bounds object for each sided plane */
protected Map<SidedPlane, Membership> eitherBounds = null;
- /** Edge plane for one side of intersection */
- protected Map<SidedPlane, Plane> edgePlanes = null;
- /** Intersection bounds */
- protected Map<SidedPlane, Membership> intersectionBounds = null;
+ /** Map from edge to its previous non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
+ /** Map from edge to its next non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> nextBrotherMap = null;
/**
* Create a concave polygon from a list of points. The first point must be on the
@@ -214,8 +214,8 @@ class GeoConcavePolygon extends GeoBasePolygon {
// For each edge, create a bounds object.
eitherBounds = new HashMap<>(edges.length);
- intersectionBounds = new HashMap<>(edges.length);
- edgePlanes = new HashMap<>(edges.length);
+ prevBrotherMap = new HashMap<>(edges.length);
+ nextBrotherMap = new HashMap<>(edges.length);
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
final SidedPlane invertedEdge = invertedEdges[edgeIndex];
@@ -224,16 +224,6 @@ class GeoConcavePolygon extends GeoBasePolygon {
bound1Index++;
}
int bound2Index = legalIndex(edgeIndex-1);
- int otherIndex = bound2Index;
- final SidedPlane otherEdge;
- final SidedPlane otherInvertedEdge;
- if (invertedEdges[legalIndex(otherIndex)].isNumericallyIdentical(invertedEdge)) {
- otherInvertedEdge = null;
- otherEdge = null;
- } else {
- otherInvertedEdge = invertedEdges[legalIndex(otherIndex)];
- otherEdge = edges[legalIndex(otherIndex)];
- }
while (invertedEdges[legalIndex(bound2Index)].isNumericallyIdentical(invertedEdge)) {
bound2Index--;
}
@@ -252,15 +242,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
}
}
eitherBounds.put(edge, new EitherBound(invertedEdges[bound1Index], invertedEdges[bound2Index]));
- // For intersections, we look at the point at the intersection between the previous edge and this one. We need to locate the
- // Intersection bounds needs to look even further forwards/backwards
- if (otherInvertedEdge != null) {
- while (invertedEdges[legalIndex(otherIndex)].isNumericallyIdentical(otherInvertedEdge)) {
- otherIndex--;
- }
- intersectionBounds.put(edge, new EitherBound(invertedEdges[legalIndex(otherIndex)], invertedEdges[legalIndex(bound2Index)]));
- edgePlanes.put(edge, otherEdge);
- }
+ // When we are done with this cycle, we'll need to build the intersection bound for each edge and its brother.
+ // For now, keep track of the relationships.
+ nextBrotherMap.put(invertedEdge, invertedEdges[bound1Index]);
+ prevBrotherMap.put(invertedEdge, invertedEdges[bound2Index]);
}
// Pick an edge point arbitrarily from the outer polygon. Glom this together with all edge points from
@@ -383,7 +368,7 @@ class GeoConcavePolygon extends GeoBasePolygon {
/** A membership implementation representing polygon edges that must apply.
*/
- protected class EitherBound implements Membership {
+ protected static class EitherBound implements Membership {
protected final SidedPlane sideBound1;
protected final SidedPlane sideBound2;
@@ -406,6 +391,12 @@ class GeoConcavePolygon extends GeoBasePolygon {
public boolean isWithin(final double x, final double y, final double z) {
return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
}
+
+ @Override
+ public String toString() {
+ return "(" + sideBound1 + "," + sideBound2 + ")";
+ }
+
}
@Override
@@ -442,10 +433,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
// Add planes with membership.
for (final SidedPlane edge : edges) {
bounds.addPlane(planetModel, edge, eitherBounds.get(edge));
- final Membership m = intersectionBounds.get(edge);
- if (m != null) {
- bounds.addIntersection(planetModel, edgePlanes.get(edge), edge, m);
- }
+ }
+ for (final SidedPlane invertedEdge : invertedEdges) {
+ final SidedPlane nextEdge = nextBrotherMap.get(invertedEdge);
+ bounds.addIntersection(planetModel, invertedEdge, nextEdge, prevBrotherMap.get(invertedEdge), nextBrotherMap.get(nextEdge));
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
index dbf8f9f..6bd0aad 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
@@ -48,10 +48,10 @@ class GeoConvexPolygon extends GeoBasePolygon {
protected boolean isDone = false;
/** A bounds object for each sided plane */
protected Map<SidedPlane, Membership> eitherBounds = null;
- /** Edge plane for one side of intersection */
- protected Map<SidedPlane, Plane> edgePlanes = null;
- /** Intersection bounds */
- protected Map<SidedPlane, Membership> intersectionBounds = null;
+ /** Map from edge to its previous non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
+ /** Map from edge to its next non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> nextBrotherMap = null;
/**
* Create a convex polygon from a list of points. The first point must be on the
@@ -210,8 +210,8 @@ class GeoConvexPolygon extends GeoBasePolygon {
// For each edge, create a bounds object.
eitherBounds = new HashMap<>(edges.length);
- intersectionBounds = new HashMap<>(edges.length);
- edgePlanes = new HashMap<>(edges.length);
+ prevBrotherMap = new HashMap<>(edges.length);
+ nextBrotherMap = new HashMap<>(edges.length);
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
int bound1Index = legalIndex(edgeIndex+1);
@@ -219,13 +219,6 @@ class GeoConvexPolygon extends GeoBasePolygon {
bound1Index++;
}
int bound2Index = legalIndex(edgeIndex-1);
- int otherIndex = bound2Index;
- final SidedPlane otherEdge;
- if (edges[legalIndex(otherIndex)].isNumericallyIdentical(edge)) {
- otherEdge = null;
- } else {
- otherEdge = edges[legalIndex(otherIndex)];
- }
// Look for bound2
while (edges[legalIndex(bound2Index)].isNumericallyIdentical(edge)) {
bound2Index--;
@@ -245,17 +238,12 @@ class GeoConvexPolygon extends GeoBasePolygon {
}
}
eitherBounds.put(edge, new EitherBound(edges[bound1Index], edges[bound2Index]));
- // For intersections, we look at the point at the intersection between the previous edge and this one. We need to locate the
- // Intersection bounds needs to look even further forwards/backwards
- if (otherEdge != null) {
- while (edges[legalIndex(otherIndex)].isNumericallyIdentical(otherEdge)) {
- otherIndex--;
- }
- intersectionBounds.put(edge, new EitherBound(edges[legalIndex(otherIndex)], edges[legalIndex(bound2Index)]));
- edgePlanes.put(edge, otherEdge);
- }
+ // When we are done with this cycle, we'll need to build the intersection bound for each edge and its brother.
+ // For now, keep track of the relationships.
+ nextBrotherMap.put(edge, edges[bound1Index]);
+ prevBrotherMap.put(edge, edges[bound2Index]);
}
-
+
// Pick an edge point arbitrarily from the outer polygon. Glom this together with all edge points from
// inner polygons.
int edgePointCount = 1;
@@ -370,7 +358,7 @@ class GeoConvexPolygon extends GeoBasePolygon {
/** A membership implementation representing polygon edges that must apply.
*/
- protected class EitherBound implements Membership {
+ protected static class EitherBound implements Membership {
protected final SidedPlane sideBound1;
protected final SidedPlane sideBound2;
@@ -393,6 +381,11 @@ class GeoConvexPolygon extends GeoBasePolygon {
public boolean isWithin(final double x, final double y, final double z) {
return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
}
+
+ @Override
+ public String toString() {
+ return "(" + sideBound1 + "," + sideBound2 + ")";
+ }
}
@@ -428,10 +421,8 @@ class GeoConvexPolygon extends GeoBasePolygon {
// Add planes with membership.
for (final SidedPlane edge : edges) {
bounds.addPlane(planetModel, edge, eitherBounds.get(edge));
- final Membership m = intersectionBounds.get(edge);
- if (m != null) {
- bounds.addIntersection(planetModel, edgePlanes.get(edge), edge, m);
- }
+ final SidedPlane nextEdge = nextBrotherMap.get(edge);
+ bounds.addIntersection(planetModel, edge, nextEdge, prevBrotherMap.get(edge), nextBrotherMap.get(nextEdge));
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
index 6745060..8527e99 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
@@ -927,5 +927,44 @@ shape:
assertTrue(!result);
}
+
+ @Test
+ public void testPolygonFailureCase2() {
+ /*
+ [junit4] 1> shape=GeoCompositeMembershipShape: {[GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=[
+ [lat=1.079437865394857, lon=-1.720224083538152E-11([X=0.47111944719262044, Y=-8.104310192839264E-12, Z=0.8803759987367299])],
+ [lat=-1.5707963267948966, lon=0.017453291479645996([X=6.108601474971234E-17, Y=1.066260290095308E-18, Z=-0.997762292022105])],
+ [lat=0.017453291479645996, lon=2.4457272005608357E-47([X=1.0009653513901666, Y=2.448088186713865E-47, Z=0.01747191415779267])]], internalEdges={2}},
+ GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=[
+ [lat=1.079437865394857, lon=-1.720224083538152E-11([X=0.47111944719262044, Y=-8.104310192839264E-12, Z=0.8803759987367299])],
+ [lat=0.017453291479645996, lon=2.4457272005608357E-47([X=1.0009653513901666, Y=2.448088186713865E-47, Z=0.01747191415779267])],
+ [lat=0.0884233366943164, lon=0.4323234231678824([X=0.9054355304510789, Y=0.4178006803188124, Z=0.08840463683725623])]], internalEdges={0}}]}
+ */
+ final List<GeoPoint> poly1List = new ArrayList<>();
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, 1.079437865394857, -1.720224083538152E-11));
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, -1.5707963267948966, 0.017453291479645996));
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, 0.017453291479645996, 2.4457272005608357E-47));
+
+ final GeoConvexPolygon poly1 = new GeoConvexPolygon(PlanetModel.WGS84, poly1List);
+
+ /*
+ [junit4] 1> unquantized=[lat=-1.5316724989005415, lon=3.141592653589793([X=-0.03902652216795768, Y=4.779370545484258E-18, Z=-0.9970038705813589])]
+ [junit4] 1> quantized=[X=-0.03902652216283731, Y=2.3309121299774915E-10, Z=-0.9970038706538652]
+ */
+
+ final GeoPoint point = new GeoPoint(PlanetModel.WGS84, -1.5316724989005415, 3.141592653589793);
+
+ assertTrue(poly1.isWithin(point));
+
+ final XYZBounds actualBounds1 = new XYZBounds();
+ poly1.getBounds(actualBounds1);
+
+ final XYZSolid solid = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84,
+ actualBounds1.getMinimumX(), actualBounds1.getMaximumX(),
+ actualBounds1.getMinimumY(), actualBounds1.getMaximumY(),
+ actualBounds1.getMinimumZ(), actualBounds1.getMaximumZ());
+
+ assertTrue(solid.isWithin(point));
+ }
}
[2/2] lucene-solr:master: Merge branch 'master' of
https://git-wip-us.apache.org/repos/asf/lucene-solr
Posted by kw...@apache.org.
Merge branch 'master' of https://git-wip-us.apache.org/repos/asf/lucene-solr
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/8683da80
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/8683da80
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/8683da80
Branch: refs/heads/master
Commit: 8683da80ed2befd4abe0a7028ae95aefd4b3eb21
Parents: 884aa16 d489b8c
Author: Karl Wright <Da...@gmail.com>
Authored: Thu Aug 25 18:10:16 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu Aug 25 18:10:16 2016 -0400
----------------------------------------------------------------------
dev-tools/idea/lucene/join/join.iml | 1 -
.../idea/lucene/queryparser/queryparser.iml | 1 -
dev-tools/scripts/smokeTestRelease.py | 17 +-
lucene/CHANGES.txt | 7 +-
.../analysis/miscellaneous/TestTrimFilter.java | 46 +-
.../lucene/codecs/lucene50/Lucene50Codec.java | 170 ---
.../lucene50/Lucene50DocValuesConsumer.java | 658 ---------
.../lucene50/Lucene50DocValuesFormat.java | 115 --
.../lucene50/Lucene50DocValuesProducer.java | 1299 ------------------
.../codecs/lucene50/Lucene50NormsFormat.java | 62 -
.../codecs/lucene50/Lucene50NormsProducer.java | 481 -------
.../lucene50/Lucene50SegmentInfoFormat.java | 21 +-
.../lucene/codecs/lucene53/Lucene53Codec.java | 176 ---
.../apache/lucene/codecs/lucene53/package.html | 25 -
.../lucene/codecs/lucene54/Lucene54Codec.java | 178 ---
.../apache/lucene/codecs/lucene54/package.html | 25 -
.../services/org.apache.lucene.codecs.Codec | 3 -
.../org.apache.lucene.codecs.DocValuesFormat | 1 -
.../codecs/lucene50/Lucene50NormsConsumer.java | 403 ------
.../lucene/codecs/lucene50/Lucene50RWCodec.java | 41 -
.../codecs/lucene50/Lucene50RWNormsFormat.java | 36 -
.../lucene50/Lucene50RWSegmentInfoFormat.java | 21 +-
.../lucene50/TestLucene50DocValuesFormat.java | 281 ----
.../lucene50/TestLucene50NormsFormat.java | 130 --
.../index/TestBackwardsCompatibility.java | 4 +-
.../org/apache/lucene/index/index.6.2.0-cfs.zip | Bin 0 -> 15880 bytes
.../apache/lucene/index/index.6.2.0-nocfs.zip | Bin 0 -> 15867 bytes
.../lucene50/Lucene50FieldInfosFormat.java | 12 +-
.../org/apache/lucene/index/IndexWriter.java | 18 -
.../org/apache/lucene/index/SegmentInfos.java | 24 +-
.../org/apache/lucene/search/BooleanQuery.java | 40 +
.../java/org/apache/lucene/store/DataInput.java | 33 -
.../org/apache/lucene/store/DataOutput.java | 45 -
.../index/TestAllFilesCheckIndexHeader.java | 7 +-
.../lucene/search/TestBooleanRewrites.java | 59 +
.../CustomSeparatorBreakIterator.java | 4 +-
.../postingshighlight/WholeBreakIterator.java | 4 +-
lucene/join/build.xml | 6 +-
.../search/join/DocValuesTermsCollector.java | 82 --
.../org/apache/lucene/search/join/JoinUtil.java | 45 -
.../search/join/TermsIncludingScoreQuery.java | 9 -
.../apache/lucene/search/join/TestJoinUtil.java | 23 +-
lucene/queryparser/build.xml | 6 +-
.../flexible/standard/StandardQueryParser.java | 19 -
.../LegacyNumericRangeQueryNodeBuilder.java | 93 --
.../builders/StandardQueryTreeBuilder.java | 4 -
.../standard/config/LegacyNumericConfig.java | 165 ---
.../LegacyNumericFieldConfigListener.java | 75 -
.../config/StandardQueryConfigHandler.java | 29 +-
.../standard/nodes/LegacyNumericQueryNode.java | 153 ---
.../nodes/LegacyNumericRangeQueryNode.java | 152 --
.../LegacyNumericQueryNodeProcessor.java | 154 ---
.../LegacyNumericRangeQueryNodeProcessor.java | 170 ---
.../StandardQueryNodeProcessorPipeline.java | 2 -
.../lucene/queryparser/xml/CoreParser.java | 1 -
.../LegacyNumericRangeQueryBuilder.java | 135 --
.../standard/TestLegacyNumericQueryParser.java | 535 --------
.../xml/CoreParserTestIndexData.java | 2 -
.../queryparser/xml/LegacyNumericRangeQuery.xml | 31 -
.../LegacyNumericRangeQueryWithoutLowerTerm.xml | 31 -
.../xml/LegacyNumericRangeQueryWithoutRange.xml | 31 -
.../LegacyNumericRangeQueryWithoutUpperTerm.xml | 31 -
.../lucene/queryparser/xml/TestCoreParser.java | 20 -
.../builders/TestNumericRangeQueryBuilder.java | 179 ---
.../lucene/document/InetAddressPoint.java | 2 +-
.../lucene/store/BaseDirectoryTestCase.java | 30 -
.../lucene/store/MockIndexInputWrapper.java | 20 +-
lucene/tools/junit4/solr-tests.policy | 1 +
lucene/tools/junit4/tests.policy | 1 +
solr/CHANGES.txt | 22 +-
.../org/apache/solr/core/RequestParams.java | 7 +-
.../src/java/org/apache/solr/core/SolrCore.java | 20 +-
.../apache/solr/handler/SolrConfigHandler.java | 25 +-
.../handler/component/RealTimeGetComponent.java | 18 +-
.../solr/request/macro/MacroExpander.java | 12 +
.../solr/rest/ManagedResourceStorage.java | 9 +-
.../search/LegacyNumericRangeQueryBuilder.java | 136 ++
.../org/apache/solr/search/SolrCoreParser.java | 2 +-
.../apache/solr/search/SolrIndexSearcher.java | 18 +-
.../apache/solr/search/facet/FacetField.java | 47 +-
.../solr/search/facet/FacetFieldMerger.java | 211 +++
.../apache/solr/search/facet/FacetMerger.java | 126 +-
.../apache/solr/search/facet/FacetModule.java | 550 +++-----
.../apache/solr/search/facet/FacetRange.java | 8 +-
.../solr/search/facet/FacetRangeMerger.java | 123 ++
.../apache/solr/search/facet/FacetRequest.java | 69 +-
.../search/facet/FacetRequestSortedMerger.java | 234 ++++
.../org/apache/solr/search/facet/HLLAgg.java | 2 +-
.../apache/solr/search/facet/PercentileAgg.java | 2 +-
.../org/apache/solr/search/facet/UniqueAgg.java | 2 +-
.../solr/spelling/suggest/SolrSuggester.java | 20 +-
.../java/org/apache/solr/update/PeerSync.java | 27 +-
.../java/org/apache/solr/update/UpdateLog.java | 7 +-
.../processor/DistributedUpdateProcessor.java | 10 +-
.../solr/collection1/conf/solrconfig-tlog.xml | 2 +-
.../solr/cloud/PeerSyncReplicationTest.java | 360 +++++
.../apache/solr/handler/TestReqParamsAPI.java | 73 +-
.../solr/request/macro/TestMacroExpander.java | 116 ++
.../TestLegacyNumericRangeQueryBuilder.java | 179 +++
.../apache/solr/common/cloud/ZkStateReader.java | 6 +-
.../src/java/org/apache/solr/JSONTestUtil.java | 13 +
101 files changed, 2146 insertions(+), 6995 deletions(-)
----------------------------------------------------------------------