You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2021/03/09 07:51:15 UTC
[lucene-solr] branch master updated: LUCENE-9580: Fix bug in the
polygon tessellator when introducing collinear edges during polygon
splitting (#2452)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/master by this push:
new 578b2ae LUCENE-9580: Fix bug in the polygon tessellator when introducing collinear edges during polygon splitting (#2452)
578b2ae is described below
commit 578b2aea8f50deead79a70fac229140a63b8221c
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Tue Mar 9 08:50:58 2021 +0100
LUCENE-9580: Fix bug in the polygon tessellator when introducing collinear edges during polygon splitting (#2452)
---
lucene/CHANGES.txt | 3 +++
.../src/java/org/apache/lucene/geo/Tessellator.java | 13 +++++++------
.../src/test/org/apache/lucene/geo/TestTessellator.java | 17 +++++++++++++++++
3 files changed, 27 insertions(+), 6 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d906a69..56f3858 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -217,6 +217,9 @@ Bug fixes
* LUCENE-9365: FuzzyQuery was missing matches when prefix length was equal to the term length
(Mark Harwood, Mike Drob)
+* LUCENE-9580: Fix bug in the polygon tessellator when introducing collinear edges during polygon
+ splitting. (Ignacio Vera)
+
Changes in Backwards Compatibility Policy
* LUCENE-9669: DirectoryReader#open now accepts an argument to open indices created with versions
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
index 4d65b44..cd45056 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -968,7 +968,12 @@ public final class Tessellator {
&& isIntersectingPolygon(a, a.getX(), a.getY(), b.getX(), b.getY()) == false
&& isLocallyInside(a, b)
&& isLocallyInside(b, a)
- && middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY());
+ && middleInsert(a, a.getX(), a.getY(), b.getX(), b.getY())
+ // make sure we don't introduce collinear lines
+ && area(a.previous.getX(), a.previous.getY(), a.getX(), a.getY(), b.getX(), b.getY()) != 0
+ && area(a.getX(), a.getY(), b.getX(), b.getY(), b.next.getX(), b.next.getY()) != 0
+ && area(a.next.getX(), a.next.getY(), a.getX(), a.getY(), b.getX(), b.getY()) != 0
+ && area(a.getX(), a.getY(), b.getX(), b.getY(), b.previous.getX(), b.previous.getY()) != 0;
}
/** Determine whether the polygon defined between node start and node end is CW */
@@ -1175,11 +1180,7 @@ public final class Tessellator {
nextNode.getY())
== 0)) {
// Remove the node
- boolean nextEdgeFromPol =
- prevNode.isNextEdgeFromPolygon != node.isNextEdgeFromPolygon
- ? true
- : prevNode.isNextEdgeFromPolygon;
- removeNode(node, nextEdgeFromPol);
+ removeNode(node, prevNode.isNextEdgeFromPolygon);
node = end = prevNode;
if (node == nextNode) {
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
index e8d101a..742d92a 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -677,6 +677,23 @@ public class TestTessellator extends LuceneTestCase {
}
}
+ public void testComplexPolygon43() throws Exception {
+ String wkt =
+ "POLYGON((-88.3245325358123 41.9306419084828,-88.3243288475156 41.9308130944597,-88.3244513948451 41.930891654082,-88.3246174067624 41.930998076295,-88.3245448815692 41.9310557712027,-88.3239353718069 41.9313272600886,-88.3237355617867 41.9313362704162,"
+ + "-88.3237347670323 41.9311150951881,-88.3237340649402 41.931103661118,-88.3235660813522 41.9311112432041,-88.3234509652339 41.9311164377155,-88.3232353124097 41.9311261692953,-88.3232343331295 41.9313588701899,-88.323028772523 41.9313681383084,"
+ + "-88.3229999744274 41.930651995613,-88.3236147717043 41.9303655647412,-88.323780013667 41.929458561339,-88.3240657895016 41.9293998882959,-88.3243948640426 41.9293028003164,-88.324740490767 41.9301340399879,-88.3251305560187 41.9302766363048,"
+ + "-88.3248260581475 41.9308286995884,-88.3246595186817 41.9307227160738,-88.3245325358123 41.9306419084828),"
+ + "(-88.3245658060855 41.930351580587,-88.3246004191532 41.9302095159456,-88.3246375011905 41.9300573183932,-88.3243392233337 41.9300159738164,-88.3243011787553 41.9301696594472,-88.3242661951392 41.9303109843373,-88.3245658060855 41.930351580587),"
+ + "(-88.3245325358123 41.9306419084828,-88.3245478066552 41.9305086556331,-88.3245658060855 41.930351580587,-88.3242368660096 41.9303327977821,-88.3242200926128 41.9304905242189,-88.324206161464 41.9306215207536,-88.3245325358123 41.9306419084828),"
+ + "(-88.3236767661893 41.9307089429871,-88.3237008716322 41.930748885445,-88.323876104365 41.9306891087739,-88.324063438129 41.9306252050871,-88.3239244290607 41.930399373909,-88.3237349076233 41.9304653056436,-88.3235653339759 41.9305242981369,-88.3236767661893 41.9307089429871))";
+ Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
+ List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
+ assertEquals(area(polygon), area(tessellation), 1e-11);
+ for (Tessellator.Triangle t : tessellation) {
+ checkTriangleEdgesFromPolygon(polygon, t);
+ }
+ }
+
private void checkPolygon(String wkt) throws Exception {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);