You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by da...@apache.org on 2018/11/12 11:55:43 UTC
[34/50] [abbrv] lucene-solr:jira/http2: LUCENE-8556: Use latitude and
longitude instead of encoding values to check if triangle is ear when using
morton optimisation
LUCENE-8556: Use latitude and longitude instead of encoding values to check if triangle is ear when using morton optimisation
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/74e3ff50
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/74e3ff50
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/74e3ff50
Branch: refs/heads/jira/http2
Commit: 74e3ff509e85982a5529ca99c8e3e9ec2f96770a
Parents: fbb9872
Author: iverase <iv...@apache.org>
Authored: Fri Nov 9 07:22:10 2018 +0100
Committer: iverase <iv...@apache.org>
Committed: Fri Nov 9 07:22:10 2018 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 5 ++++-
.../java/org/apache/lucene/geo/Tessellator.java | 23 +++++++-------------
.../org/apache/lucene/geo/TestTessellator.java | 14 ++++++++++++
3 files changed, 26 insertions(+), 16 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74e3ff50/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 586ad20..c3ff482 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -227,7 +227,10 @@ Bug fixes:
shape tessellation. (Ignacio Vera)
* LUCENE-8559: Fix bug where polygon edges were skipped when checking for intersections.
- (Ignacio Vera)
+ (Ignacio Vera)
+
+* LUCENE-8556: Use latitude and longitude instead of encoding values to check if triangle is ear
+ when using morton optimisation. (Ignacio Vera)
New Features
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74e3ff50/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
index 8fa685c..1fa0443 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -353,13 +353,6 @@ final public class Tessellator {
/** Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodes */
private static final boolean mortonIsEar(final Node ear) {
- double ax = ear.previous.x;
- double ay = ear.previous.y;
- double bx = ear.x;
- double by = ear.y;
- double cx = ear.next.x;
- double cy = ear.next.y;
-
// triangle bbox (flip the bits so negative encoded values are < positive encoded values)
int minTX = StrictMath.min(StrictMath.min(ear.previous.x, ear.x), ear.next.x) ^ 0x80000000;
int minTY = StrictMath.min(StrictMath.min(ear.previous.y, ear.y), ear.next.y) ^ 0x80000000;
@@ -378,21 +371,21 @@ final public class Tessellator {
while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0
&& n != null && Long.compareUnsigned(n.morton, maxZ) <= 0) {
if (p.idx != ear.previous.idx && p.idx != ear.next.idx &&
- pointInEar(p.x, p.y, ax, ay, bx, by, cx, cy) &&
- area(p.previous.x, p.previous.y, p.x, p.y, p.next.x, p.next.y) >= 0) return false;
+ pointInEar(p.getX(), p.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY()) &&
+ area(p.previous.getX(), p.previous.getY(), p.getX(), p.getY(), p.next.getX(), p.next.getY()) >= 0) return false;
p = p.previousZ;
if (n.idx != ear.previous.idx && n.idx != ear.next.idx &&
- pointInEar(n.x, n.y, ax, ay, bx, by, cx, cy) &&
- area(n.previous.x, n.previous.y, n.x, n.y, n.next.x, n.next.y) >= 0) return false;
+ pointInEar(n.getX(), n.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY()) &&
+ area(n.previous.getX(), n.previous.getY(), n.getX(), n.getY(), n.next.getX(), n.next.getY()) >= 0) return false;
n = n.nextZ;
}
// first look for points inside the triangle in decreasing z-order
while (p != null && Long.compareUnsigned(p.morton, minZ) >= 0) {
if (p.idx != ear.previous.idx && p.idx != ear.next.idx
- && pointInEar(p.x, p.y, ax, ay, bx, by, cx, cy)
- && area(p.previous.x, p.previous.y, p.x, p.y, p.next.x, p.next.y) >= 0) {
+ && pointInEar(p.getX(), p.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
+ && area(p.previous.getX(), p.previous.getY(), p.getX(), p.getY(), p.next.getX(), p.next.getY()) >= 0) {
return false;
}
p = p.previousZ;
@@ -401,8 +394,8 @@ final public class Tessellator {
while (n != null &&
Long.compareUnsigned(n.morton, maxZ) <= 0) {
if (n.idx != ear.previous.idx && n.idx != ear.next.idx
- && pointInEar(n.x, n.y, ax, ay, bx, by, cx, cy)
- && area(n.previous.x, n.previous.y, n.x, n.y, n.next.x, n.next.y) >= 0) {
+ && pointInEar(n.getX(), n.getY(), ear.previous.getX(), ear.previous.getY(), ear.getX(), ear.getY(), ear.next.getX(), ear.next.getY())
+ && area(n.previous.getX(), n.previous.getY(), n.getX(), n.getY(), n.next.getX(), n.next.getY()) >= 0) {
return false;
}
n = n.nextZ;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/74e3ff50/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
index 7904725..d5b7e66 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -103,4 +103,18 @@ public class TestTessellator extends LuceneTestCase {
Polygon polygon = (Polygon)SimpleWKTShapeParser.parse(wkt);
assertTrue(Tessellator.tessellate(polygon).size() > 0);
}
+
+ public void testLUCENE8556() throws Exception {
+ String wkt ="POLYGON((-111.4765 68.321,-111.47625 68.32225,-111.4765 68.3225,-111.478 68.3225,-111.47825 68.32275,-111.479 68.32275,-111.47975 68.32325,-111.48125 68.324,-111.4815 68.32375,-111.48175 68.32375," +
+ "-111.48225 68.32425,-111.48275 68.32425,-111.483 68.324,-111.4845 68.324,-111.48475 68.32425,-111.4845 68.32475,-111.48425 68.3245,-111.483 68.325,-111.4835 68.325,-111.48425 68.3255,-111.48525 68.3255,-111.4855 68.32575," +
+ "-111.4855 68.32525,-111.486 68.32475,-111.48725 68.3245,-111.4875 68.32475,-111.48725 68.325,-111.487 68.325,-111.4865 68.32525,-111.487 68.32575,-111.486465 68.326385,-111.486 68.326,-111.48575 68.32625," +
+ "-111.48525 68.32625,-111.485 68.326,-111.48375 68.326,-111.48225 68.3265,-111.483 68.3265,-111.48325 68.32675,-111.4835 68.3265,-111.48675 68.3265,-111.487 68.32675,-111.48675 68.32725,-111.4865 68.327," +
+ "-111.48375 68.32775,-111.485 68.32775,-111.48525 68.3275,-111.4855 68.3275,-111.486 68.32775,-111.48625 68.3275,-111.48675 68.3275,-111.48725 68.327,-111.48775 68.327,-111.4875 68.32625,-111.488 68.32625," +
+ "-111.48825 68.32675,-111.49025 68.327,-111.49025 68.32675,-111.4905 68.3265,-111.49075 68.3265,-111.49125 68.326,-111.492 68.32575,-111.4945 68.32575,-111.49475 68.3255,-111.49525 68.3255,-111.4955 68.32525,-111.49625 68.32525," +
+ "-111.4965 68.325,-111.49775 68.32425,-111.498 68.3245,-111.4985 68.3245,-111.49875 68.32425,-111.49925 68.32425,-111.5005 68.324,-111.50075 68.32375,-111.501 68.32375,-111.501 68.323,-111.5015 68.323,-111.50175 68.32325,-111.5015 68.3235," +
+ "-111.5025 68.32375,-111.50275 68.3235,-111.504 68.32375,-111.50425 68.3235,-111.50525 68.32325,-111.5055 68.3235,-111.506 68.3235,-111.50625 68.32325,-111.5065 68.3225,-111.5075 68.3225,-111.50775 68.32275,-111.50825 68.32275," +
+ "-111.5085 68.3225,-111.50875 68.3225,-111.509 68.32275,-111.5125 68.32275,-111.51325 68.32225,-111.4765 68.321))";
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ assertTrue(Tessellator.tessellate(polygon).size() > 0);
+ }
}
\ No newline at end of file