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 2022/06/10 05:33:12 UTC
[lucene] branch main updated: LUCENE-10604: Add Tessellation monitor for easier debugging of triangulation algorithm (#946)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 66b65b79e8b LUCENE-10604: Add Tessellation monitor for easier debugging of triangulation algorithm (#946)
66b65b79e8b is described below
commit 66b65b79e8baa8a2e7f059bd3f24da0a89e0049b
Author: Craig Taverner <cr...@amanzi.com>
AuthorDate: Fri Jun 10 07:33:07 2022 +0200
LUCENE-10604: Add Tessellation monitor for easier debugging of triangulation algorithm (#946)
---
lucene/CHANGES.txt | 2 +
.../java/org/apache/lucene/geo/Tessellator.java | 106 +++++++++++++++++++--
.../org/apache/lucene/geo/TestTessellator.java | 36 +++++++
3 files changed, 137 insertions(+), 7 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a87e12e610e..f2afcd714bb 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -106,6 +106,8 @@ Other
* LUCENE-10370: pass proper classpath/module arguments for forking jvms from within tests. (Dawid Weiss)
+* LUCENE-10604: Improve ability to test and debug triangulation algorithm in Tessellator.
+ (Craig Taverner)
======================= Lucene 9.2.0 =======================
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 cfdd3efcb21..be6a3efce0a 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java
@@ -86,6 +86,11 @@ public final class Tessellator {
private Tessellator() {}
public static List<Triangle> tessellate(final Polygon polygon, boolean checkSelfIntersections) {
+ return tessellate(polygon, checkSelfIntersections, null);
+ }
+
+ public static List<Triangle> tessellate(
+ final Polygon polygon, boolean checkSelfIntersections, Monitor monitor) {
// Attempt to establish a doubly-linked list of the provided shell points (should be CCW, but
// this will correct);
// then filter instances of intersections.
@@ -131,16 +136,24 @@ public final class Tessellator {
}
// Calculate the tessellation using the doubly LinkedList.
List<Triangle> result =
- earcutLinkedList(polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized);
+ earcutLinkedList(
+ polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized, monitor, 0);
if (result.size() == 0) {
+ notifyMonitor(Monitor.FAILED, monitor, null, result);
throw new IllegalArgumentException(
"Unable to Tessellate shape. Possible malformed shape detected.");
}
+ notifyMonitor(Monitor.COMPLETED, monitor, null, result);
return result;
}
public static List<Triangle> tessellate(final XYPolygon polygon, boolean checkSelfIntersections) {
+ return tessellate(polygon, checkSelfIntersections, null);
+ }
+
+ public static List<Triangle> tessellate(
+ final XYPolygon polygon, boolean checkSelfIntersections, Monitor monitor) {
// Attempt to establish a doubly-linked list of the provided shell points (should be CCW, but
// this will correct);
// then filter instances of intersections.0
@@ -186,11 +199,14 @@ public final class Tessellator {
}
// Calculate the tessellation using the doubly LinkedList.
List<Triangle> result =
- earcutLinkedList(polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized);
+ earcutLinkedList(
+ polygon, outerNode, new ArrayList<>(), State.INIT, mortonOptimized, monitor, 0);
if (result.size() == 0) {
+ notifyMonitor(Monitor.FAILED, monitor, null, result);
throw new IllegalArgumentException(
"Unable to Tessellate shape. Possible malformed shape detected.");
}
+ notifyMonitor(Monitor.COMPLETED, monitor, null, result);
return result;
}
@@ -512,7 +528,9 @@ public final class Tessellator {
Node currEar,
final List<Triangle> tessellation,
State state,
- final boolean mortonOptimized) {
+ final boolean mortonOptimized,
+ final Monitor monitor,
+ int depth) {
earcut:
do {
if (currEar == null || currEar.previous == currEar.next) {
@@ -525,6 +543,7 @@ public final class Tessellator {
// Iteratively slice ears
do {
+ notifyMonitor(state, depth, monitor, currEar, tessellation);
prevNode = currEar.previous;
nextNode = currEar.next;
// Determine whether the current triangle must be cut off.
@@ -570,8 +589,10 @@ public final class Tessellator {
continue earcut;
case SPLIT:
// as a last resort, try splitting the remaining polygon into two
- if (splitEarcut(polygon, currEar, tessellation, mortonOptimized) == false) {
+ if (splitEarcut(polygon, currEar, tessellation, mortonOptimized, monitor, depth + 1)
+ == false) {
// we could not process all points. Tessellation failed
+ notifyMonitor(state.name() + "[FAILED]", monitor, currEar, tessellation);
throw new IllegalArgumentException(
"Unable to Tessellate shape. Possible malformed shape detected.");
}
@@ -797,7 +818,9 @@ public final class Tessellator {
final Object polygon,
final Node start,
final List<Triangle> tessellation,
- final boolean mortonOptimized) {
+ final boolean mortonOptimized,
+ final Monitor monitor,
+ int depth) {
// Search for a valid diagonal that divides the polygon into two.
Node searchNode = start;
do {
@@ -817,8 +840,12 @@ public final class Tessellator {
sortByMortonWithReset(searchNode);
sortByMortonWithReset(splitNode);
}
- earcutLinkedList(polygon, searchNode, tessellation, State.INIT, mortonOptimized);
- earcutLinkedList(polygon, splitNode, tessellation, State.INIT, mortonOptimized);
+ notifyMonitorSplit(depth, monitor, searchNode, splitNode);
+ earcutLinkedList(
+ polygon, searchNode, tessellation, State.INIT, mortonOptimized, monitor, depth);
+ earcutLinkedList(
+ polygon, splitNode, tessellation, State.INIT, mortonOptimized, monitor, depth);
+ notifyMonitorSplitEnd(depth, monitor);
// Finish the iterative search
return true;
}
@@ -1444,6 +1471,71 @@ public final class Tessellator {
return false;
}
+ /**
+ * Implementation of this interface will receive calls with internal data at each step of the
+ * triangulation algorithm. This is of use for debugging complex cases, as well as gaining insight
+ * into the way the algorithm works. Data provided includes a status string containing the current
+ * mode, list of points representing the current linked-list of internal nodes used for
+ * triangulation, and a list of triangles so far created by the algorithm.
+ */
+ public interface Monitor {
+ String FAILED = "FAILED";
+ String COMPLETED = "COMPLETED";
+
+ /** Each loop of the main earclip algorithm will call this with the current state */
+ void currentState(String status, List<Point> points, List<Triangle> tessellation);
+
+ /** When a new polygon split is entered for mode=SPLIT, this is called. */
+ void startSplit(String status, List<Point> leftPolygon, List<Point> rightPolygon);
+
+ /** When a polygon split is completed, this is called. */
+ void endSplit(String status);
+ }
+
+ private static List<Point> getPoints(Node start) {
+ Node node = start;
+ ArrayList<Point> points = new ArrayList<>();
+ do {
+ points.add(new Point(node.getY(), node.getX()));
+ node = node.next;
+ } while (node != start);
+ return points;
+ }
+
+ private static void notifyMonitorSplit(
+ int depth, Monitor monitor, Node searchNode, Node diagonalNode) {
+ if (monitor != null) {
+ if (searchNode == null || diagonalNode == null)
+ throw new IllegalStateException("Invalid split provided to monitor");
+ monitor.startSplit("SPLIT[" + depth + "]", getPoints(searchNode), getPoints(diagonalNode));
+ }
+ }
+
+ private static void notifyMonitorSplitEnd(int depth, Monitor monitor) {
+ if (monitor != null) {
+ monitor.endSplit("SPLIT[" + depth + "]");
+ }
+ }
+
+ private static void notifyMonitor(
+ State state, int depth, Monitor monitor, Node start, List<Triangle> tessellation) {
+ if (monitor != null) {
+ notifyMonitor(
+ state.name() + (depth == 0 ? "" : "[" + depth + "]"), monitor, start, tessellation);
+ }
+ }
+
+ private static void notifyMonitor(
+ String status, Monitor monitor, Node start, List<Triangle> tessellation) {
+ if (monitor != null) {
+ if (start == null) {
+ monitor.currentState(status, null, tessellation);
+ } else {
+ monitor.currentState(status, getPoints(start), tessellation);
+ }
+ }
+ }
+
/** Circular Doubly-linked list used for polygon coordinates */
protected static class Node {
// node index in the linked list
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 1c491bf8ae2..dfb213d97bd 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java
@@ -18,6 +18,7 @@ package org.apache.lucene.geo;
import static org.apache.lucene.tests.geo.GeoTestUtil.nextBoxNotCrossingDateline;
import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.greaterThan;
import java.text.ParseException;
import java.util.List;
@@ -837,6 +838,19 @@ public class TestTessellator extends LuceneTestCase {
}
}
+ public void testComplexPolygon50_WithMonitor() throws Exception {
+ String geoJson = GeoTestUtil.readShape("lucene-10563-1.geojson.gz");
+ Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
+ assertThat("Only one polygon", polygons.length, equalTo(1));
+ Polygon polygon = polygons[0];
+ TestCountingMonitor monitor = new TestCountingMonitor();
+ Tessellator.tessellate(polygon, true, monitor);
+ assertThat("Expected many monitor calls", monitor.count, greaterThan(400));
+ assertThat("Expected specific number of splits", monitor.splitsStarted, equalTo(3));
+ assertThat(
+ "Expected splits to start and end", monitor.splitsStarted, equalTo(monitor.splitsEnded));
+ }
+
public void testComplexPolygon51() throws Exception {
String geoJson = GeoTestUtil.readShape("lucene-10563-2.geojson.gz");
Polygon[] polygons = Polygon.fromGeoJSON(geoJson);
@@ -877,6 +891,28 @@ public class TestTessellator extends LuceneTestCase {
ex.getMessage());
}
+ private static class TestCountingMonitor implements Tessellator.Monitor {
+ private int count = 0;
+ private int splitsStarted = 0;
+ private int splitsEnded = 0;
+
+ @Override
+ public void currentState(
+ String status, List<Point> points, List<Tessellator.Triangle> tessellation) {
+ count++;
+ }
+
+ @Override
+ public void startSplit(String status, List<Point> leftPolygon, List<Point> rightPolygon) {
+ splitsStarted++;
+ }
+
+ @Override
+ public void endSplit(String status) {
+ splitsEnded++;
+ }
+ }
+
private void checkPolygon(String wkt) throws Exception {
Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
List<Tessellator.Triangle> tessellation =