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/05 11:01:35 UTC
[08/19] lucene-solr:jira/http2: LUCENE-8534: Fix incorrect
computation for triangles intersecting polygon edges in shape tessellation
LUCENE-8534: Fix incorrect computation for triangles intersecting polygon edges in shape tessellation
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/6ae9aa2a
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6ae9aa2a
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6ae9aa2a
Branch: refs/heads/jira/http2
Commit: 6ae9aa2a320420537f85908a899dbb995f7802e4
Parents: 07b93a9
Author: iverase <iv...@apache.org>
Authored: Fri Nov 2 07:38:49 2018 +0100
Committer: iverase <iv...@apache.org>
Committed: Fri Nov 2 07:38:49 2018 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +++
.../java/org/apache/lucene/geo/Tessellator.java | 20 +++++++++++++++++++-
.../org/apache/lucene/geo/TestTessellator.java | 20 ++++++++++++++++++++
3 files changed, 42 insertions(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6ae9aa2a/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index dc1336d..64c2c6d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -240,6 +240,9 @@ Bug Fixes:
* LUCENE-8540: Better handling of min/max values for Geo3d encoding. (Ignacio Vera)
+* LUCENE-8534: Fix incorrect computation for triangles intersecting polygon edges in
+ shape tessellation. (Ignacio Vera)
+
Other:
* LUCENE-8523: Correct typo in JapaneseNumberFilterFactory javadocs (Ankush Jhalani
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6ae9aa2a/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 c68a9df..9f72b22 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Tessellator.java
@@ -422,6 +422,7 @@ final public class Tessellator {
// a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
if (isVertexEquals(a, b) == false
+ && isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
&& linesIntersect(a.getX(), a.getY(), node.getX(), node.getY(), nextNode.getX(), nextNode.getY(), b.getX(), b.getY())
&& isLocallyInside(a, b) && isLocallyInside(b, a)) {
// Return the triangulated vertices to the tessellation
@@ -454,6 +455,10 @@ final public class Tessellator {
searchNode = filterPoints(searchNode, searchNode.next);
splitNode = filterPoints(splitNode, splitNode.next);
// Attempt to earcut both of the resulting polygons
+ if (mortonIndexed) {
+ sortByMortonWithReset(searchNode);
+ sortByMortonWithReset(splitNode);
+ }
earcutLinkedList(searchNode, tessellation, State.INIT, mortonIndexed);
earcutLinkedList(splitNode, tessellation, State.INIT, mortonIndexed);
// Finish the iterative search
@@ -538,7 +543,9 @@ final public class Tessellator {
if(node.getX() != x0 && node.getY() != y0 && nextNode.getX() != x0
&& nextNode.getY() != y0 && node.getX() != x1 && node.getY() != y1
&& nextNode.getX() != x1 && nextNode.getY() != y1) {
- return linesIntersect(node.getX(), node.getY(), nextNode.getX(), nextNode.getY(), x0, y0, x1, y1);
+ if (linesIntersect(node.getX(), node.getY(), nextNode.getX(), nextNode.getY(), x0, y0, x1, y1)) {
+ return true;
+ }
}
node = nextNode;
} while (node != start);
@@ -553,6 +560,17 @@ final public class Tessellator {
&& (area(bX0, bY0, bX1, bY1, aX0, aY0) > 0) != (area(bX0, bY0, bX1, bY1, aX1, aY1) > 0);
}
+ /** Interlinks polygon nodes in Z-Order. It reset the values on the z values**/
+ private static final void sortByMortonWithReset(Node start) {
+ Node next = start;
+ do {
+ next.previousZ = next.previous;
+ next.nextZ = next.next;
+ next = next.next;
+ } while (next != start);
+ sortByMorton(start);
+ }
+
/** Interlinks polygon nodes in Z-Order. **/
private static final void sortByMorton(Node start) {
start.previousZ.nextZ = null;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6ae9aa2a/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 055e025..a2e9a8a 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -64,4 +64,24 @@ public class TestTessellator extends LuceneTestCase {
List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
assertEquals(result.size(), 84);
}
+
+ public void testLUCENE8534() throws ParseException {
+ String geoJson = "{\"type\":\"Polygon\",\"coordinates\":[[[168.412605,-32.061828],[168.41260500337557,-32.06164814731918],[168.263154,-32.061754],[168.263074,-31.795333],[168.2631866330167,-31.79533292075007],[168.26293615809584,-31.55183198959802],[168.26271862830876,-31.55183199836296]," +
+ "[168.26260885857246,-31.79551898342183],[168.262799,-31.795519],[168.262922,-32.061969],[168.113391,-32.061955],[168.1136947020627,-31.797506925167987],[168.1134623401242,-31.7975067304478],[168.112867,-32.061933],[167.96342,-32.061572],[167.964447,-31.795078],[167.96462554945853,-31.79507843013861]," +
+ "[167.96521264500555,-31.551376165945904],[167.965145,-31.551376],[167.9663078329189,-31.287013079577566],[167.966251,-31.287013],[167.9664724470441,-31.186852765132446],[167.966135,-31.286996],[167.96583002270634,-31.28699509215832],[167.96514242732414,-31.530648904745615],[167.96518,-31.530649]," +
+ "[167.964244373485,-31.795342905910022],[167.964267,-31.795343],[167.963051,-32.06191],[167.813527,-32.061286],[167.81515841152935,-31.796764131690956],[167.815107,-31.796764],[167.8163675951437,-31.55101526478777],[167.81635023954297,-31.551015225373174],[167.814827,-31.796834]," +
+ "[167.81479823247224,-31.796833898826222],[167.813495,-32.061159],[167.664068,-32.060513],[167.66581,-31.794011],[167.6658519100183,-31.794011179736117],[167.6677495759609,-31.550438401064135],[167.667432,-31.550437],[167.66930180157829,-31.286073839134556],[167.669105,-31.286073],[167.670807,-31.019532]," +
+ "[167.818843,-31.020159],[167.8175723936035,-31.284543327213736],[167.81766095836642,-31.284543526532044],[167.818971,-31.020062],[167.967033,-31.020499],[167.96703262843647,-31.020609267886275],[168.114968,-31.020815],[168.1149445990616,-31.05814524188174],[168.114978,-31.020912],[168.26306,-31.021035]," +
+ "[168.2631849793437,-31.203987591682104],[168.263163,-31.021002],[168.411259,-31.020914],[168.41125954741193,-31.02123593258559],[168.5589863328454,-31.020786105561243],[168.558986,-31.020705],[168.707027,-31.020199],[168.70828992266655,-31.242361611483734],[168.707298,-31.020426],[168.855538,-31.019789]," +
+ "[168.85713808565947,-31.284233200286536],[168.857209,-31.284233],[168.8583969293829,-31.54547348363567],[168.86057,-31.796021],[168.86004803213373,-31.796023826818654],[168.862202,-32.060514],[168.712722,-32.061376],[168.71099229524427,-31.796760977737968],[168.7108263042178,-31.79676167516991],[168.712468,-32.061301]," +
+ "[168.56291,-32.061787],[168.561684,-31.795261],[168.56198761104602,-31.795260018704994],[168.560821,-31.530975],[168.56092374559077,-31.530974570518158],[168.56001677082173,-31.287057906497665],[168.5597021283975,-31.287058866102726],[168.5607530382453,-31.530880020491022],[168.560769,-31.53088]," +
+ "[168.56079128925168,-31.539754620482725],[168.560842,-31.55152],[168.56082083893278,-31.551520031401303],[168.56143311036655,-31.7953001584517],[168.561622,-31.7953],[168.562045,-32.0617],[168.412605,-32.061828]]," +
+ "[[168.41212499436773,-31.68171617103951],[168.41200593405762,-31.551740860609502],[168.411912,-31.551741],[168.41154546767467,-31.416898111348704],[168.41158059852074,-31.53102923335134],[168.411729,-31.531029],[168.41212499436773,-31.68171617103951]]," +
+ "[[168.7083938476212,-31.28652950649234],[168.70945084576658,-31.485690997091577],[168.70886199577689,-31.28667838236468],[168.708488,-31.28668],[168.7084873259438,-31.28652918474386],[168.7083938476212,-31.28652950649234]]," +
+ "[[168.71121460687698,-31.795031659971823],[168.71136127361123,-31.79503081865431],[168.71038567290682,-31.657182838382653],[168.71121460687698,-31.795031659971823]]," +
+ "[[167.81624041598312,-31.53023516975434],[167.81634270442586,-31.530235525706665],[167.81676369867318,-31.434841665952604],[167.81624041598312,-31.53023516975434]]]}";
+ Polygon[] polygons =Polygon.fromGeoJSON(geoJson);
+ List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
+ assertEquals(113, result.size());
+ }
}
\ No newline at end of file